Calculate all possible endgame states in game Tic-Tac-Toe

tic-tac-toe.py

'''
Tic Tac Toe Endstate Calculation

Assumption: X always moves first.
Including all symmetric or rotate situations.
Using 1D list to represent board, 1 as X, -1 as O, 0 as blank.
'''


def check(board):
    '''
    Check whether a board is a win state
    '''
    
    for indices in end_indices:
        if abs(sum(board[idx] for idx in indices)) == 3:
            return True
        
            
def move(board, turn, blank, board_pool):
    '''
    Loop through all starting positions and using recursion to alternate players to move
    forward, until a board is either visited, win or tie.
    '''
    
    board_str = str(board)
    if board_str in board_pool:
        return 0
    
    if blank == 0 or check(board):
        board_pool.add(board_str)
        return 1
    
    result = 0
    
    # Loop through 9 positions for starting board
    for i in range(9):
        if board[i] == 0:
            board[i] = turn
        # Alter player and go into next move
            result += move(board, -1*turn, blank-1, board_pool)
            # Clear position for next starting board
            board[i] = 0
    return result
    
    
if __name__ == '__main__':
    # All possible indices for win
    end_indices = [[0,1,2], [3,4,5], [6,7,8],
                    [0,3,6], [1,4,7], [2,5,8],
                    [0,4,8], [2,4,6]]
    # Inital a board
    board = [0 for _ in range(9)]
    # All visited boards
    board_pool = set()
    print("Total endstates: {0}".format(move(board, 1, 9, board_pool)))

Result:

Total endstates: 958

Reference:

1. Quora Questions, Code
2. Mathematics Questions, Code
3. Article by Steve Shaffer on mathrec.org