Reversi

Last Update: 15.01.2008. By Axel in game development | java | tools | Algorithms

Strategic game programming is a fascinating subject, that I have been attracted to for several years now. I always wanted to implement my own chess program but that seemed to complicated for the beginning. Therefore I started with Reversi and a simple minimax alogrithm on my beloved Amiga. Then I turned to chess and learned about more sophisticated variations of the minimax.

Recently I decided to give Reversi a second shot - this time using Java and two days work. So here it comes:

Reversi.jar

Minimax

For those who are interested in the idea behind minimax, here comes a short explanation of the idea behind it. If you take a look at the board, there are several fields, where the current player is allowed to place a tile. Let’s call that a move. For each allowed move the opponent can answer with another set of moves and so on. You can describe this as a tree with the moves representing the branches.

But how do you choose the best move from that tree? Well for minimax you start by giving each leave a value. Then you compare all leaves branching from one move and choose the branch with best value, if it’s your turn, or the branch with the worst value, if the oponent may move. The value of the chosen branch becomes now the value for its ancestor. Doing so, you go back in the tree until you arrive at the trees root and play the move / branch with the best value.

So, what does this mean? Playing the move determined by minimax guarantees, that even if the oponent plays perfect, the value reached at the end of the tree cannot drop beyond the evaluated value.

Unfortunately this holds only true, if the tree is evaluated up to the end of the game. As the tree grows exponentially with the moves one has to stop the evaluation after a rather limited number of moves, which is the reason, why you can possibly beat my program ;-)

That’s enough for today. Have fun with the program. If you have any comments or questions, feel free to add them here, in which case I might improve on the program or add more explanations.