Need instructions for Reversi game

Question

I am trying to write Reversi game in Python. Can anyone give me some basic ideas and strategy which are simple, good and easy to use?

I would appreciate for any help because I've gone to a little far but is stucked between codes and it became more complex too. I think I overdid in some part that should be fairly simple. So....

Answer 1

Reversi is an elegantly simple game. I'm going to use a psuedo C#/Java langauge to explain some concepts, but you can transpose them to Python.

To break it down into its most simple compnents, you have two basic things:

A 2 dimensional array that represents the game board:

gameBoard[10,10]

And some form of enumaration that stores the state of each tile in the gameboard:

enum tile
{
    none,
    white,
    black
}

To render the board, you loop through the gameBoard array, increasing by an offset of the piece size:

for (int i = 0; i < 10; i++)
{
    for (int j = 0; j < 10; j++)
    {
        // The Piece to draw would be at gameBoard[i,j];
        // Pixel locations are calculated by multiplying the array location by an offset.
        DrawPiece(gameBoard[i,j],i * Width of Tile, j * width of tile);
    }
}

Likewise, resolving a mouse click back to a location in the array would be similar, use the mouse location and offset to calculate the actual tile you are on.

Each time a tile is placed, you scan the entire array, and apply a simple rules based engine on what the new colors should be. (This is the real challenge, and I'll leave it up to you.)

The AI can take advantage of doing this array scan with hypothetical moves, have it scan 10 or so possible moves, then choose the one that produces the best outcome. Try to not make it to smart, as its easy to make an unbeatable AI when you let it play out the entire game in its head.

When there are no longer any free locations in the array, You end the game.

Answer 2

You'll need a 2D array. Beware of [[0] * 8] * 8, instead use [[0 for _ in [0] * 8] for _ in [0] * 8]

White should be 1 and black -1 (Or vice versa, of course). This way you can do flips with *=-1 and keep blank blank Double four loops will be able to total scores and determine if the game is done pretty well. map(sum,map(sum,board)) will give you the net score

Don't forget to check and see if the player can even move at the beginning of a round

Answer 3

The wikipedia page has all of the rules and some decent strategy advice for reversi/othello. Basically, you need some sort of data structure to represent board state, that is to say the position of all the pieces on the board at any point in the game. As suggested by others, a 2d array is probably a decent choice, but it doesn't really matter so long as it is a representation that makes sense to you. Some of the hard stuff is figuring out which spaces are valid moves and then which pieces to flip over but, again, the wikipedia page has all of the details so it shouldn't be too hard to implement.

If you want to create an AI for your game, then I would suggest look at some sort of minimax type algorithm with Alpha-Beta pruning. There are a ton of resources on the web for these and an ai that uses minimax with a decent evaluation function will be able to beat most human players pretty easily, as it can look at least 8 or 9 moves ahead in very little time. There are some other fancier variants on minimax, like negamax or negascout that can do even better than basic minimax, but I'd start with the simpler ones. Wikipedia has pages on all of these algorithms and there is a ton of information on all of them as many AI courses use them for Othello or something similar. One page that is particularly useful is this Java Applet. It allows you to step through the steps of minimax and negamax on a sample state tree with and without alpha-beta pruning.

If none of this makes sense, let me know.

Answer 4

You may also wish to consider the application of a "fuzzy logic" loop to analyze positions. Reversi/Othello is notorious for forcing players to consider certain strategic gains against strategic losses for each move, as well as prioritizing one positive move over another.

A fuzzy system would give you greater control over testing move selection by setting various settings against each other, as well as giving you the ability to create multiple "personalities" to play against by shifting the various weights.

Answer 5

Don't get suckered into the multi-dim array solution. I've already written a tic-tac-toe with a multi-dim and it worked alright, but then when I started my own version of othello I did a linear integer array and its almost 2x faster.

http://stackoverflow.com/questions/507295/alternative-faster-methods-of-converting-an-integer-to-a-cartesian-coordinate

I've got everything mostly coded out in PHP but still researching Idea's for the AI as a brute force solution like in Tic-tac-toe isn't going to work.

Answer 6

You don't even need a linear array. Two 64-bit java long values suffice (one for the white pieces, one for the black. assert (white&black)==0 .

You can make play stronger by counting not pieces that are joined to a corner, but pieces that cannot be taken.