Reversi

• Basic Info

  • Rules: Search on Google
  • Screenshot: ss1.jpg
  • Download: Reversi.zip (555k)
  
  

• Features

  • 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.
  
  

• Implementation (Technical)

  • Library: OpenGL, GLUT, STL (This code is platform independent)
  • Compiler: MS Visual C++ 6.0
  • Source: Reversi.zip (555k)
  
  

• Algorithm (Technical)

  • 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.