Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# speeding up Othello

Nick Stevens
Greenhorn
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
Posts: 815
if you're talking about one array, my guess is that the effect would be less than negligible.

Steven Bell
Ranch Hand
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
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
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
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
Posts: 750
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
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