Click here to Skip to main content
12,691,789 members (27,509 online)
Click here to Skip to main content
Add your own
alternative version


17 bookmarked

Tic Tac Toe - An Artificial Intelligence Implementation

, 15 Feb 2006
Rate this:
Please Sign up or sign in to vote.
A complete Tic Tac Toe describes full implementation of Artificial Intelligence

Sample Image - maximum width is 600 pixels


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

Constructor assigns a initial values to variables.

Dim I As Integer
For I = 0 To 8
    HumanBox(I) = "Empty"
    MachineBox(I) = "Empty"
Next I

Sets the Player to Human.

Sets the Player to Machine.

Returns the name of the player i.e. either Human or Machine.

If Play = False Then
    NowPlaying = "Human"
    Play = True
    NowPlaying = "Machine"
   Play = False
End If

Returns true if the move is legal else false.

If HumanBox(Index) = "Empty" And MachineBox(Index) = "Empty" Then
    IsLegalMove = True
    IsLegalMove = False
End If

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
        Call Box(TreeDepth).whoplay
        S = MachineMoveEvaluation(RecursiveScore)

        If (RecursiveScore = WS) Then
            WasWin = True
            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
    AverageScore = TotalScore / LegalMove
    If (WasWin = True And WasLost = True) Then
       S = WS - (WS - AverageScore) / 5
       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
    select some rule R that can be applied to DATA
    return DATA (binded with the result of when R was applied to DATA)

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 StateOne 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).


This project is based on the work done by Rohit Soam in Artificial Intelligence during MCA studies. Thanks very much!


  • v1.1 (16/February/2006)
    First release


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Web Developer
India India
No Biography provided

You may also be interested in...


Comments and Discussions

QuestionProject on AI Pin
amit201115-Jan-09 3:50
memberamit201115-Jan-09 3:50 
AnswerRe: Project on AI Pin
jasontls17-Mar-09 7:17
memberjasontls17-Mar-09 7:17 
Generalhi!!! Pin
AinJheL_mi28-Jun-06 1:34
memberAinJheL_mi28-Jun-06 1:34 
GeneralIn modula 2 Pin
alexlaohoucheong15-May-06 8:32
memberalexlaohoucheong15-May-06 8:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170117.1 | Last Updated 15 Feb 2006
Article Copyright 2006 by parinit
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid