Jump to content

Ultimate tic-tac-toe

From Wikipedia, the free encyclopedia

An incomplete board of Ultimate Tic-Tac-Toe.
Incomplete super tic-tac-toe game (the large 'X's and 'O's represent small boards that are won by that player). The previous move was O playing in the center square of the bottom-right board, forcing X to play their next move in smaller board located in the center of the larger board (highlighted in blue).
Since X played in the top-right corner of the small board, O is forced to play their next move in the top-right small board of the larger board (highlighted in red).

Ultimate tic-tac-toe (also known as super tic-tac-toe, meta tic-tac-toe or (tic-tac-toe)²[1]) is a board game composed of nine tic-tac-toe boards arranged in a 3 × 3 grid.[2][3] Players take turns playing on the smaller tic-tac-toe boards until one of them wins on the larger board. Compared to traditional tic-tac-toe, strategy in this game is conceptually more difficult and has proven more challenging for computers.[4]

Rules

[edit]

Just like in regular tic-tac-toe, the two players (X and O) take turns, starting with X. The game starts with X playing wherever they want in any of the 81 empty spots. Next the opponent plays, however they are forced to play in the small board indicated by the relative location of the previous move. For example, if X plays in the top right square of a small (3 × 3) board, then O has to play in the small board located at the top right of the larger board. Playing any of the available spots decides in which small board the next player plays.

If a move is played so that it is to win a small board by the rules of normal tic-tac-toe, then the entire small board is marked as won by the player in the larger board. Once a small board is won by a player or it is filled completely, 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 larger board or there are no legal moves remaining, in which case the game is a draw.[3]

Gameplay

[edit]

Super 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 small board, equivalent to a normal tic-tac-toe board, each move must take into account the larger board in several ways:

  1. Anticipating the next move: Each move played in a small board determines where the opponent's next move can be played. This might make moves that are considered bad in normal tic-tac-toe viable, since the opponent is forced to play on certain board. This way a player could play the same smaller board multiple times in a row, without their opponent being able to respond. Therefore, players are forced to consider the larger game board instead of simply focusing on the smaller boards.
  2. Visualizing the game tree: Visualizing future branches of the game tree is more difficult than single board tic-tac-toe. Each move determines the next move, and therefore reading ahead—predicting future moves—follows a much less linear path. Future board positions are no longer interchangeable, each move leading to starkly different possible future positions. This makes the game tree difficult to visualize, possibly leaving many possible paths overlooked.
  3. Winning the game: Due to the rules of super tic-tac-toe, the larger board is never directly affected. It is governed only by actions that occur in smaller boards. This means that each move played is not intended to win the small board, but to win the larger board. In fact, it may be strategic to sacrifice a small board to your opponent in order to win a more important small board yourself. This added layer of complexity makes it harder to analyze the relative importance and significance of moves, and consequently harder to play well.

Computer implementations

[edit]

While tic-tac-toe is elementary to solve[5] 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 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 small board 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.[4]

However, artificial intelligence algorithms that don't need evaluation functions, like the Monte Carlo tree-search algorithm, have no problem in playing this game. The Monte Carlo tree search relies on random simulations of games to determine how good a position is instead of a positional evaluation and is therefore able to accurately assess how good a current position is. Therefore, computer implementations using these algorithms tend to outperform minimax solutions and can consistently beat human opponents.[2][6]

Variants

[edit]

A variant of the game allows players to continue playing in already won boxes if there are still empty spaces. This allows the game to last longer and involves further strategic moves. It was shown in 2020 that this set of rules for the game admits a winning strategy for the first player to move, meaning that the first player to move can always win assuming perfect play.[7] If playing with this rule set is still preferred, the forced-win problem can be practically solved by generating the first 4 moves at random. This is most effectively done by randomly generating a 5-digit number, then using the first digit to select a larger board and the next four digits to place "X"s and "O"s in the appropriate small board.[8]

Tic-Tac-Ku, a game invented by Mark Asperheim and Cris Van Oosterum,[9][10][11] has similar rules to ultimate tic-tac-toe, however a player wins the game by winning at least five small boards, instead of three in a line.

See also

[edit]

References

[edit]
  1. ^ Konforti, Nicole; Epstein, Dave. "NP Completeness in Contemporary Board Games".[dead link]
  2. ^ a b Whitney, George; Janoski, Janine (November 26, 2016). "Group Actions on Winning Games of Super Tic-Tac-Toe". arXiv:1606.04779 [math.CO].
  3. ^ a b Orlin, Ben (June 1, 2013). "Ultimate Tic-Tac-Toe". Math with Bad Drawings. Archived from the original on August 30, 2021. Retrieved October 18, 2016.
  4. ^ a b Lifshitz, Eytan; Tsurel, David (December 26, 2016). "AI Approaches to Ultimate Tic-Tac-Toe" (PDF). The Rachel and Selim Benin School of Computer Science and Engineering. Archived from the original (PDF) on July 29, 2021.
  5. ^ Schaefer, Steve (2002). "MathRec Solutions (Tic-Tac-Toe)". Archived from the original on February 24, 2020. Retrieved October 18, 2016.
  6. ^ Gila, Ofek (June 2, 2016). "What is the Monte Carlo tree search?". We Blog. Retrieved October 18, 2016.
  7. ^ Bertholon, Guillaume; Géraud-Stewart, Rémi; Kugelmann, Axel; Lenoir, Théo; Naccache, David (June 3, 2020). "At Most 43 Moves, At Least 29: Optimal Strategies and Bounds for Ultimate Tic-Tac-Toe". arXiv:2006.02353v2 [cs.GT].
  8. ^ Diamond, Justin (July 13, 2022). "A Practical Method for Preventing Forced Wins in Ultimate Tic-Tac-Toe". arXiv:2207.06239 [math.HO].
  9. ^ Erik Arneson. "Mensa Select Award Winners". Archived from the original on June 26, 2015. Retrieved May 19, 2012.
  10. ^ "2009年度门萨最佳动脑奖揭晓" [2009 Mensah Best Brain Picking Award Announced]. www.boardgamenews.com (in Chinese). April 29, 2009. Archived from the original on March 4, 2016. Retrieved May 19, 2012 – via 173zy.com.
  11. ^ "Tic Tac Ku". marbles – the brain store. Archived from the original on June 10, 2012. Retrieved May 19, 2012.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ultimate_tic-tac-toe&oldid=1235984231"