Tic is a Java Applet that plays the game Tic Tac Toe: Two players alternately place es and s on a 3x3 board, the one who first gets three of his symbols in a line (horizontal, vertical or diagonal) wins. You start with !
The computer's playing algorithm works as follows:
"Rating assuming that both players always choose the best move" given a board situation and whose turn it is is recursively done as follows:
"Rating assuming that the computer always chooses the best move while the human player chooses every possible move with equal probability" given a board situation and whose turn it is is recursively done as follows:
Because this approach is exhaustive, i.e. searches the whole tree of all possible games, it always returns the really best move. This is possible because Tic Tac Toe is such a simple game - although even in this simple game (not taking into accout that many games end before the board is full) 9! = 362 880 different games are possible and the game tree consists of 986 400 nodes!