Tic-tac-toe is a classic game which requires no introduction. It is a pen and paper game played between 2 players (marked on paper as ‘X’ & ‘O’).The board setup consists of a 3x3 grid on which each player alternates between each moves. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game.
This project is an attempt to recreate the classic game in a digital format. To spice things up a bit, instead of using the regular 2 player setup it uses an inbuilt AI mechanism to compete against the player.
Design: The project uses an 8x8 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. 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.
Working: An interesting thing with tic-tac-toe is if both the players are playing with their best strategy, the game will always end in a tie. To make the game more challenging the player is allowed to make the first move as the odds of winning are high. The bot used in this project is designed to always play the optimal move and never lose.
In order to achieve the goal, a well known algorithm Minimax is used. The minimax algorithm optimizes its chance of winning by predicting the future states as the game progresses. It exploits the fact that two players are working to reach opposite goals. The main objective in this algorithm is to try minimizing 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. Wikipedia has a nice explanation of game tree with tic-tac-toe as example.
How to play: The design is kept to a bare minimum. The user needs to put a mark on the grid by using the scroll and enter button. The grids are marked internally from 0-8. Click the scroll button repeatedly until the desired grid is counted for. Then hit the enter button to mark it on display. If the grid selected is already filled, the input will be discarded. Depending on win, lose or tie situation appropriate message is displayed at the end of the game.
For the display driver MAX7219 add decoupling capacitors to the power pins of the IC as close as possible to reduce noise. For Iset use 15 k? resistance for optimal brightness. Follow the tutorial here to program ATtiny85 using the Arduino software.