Tic-Tac-Toe Recursive Solver

Question

I am attempting to create a Tic-Tac-Toe game that uses a recursively checks every possible game board, and finds which boards result in a victory for X. (I ultimately plan to turn this into an AI which implements a minimax algorithm to play against a human player.) I am running into issues with the time efficiency of my code.

import time

X, O, NONE = ("X", "O", ".")


class Board():
    def __init__(self):
        self.board_length = 9;
        self.squares = [NONE for idx in range(self.board_length)]
        self.winning_combinations = [
            [0,1,2], [3,4,5], [6,7,8],
            [0,3,6], [1,4,7], [2,5,8],
            [0,4,8], [2,4,6]]

    def __str__(self):
        return  ("-------------\n| {} | {} | {} |\n" * 3 + "-------------").format(*self.squares)

    def make_move(self, location, player):
        if self.is_valid_move(location):
            self.squares[location] = player
            return True
        return False

    def undo_move(self, location):
        if self.is_valid_location(location):
            self.squares[location] = NONE
            return True
        return False

    def is_valid_move(self, location):
        return self.is_valid_location(location) and self.squares[location] == NONE

    def is_valid_location(self, location):
        return location >= 0 and location < self.board_length

    def get_winner(self):
        for player in (X, O):
            for combo in self.winning_combinations:
                if self.squares[combo[0]] == player and self.squares[combo[1]] == player and self.squares[combo[2]] == player:
                    return player
        return NONE

    def get_moves(self):
        return filter(self.is_valid_move, range(9))

iters = 0
def find_winners(board, depth=0, player=X):
    global iters
    iters += 1
    for move in board.get_moves():
        board.make_move(move, player)
        if board.get_winner() == X:
            #print(board)
            _ = 1
        else:
            find_winners(board, depth + 1, O if player == X else X)
        board.undo_move(move)

if __name__ == "__main__":
    start = time.time()
    find_winners(Board())
    print("Took: {time:.4f} seconds to execute {iters} times.".format(time=(time.time() - start), iters=iters))

When I run this code, I get an output of: Took: 8.4968 seconds to execute 986410 times.

Considering my code is only executing ~1m times, a time of almost 10 seconds to execute seems rather extreme. I can't find anything in my code that would particularly lead to this slowdown, or much that I can do to improve the efficiency of my code.

Any and all advice, on the efficiency of my code, or on my coding style in general, would be much appreciated.

Answer 1

Some remarks:

def is_valid_location(self, location):
    return location >= 0 and location < self.board_length

In contrast to many other programming languages, this can be expressed in Python more succinctly as a chained comparison:

def is_valid_location(self, location):
    return 0 <= location < self.board_length

However, that function seems unnecessary to me, since nowhere in your program an invalid location is created.

---

The winning combinations are not dependent on the particular instance of a board, it is more logical to define them as a class variable:

class Board():
    winning_combinations = [
            [0,1,2], [3,4,5], [6,7,8],
            [0,3,6], [1,4,7], [2,5,8],
            [0,4,8], [2,4,6]]

    def __init__(self):
        self.board_length = 9;
        self.squares = [NONE for idx in range(self.board_length)]

    // ...

---

The efficiency of the get_winner function can be improved. It is not necessary to check both players against each winning combination:

def get_winner(self):
    for combo in self.winning_combinations:
        player = self.squares[combo[0]]
        if player is not None and self.squares[combo[1]] == player and self.squares[combo[2]] == player:
            return player
    return NONE

---

The only purpose of _ = 1 in

    if board.get_winner() == X:
        #print(board)
        _ = 1
    else:
        find_winners(board, depth + 1, O if player == X else X)

seems to be to avoid an empty if-block. Python has a pass statement for that purpose:

    if board.get_winner() == X:
        #print(board)
        pass
    else:
        find_winners(board, depth + 1, O if player == X else X)

---

You define three variables

X, O, NONE = ("X", "O", ".")

for the possible states of a cell. A better way to express mutually exclusive values is an enumeration:

from enum import Enum

class Cell(Enum):
    X = "X"
    O = "O"
    empty = "."

Answer 2

A few things before we get to the efficiency part of the program.

1. When I copied your code and ran on my laptop, I got

   "Took: 7.3347 seconds to execute 489610 times."

   instead of 986410 times.

2. I think in your find_winners function you have a bug that prevents the game from stopping when play O wins.

   for move in board.get_moves():
       board.make_move(move, player)
       if board.get_winner() == player # should check against the current move first
           if player == O:
               # player X loses. The game stops here
               # do you logging             
           elif player == X:
               # print(board)
               _ = 1
       else:
           find_winners(board, depth+1, O if player == X else X)
       board.undo_move(move)
   

   After this fix, the program stops after 7.1500 seconds with 340858 executions.

---

In terms of efficiency, in get_winner function you tested against all possible winning positions for both X and O players. And during your recursive calls to get_winner within find_winners function, the same test is done over and over again. Before you actually have a winner of the game, you always end up testing against all the possible winning positions. In fact you could keep such information as internal state of your board class to save you some time.

Say you assign +1 to X, -1 to O and 0 to . on the board. You can track the score for each row, each column and two diagonals. If any of these scores is 3 or -3 you know you have a winner.

Add the following states to the __init__ function:

self.col_score = [0, 0, 0]
self.row_score = [0, 0, 0]
# left diag goes as 0, 4, 8, and right diag goes as 2, 4, 6
self.left_diag, self.right_diag = 0, 0

Add a utility member function to handle score update:

def update_score(self, location, make_move=True):
    if self.squares[location] == X: 
        score = 1
    elif self.squares[location] == O: 
        score = -1
    else: 
        return
    score *= (1 if make_move else -1)
    i, j = divmod(location, 3)
    self.row_score[i] += score
    self.col_score[j] += score
    if i == j: self.left_diag += score
    if i+j == 2: self.right_diag += score

And then your make_move and undo_move functions will have to call this function to make updates to the states:

def make_move(self, location, player):
    if self.is_valid_move(location):
        self.squares[location] = player
        self.update_score(location, True)
        return True
    return False

def undo_move(self, location):
    if self.is_valid_location(location):
        self.update_score(location, False)
        self.squares[location] = NONE
        return True
    return False

And to test if we have a winner, use the following:

def get_winner(self):
    if 3 in self.col_score: return X
    elif -3 in self.col_score: return O
    if 3 in self.row_score: return X
    elif -3 in self.row_score: return O
    if self.left_diag == 3: return X
    elif self.left_diag == -3: return O
    if self.right_diag == 3: return X
    elif self.right_diag == -3: return O
    return NONE

There are probably further enhancements you could make to the code I proposed here, but with these changes alone, it finishes in 5.2833 seconds; that is about 2 seconds improvement from 7.15 seconds (with the bug fix).