MCαβ

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * MCαβ

Monte-Carlo Alpha-Beta, (MCαβ)
is a Best-First search algorithm based on Monte-Carlo Tree Search and a shallow alpha-beta depth-first-search. It is used in Lines of Action and in conjunction with UCT (Upper Confidence bounds applied to Trees) also in Chess. It is similar to the the Best-first minimax search proposed by Richard Korf and Max Chickering [1], one distinction between the two might be that MCTS uses usually win/draw/loss scores and Best-First a score from a heuristic evaluation function.

Four Phases

MCαβ can be divided into four strategic phases, repeated as long as there is time left:

  1. In the Selection phase the tree is traversed from the root node until it selects a leaf node that is not added to the tree yet
  2. The Expansion strategy adds the leaf node to the tree
  3. The Playout phase performs a shallow alpha-beta search
  4. The Backpropagation strategy propagates the results through the tree

See also

Publications

Forum Posts

External Links

References