This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
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?
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.
Joined: Nov 13, 2004
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..).
Joined: Aug 07, 2003
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.
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!!!
Joined: Nov 13, 2004
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% :-)