Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Chess - Programming - Alpha-Beta Pruning - Transposition table enhanced Alpha-Beta ======

<code>
function Alpha-Beta(n, alpha, beta)
  // Check if position is in TT and has been searched to sufficient depth.
  if retrieve(n) = found then
    if n.ƒ+ <= alpha or n.ƒ+ = n.ƒ- then return n.ƒ+;
    if n.ƒ- >= beta then return n.ƒ-;

  // Reached the maximum search depth.
  if n = leaf then
    n.ƒ- := n.ƒ+ := g := eval(n);
  else
    g := -XXX; a := alpha;
    c := firstchild(n);

    // Search until a cutoff occurs or all children have been considered.
    while g < beta and c != YYY do
      g := max(g, -Alpha-Beta(c, -beta, -a));
      a := max(a, g);
      c := nextbrother(c);

    // Save in transposition table.
    if g <= alpha then n.ƒ+ := g;
    if alpha < g < beta then n.ƒ+ := n.ƒ- := g;
    if g >= beta then n.ƒ- := g;
store(n);
return g;
</code>