Recursive Tic-Tac-Toe Solver in Python

Question

I'm implementing a Tic-Tac-Toe solver in Python. It contains two functions: assess to determine whether a given board position is a win for either side, and is_winner to traverse the game tree.

The end goal is to use this program to construct a lookup table that will be used by a JavaScript Tic-Tac-Toe frontend. But I want this to be a well-documented, freestanding piece of code.

• Are the tests comprehensive and self-documenting?
• Is the use of Enum warranted and well implemented?
• Do the docstrings make the functions' API clear? Is it a good idea to use None in a non-exceptional case, as I do in assess?
• I agonized for a long time about this, but in the first part of is_winner I call assess three times instead of saving the result. I thought it would be more clear -- is it?
• When making a move I need to convert the board string to a list, mutate it, and reconvert to a string to recurse on. I do this because most of the time it seems to me convenient to have board as a string, but now I'm questioning that decision.
• (Least importantly) Any optimizations that could be made? Right now the code takes a noticeable amount of time to determine that the game is a draw (starting from an empty board).

import unittest
import enum
import random

class Result(enum.Enum):
    lose = -1
    draw = 0
    win = 1

def assess(board):
    """
    Takes: a board string.
    Returns: 'x' or 'o' if either of them win, '?' for draw, else None.
    """

    # Draw? (no spaces left?)
    if '-' not in board:
        return '?'

    for sym in 'x', 'o':
        winning_three = [sym] * 3

        # Vertical win?
        if winning_three in (
            [board[0], board[3], board[6]],
            [board[1], board[4], board[7]],
            [board[2], board[5], board[8]],
            ): return sym

        # Vertical win?
        if winning_three in (
            [board[0], board[1], board[2]],
            [board[3], board[4], board[5]],
            [board[6], board[7], board[8]],
            ): return sym

        # Diagonal win?
        if winning_three in (
            [board[0], board[4], board[8]],
            [board[2], board[4], board[6]]
            ): return sym

def random_move(board):
    """
    Takes: a board string.
    Returns: the index (0 - 8) of a random unoccupied space.
    """

    return random.choice([i for i, char in enumerate(board) if char == '-'])

def is_winner(board, sym):
    """
    Takes: a board string, the symbol which is to move.
    Returns: win, lose or draw (assuming both sides play optimally).
    """

    # If it's a win/lose/draw right away, report the result (no move).
    if assess(board) is not None:
        if assess(board) == sym:
            return Result.win, -1
        elif assess(board) == '?':
            return Result.draw, -1
        else:
            return Result.lose, -1

    # Otherwise, we check all the available moves.
    drawing_moves = []

    for i, char in enumerate(board):
        # Check if the spot is full.
        if char != '-': continue

        # Make the move.
        next_board = list(board)
        next_board[i] = sym
        next_board = "".join(next_board)

        # Determine the next symbol to play.
        next_sym = 'x' if sym == 'o' else 'o'

        opponent_outcome, _ = is_winner(next_board, next_sym)
        # If we can force a loss, that means we can win.
        if opponent_outcome == Result.lose:
            return Result.win, i
        elif opponent_outcome == Result.draw:
            drawing_moves.append(i)

    # Otherwise, use one of our moves that can draw (if we found any).
    if drawing_moves:
        return Result.draw, drawing_moves.pop()

    # If not, we lose, so move randomly.
    return Result.lose, random_move(board)

And here are the tests:

class TestMoveFinding(unittest.TestCase):
    def test_shallow(self):
        board = ["xx-",
                 "---",
                 "o-x"]

        result, move = is_winner("".join(board), 'x')
        self.assertEqual(2, move)
        self.assertEqual(Result.win, result)

        board = ["x--",
                 "-x-",
                 "oo-"]

        result, move = is_winner("".join(board), 'o')
        self.assertEqual(8, move)
        self.assertEqual(Result.win, result)

    def test_deep(self):
        board = ["--o",
                 "-xo",
                 "x--"]

        result, move = is_winner("".join(board), 'x')
        self.assertEqual(move, 8)
        self.assertEqual(Result.win, result)

        board = ["--o",
                 "-x-",
                 "---"]

        result, move = is_winner("".join(board), 'x')
        self.assertEqual(Result.draw, result)

        board = ["---",
                 "-x-",
                 "---"]

        result, move = is_winner("".join(board), 'o')
        self.assertEqual(Result.draw, result)

class TestBoardAssessment(unittest.TestCase):
    def test_horizontal(self):
        board = ["???",
                 "--o",
                 "o-x"]

        for sym in 'x', 'o':
            self.assertEqual(sym, assess("".join(board).replace('?', sym)))

    def test_vertical(self):
        board = ["?-x",
                 "?ox",
                 "?--"]

        for sym in 'x', 'o':
            self.assertEqual(sym, assess("".join(board).replace('?', sym)))

    def test_diagonal(self):
        board = ["?-x",
                 "o?-",
                 "--?"]

        for sym in 'x', 'o':
            self.assertEqual(sym, assess("".join(board).replace('?', sym)))

if __name__ == "__main__":
    unittest.main()

Answer 1

Overall I think this is good.

Some issues:

1. assess will return ? even if someone wins on the last move. You should do the empty check after you check for any wins.
2. Your comments in asses has # Vertical win? twice. The second should be # Horizontal win?

And some suggestions:

1. There is no reason to keep track of all moves that result in a draw, you only ever use one so it is better to just keep the first.
2. It is considered bad style to have one-line code blocks, such as one-line if tests or for loops (ignoring ternary expressions and list comprehensions, of course). For things like if tests and for loops, put the for or if on one line and the stuff after the : on the next line.
3. You convert back and forth between a str and list a lot, but you never use any string features. I think it would be better to just keep it a list all the time. This will also improve performance. This would also allow you to use slices for the wins.
4. You only need to asses the player that moved last, so you can specify a player in assess and just test that one.
5. I would do if assess(board) is None: pass (on separate lines) so you can reduce the nesting level.
6. I would split the winning test portion of is_winner into a separate function and have the recursive portion call that function. And again, you only need to check the player who moved last.
7. An enum is valid in this case, but it seems a bit overkill. Everywhere else you use strings, so I would do the same.
8. I would use a dict to handle the result of assess in is_winner.
9. I would have just one big win list, rather than three.