minimax

An algorithm for playing zero sum games with alternating moves, such as chess, checkers, and tic-tac-toe. It's based on the assumption that each position in the game has a value, and that your opponent is trying to minimize these values while you're trying to maximize them.

The idea is to look ahead at your possible moves, the possible responses by your opponent to those moves, your responses to your opponent's responses, etc., until you reach some limit. This forms a tree, where the current position is the root and the terminal positions are the leaves. The limit might be a predefined depth (such as "I'll always look four moves deep") or be determined dynamically, based on the situation (such as "I'll look ahead until the situation seems stable").

At that point, a score (value) is assigned to the position. A positive score is good for you; a negative score is good for your opponent. The minimax algorithm propagates the scores of final positions (i.e., leaf nodes to earlier positions by assuming that your opponent will select moves that minimize the score and that you will make moves that maximize the score. So, scores from "deep" moves propagate their way upwards and the path from the root to the best move is the optimal sequence of moves.

minimax(input board, output actual_score, output actual_move)

        best_score = -infinity;

        for each possible move (call it current_move): 
            copy board into temp_board
            simulate current_move on temp_board
            //recursively find each subsequent 'best move'
            minimax(board, the_score,the_move)
            if the_score is greater than best_score
                best_score = the_score
                best_move = current_move
            end if
         end for

         actual_move = best_move
         if there are no possible moves (leaf node)
            actual_score = evaluated value of board
         end if
         else
            actual_score = best_score
         end else
end function