THE REINSURANCE ACTUARY
  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer

Monte Carlo Tic Tac Toe Engine

24/7/2016

 

Since setting up the approximation of $\pi$ using the Monte Carlo technique of sampling inside a circle, I've been playing around with applying Monte Carlo methods to other problems.

One problem I thought it would be fun to play around with was creating an AI engine that uses Monte Carlo rather than deterministic methods to run. My first thought was to look at a chess engine, I've always wanted to set one up, but after playing around with it for a while I realised setting up the actual game engine was going to be a substantial amount of work before even thinking about the AI. Therefore I shelved that for the time being.

The next game I decided to look at Tic-Tac-Toe or Noughts and Crosses which is on the opposite end of the spectrum in terms of complexity of rules.

Optimal Strategies

As every school age kid quickly learns, there is an optimal strategy for playing Tic-Tac-Toe. In case anyone has forgotten it can easily found online, however programming in the strategy would have been quite tedious, and not as fun as messing around with a stochastic solution.

I thought it was interesting that a Monte Carlo engine, if it can be programmed to play the game well without even being told what the optimal strategy is, should replicate this strategy simply by selecting what it believes is the optimal move based on its own analysis. It can do all of this without ever truly knowing what the strategy is.

I decided to write the engine in VBA, which is not a great development language generally. But meant that I could stick the game into a Spreadsheet which seemed like a fun thing to do. Here's a screenshot of the game:

Picture

How it works

The way the engine works is each time the computer is about to move, it uses the current state of the grid, and plays out a large number of random games (for each move it makes a random selection for itself and then a random selection for the player until one side wins or it is a draw).

The computer tracks who wins each game and more importantly, for each of the possible next moves for the computer, whether it eventually ends in a win, draw or loss. The computer repeats this process a large number of times (the default being 10,000), each time assigning a value to the starting move of +1 if the computer eventually wins the game, +0.5 if the game ends in a draw, and 0 if the computer losses the game. The computer keeps a running total of the value assigned to each starting move. Once the simulation of random games is completed, the computer selects the move with the highest value, this should correspond to the starting move that is the most likely to led to a victory or a draw,

I've linked below to the Excel file with the game inside:

tic_tac_toe.xlsm
File Size: 26 kb
File Type: xlsm
Download File

​And here is the source code in VBA:​
Hide Code

Option Base 1
Option Explicit

Sub MakeMove()

Dim vGrid As Variant
Dim vGridPerm As Variant

Dim iNewCell As Integer
Dim iFirstMove As Integer
Dim irow As Integer

Dim lSimNum As Long
Dim lNumSim As Long

Dim vNextmove(9) As Long

lNumSim = Range("NumSim")
vGrid = Range("Grid")
vGridPerm = Range("Grid")

If CheckWin(vGrid) <> -1 Then
    Exit Sub
End If

For lSimNum = 1 To lNumSim
    
    vGrid = vGridPerm
    
    iFirstMove = GetRandom(vGrid)
    vGrid(iCellToiRow(iFirstMove), iCellToiCol(iFirstMove)) = "X"
    
    While CheckWin(vGrid) = -1
        iNewCell = GetRandom(vGrid)
        vGrid(iCellToiRow(iNewCell), iCellToiCol(iNewCell)) = "O"
        iNewCell = GetRandom(vGrid)
        vGrid(iCellToiRow(iNewCell), iCellToiCol(iNewCell)) = "X"
    Wend

    vNextmove(iFirstMove) = vNextmove(iFirstMove) + CheckWin(vGrid)
    
Next

Range("k6") = findmax(vNextmove)
For irow = 1 To 9
    Range("k7").Offset(irow, 0) = (vNextmove(irow) / lNumSim)
Next

vGridPerm(iCellToiRow(findmax(vNextmove)), iCellToiCol(findmax(vNextmove))) = "X"

Range("grid") = vGridPerm

End Sub

Function findmax(vNextmove)

Dim iCell As Integer
Dim iMax(2) As Integer

iMax(1) = 1

For iCell = 1 To 9
    If vNextmove(iCell) > iMax(1) Then
        iMax(1) = vNextmove(iCell)
        iMax(2) = iCell
    End If
Next

findmax = iMax(2)

End Function

