Tic Tac Toe - An Artificial Intelligence Implementation

• Download demo project - 15 Kb
• Download source - 12 Kb

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:

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