wood burning stoves 2.0*
The moose likes Game Development and the fly likes speeding up Othello Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Game Development
Bookmark "speeding up Othello" Watch "speeding up Othello" New topic
Author

speeding up Othello

Nick Stevens
Greenhorn

Joined: Nov 13, 2004
Posts: 15
Hello,

I' written a Othello game (that uses the mini-max algorithm)
and I'm looking for ways to speed it up. I've represented
the board using a 8 x 8 array of integers, but I've read
that using four (32) bit integers and setting the individual
bits can speed things up. Do you think this would have
much effect?

many thanks

N.
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
if you're talking about one array, my guess is that the effect would be less than negligible.


I've heard it takes forever to grow a woman from the ground
Steven Bell
Ranch Hand

Joined: Dec 29, 2004
Posts: 1071
Get a profiling tool and use it. Trying to speed up an app without a profiler is like doing target practice with a blindfold on.
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Before you even consider the performance implications of this solution, verify that the solution could even work. What does an Othello board look like? In your case, it's an 8x8 board of squares, and each square has three states: empty, black piece, or white piece. How many states does a bit (boolean) hold?

So that won't work, but assume it would. Now to determine the state of any given square requires choosing the correct int, masking off the other bits (bitwise and), and testing the value. To do this with an 8x8 array only requires accessing the correct array element. Right there you can make an educated guess that the performance will be very similar or maybe a bit worse.

And now consider the amount of work involved in your min-max algorithm and especially the code you use to evaluate the board position for a particular player. This probably involves far more work than simply accessing a single square's state. One way to speed it up is to look fewer moves ahead, but this obviously sacrifices the quality of the computer players. If you can find a more intelligent evaluation algorithm, perhaps you can mitigate the loss from looking fewer moves ahead.

Another thing to look at is how you manage the multiple board states while traversing the move tree. Do you copy the board for each move? Maybe you can find a quicker method of altering the board in place by keeping track of the effects of each move so you can undo them when backtracking in the tree. I suspect this will actually be slower and more difficult since each move can have many side effects, but it's something to consider.
Nick Stevens
Greenhorn

Joined: Nov 13, 2004
Posts: 15
Thanks a lot for your replies. It doesn't sounds like changing the board representation will make much difference, so I'll leave it for now (if I did do it I'd use two 32-bit integers to represent the locations of the white pieces and another two to represent the black positions). I haven't used a profiler before but I think it will be very useful - I'll download one and give it a go :-) I think having looking at the evaluation algorithm is a good idea since it's used so much (perhaps the profiler will show how much?). Also, while tranversing the move tree the board *is* copied for each move - this is done lots of times so any improvement here would be very helpful (I'll have to think about that..).
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Originally posted by Nick Stevens:
If I did do it I'd use two 32-bit integers to represent the locations of the white pieces and another two to represent the black positions.
Or a single long (64 bits) for each (two longs total). This would speed up copying a board position greatly.

I'd bet with a lot of coffee and many hours spent meditating on board positions, after becoming an Othello master of course, would provide many insights into fast bit-manipulation algorithms that would evaluate several aspects of a board position to provide a switch evaluation method.

Hopefully your algorithm is better than this site's. I haven't played in over fifteen years at least, and I just beat it in eleven moves. It was happy to lead me right into acquiring a border position and barely put up a fight.
I haven't used a profiler before . . . . I think having looking at the evaluation algorithm is a good idea since it's used so much (perhaps the profiler will show how much?).
This is precisely what a profiler will show you. It will give you the absolute and percentage time spent in each method of your application and show you how many objects of each class you're creating over time.
colin shuker
Ranch Hand

Joined: Apr 11, 2005
Posts: 744
Hi, I've just written a chess game using minimax too.
This is what I reckon you should do, use alpha-beta
pruning on your search tree. It's a bit awquard to get
your head around, but is just an extension of minimax,
that basically ignores searching all the bad moves.
Apparently the number of positions searched is square
rooted,equivalently,you can double the depth of the
search, in the time taken normally. This is used in most
chess games I believe.
There are quite a few links to alpha-beta related stuff,
but a lot of it is badly written, here is a link that I
think best explains it. It should only require a slight
modification to your code.
http://pages.cpsc.ucalgary.ca/~sueng/533/AlphaBetaPruning.html
Good luck!!!
Nick Stevens
Greenhorn

Joined: Nov 13, 2004
Posts: 15
Thanks for your replies. I've spent quite a lot of time trying to install a profiler. I've got Mandrake Linux on my pc and I've installed other things (like Firefox and Thunderbird) without any problems, but I'm still trying to get a profiler to work! Anwyay, I recently decided to take David's advice and changed all the code to use two 64-bit longs to represent the black and white board positions. The program now runs faster than it did, which is great, but from what I've read I think it could be a bit better. My pc is a Pentium II, with 500MB of RAM and the game can only really look 4 moves ahead (if it tries to search any deeper than this, it takes a long time to determine the next move). I'm already using alpha-beta pruning - good suggestion though. I'd say using alpha-beta pruning has had the biggest effect on the game speed so far.
I've recently read that a particular board position can potentially be reached by more than one sequence of moves. This means that a board might be evaluated more than once, but this can be avoided by storing boards (and the best move for the board) in a hashtable. Before a board is evaluated, the hash table is searched and if the board is found the best move is just read from the table, saving time. On one website I read this can speed up a program by 20 to 50% :-)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: speeding up Othello