Artifitial Intelligence: Chapter 2 AI for Tic Tac Toe Game Part 2

PROGRAM 2

Data Structure
Board
A nine –element vector representing the board : B[1..9]

• 2-indicates blank
• 3-X
• 5-0

Turn
An integer

• 1-First move
• 9-Last move

Algorithm
There are three sub procedures

• Make_2 -Tries to make valid 2
• It first tries to play in the center. If not possible, then it tries the various suitable non corner square
• So, it returns 5 if the center is free else returns number of suitable blank non corner square.
• PossWin(P) -Returns 0
• It returns 0, if player P cannot win in its next move, otherwise returns the number of square that constitutes a winning move for P.
• If PossWin(P) = 0 {P can not win}, then find whether opponent can win. If so, then block it.
• Strategy used by PosWin - It operates by checking, one at a time, each of rows /columns and diagonals. It can test for each row/column/diagonal as follows:

If 3 * 3 * 2 = 18then X can win

Else if 5 * 5 * 2 = 50 then O can win.

• Go(n) -makes a move in square n {which is blank i.e. having 2}

These three procedures are used in the following algorithm.
Assumption: The first player uses symbol X.
Computer ( C ) gets chance to play first (C plays X, H plays O)-Odd moves
Human ( H ) gets change to play first. (Computer plays O, H plays X) -Even moves
1 move :go (5)
2 move: If B[5] is blank, then Go(5) else Go(1)
3 move :If B[9] is blank, then Go(9) else Go(3) {make 2}
4 move: {By now human (playing X) has played 2 chances}If PossWin(X) then {block H}Go (PossWin(X)) else Go (Make_2)
5 move : {By now computer has played 2 chances}If PossWin(X) then {won}Go(PossWin(X)) else {block H}if PossWin(O) then Go(PossWin(O)) else if B[7] is blank then Go(7) else Go(3)
6 move: {By now both have played 2 chances}If PossWin(O) then {won}Go(PossWin(O)) else {block H}if PossWin(X) then Go(PossWin(X)) else Go(Make_2)
7 & 9 moves :{By now human (playing O) has played 3 chances}If PossWin(X) then {won}Go(PossWin(X)) else {block H}if PossWin(O) then Go(PossWin(O)) else Go(Anywhere)
8 move:{By now computer has played 3 chances}If PossWin(O) then {won}Go(PossWin(O)) else {block H}if PossWin(X) then Go(PossWin(X)) else Go(Anywhere)

Conclusion

• Not as efficient as first one in terms of time. Several conditions are checked before each move.
• It is memory efficient.
• Easier to understand &; complete strategy has been determined in advance
• Still can not generalize to 3-D.