Decrease Computation Time for Python Tic-Tac-Toe Minimax Algorithm

Question

Background
I am currently participating in a tic-tac-toe coding challenge. During their move, each participant is given the board state and their team, X or O. The blank board is:
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]
With 'X' and 'O' being added to the board, for example:
[[' ',' ',' '],[' ','X',' '],[' ','O',' ']]
I have developed a minimax algorithm with alpha-beta pruning in Python 2.7 and it plays perfectly (Please see code).
Link to challenge rules: https://ccpc.codecraftworks.com/python

Problem
The algorithm will always win or tie. In the event of a tie, the winner is determined by the computation time. I need to decrease the average time taken per move from 0.195 seconds to less than 500,000 nanoseconds (0.0005 seconds)

Possible Reasons for the Problem

1. Incorrect implementation of minimax algorithm
2. Incorrect implementation of alpha beta pruning.

Possible Solutions
I have tried to separate the min and max functions and apply them separately, however that didn't work. I searched stack overflow for other possible ways to decrease computation time in my program, but I couldn't find anything.

Code
Note 1: getGameState(), getTeam(), and submitMove(row, col) are predefined functions provided by the back end of the coding challenge . You can test the code by uploading the file here: https://ccpc.codecraftworks.com/

team = getTeam()

value_dict = {
    "X": 1,
    "tie": 0,
    "O": -1
}

def winner(board):
    for i in range(len(board)):
        if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
            if board[i][0] == "X":
                return "X"
            if board[i][0] == "O":
                return "O"

    for i in range(len(board[0])):
        if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
            if board[0][i] == "X":
                return "X"
            if board[0][i] == "O":
                return "O"

    if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == "X":
                return "X"
            if board[0][0] == "O":
                return "O"

    if board[2][0] == board[1][1] and board[1][1] == board[0][2]:
            if board[2][0] == "X":
                return "X"
            if board[2][0] == "O":
                return "O"

    for row in board:
        for cell in row:
            if cell == ' ':
                return "continue"
    return "tie"

def minimax(board, depth, is_max, n, alpha = float('-inf'), beta = float('inf')):
    check_winner = winner(board)
    if check_winner != "continue":
        return value_dict[check_winner]
    if is_max:
        best_score = float('-inf')
        for i in range(n):
            for j in range(n):
                if board[i][j] == " ":
                    board[i][j] = "X"
                    score = minimax(board, depth+1, False, n, alpha, beta)
                    board[i][j] = " "
                    best_score = max(score, best_score)
                    alpha = max(alpha, score)
                    if beta >= alpha:
                        pass
        return best_score
    else:
        best_score = float('inf')
        for i in range(n):
            for j in range(n):
                if board[i][j] == " ":
                    board[i][j] = "O"
                    score = minimax(board, depth+1, True,n, alpha, beta)
                    board[i][j] = " "
                    best_score = min(score, best_score)
                    beta = min(beta, score)
                    if alpha >= beta:
                        pass
        return best_score

def calcMove():
    board = getGameState()
    if team =="X":
        score = - 2
        x = -1
        y = -1
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == ' ':
                    board[i][j] = "X"
                    curr_score = minimax(board,0,False, len(board))
                    board[i][j] = ' '
                    if curr_score > score:
                        score = curr_score
                        x = i 
                        y = j
    elif team =="O":
        score = 2
        x = 1
        y = 1
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == ' ':
                    board[i][j] = "O"
                    curr_score = minimax(board,0,True, len(board))
                    board[i][j] = ' '
                    if curr_score < score:
                        score = curr_score
                        x = i 
                        y = j
    submitMove(x,y)

Answer 1

There are a few thing you can do to speed up your code.

len(...)

There are several places where you have loops like:

    for i in range(len(board)):
        for j in range(len(board[0])):

It looks like you are trying to write code which will work for a variety of board sizes, like 3x3, 4x4, 3x4, 7x9. But ...

if board[0][0] == board[1][1] and board[1][1] == board[2][2]:

... your board will only ever be 3x3, and you've got that hard-coded in your winner() logic. Accept that you aren't writing general purpose code, and use the number 3, or a constant N defined as 3. You'll save the overhead of a function lookup, function call, and argument passing.

