Reversi / Othello

[Paul Aubrey-Rees]

I've put together some code for playing noughts and crosses / tic tac toe (against the computer), which uses the MiniMax algorithm. It works ok so I've tried to modify it to play Reversi / Othello, but I've got stuck trying to undo the moves. With tic tac toe you can undo a move by just setting the board position to empty, but you can't do this with reversi
because making a move causes other pieces to change colour. I've tried making a copy of the board array before making a move and before the recursive call to nextMove and using this to restore the board (in place of myBoard[i][j] = VACANT), but it doesn't work. Any help would be much appreciated!

 
public int nextMove(int[][] myBoard, int player, int[] bestPosition){ 
    
        for(int i = 0; i < BOARDSIZE; i++){
            for(int j = 0; j < BOARDSIZE; j++){
                if(myBoard(i, j) == VACANT{
                    myBoard(i, j) = player
                    number = nextMove(myBoard, -player, position)
                    myBoard(i, j) = VACANT

(I've deleted most of the code from the method, but hopefully this bit makes sense)

[ Jess added UBB [code] tags to perserve whitespace ]
[ August 26, 2004: Message edited by: Jessica Sant ]

[Warren Dew]

The two obvious possibilities, to me, are (1) store the board position after each move, and (2) store the sequence of moves from the beginning of the game, so you can recreate any previous position. For Reversi, which doesn't involve that many moves, I think I'd do the latter.

If it's a Swing application, you could also look into the javax.swing.undo package. I haven't used it, but it seems like it might help here.

[Eric Pascarello]

You can store the positions affected in an array and if the move is reverted, chnage back to that array.

I did not even try to add an undo in my reversi game.

Eric

[Jessica Sant]

hmmm ok...

so what if to undo a move -- you just do the opposite process of making a move

|---|---|---|---|---|---|---|
| x | x | o | o | o | o |   |  initial board
|---|---|---|---|---|---|---|
 
  0   1   2   3   4   5   6
|---|---|---|---|---|---|---|
| x | x | o | o | o | o | x |  put down an 'x' in 6
|---|---|---|---|---|---|---|
 
  0   1   2   3   4   5   6
|---|---|---|---|---|---|---|
| x | x | x | x | x | x | x | flip all the pieces between 1 and 6
|---|---|---|---|---|---|---|

So -- if you know that the piece you put down was 6, and that the piece that triggered the move was 1 -- all the pieces, 2-5 were o's before... so to undo the move you simply remove piece 6 and flip 2-5 back to o's

That "trigger" piece may need to be a list of positions because its possible you could turn over pieces diagonnaly and horizontally.

I would think that method would require less storage too -- cause instead of keeping a copy of the actual board, you're just storing a copy of the differences in the board. What do you think of that?

[Warren Dew]

Jessica Sant:

What do you think of that?

I think your method is more elegant and intellectually appealing.

I'd probably use the brute for repeat-from-start method, though, because it would be quicker to program. A few hundred bytes of storage and a few thousand machine instructions shouldn't make a difference on today's machines - except possibly on cell phones?
[ August 26, 2004: Message edited by: Warren Dew ]

[Paul Aubrey-Rees]

Thanks a lot for your replies - I didn't explain myself very well though. In a noughts and crosses game with a single cross, there are 8 possible moves for the noughts player and for each of these moves there are 7 possible moves for the crosses player etc. Using the MiniMax algorithm the game can be represented as a tree that consists of all possible moves. With noughts and crosses this tree is sufficiently small that it can be evaluated. The leaves of the tree represent the final positions, either a win a loss or a draw. These outcomes are assigned values, 1 for a win, 0 for a draw and –1 for a loss. As the evaluation progresses up through the tree, the values are passed to the nodes above, until we get to the current board. Each move now has a value that can be used to select the best move for the current player.(Apparently, in Othello the game tree is too big to evaluate down to the depth of the leaves – I think you can only evaluate four or 5 levels to start with, then when you get towards the end of the game and there are less positions free you can go to a greater depth).
Anyway, during this creating and evalution of the game tree, moves are made and at some point undone. I'll try both of the undo methods you've suggested and see what happens...

[Warren Dew]

So you're writing the strategy for the computer player?

I'd suggest you read up a bit on alpha beta pruning assuming you are already familiar with the minimax strategy from game theory.

[Paul Aubrey-Rees]

Thanks, that's a great web site - alpha beta pruning is definely the way to go :-)
I wish it was otherwise, but the reason I first got stuck with the undo move was because I declared my tempBoard array (to store the board before making a move) as a class variable. It's taken me long time to realise that this doesn't work - it must be declared at the start of the recursive method. I think this is because during the recursive calls there are quite a few copies of the function existing simultaneously in memory and each one has to have it's own copy of tempBoard (?) Anyway, I've tested it with noughts and crosses and it works ok, so hopefully it'll work with Reversi.
Thanks again for your suggestions - perhaps next time I should post in the beginners forum :-)

P.

[Jessica Sant]

[ perhaps next time I should post in the beginners forum]

Not at all! Questions about game strategey, game logic, gaming algorithms (like minimax, alpha-beta pruning, etc). Or stuff like "Hey I'm building this game and can't figure out how to represent the ________ (insert board, players, movement, etc). If it has to do with a game -- post it here!

[Paul Aubrey-Rees]

This isn't actually anything to do with Paul's question but I was quite staggeringly surprised at the coincidence of someone out there having the same name as me (down to the hyphen), especially given the site contents (I am a Java/C/C++ programmer in Bristol, [England]).

How 'ya doing over there - wherever that is?