![]() ![]() 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 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |