display | more...

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.

Here is some psuedocode for one who wishes to implement this search strategy.

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

Log in or register to write something here or to contact authors.