Aritifical Intelligence

Example

Project: Using minimax, make a tic-tac-toe game with an unbeatable computer opponent.

What is Minimax?

For two-player games, minimax is an algorithm that attempts to choose the best possible move for any given game state. It does this by assigning a score to every possible move, and then choosing the move with the best score. The score is determined by recursively looking multiple moves ahead.

Illustration

minimax illustration

Pseudocode

function score(move, computerTurn):
    if game is over:
        return score of game state
    else:
        if computerTurn:
            bestScore = Infinity

            for each possible next move:
                score = score(nextMove, false)
                bestScore = min(score, bestScore)

            return bestScore
        else:
            bestScore = -Infinity

            for each possible next move:
                score = score(nextMove, true)
                bestScore = max(score, bestScore)

            return bestScore
Last topic Next topic