Simple data structure for the Othello board game?

I've done my program ages ago h开发者_Python百科ere as a uni project, at least it works to some extent (you may try the Monkey and Novice level:) ).

I'd like to redesign and re-implement it, so to practice on data structure and algorithm.

In my previous project, min-max search and alpha-beta pruning was the missing part, as well as a lack of opening dictionary.

Because the game board is symmetric both horizontally and vertically, I need a better data structure than my previous approach:

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 11 12 13 14 15 16 17 18 -1
-1 21 22 23 24 25 26 27 28 -1
-1 31 32 33 34 35 36 37 38 -1
    . . . . . .

In this way, one can easily calculate the adjacent positions given any cell value like this:

x-11 x-10 x-9
x-1   x   x+1
x+9  x+10 x+11

Those -1s are acting like "walls" to prevent wrong calculation.

The biggest issue is it doesn't take any consideration of symmetric/orientation, i.e., same opening like parallel opening would have 4 corresponding opening cases in database, one for each orientation.

Any good suggestion? I am also considering to try ruby as to have a quicker calculation speed than PHP (just for min-max alpha-beta pruning, in case I will program it to look n steps ahead).

Many thanks for the suggestions in advance.

When you hash a position to store or lookup in your database, takes hashes of all eight symmetric positions, and store or lookup only the smallest of the eight. Thus all symmetric positions hash to the same value.

This reduces the size of your database by 8 but multiplies the cost of hashing by 8. Is this a good trade-off? It depends on how big your database is and how often you do database lookups.

After you move to C/C++ :-) consider representing the game board as "bit-boards" e.g. two 64-bit-vectors e.g. for white and black e.g. struct Board { unsigned long white, black };

With care you can then avoid array indexing to test piece positions, and in fact can search in parallel for all up-captures, up-right-captures, etc. from a position using a series of bit logical operators, shifts, and masks, and no loops (!). Much faster.

This representation idea is orthogonal to your questino of opening book symmetries though.

Happy hacking.

The problem is easy to deal with if you seperate the presentation of the board from the internal representation. Once the opening move is made, you get parallel, diagional, or perpendicular opening. Each one of them can be in any of the 4 orientations. Rotate the internal board representation, until it is aligned with your opening book. Then simply take the rotation into account when drawing the board.

In regard to play, you need to look into Mobility Theory. Take a look at Hugo Calendars book on the topic. Also Nick Buro has written a bit about his program Logistello. A FAQ

As that parallel opening only applies for the very first move, I would just make the first move fixed.

If you really want speed, I'd recommend C++.

I would also imagine checking the space is on the board is faster than checking if the space contains a -1.