Abstract
This program was created by Mohit Soam. It is my first real project in AI.
The comments are easy to follow and will help you develop similar programs where low-level
AI is involved. In most case computer is impossible to beat, but it can be beat
in few case. If you can't seem to beat it then you might want to analyze the code.
The only thing I'd like to clean up is the fact that how the game actually begins. It starts
when the human clicks on a non-occupied square.
Using the code
A brief description of how to use the article or code. The class names and the
methods are below :
' ###### ####### ####### ###
' # # ### # ### ### # ### # #
' # # # # # # # # # ####
' # # # # # ## # # # # #
' # # ### # ## ## ### # ### ####
Class methods
Class_Initialize
Constructor assigns a initial values to variables.
Dim I As Integer
For I = 0 To 8
HumanBox(I) = "Empty"
MachineBox(I) = "Empty"
Next I
SetHuman
Sets the Player to Human.
SetMachine
Sets the Player to Machine.
whoplay
Returns the name of the player i.e. either Human or Machine.
If Play = False Then
NowPlaying = "Human"
Play = True
Else
NowPlaying = "Machine"
Play = False
End If
IsLegalMove
Returns true if the move is legal else false.
If HumanBox(Index) = "Empty" And MachineBox(Index) = "Empty" Then
IsLegalMove = True
Else
IsLegalMove = False
End If
COMPARE
Check the all possible cases to win the game & returns true if anyone wins.
Dim I As Integer
If NowPlaying = "Human" Then
For I = 0 To 8
EmptyBox(I) = HumanBox(I)
Next I
ElseIf NowPlaying = "Machine" Then
For I = 0 To 8
EmptyBox(I) = MachineBox(I)
Next I
End If
If (EmptyBox(0) = "1" And EmptyBox(1) = "1" And EmptyBox(2) = "1") Or _
(EmptyBox(3) = "1" And EmptyBox(4) = "1" And EmptyBox(5) = "1") Or _
(EmptyBox(6) = "1" And EmptyBox(7) = "1" And EmptyBox(8) = "1") Then
COMPARE = True
ElseIf (EmptyBox(0) = "1" And EmptyBox(3) = "1" And EmptyBox(6) = "1") Or _
(EmptyBox(1) = "1" And EmptyBox(4) = "1" And EmptyBox(7) = "1") Or _
(EmptyBox(2) = "1" And EmptyBox(5) = "1" And EmptyBox(8) = "1") Then
COMPARE = True
ElseIf (EmptyBox(0) = "1" And EmptyBox(4) = "1" And EmptyBox(8) = "1") Or _
(EmptyBox(2) = "1" And EmptyBox(4) = "1" And EmptyBox(6) = "1") Then
COMPARE = True
End If
Function to Evaluate Machine Move
After the human move, its computer turn to evaluate the best move we
call MachineMoveEvaluation function to perform that:
Variables declaration
Dim Move As Integer
Dim FinalMove As Integer
Dim LegalMove As Integer
Dim TotalScore As Integer
Dim HighestScore As Integer
Dim AverageScore As Integer
Dim RecursiveScore As Integer
Dim WasWin As Boolean
Dim WasLost As Boolean
Dim HumanBox As String
Dim MachineBox As String
Dim X As Integer
Variables initialization
Const WS = 100
Const DS = 50
LegalMove = 0
TotalScore = 0
HighestScore = 0
Main Logic to evaluate best move
TreeDepth = TreeDepth + 1
For Move = 0 To 8
If Box(TreeDepth - 1).IsLegalMove(Move) = True Then
If LegalMove = 0 Then
FinalMove = Move
End If
LegalMove = LegalMove + 1
'Create New Object
Set Box(TreeDepth) = New ClsTicTacToe
For X = 0 To 8
HumanBox = Box(TreeDepth - 1).GetHuman(X)
MachineBox = Box(TreeDepth - 1).GetMachine(X)
Call Box(TreeDepth).SetHuman(X, HumanBox)
Call Box(TreeDepth).SetMachine(X, MachineBox)
Next X
Box(TreeDepth).NowPlaying = Box(TreeDepth - 1).NowPlaying
Box(TreeDepth).Play = Box(TreeDepth - 1).Play
Box(TreeDepth).FillBox (Move)
If Box(TreeDepth).COMPARE = True Then
WasWin = True
HighestScore = WS
TotalScore = TotalScore + WS
FinalMove = Move
Else
Call Box(TreeDepth).whoplay
S = MachineMoveEvaluation(RecursiveScore)
If (RecursiveScore = WS) Then
WasWin = True
Else
WasLost = True
TotalScore = TotalScore + RecursiveScore
If (RecursiveScore > HighestScore) Then
HighestScore = RecursiveScore
FinalMove = Move
End If
End If
'Destroy Object
Set Box(TreeDepth) = Nothing
End If
End If
Next Move
If LegalMove = 0 Then
S = DS
TreeDepth = TreeDepth - 1
MachineMoveEvaluation = 99
Else
AverageScore = TotalScore / LegalMove
If (WasWin = True And WasLost = True) Then
S = WS - (WS - AverageScore) / 5
Else
S = AverageScore
End If
S = 100 - S
TreeDepth = TreeDepth - 1
MachineMoveEvaluation = FinalMove
End If
Points of Interest
This application is an example of a production system. Production systems are
applied to problem solving programs that must perform a wide-range of searches.
Production systems are symbolic AI systems. The difference between these two
terms is only one of semantics. A symbolic AI system may not be restricted to
the very definition of production systems, but they can't be much different
either.
Production systems are composed of three parts, a global database, production
rules and a control structure.
The global database is the system's short-term memory. These are collections
of facts that are to be analyzed. A part of the global database represents the
current state of the system's environment. In a game of chess, the current state
could represent all the positions of the pieces for example.
Production rules (or simply productions) are conditional if-then branches. In
a production system whenever a or condition in the system is satisfied, the
system is allowed to execute or perform a specific action which may be specified
under that rule. If the rule is not fulfilled, it may perform another action.
This can be simply paraphrased:
WHEN (condition) IS SATISFIED,
PERFORM (action)
A Production System Algorithm
DATA (binded with initial global data base)
when DATA satisfies the halting condition do
begin
select some rule R that can be applied to DATA
return DATA (binded with the result of when R was applied to DATA)
end
|
For a scenario where a production system is attempting to find the best move
in a Tic Tac Toe,
pattern matching is required to tell whether or not a condition is satisfied. If
the current state of a Tic Tac Toe matches the desired state (win state or the solution to
game), then anyone wins in game. However, if this case is not
so, the system must attempt an action that will contribute to manipulating the
global database, under the production rules in such a way that the Machine (i.e
Computer)
will eventually be winner.
 |
 |
