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]