This Tic-Tac-Toe game uses an alpha-beta search algorithm. The implementation is
kind of unconventional. It's recursive, with reversing and negating alpha-betas with each
recursion. A version of this algorithm appeared in June 2001, JAVAPro magazine. It looked
impressive, so we've reimplemented it (with a few modifications). The UI is mostly borrowed
from the JDK demo TicTacToe.
The skill level directly represents the search depth. Skill 1 just generates moves, and
then gets an estimate for each of those moves. Skill 2 generates the moves, recursively goes
though those moves, then recursively goes though more moves, then, using an estimate, figures
out the best move. Subsequent skills just increase the number of recursions that happen (thus,
increasing the strength of this game).
So far we've managed to beat it (quite easily) on skills 1 through 3. If you can defeat it
on skill 4 and up, please let us know (with the moves ;-) The reason the game gets virtually
unbeatable around skill 4 is that by that point, it's looking though 7 ply+estimate in the
game, which is nearly a complete game tree (ie: most of the time you either win or loose in
4 moves or less; beyond that it's usually a draw).
Note, tic-tac-toe is one of those games where you can always force a draw. Even on skill 6,
(where it definitely goes through the complete game tree; and plays a perfect game), you can
still not let the computer win.
Anyway, have fun. (Compiled via JDK 1.0.2; Tested under IE5.5 & NS3)
Btw: if you want the source, just get it here: [pTicTacToe.java]