- Play against 3 different levels of computer or play with a friend.
- Undo and Redo as many moves as you like.
- Display valid moves, and number of pieces for each player.
- Hint available upon request.
- Switch between you can computer player.
- Save/Load games for future review.
- Library: OpenGL, GLUT, STL (This code is platform independent)
- Compiler: MS Visual C++ 6.0
- Source: Reversi.zip (555k)
- Standard Game Tree Algorithm with the following modification
- Add a search priority so that better move are likely to be searched first.
- Attempt to minimize cache miss.
- Few memory allocations: Allocated memory are passed from functions to function.
- Continuous block of memory: Almost all major memory allocations occur at the very beginning
- Remember searched position to speed up later search. I decided NOT to use it
- It turns out this algorithm slow down the program too much, making it less effective than not storing.
- Repeated situation does not occur often in Reversi.
- The increase in memory usage actually slow the program down.
- (A little randomization to make the game more fun.)
- Evaluate function uses the following parameters.
- Mobility: The number of valid move.
- Position: A set of parameters determining the weight of each position.
- Piece Count: This is used at the very end of the game, when it is possible to search all moves.
- Adjusted Position: locations adjacent to corner is weighted negatively if the corner is not occupied.
- Because sometimes the computer would make a move that eventully give up a corner.
- Parameter searching algorithm: Algorithm to figure out the appropriate parameter for evaluate function.
- Disable randomness in game tree algorithm
- Start with a set of parameter, call this winner.
- For each test
- Randomly change one of the parameter to create a new opponent, let's call this challenger.
- Play two games, challenger vs winner. Challenger goes first in round 1, and second in round 2.
- If challenger wins both game, the winner's parameter is changed to challenger's.
- If not, the winner survive, and add 1 to the #Survive counter
- Repeat the test.
- The set of parameter that survived the most game will be the parameter used.