Tic-tac-toe (or Noughts and crosses, Xs and Os) is a traditional paper-and-pencil game for two players, X and O, with each taking turns marking the spaces in a 3×3 grid. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game.
According to Wikipedia, an early variant of Tic-tac-toe was played in the Roman Empire around the first century BC – which may actually have originated in ancient Egypt. Fast forward to 2013: Tic-Tac-Toe is going Atmel, courtesy of Rahul Kar. Powered by Atmel’s ATtiny85, the digital implementation of the classic Tic-Tac-Toe game boasts an AI mechanism capable of making defending or winning moves against a human opponent.
“The project uses an 8×8 LED matrix to display the player’s move. The LED matrix is controlled by a display driver – MAX7219. The MAX7219 takes care of all the multiplexing, decoding and refresh circuitry via SPI interface connected to Attiny85. The processing and logic part is handled by ATtiny85,” Kar explained.
“[The] Attiny85 is a high-performance, low-power 8-bit AVR RISC-based microcontroller combining 8 KB ISP flash memory, 512-Byte SRAM and 6 general purpose I/O lines. Input is taken via 2 push button switches: scroll & enter. Scroll button is used to navigate to a particular grid [0-8] while enter is used for confirmation. The display blinks briefly to acknowledge key press.”
To avoid the ubiquitous tie of traditional tic-tac-toe games, Kar implements a specially coded algorithm programmed to always play the optimal move and never lose.
“In order to achieve the goal, the well known algorithm Minimax is used, [which] optimizes its chance of winning by predicting the future states as the game progresses. [Basically], it exploits the fact that two players are working to reach opposite goals,” said Kar.
“The [primary] objective [of the] algorithm is to minimize whatever value the opponent’s algorithm is trying to maximize. In this project, the Minimax function recursively finds the best possible move with respect to users input. It does so by generating a complete game tree. A game tree contains all possible moves from each position for a given game.”