Tic Tac Toe Using AI

Artificial Intelligence (AI) Can be used to build in order to play only single player, in other words human against computer.
so lets, start......

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:

We will get to know about the code for the same in next blog