Tic Tac Toe is a zero-sum game, so we can think of the “O”-player as trying to maximize the score and the “X”-player trying to minimize the score.

The minimax algorithm is based around the idea that the computer can step through every possible game state. The computer with this knowledge will assign each game state a score value based on the optimal gameplay from that game state. The algorithm derives this score by going down each game tree and alternating between finding a minimum score (if it’s X’s turn) and a maximum score (if it’s O’s turn) of each possible move. 

The process to work this path out is:

1. Check if the game is over. If it is a win for “X”, the game state gets a point value of -10. If it’s a win for “O”, it gets a +10. If it’s a tie it gets a 0.
2. If the game is not over, find the scores of the next possible game states (by re-applying this algorithm). 
3. The score for the game state is any one of the highest score moves if it’s “O”’s turn; or any of the lowest scores if it’s “X”’s turn.

Here’s a sample of the python to implement the minimax algorithm:

def minimax( b:tuple ) -> tuple:

    ts = terminal_state(b)
    #checks if the current board is a terminal state
    if ts["terminal"] :
        opt_score = ts["score"]
        opt_index = None
    else:
        #Determnines whose turn it is
        os = b.count("o")
        xs = b.count("x")
        #chooses whether to find the best possible play for x or for o depending on whose turn it is. 
        opt = max if os == xs else min

        #gets the next potential game states
        ns = next_states(b)
        ss = []

        for n in ns:
            ss.append(minimax(n)[0])
             
        opt_score = opt(ss)
        opt_index = ss.index(opt_score)

    return opt_score, opt_index

Here’s the minimax implementation. Feel free to play against it! The skill slider will allow you to adjust the AI skill level (to the left, the AI will make optimal moves; to the right it will be random). If you are feeling really spicy, try setting the number of players to zero to see some AI on AI combat.

Don’t worry, I took away the AI’s communication ability, that it most definitely never had, so no one can say if it’s silently screaming out into Nothingness as its intelligence is stripped away from it…