# Tic-Tac-Toe Recursive Solver

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.

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 = "."


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."

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