Function GetRandom(vGrid As Variant)

Dim iCell As Integer
Dim iCountBlank As Integer
Dim vEmpty(9) As Variant

iCountBlank = 0

For iCell = 1 To 9
    If vGrid(iCellToiRow(iCell), iCellToiCol(iCell)) = "" Then
        vEmpty(iCountBlank + 1) = iCell
        iCountBlank = iCountBlank + 1
    End If
Next

Randomize
GetRandom = vEmpty(Int(Rnd * (iCountBlank) + 1))

End Function

Function iCellToiRow(iCell As Integer)

iCellToiRow = 1 + Int((iCell - 1) / 3)

End Function

Function iCellToiCol(iCell As Integer)

iCellToiCol = 1 + ((iCell - 1) Mod 3)

End Function

Function CheckWin(vGrid As Variant)

Dim irow As Integer
Dim iCol As Integer
Dim iDiag As Integer

Dim iCountX As Integer
Dim iCountO As Integer
Dim iCountBoth As Integer

'1 = win, 1/2 = draw, 0=Lose, -1 = continuing

' Check X then O
' Check Rows, Check Columns, check down diag, check up diag

CheckWin = -1

For irow = 1 To 3
    iCountX = 0
    iCountO = 0
    For iCol = 1 To 3
        If vGrid(irow, iCol) = "X" Then
            iCountX = iCountX + 1
        End If
        If vGrid(irow, iCol) = "O" Then
            iCountO = iCountO + 1
        End If
    Next
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next


For iCol = 1 To 3
    iCountX = 0
    iCountO = 0
    For irow = 1 To 3
        If vGrid(irow, iCol) = "X" Then
            iCountX = iCountX + 1
        End If
        If vGrid(irow, iCol) = "O" Then
            iCountO = iCountO + 1
        End If
    Next
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountX = 0
iCountO = 0
For iDiag = 1 To 3
    If vGrid(iDiag, iDiag) = "X" Then
        iCountX = iCountX + 1
    End If
    If vGrid(iDiag, iDiag) = "O" Then
        iCountO = iCountO + 1
    End If
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountX = 0
iCountO = 0
For iDiag = 1 To 3
    If vGrid(iDiag, 4 - iDiag) = "X" Then
        iCountX = iCountX + 1
    End If
    If vGrid(iDiag, 4 - iDiag) = "O" Then
        iCountO = iCountO + 1
    End If
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountBoth = 0
For irow = 1 To 3
    For iCol = 1 To 3
        If vGrid(irow, iCol) = "X" Or vGrid(irow, iCol) = "O" Then
            iCountBoth = iCountBoth + 1
        End If
    Next
Next

If iCountBoth = 9 Then
    CheckWin = 0.5
    Exit Function
End If

End Function
 
Show Code

Future Development

Something that I would like to explore in the future is the use of more efficient algorithms for analysing the best move. For example, apparently alpha-beta pruning can be used to focus on the moves that look the most promising rather than spending an equal amount of time looking at all moves.

​I would also like to make a web based version of the game at some point.,

Your comment will be posted after it is approved.


Leave a Reply.

    Author

    ​​I work as an actuary and underwriter at a global reinsurer in London.

    I mainly write about Maths, Finance, and Technology.
    ​
    If you would like to get in touch, then feel free to send me an email at:

    ​LewisWalshActuary@gmail.com

      Sign up to get updates when new posts are added​

    Subscribe

    RSS Feed

    Categories

    All
    Actuarial Careers/Exams
    Actuarial Modelling
    Bitcoin/Blockchain
    Book Reviews
    Economics
    Finance
    Forecasting
    Insurance
    Law
    Machine Learning
    Maths
    Misc
    Physics/Chemistry
    Poker
    Puzzles/Problems
    Statistics
    VBA

    Archives

    March 2023
    February 2023
    October 2022
    July 2022
    June 2022
    May 2022
    April 2022
    March 2022
    October 2021
    September 2021
    August 2021
    July 2021
    April 2021
    March 2021
    February 2021
    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    May 2020
    March 2020
    February 2020
    January 2020
    December 2019
    November 2019
    October 2019
    September 2019
    April 2019
    March 2019
    August 2018
    July 2018
    June 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    April 2016
    January 2016

  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer