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 3×3 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 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. 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.
Project Source Code
###
/** * Digital Tic-Tac-Toe Using ATtiny85 * Arduino 1.0.1 IDE * Rahul Kar * 08/18/2013 */ #include "LedControl.h"/* pin 2 is connected to the DataIn
pin 1 is connected to the CLK
pin 0 is connected to LOAD */
LedControl lc=LedControl(2,1,0,1);byte p1[8]={
B00000000,B00000010,B00111110,B00010010,B00000000,B00111000,B00101000,B00111110};
byte p2[8]={
B00000000,B00111010,B00101010,B00101110,B00000000,B00111000,B00101000,B00111110};
byte d[8]={
B11110000,B11110000,B11110000,B11110000,B11110000,B11110000,B11110000,B11110000};
byte f[8]={
B11111111,B11111111,B11111111,B11111111,B11111111,B11111111,B11111111,B11111111};const int counterpin=3;
const int enterpin=4;
void setup()
{
lc.shutdown(0,false);
lc.setIntensity(0,8);
lc.clearDisplay(0);
pinMode(counterpin,INPUT);
pinMode(enterpin,INPUT);
}int userinput(int board[])
{
int counter=0;
int p=0,q=0,debounce;
while(!digitalRead(enterpin))
{
p=digitalRead(counterpin);
if(p!=q)
{
if(p==HIGH)
{
counter++;
lc.clearDisplay(0);
delay(300);
drawboard(board);
}
}
p=q;
}
lc.clearDisplay(0);
delay(300);
drawboard(board);
return counter;
}int win(int board[])
{
int wins[][8] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
for(int i=0;i<8;++i)
{
if(board[wins[i][0]] != 0 && board[wins[i][0]] == board[wins[i][1]] && board[wins[i][0]] == board[wins[i][2]])
return board[wins[i][2]];
}
return 0;
}int minimax(int board[],int player)
{
int winner=win(board);
if(winner!=0)
return winner*player;int moveval=-1;
int score=-2; //Losing moves are preferred to no move
for(int i=0;i<9;++i)
{
if(board[i]==0)
{
board[i]=player; //Try the move
int thisScore=-minimax(board,player*-1);
if(thisScore>score)
{
score=thisScore;
moveval=i;
}//Pick the one that's worst for the opponent
board[i]=0;//Reset board after try
}
}
if(moveval==-1) return 0;
return score;
}void computerMove(int board[])
{
int moveval=-1;
int score=-2;
int i;
for(i=0;i<9;++i)
{
if(board[i]==0)
{
board[i]=1;
int tempScore=-minimax(board,-1);
board[i]=0;
if(tempScore>score)
{
score=tempScore;
moveval=i;
}
}
}
//returns a score based on minimax tree at a given node.
board[moveval]=1;
}void playerMove(int board[])
{
int moveval=0,flag=0;
moveval=userinput(board);
delay(800);
if(board[moveval]==1 || board[moveval]==-1)
{
playerMove(board); //position already filled
}
else if(board[moveval]==0)
{
board[moveval]=-1; //empty position
}
}
void drawboard(int board[]) //handles the matrix display based on board vales
{
lc.clearDisplay(0);
if(board[0]==-1)
row1col1_sqr(true);
if(board[0]==1)
row1col1_sls(true);if(board[1]==-1)
row1col2_sqr(true);
if(board[1]==1)
row1col2_sls(true);if(board[2]==-1)
row1col3_sqr(true);
if(board[2]==1)
row1col3_sls(true);if(board[3]==-1)
row2col1_sqr(true);
if(board[3]==1)
row2col1_sls(true);if(board[4]==-1)
row2col2_sqr(true);
if(board[4]==1)
row2col2_sls(true);if(board[5]==-1)
row2col3_sqr(true);
if(board[5]==1)
row2col3_sls(true);if(board[6]==-1)
row3col1_sqr(true);
if(board[6]==1)
row3col1_sls(true);if(board[7]==-1)
row3col2_sqr(true);
if(board[7]==1)
row3col2_sls(true);
if(board[8]==-1)
row3col3_sqr(true);
if(board[8]==1)
row3col3_sls(true);if(board[0]==0&&board[1]==0&&board[2]==0&&board[3]==0&&board[4]==0&&board[5]==0&&board[6]==0&&board[7]==0&&board[8]==0)
fillall();
}void player1() //display the word 'P1' in matrix
{
for(int i=0;i<8;i++)
{
lc.setRow(0,i,p1[i]);
}
}void player2() //display the word 'P2' in matrix
{
for(int i=0;i<8;i++)
{
lc.setRow(0,i,p2[i]);
}
}
void draw() //fills up half of matrix for displaying draw condition
{
for(int i=0;i<8;i++)
{
lc.setRow(0,i,d[i]);
}
}
void fillall() //fills the entire matrix
{
for(int i=0;i<8;i++)
{
lc.setRow(0,i,f[i]);
}
}
/*--------------------------------------*/
void row1col1_sqr(boolean inp)
{
lc.setLed(0,6,0,inp);
lc.setLed(0,6,1,inp);
lc.setLed(0,7,0,inp);
lc.setLed(0,7,1,inp);
}void row1col2_sqr(boolean inp)
{
lc.setLed(0,3,0,inp);
lc.setLed(0,3,1,inp);
lc.setLed(0,4,0,inp);
lc.setLed(0,4,1,inp);
}void row1col3_sqr(boolean inp)
{
lc.setLed(0,0,0,inp);
lc.setLed(0,0,1,inp);
lc.setLed(0,1,0,inp);
lc.setLed(0,1,1,inp);
}void row1col1_sls(boolean inp)
{
lc.setLed(0,6,0,inp);
lc.setLed(0,7,1,inp);
}void row1col2_sls(boolean inp)
{
lc.setLed(0,3,0,inp);
lc.setLed(0,4,1,inp);
}void row1col3_sls(boolean inp)
{
lc.setLed(0,0,0,inp);
lc.setLed(0,1,1,inp);
}
/*---------------------------------------*/
void row2col1_sqr(boolean inp)
{
lc.setLed(0,6,3,inp);
lc.setLed(0,6,4,inp);
lc.setLed(0,7,3,inp);
lc.setLed(0,7,4,inp);
}void row2col2_sqr(boolean inp)
{
lc.setLed(0,3,3,inp);
lc.setLed(0,3,4,inp);
lc.setLed(0,4,3,inp);
lc.setLed(0,4,4,inp);
}void row2col3_sqr(boolean inp)
{
lc.setLed(0,0,3,inp);
lc.setLed(0,0,4,inp);
lc.setLed(0,1,3,inp);
lc.setLed(0,1,4,inp);
}void row2col1_sls(boolean inp)
{
lc.setLed(0,6,3,inp);
lc.setLed(0,7,4,inp);
}void row2col2_sls(boolean inp)
{
lc.setLed(0,3,3,inp);
lc.setLed(0,4,4,inp);
}void row2col3_sls(boolean inp)
{
lc.setLed(0,0,3,inp);
lc.setLed(0,1,4,inp);
}
/*---------------------------------------*/void row3col1_sqr(boolean inp)
{
lc.setLed(0,6,6,inp);
lc.setLed(0,6,7,inp);
lc.setLed(0,7,6,inp);
lc.setLed(0,7,7,inp);
}void row3col2_sqr(boolean inp)
{
lc.setLed(0,3,6,inp);
lc.setLed(0,3,7,inp);
lc.setLed(0,4,6,inp);
lc.setLed(0,4,7,inp);
}void row3col3_sqr(boolean inp)
{
lc.setLed(0,0,6,inp);
lc.setLed(0,0,7,inp);
lc.setLed(0,1,6,inp);
lc.setLed(0,1,7,inp);
}void row3col1_sls(boolean inp)
{
lc.setLed(0,6,6,inp);
lc.setLed(0,7,7,inp);
}void row3col2_sls(boolean inp)
{
lc.setLed(0,3,6,inp);
lc.setLed(0,4,7,inp);
}void row3col3_sls(boolean inp)
{
lc.setLed(0,0,6,inp);
lc.setLed(0,1,7,inp);
}
/*---------------------------------------*/void loop()
{
int board[]={0,0,0,0,0,0,0,0,0};
int player=1; //flag for first player setting
fillall();
delay(700);
for(int turn=0;turn<9 && win(board)==0;++turn)
{
if((turn+player)%2==0)
computerMove(board);
else
{
drawboard(board);
playerMove(board);
}
}
switch(win(board))
{
case 0:
drawboard(board);
delay(3000);
draw();
delay(99999);
break;
case 1:
drawboard(board);
delay(3000);
player2();
delay(999999);
break;
case -1:
drawboard(board);
delay(3000);
player1();
delay(999999);
break;
}
}
###
Circuit Diagrams
Project Video
Filed Under: Electronic Projects
Filed Under: Electronic Projects
Questions related to this article?
👉Ask and discuss on EDAboard.com and Electro-Tech-Online.com forums.
Tell Us What You Think!!
You must be logged in to post a comment.