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.

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.

Artifitial Intelligence: Chapter 1 Introduction

What is AI?

1. Modeling human cognition or mental faculty using computers
2. Study of making computers do things which at the moment people better
3. Making computers do things which require intelligence

Intelligence is a property of mind that encompasses many related mental abilities, such as the capacities to

• reason
• plan
  
• solve problems
• think abstractly,
• comprehend ideas and language, and
• learn

More formally AI is a branch of computer science which is concerned with the study and creation of computer systems that exhibit

• some form of intelligence or
• the characteristics we associate with intelligence in human behavior
  

Two Views of AI Goals

• AI is about duplicating what the (human) brain DOES
• Cognitive Science
• AI is about duplicating what the (human) brain SHOULD do
• Rationality (doing things logically)

Cool Stuff in AI

1. Game playing agents
2. Machine learning
3. Speech
4. Language
5. Vision
6. Data Mining
7. Web agents

Useful Stuff

1. Medical Diagnosis
2. Fraud Detection
3. Object Identification
4. Space Shuttle Scheduling
5. Information Retrieval

What is AI today?
Three typical components of AI Systems

THE WORLD ----->Perception-----> Action------> Reasoning------>THE WORLD

Recent AI: Heavy use of

• probability theory
• decision theory
• statistics
• logic (fuzzy, modal, temporal)