The player continues to look for moves to make sure a better one hasn't been missed. Move "A" will improve the player's position. To illustrate this with a real-life example, suppose somebody is playing chess, and it is their turn. beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play. the "beta" player) is assured of becomes less than the minimum score that the maximizing player (i.e., the "alpha" player) is assured of (i.e. Whenever the maximum score that the minimizing player (i.e. both players start with their worst possible score. Initially, alpha is negative infinity and beta is positive infinity, i.e. The algorithm maintains two values, alpha and beta, which respectively represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of.
Each terminal node (outcome) of a branch is assigned a numeric score that determines the value of the outcome to the player with the next move. Each node in the tree represents a possible situation in the game. Core idea Ī game tree can represent many two-player zero-sum games, such as chess, checkers, and reversi. The optimality of the randomized version of alpha–beta was shown by Michael Saks and Avi Wigderson in 1986. Judea Pearl proved its optimality in terms of the expected running time for trees with randomly assigned leaf values in two papers. Alexander Brudno independently conceived the alpha–beta algorithm, publishing his results in 1963. McCarthy proposed similar ideas during the Dartmouth workshop in 1956 and suggested it to a group of his students including Alan Kotok at MIT in 1961. Richards, Timothy Hart, Michael Levin and/or Daniel Edwards also invented alpha–beta independently in the United States. Arthur Samuel had an early version for a checkers simulation. Simon who used what John McCarthy calls an "approximation" in 1958 wrote that alpha–beta "appears to have been reinvented a number of times".
0 kommentar(er)