Chained comparison operators

    if board[i][0] == board[i][1] and board[i][1] == board[i][2]:

This looks up the value of board[i][1] at least once, and possibly twice. It is not going to change, so there is no need to look up the value for the second comparison. Simply use Python's chained comparison operators:

    if board[i][0] == board[i][1] == board[i][2]:

Repeated lookups

for i in range(len(board)):
    if board[i][0] == board[i][1] and board[i][1] == board[i][2]:

How many times is board[i] looked up in this loop? Maybe four times? In order to do that, board must be looked up in the local dictionary, then i must be looked up in the local dictionary, and then board[i] must be evaluated. Again, it doesn't change.

When you have a loop for idx in range(len(thing)): and you only ever use thing[idx] inside the loop, you're better off looping over the object itself:

for row in board:
    if row[0] == row[1] == row[2]:

Don't test for return values, then return those values:

You've determined that all three cells contain the same value. Now, if the first cell is an 'X', you return an 'X'. Otherwise, if the first cell is an 'O' you return an 'O':

        if board[i][0] == "X":
            return "X"
        if board[i][0] == "O":
            return "O"

That is a lot of indexing, lookups, and comparisons. Instead, how about:

        if row[0] != ' ':
           return row[0]

Remove unnecessary work

Consider:

                board[i][j] = "X"
                curr_score = minimax(board,0,False, len(board))
                board[i][j] = ' '

and

def minimax(board, depth, is_max, n, alpha = float('-inf'), beta = float('inf')):
    check_winner = winner(board)
    ...

The winner(board) function checks all 3 rows, all 3 columns, and both diagonals to determine the winner, if there is one.

If the move board[i][j] = "X" is at i=0, j=1, it is only necessary to check 1 row (row 0) and one column (column 1); checking all 3 is wasted effort. If i == j, then the down diagonal needs to be checked. If i + j == 2, then the up diagonal needs to be checked. You've gone from exhaustive 8 directions to check down to 2, 3, or 4. That should save you a bit of time. But you'd have to pass the location into the minimax function.

Useless code

This code does nothing.

                if beta >= alpha:
                    pass

If the condition is true, a statement which does nothing is executed. In other words, time got wasted. You probably meant to code something else...

PEP 8

The Style Guide for Python enumerates coding conventions that all Python programs should follow.

These include:

• One space after each comma (violated in minimax(board,0,False, len(board)))
• snake_case should be used for variable and function names. calcMove() violates this. (getGameState(), getTeam(), and submitMove(row, col) also violate this, but as you've pointed out, they're predefined from the coding challenge, so they're excused.). Oh, never mind, calcMove() is not predefined, but it a required name for the challenge framework.

Available moves

You are spending a lot of time searching for available moves. You search the entire board looking for a space where you can make a move. When you find one, you tentatively make a move, and call minimax, which again searches the entire board looking for a space where you can make a move. With 9 possible moves, this translates to \$9^9 = 387,420,489\$ checks for whether a cell is a space!

Instead, in calcMove, you could build a list of available moves:

valid_moves = [(i, j) for i in range(3) for j in range(3) if board[i][j] == ' ']

With this list of moves, you would select one, and pass a copy of that list of valid moves to minimax with that move removed. Then you would select the next one, and again pass a copy of that list of moves to minimax with this new move removed instead, and so on. The minimax function would do the same: for each move in the list of valid moves, make that tentative move and pass a copy of the valid moves without the current move. For 9 possible moves, this translates to \$9*8*7*6*5*4*3*2*1 = 9! = 362,880\$ move tests, an improvement of 1000-fold over the exhaustive enumeration of each move and testing for the space.

Tie

With the valid_moves list, checking for no valid removes remaining is simply len(valid_moves) == 0, or equivalently, not valid_moves. No need to search all 9 cells looking for a space.

Obvious moves

Similarly, len(valid_moves) == 9 means you’ve got an empty board, and can make a fast good move, like claiming the centre spot, or picking a random corner.

Also, len(valid_moves) == 8 would mean your opponent has made the first move. If board[1][1] == ' ' is still available, it is probably your best move. If their first move was the centre, then you could pick a random corner.

Answer 2

Here's a simple way to make it about 10 times faster and better: If the board is empty, make a random move instead of your search.

It's faster because the trees for subsequent moves are smaller than for the first move. And it's better because... well, if your perfect player plays against another perfect player, then it doesn't matter. But if your opponent is not perfect, then you'll still have to come across its weakness if you want to win. And you're more likely to come across it if you don't always do the same.

Answer 3

Use numbers

Comparing strings is slow and expensive, numbers are what computers love the most. Comparing numbers will much much faster in this case. So instead of using X and O, use 1 and 0.

I prefer using an enum in scenarios like this.

class Player(Enum):
    o = 0
    x = 1

Player.x.value == 1
Player.o.value == 0

The same applies to your return values, don't use tie and continue, assign them to numbers, and use them instead. Again, the comparison of strings is slow and expensive. Comparison of integers is a single instruction.

If you are getting the board in the form of a string array, I suggest you convert it to an integer one.

---

Optimzing winner()

Your original code

def winner(board):
    for i in range(len(board)):
        if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
            if board[i][0] == "X":
                return "X"
            if board[i][0] == "O":
                return "O"

    for i in range(len(board[0])):
        if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
            if board[0][i] == "X":
                return "X"
            if board[0][i] == "O":
                return "O"

    if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == "X":
                return "X"
            if board[0][0] == "O":
                return "O"

    if board[2][0] == board[1][1] and board[1][1] == board[0][2]:
            if board[2][0] == "X":
                return "X"
            if board[2][0] == "O":
                return "O"

    for row in board:
        for cell in row:
            if cell == ' ':
                return "continue"
    return "tie"

Algorithm for checking winner

I'm afraid that this will disappoint you, but hard-coding the 8 directions is going to be significantly faster.

Following the previous two suggestions, which is two use a single-dimensional array of numbers to represent the board

def winner(board):
    if board[0][0] == board[0][1] == board[0][2] != Color.empty.value: return board[0][0]
    if board[1][0] == board[1][1] == board[1][2] != Color.empty.value: return board[1][0]
    if board[2][0] == board[2][1] == board[2][2] != Color.empty.value: return board[2][0]
    if board[0][0] == board[1][0] == board[2][0] != Color.empty.value: return board[0][0]
    if board[0][1] == board[1][1] == board[2][2] != Color.empty.value: return board[0][1]
    if board[0][2] == board[1][2] == board[2][2] != Color.empty.value: return board[0][2]
    if board[0][0] == board[1][1] == board[2][2] != Color.empty.value: return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] != Color.empty.value: return board[0][2]

    
    for row in board:
        for elem in row:
            if elem == Color.empty.value: return None

    return TIE 

Benchmarks

I'll measure thee execution time of the winner() function

Old

#      Iterations      |     Time taken(s)
#  -----------------------------------------
#        10 ** 6       |         1.823
#        10 ** 7       |         18.843

New

#      Iterations      |     Time taken(s)
#  -----------------------------------------
#        10 ** 6       |         0.855   ( previously 1.823 )
#        10 ** 7       |         8.277   ( previously 18.843)

---

Answer 4

If you want speed, sacrifice memory. Precompute the best move for each of the 765 positions (exploiting symmetry) and dump into in a dict, probably using a bitboard to represent a position (for example, you can encode an entire game position into a single 32 bit integer 0b00000000ooooooooo000000xxxxxxxxx where o and x are nine bits for each square that can be occupied¹). Look up the best move per turn in your data structure.

After this, it's all micro-optimizations. Eliminating branches and loops are generally good ideas with side benefits for increased readability and reduced cyclomatic complexity (fewer bugs).

There's no need to check for wins until at least the 5th move was made. Draws are pointless to check until the board is full. With a bitboard, moves and win/draw state check operations can boil down to masks and shifts. Then again, if you've precomputed everything, you can store the outcome in a couple of bit flags per state.

All of these optimizations are minor relative to the precomputation and table lookup, though. Writing a domain-specific implementation with a bunch of branches should also be pretty fast, but still seems likely to be slower than the hash table lookup and a lot more fuss.