Artifitial Intelligence: Chapter 2 AI for Tic Tac Toe Game - Part1

Tic–Tac–Toe Game Playing There is one human player and other player is computer. The objective is to write a computer program which wins most of the time. We will present three approaches to play this game which increase in

1. Complexity
2. Use of generalization
3. Clarity of their knowledge
4. Extensibility of their approach

These approaches will move towards being representations of what we will call AI techniques.

PROGRAM 1

Data Structures

Board 
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.

Conclusion

1. Very efficient in terms of time but has several disadvantages
2. Lot of space to store the move table.
3. Lot of work to specify all the entries in move table.
4. Error prone because of the data is voluminous.
5. Poor extensibility: 3D tic-tac-toe = 327board position to be stored.
6. Not intelligent.