tic-tac-toe.py

def wins(player, A):
    for case in [[0, 1, 2],
                [3, 4, 5],
                [6, 7, 8],
                [0, 3, 6],   
                [1, 4, 7],
                [2, 5, 8],
                [0, 4, 8],
                [2, 4, 6]]:
        
        if A[case[0]] == player and A[case[1]] == player and A[case[2]] == player:
            return True
        
    return False


def game_over(A):
    return wins(USER, A) or wins(MACHINE, A)

def empty_cell(A):
    empty_index = []
    for i in range(9):
        if A[i] == None:
            empty_index.append(i)
    return empty_index

def valid_move(cell, A):
    if cell in empty_cell(A):
        return True
    else: return False

def reverse(player):
    if player == USER: return MACHINE
    else: return USER
    

def playgame(player, A, remains):
    """
    ARGs:
         player: the one playing, MACHINE or USER.
              A: the board.
        remains: the number of empty cells,
                 which is the number of states we can get from the current state.
    
    RETURN:
          tick_cell: tick position. Negative position means not able to tick.
              score: the bigger the better for MACHINE, and worse for USER. best is larger
                     the smaller the better for USER, and worse for MACHINE. best is smaller
    """
    
    if remains == 0 or game_over(A):
        if wins(MACHINE, A): return (-1, +99)
        elif wins(USER, A):  return (-1, -99)
        else: return (-1, 0)
    
    if player is MACHINE:
        best = -99
    else:
        best = +99

    tick_cell = -1
    
    for cell in empty_cell(A):
        A[cell] = player    # tick a empty cell (fake move)
        # Get opponent's status if we made that fake move
        tick, score = playgame(reverse(player), A, remains-1)
        A[cell] = None      # then erase the tick
        
        if player is MACHINE:  # maximize score -> put user into bad situation
            if score > best:
                best = score
                tick_cell = cell
        else:
            if score < best:   # minimize score -> put machine into bad situation
                best = score            
                tick_cell = cell

    return (tick_cell, best)