Introductory Problem-Tic Tac Toe

The game Tic Tac Toe is also known as Noughts and Crosses or Xs and Os ,the player needs to take turns marking the spaces in a 3x3 grid with their own marks,if 3 consecutive marks (Horizontal, Vertical,Diagonal) are formed then the player who owns these moves get won.

Assume ,

Player 1 - X
Player 2 - O

 

 

So,a player who gets 3 consecutive marks first,they will win the game .

Let's have a discussion about how a board's data structure looks and how the Tic Tac Toe algorithm works.

Board's Data Structure:

The cells could be represent as Center square,Corner,Edge as like below

Number each square starts from 1 to 9 like following image

 Consider a Board having nine elements vector.Each element will contain

• 0 for blank
• 1 indicating X player move
• 2 indicating O player move

Computer may play as X or O player. First player is always X.

Move Table
It is a vector of 3^9 elements, each element of which is a nine element vector representing board position.
Total of 3^9(19683) elements in move table
Move Table
Index Current Board position New Board position
0             000000000                 000010000
1             000000001                 020000001
2             000000002                 000100002
3             000000010                 002000010
.
.

Algorithm

To make a move, do the following:

1. View the vector (board) as a ternary number and convert it to its corresponding decimal number.
2. Use the computed number as an index into the move table and access the vector stored there.
3. The vector selected in step 2 represents the way the board will look after the move that should be made. So set board equal to that vector.

Let's start with empty board

 

 

 

Step 1:Now our board looks like 000 000 000 (tenary number) convert it into decimal no.The decimal no is 0
 Step 2:Use the computed number ie 0 as an index into the move table and access the vector stored in
New Board Position.
The new board position is 000 010 000 
Step 3:The vector selected in step 2(000 010 000 ) represents the way the board will look after the move that should be made. So set board equal to that vector.
After complete the 3rd step your board looks like\
 



 

This process continues until the player get win or tie.  

Flowchart:

Hope you all understood .......