In the previous post we looked at variants of random move selection, with them slowly getting better with each iteration. However, intuitively we know that there are better options available to us.

Improving on Random
Making Dynamic Selections
Time for a Game!
Adding Strategies

Improving on Random Link to heading

While the WinRandom & WinBlockRandom methods perform well, they still rely on a random choice of move when no winning or blocking move is found. We can improve this further by selecting places that are known to be better than others. We will initially assign each place a probability based on how often it appears in a winning combination.

staticProbs = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
def generateStaticProbabilities():
    # Initially we will use a 'dumb' method just using the probability that each cell is part of a winning combination
    
    # The corners each appear in 3 winning sets
    staticProbs[0][0] = 3
    staticProbs[0][2] = 3
    staticProbs[2][0] = 3
    staticProbs[2][2] = 3

    # The middle of a row/column each appear in 2 winning sets
    staticProbs[0][1] = 2
    staticProbs[1][0] = 2
    staticProbs[1][2] = 2
    staticProbs[2][1] = 2

    # The central cell appears in 4 winning sets
    staticProbs[1][1] = 4

    # We will then scale these by the total number of cells used in all possible winning combinations
    for row in range(3):
        for col in range(3):
            staticProbs[row][col] = staticProbs[row][col] / 24

    # Now turn these into a cumulative probability.
    for row in range(3):
        for col in range(3):
            if (row == 0 and col == 0):
                staticProbs[row][col] = staticProbs[row][col] + 0
            elif (col == 0):
                staticProbs[row][col] = staticProbs[row][col] + staticProbs[row - 1][2]
            else:
                staticProbs[row][col] = staticProbs[row][col] + staticProbs[row][col - 1]

generateStaticProbabilities()    

def getProbabilityCell(board, probabilities):
    valid = False
    while (valid == False):
        cell = random()
        for row in range(3):
            for col in range(3):
                if (probabilities[row][col] > cell and board[row][col] == " "): 
                    return row, col 

    return -1, -1

def makeMove(board, Me, Enemy, strategy):
  if (strategy == "Random"):
    row, col = getRandomCell(board)
  elif (strategy == "WinRandom"):
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1):
      # If no winning move is found, then we will select a random cell
      row, col = getRandomCell(board)
  elif (strategy == "WinBlockRandom"):
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1):
      # If no winning move is found, then check if we need to block our opponent
      # We can check for a winning move 'pretending' that we are the enemy player to see if we need to block
      row, col = checkWinningCell(board, Enemy, Me)
      if (row == -1):
        row, col = getRandomCell(board)
  elif (strategy == "StaticProbability"):
    # We will first check winning/blocking moves as above
    # If these aren't suffice to select a cell we will use a probability

    # Check to see if we have a winning move
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1): 
      # We can check for a winning move 'pretending' that we are the enemy player to see if we need to block
      row, col = checkWinningCell(board, Enemy, Me,) 
    
    if (row == -1):
      row, col = getProbabilityCell(board, staticProbs)

  board[row][col] = Me


strategies = ["Random", "WinRandom", "WinBlockRandom", "StaticProbability"]
tableheader = ["P1 / D / P2", "Random", "WinRandom", "WinBlockRandom", "StaticProbability"]
record = [["" for x in range(len(strategies))] for y in range(len(strategies))]

loopGames(1000)

It appears that this is a small improvement over the previous strategies:

+-------------------+-----------------+-----------------+-----------------+-------------------+
|    P1 / D / P2    |      Random     |    WinRandom    |  WinBlockRandom | StaticProbability |
+-------------------+-----------------+-----------------+-----------------+-------------------+
|       Random      | 563 / 136 / 301 | 377 / 080 / 543 | 057 / 241 / 702 |  063 / 221 / 716  |
|     WinRandom     | 838 / 063 / 099 | 683 / 045 / 272 | 151 / 200 / 649 |  137 / 192 / 671  |
|   WinBlockRandom  | 899 / 089 / 012 | 876 / 090 / 034 | 302 / 523 / 175 |  285 / 541 / 174  |
| StaticProbability | 900 / 088 / 012 | 900 / 083 / 017 | 328 / 525 / 147 |  304 / 544 / 152  |
+-------------------+-----------------+-----------------+-----------------+-------------------+

Making Dynamic Selections Link to heading

However, this is still a relatively ‘simple’ approach to assigning a probability to each place. It is clear that in the following position, moving in the top centre will not help X win the game as it can’t contribute to a winning combination of counters:

   |   | O
-----------
   |   | X
-----------
 X | O | O

In the current method, there will still be a chance that player X will choose that place for their counter. We can improve our probability based strategy further by updating them on each move, depending on the current state of the board.

dynamicProbs = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

