Xman Blog Inside

Wednesday, August 16, 2006

REVERSI: Yet another program that I had put in storeroom for a long time

I started with writing a Reversi board game in Java. Then I ported it to C++, called xversi-c which is under GPL and hope that it will run much faster. The implementation ideas are simple:
  • Generate all possible moves.
  • For each of the moves generated above, evaluate and keep the best move.
  • The real question is, how do we evaluate each of the possible moves?
  • Just use your imagination, to determine whether a move is good, just find out what are all the next possible moves? what are all the next next possible moves? ...... eventually, the board will be filled up with all the possible moves :)
  • Practically, we cannot imagine too many moves. At one point, we will want to use some criteria to determine whether a move is good. I have use some simple heuristics to calculate a score for each move.
    • Count number of pieces. When game started, we dont want to have many pieces. But as game closer to end game, we want more pieces.
    • Count mobility, that's the number of moves that each player has. Having more moves, probably means having more controlling power over opponent.
    • Count the number of corners obtained.
  • As the game closer to the end, number of possible moves are limited. Thus, when game is near end, I set it to compute all the possible moves till the end. At the end, evaluation is simple, simply count the number of pieces each player has.
  • For more information about evaluation, search for Game tree generation with alpha-beta prunning.
Phew..... no point having too many explainations. :) Read the codes if you care. :) I hope it's readable enough. :p

Labels: , , , , ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home