Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin"—to maximize the minimum gain. Originally formulated for n-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training.
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.
Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, the programs of the era were weak. The best efforts of the 1980s produced only AIs that could be defeated by beginners, and AIs of the 1990s and early 2000s were intermediate level at best. Professionals could defeat these programs even given handicaps of 10+ stones in favor of the AI. Many of the algorithms such as alpha-beta minimax that performed well as AIs for checkers and chess fell apart on Go's 19x19 board, as there were too many branching possibilities to consider. Creation of a human professional quality program with the techniques and hardware of the time was out of reach. Some AI researchers speculated that the problem was unsolvable without creation of human-like AI.
A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position. Transposition tables are primarily useful in perfect-information games. The usage of transposition tables is essentially memoization applied to the tree search and is a form of dynamic programming.
In the context of Combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, checkers, Go, and tic-tac-toe. This can be used to measure the complexity of a game, as it represents all the possible ways a game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minimax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.
Maven is an artificial intelligence Scrabble player, created by Brian Sheppard. It has been used in official licensed Hasbro Scrabble games.
ChessV is a free computer program designed to play many chess variants. ChessV is an open-source, universal chess variant program with a graphical user-interface, sophisticated AI, support for opening books and other features of traditional chess programs. The developer of this program, Gregory Strong, has been adding more variants with each release of ChessV. Over 100 chess variants are supported, including the developer's few own variants and other exotic variants, and can be programmed to play additional variants. ChessV is designed to be able to play any game that is reasonably similar to chess. ChessV is one of only a few such programs that exist. The source code of this program is freely available for download as well as the executable program.
Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game.
Principal variation search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree. It dominates alpha-beta pruning in the sense that it will never examine a node that can be pruned by alpha-beta; however, it relies on accurate node ordering to capitalize on this advantage.
MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory-enhanced Test Driver with node ‘n’ and value ‘f’. The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess. The memory structure is used to save an initial guess determined elsewhere.
In game theory, a null move or pass is a decision by a player to not make a move when it is that player's turn to move. Even though null moves are against the rules of many games, they are often useful to consider when analyzing these games. Examples of this include the analysis of zugzwang, and the null-move heuristic in game tree analysis.
Computer bridge is the playing of the game contract bridge using computer software. After years of limited progress, since around the end of the 20th century the field of computer bridge has made major advances. In 1996 the American Contract Bridge League (ACBL) established an official World Computer-Bridge Championship, to be held annually along with a major bridge event. The first championship took place in 1997 at the North American Bridge Championships in Albuquerque. Since 1999 the event has been conducted as a joint activity of the American Contract Bridge League and the World Bridge Federation. Alvin Levy, ACBL Board member, initiated this championship and has coordinated the event annually since its inception. The event history, articles and publications, analysis, and playing records can be found at the official website.
Alexander L'vovich Brudno was a Russian computer scientist, best known for fully describing the alpha-beta pruning algorithm. From 1991 until his death he lived in Israel.
SSS* is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm.
Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It is also known as Reversi for Microsoft Windows and Classic Mac OS.
Computer Arimaa refers to the playing of the board game Arimaa by computer programs.
In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.
