Meta-tic-tac-toe

from Wikipedia, the free encyclopedia
An incomplete board of Ultimate Tic-Tac-Toe.
Representation of a running game of Meta-Tic-Tac-Toe (the big "X" and "O" mark local boards that have already been won). The last move of "O" was played on the middle top local board in the middle left box. Therefore "x" has to make a move in the middle left local board (marked).

Meta-Tic-Tac-Toe is a board game that consists of nine Tic-Tac-Toe boards arranged in a 3 × 3 grid. Players take turns playing on the smaller tic-tac-toe boards until one of them wins on the larger tic-tac-toe board. Compared to traditional tic-tac-toe, the strategy in this game is conceptually more difficult and has proven to be more challenging for computers.

regulate

Since "X" played a move in the box in the top right corner of the middle local board, "O" must put in the local board in the top right corner (marked).

Each small 3 × 3 tic-tac-toe board is called a local board, and the larger 3 × 3 board is called a global board. The game begins with the starting player playing in one of the 81 empty spaces. This move "sends" its opponent to another local board, which is determined by the position of the move on the global board. For example, if X is played in the top right hand space of the local board, O must next play on the local board in the top right of the global board. O can then play in one of the available places on this local board, each move sending X to a different local board.

If a move is played to win a local board according to the rules of normal tic-tac-toe, the entire local board is marked as a win for the player on the global board.

As soon as a local board has been won or completely filled by a player, no further moves may be played on this board. If a player is sent to such a board, that player can play on any other board.

The game ends when either one player wins the global board or there are no legal moves left. In this case it is a tie.

Style of play

Meta-Tic-Tac-Toe is much more complex than most other variations of Tic-Tac-Toe because there is no clear strategy for playing it. This is due to the complicated game branching in this game. Although each move must be played on a local board, which is the same as a normal tic-tac-toe board, each move must account for the global board in different ways:

  1. Anticipate the next move: Every move played on a local board determines where the opponent's next move may be played. This can lead to the fact that movements that are considered bad in the normal tic-tac-toe area are feasible, as the opponent is sent to another local board and may not be able to react immediately to the move made. As a result, players are forced to consider the larger game board rather than just focusing on the local board.
  2. Predicting turn orders : Visualizing future branches of the game tree is more difficult than single-board tic-tac-toe. Every move determines the next move, and therefore predicting future moves follows a much less linear path. Future positions are no longer interchangeable, each step leads to very different possible future positions. This makes the game tree difficult to visualize, potentially overlooking many possible paths. It may not be possible to react immediately to opposing moves. As a result, players are forced to consider the larger game board rather than just focusing on the local board.
  3. Winning the game: Due to the rules of Meta-Tic-Tac-Toe, the global board is never directly affected. It is only influenced by actions that take place on local boards. This means that every local move played is not meant to win the local board but the global board. Local profits are not valuable if they cannot be used to win the global board. In fact, sacrificing a local board to your opponent can be strategic in order to gain a more important local board yourself. This added complexity makes it more difficult for humans to analyze the relative importance and importance of movement, and consequently it is more difficult to play well.

Computer implementations

While tic-tac-toe is elementary to solve and can be done almost immediately with depth-first search , meta-tic-tac-toe cannot reasonably be solved with any brute force tactic . Hence, more creative computer implementations are required to play this game.

The most common Artificial Intelligence (AI) tactic , Minimax , can be used to play Meta-Tic-Tac-Toe but has difficulty playing it. This is because the Meta-Tic-Tac-Toe lacks a simple heuristic evaluation function despite relatively simple rules. This feature is required in the Minimax as it determines how good a particular position is. Although elementary scoring functions for the meta-tic-tac-toe can be created considering the number of local wins, these largely overlook the positional advantage, which is much more difficult to quantify. Without an efficient scoring function, most typical computer implementations are weak, and hence there are few computer opponents who can consistently outperform humans.

However, artificial intelligence algorithms that do not need scoring functions, such as the Monte Carlo tree search algorithm, have no problem playing this game. Monte Carlo Tree Search relies on random simulations of games to determine how good a position is, and therefore can more accurately assess how good a current position is. Hence, computer implementations using these algorithms outperform Minimax solutions and can consistently beat human opponents.

Web links

Commons : Ultimate Tic Tac Toe  - Collection of Images

Individual evidence

  1. ↑ Eytan Lifshitz, David Tsurel: AI Approaches to Ultimate Tic-Tac-Toe . December 26, 2016.
  2. ↑ Ben Orlin: Ultimate Tic-Tac-Toe . June 16, 2013.
  3. ^ Ofek Gila: What is the Monte Carlo tree search? . June 27, 2016.