def generateDynamicProbabilities(board, Me, Enemy):
    # Here we want to account for certain cells being taken already, denying a potential winning combination
    # Check each winning combination for an enemy counter

    TotalWinningCells = 0

    # This will check each row
    for row in range(3):
        enemyCounters = [board[row][0], board[row][1], board[row][2]].count(Enemy)
        if (enemyCounters == 0):
            TotalWinningCells = TotalWinningCells + 3
            for col in range(3):
                dynamicProbs[row][col] = dynamicProbs[row][col] + 1

    # This will check each column
    for col in range(3):
        enemyCounters = [board[0][col], board[1][col], board[2][col]].count(Enemy)
        if (enemyCounters == 0):
            TotalWinningCells = TotalWinningCells + 3
            for row in range(3):
                dynamicProbs[row][col] = dynamicProbs[row][col] + 1

    # Now check the two diagonals
    enemyCounters = [board[0][0], board[1][1], board[2][2]].count(Enemy)
    if (enemyCounters == 0):
        TotalWinningCells = TotalWinningCells + 3
        for row in range(3):
            dynamicProbs[row][row] = dynamicProbs[row][row] + 1

    enemyCounters = [board[0][2], board[1][1], board[2][0]].count(Enemy)
    if (enemyCounters == 0):
        TotalWinningCells = TotalWinningCells + 3
        for row in range(3):
            dynamicProbs[row][2 - row] = dynamicProbs[row][2 - row] + 1


    for row in range(3):
        for col in range(3):
            if (TotalWinningCells > 0): dynamicProbs[row][col] = dynamicProbs[row][col] / TotalWinningCells

    for row in range(3):
        for col in range(3):
            if (row == 0 and col == 0):
                dynamicProbs[row][col] = dynamicProbs[row][col] + 0
            elif (col == 0):
                dynamicProbs[row][col] = dynamicProbs[row][col] + dynamicProbs[row - 1][2]
            else:
                dynamicProbs[row][col] = dynamicProbs[row][col] + dynamicProbs[row][col - 1]


def makeMove(board, Me, Enemy, strategy):
  if (strategy == "Random"):
    row, col = getRandomCell(board)
  elif (strategy == "WinRandom"):
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1):
      # If no winning move is found, then we will select a random cell
      row, col = getRandomCell(board)
  elif (strategy == "WinBlockRandom"):
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1):
      # If no winning move is found, then check if we need to block our opponent
      # We can check for a winning move 'pretending' that we are the enemy player to see if we need to block
      row, col = checkWinningCell(board, Enemy, Me)
      if (row == -1):
        row, col = getRandomCell(board)
  elif (strategy == "StaticProbability"):
    # We will first check winning/blocking moves as above
    # If these aren't suffice to select a cell we will use a probability

    # Check to see if we have a winning move
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1): 
      # We can check for a winning move 'pretending' that we are the enemy player to see if we need to block
      row, col = checkWinningCell(board, Enemy, Me,) 
    
    if (row == -1):
      row, col = getProbabilityCell(board, staticProbs)
  elif (strategy == "DynamicProbability"):
    # We will first check winning/blocking moves as above
    # If these aren't suffice to select a cell we will use a probability
    # This time we will update the probabilities each move, depending on the state of the board


    # Check to see if we have a winning move
    row, col = checkWinningCell(board, Me, Enemy)
    if (row == -1): 
      # We can check for a winning move 'pretending' that we are the enemy player to see if we need to block
      row, col = checkWinningCell(board, Enemy, Me,) 
    
    if (row == -1):
      generateDynamicProbabilities(board, Me, Enemy)
      row, col = getProbabilityCell(board, dynamicProbs)
  board[row][col] = Me

strategies = ["Random", "WinRandom", "WinBlockRandom", "StaticProbability", "DynamicProbability"]
tableheader = ["P1 / D / P2", "Random", "WinRandom", "WinBlockRandom", "StaticProbability", "DynamicProbability"]
record = [["" for x in range(len(strategies))] for y in range(len(strategies))]
loopGames(1000)

In our example above, the computer would now have a 25% chance of placing their counter in the top left or centre places and a 50% chance of picking the left middle place. Adding this to our list of strategies again appears to show this being an improvement:

+--------------------+-----------------+-----------------+-----------------+-------------------+--------------------+
|    P1 / D / P2     |      Random     |    WinRandom    |  WinBlockRandom | StaticProbability | DynamicProbability |
+--------------------+-----------------+-----------------+-----------------+-------------------+--------------------+
|       Random       | 592 / 133 / 275 | 386 / 089 / 525 | 067 / 262 / 671 |  043 / 248 / 709  |  053 / 193 / 754   |
|     WinRandom      | 818 / 068 / 114 | 705 / 047 / 248 | 114 / 206 / 680 |  117 / 193 / 690  |  132 / 138 / 730   |
|   WinBlockRandom   | 880 / 103 / 017 | 892 / 085 / 023 | 315 / 500 / 185 |  311 / 515 / 174  |  295 / 536 / 169   |
| StaticProbability  | 908 / 078 / 014 | 895 / 083 / 022 | 318 / 528 / 154 |  319 / 550 / 131  |  306 / 562 / 132   |
| DynamicProbability | 918 / 072 / 010 | 916 / 065 / 019 | 327 / 526 / 147 |  326 / 524 / 150  |  300 / 541 / 159   |
+--------------------+-----------------+-----------------+-----------------+-------------------+--------------------+

Overall Performance Link to heading

Generally speaking we can see a few patterns in our results:

  • Each strategy improves on its predecessors
  • Once a player starts to block possible winning moves a draw is the most common result
  • There is possible a small advantage to going first in the game

Noughts and Crosses is a ‘solved’ game, that is that we know what the outcome will be with perfect play from both players - a draw. While that is the dominant result in our testing, each player is still getting a not insignificant number of wins. Can we improve upon our strategies further to get to ‘perfect’ play?