*** Welcome to piglix ***

Ultimate tic-tac-toe


Ultimate tic-tac-toe also known as super tic-tac-toe or meta tic-tac-toe is a board game composed of nine tic-tac-toe boards arranged in a 3-by-3 grid. Players take turns playing in the smaller tic-tac-toe boards until one of them wins in the larger tic-tac-toe board. Strategy in this game is much more conceptually difficult, and has proven more challenging for computers.

Each small 3-by-3 tic-tac-toe board is referred to as a local board, and the larger 3-by-3 board is referred to as the global board.

The game starts with X playing wherever he wants in any of the 81 empty spots. This move 'sends' his opponent to its relative location. For example, if X played in the middle of his local board, then O needs to play next in the local board in the middle of the global board. O can then play in any one of the nine available spots in the top-right local board, each move sending X to a different local board.

If a move is played so that it is to win a local board by the rules of normal tic-tac-toe, then it wins that local board.

Once the outcome of a local board is decided (win or draw), no more moves may be played in that board. If a player is sent to such a board, then that player may play in any other board.

Game play ends when either a player wins the global board, or there are no legal moves remaining.

Ultimate tic-tac-toe is significantly more complex than most other variations of tic-tac-toe, as there is no clear strategy to playing. This is because of the complicated game branching in this game. Even though every move must be played in a local board, equivalent to a normal tic-tac-toe board, each move must take into account the global board in several ways:

While tic-tac-toe is elementary to solve, and can be done nearly instantly using depth-first search, ultimate tic-tac-toe cannot be reasonably solved using any brute force tactics. Therefore, more creative computer implementations are necessary in order to play this game.

The most common artificial intelligence (AI) tactic, minimax, may be used to play ultimate tic-tac-toe, but has difficulty playing this. This is because, despite having relatively simple rules, ultimate tic-tac-toe lacks any simple heuristic evaluation function. This function is necessary in minimax, for it determines how good a specific position is. Although elementary evaluation functions can be made for ultimate tic-tac-toe by taking into account the number of local victories, these largely overlook positional advantage that is much harder to quantify. Without any efficient evaluation function, most typical computer implementations are weak, and therefore there are few computer opponents that can consistently outplay humans.


...
Wikipedia

...