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 &gt;= 0 and location &lt; 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 &gt;= 0 and location &lt; 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 &lt;= location &lt; 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 = "."