To build my Java applet, I took a pragmatic engineering
approach, and re-used lot's of ideas already published on the web about programming
game-playing programs like Othello. That is to say, I re-used some ideas, but implemented
the concepts involved from scratch, in Java. The only source code re-used is a
representation of the Reversi playing board. This is a beautiful 3-D board, which I
borrowed from this site. Everything
else I programmed myself. A very useful experience for a non-programmer....
Techniques I used are the following:
- Game tree search
- minimax with alfa-beta cut-offs to prune the search tree
- move ordering to further improve the alfa-beta cut-off
ratio
- quiescence search, to avoid the 'horizon effect'
- perfect end-game search and (optional) a win-lose endgame
search, deepening the endgame search by 2 plies.
- a small opening book (~ 400 openings)
- I'm currently investigating the Negascout algorithm, which
should be even more effective then the alfa-beta algorithm
- Board evaluation
- 'mobility difference' between the applet and its opponent
- I do not use 'potential mobility': the merits are not quite
clear to me
- board position evaluation:
- corner evaluation
- center evaluation
- edge evaluation, by using a pre-computed edge value table
- Data structures
- I use a 'potential moves' list, this increases the search
speed for legal moves drastically
- I do not use 'transposition tables'. Maybe this is worth
considering for a future version
- I use only 1-dimensional arrays to increase efficiency
Click here, here or at Logistello's Homepage
if you want to have more background information on these techniques.