| Initial State |
One of the Final State |
In order to take a closer look to control structures let us look at a problem
involving the game. The Tic Tac Toe contains Nine Blank squares laid in a
three-by-three grid. Player fills square with either "X" or
"O" (according to his choice of mark). In next move computer appears
in some, obfuscated state. The goal of the production system is to reach some
final state (the win state). This can be obtained by successively moving squares into
the empty position. This system changes with every move of the square, thus, the
global database changes with time. The current state of the system is given as
the position and enumeration of the squares. This can be represented for example
as a 9 dimensional vector with components 0, 1, 2, 3,..., 8, NULL, the NULL
object being the empty space.
In this Tic Tac Toe , the most general production rule can be simply summed
up in one sentence:
First fill the empty square that makes the opponent
winner, if isn't then fill the box that help us to win the game.
However, in order to fill the empty square, the system must first verify all
the possible moves of opponent to win the game (i.e., a heuristic search must
used). All these sequences require
further production rules. The control system decides which production rules to
use, and in what sequence. To reiterate, in order to find the win cases. The
control system thus picks the production rule to be used next in a production
system algorithm (refer to the production system algorithm figure above).
Credits
This project is based on the work done by Rohit Soam in Artificial
Intelligence during MCA studies. Thanks very much!
History
- v1.1 (16/February/2006)
First release
