Java Answers Forum - Inefficiency Problem.

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Java Answers Forum
Inefficiency Problem.

4 replies on 1 page. Most recent reply: Dec 10, 2002 4:33 PM by Matt Gerrans

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 4 replies on 1 page

Zach Keatts

Posts: 3
Nickname: grundle
Registered: Dec, 2002

Inefficiency Problem.

Posted: Dec 10, 2002 12:53 PM

I am currently trying to program a Go-Moku game with AI implemented. This of course involves the alpha-beta algorithm. I am running into memory problems, and I believe it is because of the way I have been storing the "board" information.
Initially I decided to use a 2-d array so that traversal and storage would be easy e.g. board[one][two] The only problem is that in java a new array has to be created, and then all the information contained in the original array copied over. I had to use a loop as follows to accomplish this

for(int val = 0; val < BOARD_SIZE; val++){
System.arraycopy(array1[val], 0, array[val], 0, array2.length);
}

If you merely set

array1 = array2;

then everytime a value in array1 is changed it is also changed in array2. I am wondering if there is a more efficient way to either reference the many arrays I have to create (because "child" boards are generated) or maybe someone could suggest a data structure outlined with storage method that would make this more efficient?

Any help would be greatly appreciated.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Inefficiency Problem.

Posted: Dec 10, 2002 1:27 PM

First of all, I don't think alpha-beta qualifies as AI.

As for storing the board, Go is very simple (unlike chess, for instance) in that each position either contains a piece or doesn't. This means you could represent each position on the board with only two bits (black, white and empty, with 1/2 bit to spare!). Also, since it is only 2-D, it is simple enough to have a linear array and calculate positions. Admittedly not having thought about this at too much length, I would nevertheless suggest the idea of considering creating a class that manages all this with a BitSet of BOARD_SIZE*BOARD_SIZE*2 bits (I assume that a BitSet is efficient with memory and doesn't represent each bit with a whole word, but I don't know for sure -- if you don't want to take the chance, I suppose you could use ints or longs and to the bit-shifting and whatnot manually, a la C/C++).

By the way, if you are running out of memory, there are probably bugs in your code or design, because you should be able to implement this game without a ton of memory. Borland put out a book (and floppy with source) called Turbo Pascal Gameworks that included Go-Moku more than a decade ago; the memory that little program required was chicken feed compared to the amount that today's virtual swine consume.

Zach Keatts

Posts: 3
Nickname: grundle
Registered: Dec, 2002

Re: Inefficiency Problem.

Posted: Dec 10, 2002 1:57 PM

I suggest you look into this problem more, because go is one of the games that is still unsolved. Its branching complexity is greater than that of chess. Go-Moku however has been solved but with the use of the alpha-beta search tree. What you are overlooking is that the "AI" has to perform a brute force search on all possible moves that it can make as well as what the opponent will make. A simple matrix array will not suffice for a problem with this much complexity.

The tree structure is for each "move" considered. If a search looks in a 3-ply manner then it has considered (from the last move) two moves for itself as well as one for the opponent. Using a 19x19 board this means that there will be roughly 19 children for the first ply. For 2 ply there would be 361 children and for the third ply there would be 6895 children. Just looking ahead 3-ply means there will be 19^3 different positions to consider. As you can see this will increase exponentially so an efficient search method must be devised to cut down the number of nodes opened and searched. The alpha-beta search method is used in most advanced-AI systems to run Chess, Go, and other games. My alpha-beta method has worked with a simple tic-tac-toe game so I do know it works correctly as long as there are hueristics in place. The problem comes when I increase the size of the board.

Even though I have limited the number of children nodes generated for some reason it still runs out of memory. Hopefully this will clear up what I am dealing with.

Zach Keatts

Posts: 3
Nickname: grundle
Registered: Dec, 2002

Re: Inefficiency Problem.

Posted: Dec 10, 2002 2:58 PM

The solution is as follows::Fortunately the 2-d array structure need not be changed for this particular program. The error was when the board state was being generated the children were also generated via the constructor. This is bad because the children will also be stored as State Objects. As you can see since each one will call the child generation in the constructor it tries to generate n-ply children or 19^n children. This is why it would run out of memory so quickly.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Inefficiency Problem.

Posted: Dec 10, 2002 4:33 PM

What I meant by simple is that all pieces are the same and do nothing but sit where they are placed. Sure, there are a lot of them and this, naturally, is why it is "unsolved." The Travelling Salesman problem is also very simple -- it only becomes difficult when there are a lot of points to consider.

In contrast, the basic code for a for a game like chess or Chinese chess is more complicated because there are many different pieces that have different behaviors, which in many cases change based on the current situation in the game, or based on previous events (eg. en passant, castling, pawn promotion, etc.).

But let me clarify that I'm not saying that Go (or Go-Moku) itself is not a simple game or that the masters of this game are not brilliant and talented game players who have acheived an amazing level of skill. Playing the game at the highest levels involves dealing with enormous amounts of complexity. However, the basic elements of the game are quite simple and the complexity comes from the size of the playing field and the number of combinations that stems from that.

Also, with Go and other games, the search tree doesn't constitute AI; usually the AI, if present, is involved mostly in the evualation algorithm for each position (and to some extent, which branches are further examined based on that). With a simple game like Go-Moku, you can have a prefectly good and very strong engine without any AI at all.

Of course, it is possible that the evaluation of positions for Go (or probably to a lesser extent, Go-Moku) could end up being just as deep and subtle or even more so than for chess.

By the way, it seems that you should be able to store a Go-Moku position in less than 91 bytes (if it is a 19x19 board, as you said), but I would guess the size of an implementation using 2-D arrays of int Java would be significantly larger. Even so, it is still quite feasible to do it that way; the optimization of speed and memory footprint can be factored in once the basics are all working.

Flat View: This topic has 4 replies on 1 page

Previous Topic

Next Topic


	Web Artima.com