Wikispaces : chessprogramming - items matching description

ABDADA

GerdIsenberg — Wed, 30 Aug 2017 17:51:54 GMT

Home * Search * Parallel Search * ABDADA

		ABDADA, (Alpha-Bêta Distribué avec Droit d'Aînesse = Distributed Alpha-Beta Search with Eldest Son Right) a loosely synchronized, distributed search algorithm developed by Jean-Christophe Weill. The ABDADA search algorithm is based on Young Brothers Wait Concept (YBWC) (Rainer Feldmann et al. 1986, 1993) ^[1] ^[2] and αβ* (Vincent David 1993) ^[3] . From YBWC it retains the basic concept to allow parallel search only if the eldest son has been fully evaluated. From αβ* as well as Steve Otto and Ed Felten's algorithm (1988) ^[4] which both rely on a Shared Hash Table and all processors start the search simultaneously at the root, ABDADA retains the simple recursive control structure similar to a serial algorithm. With the help of additional transposition table information, i.e. the number of processors searching this node, it is possible to control speculative parallelism.
Hannah Höch - Da Dandy ^[5]

Recursion

While YBWC is difficult to implement recursively, ABDADA is not. In YBWC, when a processor receives an evaluation answer from one of its slaves, it must be able to produce a jump in the search depth if this evaluation produces a pruning of the current master node. So the values of alpha and beta must at least be kept in arrays indexed by ply distance from root, and special arrangements must be made to counteract the disruption that might occur from confusing depths. Therefor YBWC needs a hugely modified iterative search algorithm. In his paper ^[6] , Weill states that using ABDADA within a recursive NegaScout framework was 30% faster than a none-recursive search, which was observed independently by Mark Brockington in 1994 ^[7] . It can be explained by the fact that within high-level languages and their compilers for certain target platforms, the use of procedure stacks is much more optimized than the use of indexed arrays, also observed by Niklaus Wirth concerning the Quicksort algorithm ^[8] .

Algorithm

The ABDADA algorithm is described in five steps:

A TT-Entry has a field entry.nproc containing the number of processors currently searching the associated node
All processors start the search simultaneously at the root of the search tree
When a processor enters a node, it increments entry.nproc
When a processor leaves a node, it decrements entry.nproc
The analysis of a position is done in three phases:
1. The eldest son is analyzed, regardless of the activities of other processors
2. Next, all other sons not currently being analyzed by other processors are analyzed
3. In the final phase, any remaining sons not yet analyzed are searched, i.e. the corresponding entry in the TT indicates this node and its siblings have not been searched to the required depth

Pseudo Code

The C-like pseudo code below (adopted from the Pascal like pseudo code from Weill's paper), demonstrates the mentioned three phases controlled by an iteration counter. The boolean parameter exclusiveP indicates whether the node should be searched exclusively and is passed to the TT-probing code via the procedure retrieveAsk. A new value outside the usual value range need to be defined (ON_EVALUATION), and retrieveAsk returns this score if probed in exclusive move, and other processors evaluating this node.

int abdada(const CNode &position, int α, int β, int depth, bool exclusiveP) {
   if (depth == 0) return evaluate( position );
   int best = -oo;
 
   retrieveAsk(position, α, β, depth, exclusiveP);
   /* generate moves while waiting for the answer ... */
   GenerateMoves(position);
   retrieveAnswer(&α, &β, &best);
   /* The current move is not searched if causing a cutoff or */
   /* in exclusive mode and another processor is currently searching it */
   if ( α >= β || best == ON_EVALUATION )
      return best; /* entry.nproc not incremented */
 
   bool alldone = false;
   for ( int iteration = 0; iteration < 2 && α < β && !alldone; iteration++) {
      alldone = true;
      Move m = firstMove( position );
      while ( (m != 0) && (α < β) ) {
         exclusive = (iteration == 0) && !isFirstMove( m );
         /* On the first iteration, only one processor should search young sons exclusively */
         value = -abdada( position * m, -β, -max(α, best), depth-1, exclusive );
         if ( value == -ON_EVALUATION) {
            alldone = false;
         } else if ( value > best ) {
            best = value;
            if ( best > β ) goto endsearch;
         }
         m = nextMove( position );
      }
   }
endsearch:
   storeHash( position, α, β, depth, best );
   return best;
}

Implementations

Frenchess

ABDADA was implemented in Frenchess on a Cray T3D with 128 DEC Alpha 21064 processors. Frenchess participated at the WCCC 1995 finishing fourth, tied with Deep Blue Prototype ^[9], as well inside an Othello program called BUGS ^[10] .

Smash

The GPL open source chess engine Smash by Maurizio Sambati demonstrates an ABDADA implementation in C++ ^[11] ^[12] .

Publications

Jean-Christophe Weill (1995). Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche. Ph.D. Thesis. Université Paris 8, Saint-Denis, zipped ps (French)
Marc-François Baudot, Jean-Christophe Weill, Jean-Luc Seret, Michel Gondran (1995). Frenchess: A Cray T3D at the 8th World Computer Chess Championship. zipped ps
Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript

Forum Posts

1997 ...

Parallel searching by Andrew Tridgell, rgcc, March 22, 1997
Re:Parallel searching by Mark Brockington, rgcc, March 22, 1997

2000 ...

tip for "simulating" an MP computer & performance of ABDADA by Tom Kerrigan, CCC, May 28, 2000
A couple of Questions re ABDADA by Steve Maughan, CCC, May 29, 2000
Parallel algorithms in chess programming by Dieter Buerssner, CCC, April 16, 2001

2010 ...

Parallelization questions, ABDADA or DTS? by Benjamin Rosseaux, CCC, March 23, 2012
ABDADA speedup results by Daniel Shawul, CCC, May 01, 2013
IID and move sorting by Daniel Shawul, CCC, May 09, 2013 » Internal Iterative Deepening
Possible improvement to ABDADA -- checking for cutoffs by Tom Kerrigan, CCC, July 10, 2015
Actual speedups from YBWC and ABDADA on 8+ core machines? by Tom Kerrigan, CCC, July 10, 2015
Good parallel speedup with ABDADA and cutoff checks by Tom Kerrigan, CCC, February 03, 2017
Approximate ABDADA by Peter Österlund, CCC, August 23, 2017 » Lazy SMP - Lazy Cluster
"How To" guide to parallel-izing an engine by Tom Kerrigan, CCC, August 27, 2017
"Simplified ABDADA" updated by Tom Kerrigan, CCC, August 29, 2017

External Links

Algorithm

Simplified ABDADA from Parallel Search by Tom Kerrigan ^[13]
Cutoff Checks from Parallel Search by Tom Kerrigan

Misc

AB from Wikipedia
ab - Wiktionary
ab initio - Wiktionary
بد - Wiktionary
Dada from Wikipedia
Jean luc Ponty - Final Truth (Part 2), Montreal Jazz Festival, 1982, YouTube Video
feat. Allan Zavod, Jamie Glaser, Rayford Griffin and Keith Jones

References

^ Rainer Feldmann, Peter Mysliwietz, Oliver Vornberger (1986). A Local Area Network Used as a Parallel Architecture. Technical Report 31, University of Paderborn
^ Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf
^ Vincent David (1993). Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, École nationale supérieure de l'aéronautique et de l'espace, Toulouse, France
^ Ed Felten, Steve Otto (1988). Chess on a Hypercube. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications (ed. G. Fox), pp. 1329-1341
^ Hannah Höch - Da Dandy, 1919, Hannah Höch | Da-Dandy (1919) | Artsy, Hannah Höch: The “Quiet Girl” with a Big Voice (Part I) | Venetian Red Art Blog
^ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript
^ Mark Brockington (1994). An Implementation of the Young Brothers Wait Concept. Internal report, University of Alberta
^ Niklaus Wirth (1976). Algorithms + Data Structures = Programs. pp 100
^ Marc-François Baudot, Jean-Christophe Weill, Jean-Luc Seret, Michel Gondran (1995). Frenchess: A Cray T3D at the 8th World Computer Chess Championship. zipped ps
^ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript
^ Re: interested in making single procesor program multi by Alessandro Scotti, CCC, December 29, 2007
^ smash.tar.bz2 search.cpp
^ "How To" guide to parallel-izing an engine by Tom Kerrigan, CCC, August 27, 2017

What links here?

Page	Date Edited
ABDADA	Aug 30, 2017
Algorithms	May 5, 2017
Amy	May 9, 2017
Cilk	Oct 28, 2013
Daniel Shawul	Jan 28, 2018
Deep Sjeng	Jan 7, 2016
Dictionary	Aug 24, 2017
Dieter Bürssner	Dec 1, 2016
Dynamic Tree Splitting	Apr 10, 2017
EXchess	Jan 21, 2018
Frenchess	Jan 7, 2016
ICGA Journal	Dec 21, 2017
Internal Iterative Deepening	Feb 5, 2018
Iterative Search	Oct 20, 2016
Jamboree	Jun 15, 2015
Jean-Christophe Weill	Dec 17, 2016
László Gáspár	Jun 5, 2013
Lazy SMP	Jan 4, 2018
Maurizio Sambati	Apr 23, 2015
Nejmet	Mar 7, 2015
NUMA	Mar 29, 2017
Othello	Jan 4, 2018
Parallel Search	Dec 30, 2017
ParSOS	Jan 7, 2016
Peter Österlund	Aug 24, 2017
Recursion	Nov 18, 2017
Shared Hash Table	Sep 11, 2017
Smash	May 11, 2016
SMP	Dec 26, 2017
Steve Maughan	Jan 31, 2018
Storm US	Sep 6, 2013
Texel	Oct 9, 2017
Tom Kerrigan	Aug 27, 2017
Vincent David	Oct 20, 2016
Young Brothers Wait Concept	Apr 22, 2018

Up one level

AEL-Pruning

GerdIsenberg — Sat, 22 Jun 2013 08:51:59 GMT

Pseudo-Code

References

What links here?

Home * Search * Selectivity * Pruning * AEL-Pruning

AEL-pruning,
a search technique by Ernst A. Heinz that combines Adaptive Null Move Pruning (i.e., Null Move pruning with variable depth reduction R), Extended Futility Pruning (futility pruning at pre-frontier nodes) and limited razoring.

The basic idea is to first check if the depth is pre-pre-frontier, pre-frontier, or frontier, and create a bound based on the razoring margin (likely a queen), extended futility margin (usually around a rook), or futility margin (usually around a minor piece) accordingly. If none applied, only then use Adaptive Null Move Pruning. Now, when you are searching the moves of this position, apply the created bound if it applies. If the bound, plus any immediate material gain by the move is less than or equal to alpha, you may prune this move. Typically, you don't apply extended futility pruning or razoring on nodes you're extending.

Pseudo-Code

In his paper ^[1], Ernst A. Heinz] gives the following C pseudo-code:

int search (int alpha, int beta, int move, node parent, int depth) {
   node current;
   int extend, fmax, fscore, tt_hit;
   /*declare the local variables that require constant initialization*/
   int fprune = 0;
   int fpruned_moves = 0;
   int score = -infinite_val;
   /*execute the opponent's move and determine how to extend the search*/
   make_move(parent, move, &current;
   extend = extensions(move, current, depth);
   depth += extend;
   /*decide about limited razoring at the pre-pre-frontier nodes*/
   fscore = (mat_balance(current) + razor_margin);
   if (!extend && (depth == pre_pre_frontier) && (fscore <= alpha)
       { fprune = 1; score = fmax = fscore; }
   /*decide about extended futility pruning at pre-frontier nodes*/
   fscore = (mat_balance(current) + extd_futil_margin);
   if (!extend && (depth == pre_frontier) && (fscore <= alpha))
       { fprune = 1; score = fmax = fscore; }
   /*decide about selective futility pruning at frontier nodes*/
   fscore = (mat_balance(current) + futil_margin);
   if (!check(move) && (depth == frontier) && (fscore <= alpha))
       { fprune = 1; score = fmax = fscore; }
 
   /* ... */
 
   /*probe the transposition tables at the current node*/
   tt_hit = probe_transposition_tables(current, depth, &tt_ref);
   if (tt_hit) {/* ... */} else {/* ... */}
   /*try the adaptive null-move search with a minimal window around*/
   /*"beta" only if it is allowed, desired, and really promises to cut off*/
   if (!fprune && !check(move) && null_okay(current, move)
         && try_null(alpha, beta, current, depth, move, tt_ref)) {
        /* ... */
        null_score = -search(-beta, -beta + 1, null_move, current,
                        depth - R_adpt(current, depth) - 1);
        if (null_score >= beta) return null_score;
        /* ... */              /*fail-high null-move cutoff*/
   }
 
   /* ... */
   /*now continue as usual but prune all futile moves if "fprune == 1"*/
   for (move = first(current), (move != 0), move = next(current, move))
       if (!fprune || check(move)                    /*recursive PVS part*/
                   || (fmax + mat_gain(move) > alpha)) {/* ... */}
       else fpruned_moves++;
   /*"fpruned_moves > 0" => the search was selective at the current node*/
   /* ... */
}

References

^ Ernst A. Heinz (2000). AEL-Pruning. ICGA Journal, Vol. 23, No. 1, zipped postscript, pdf

What links here?

Page	Date Edited
AEL-Pruning	Jun 22, 2013
Amundsen	Sep 3, 2013
Ernst A. Heinz	Mar 6, 2017
Fischerle	Aug 21, 2017
Futility Pruning	Aug 30, 2017
Napoleon	Jun 25, 2017
Pepito	Nov 27, 2014
Pruning	Jan 1, 2018
Razoring	Oct 5, 2015
RDChess	May 3, 2013
Reverse Futility Pruning	Jun 2, 2017
Selectivity	Jan 12, 2018
Warrior	Feb 23, 2015

Up one Level

Alpha

GerdIsenberg — Sun, 11 Mar 2012 12:08:17 GMT

Home * Search * Score * Alpha

α		Alpha (α) is the lower bound, representing the minimum score that a node must reach in order to change the value of a previous node. Alpha has the same semantic as max in Negamax, and represents the minimum score that the maximizing player is assured of assuming optimal play of both sides.

External Links

What links here?

Page	Date Edited
More Links
ABDADA	Aug 30, 2017
Alpha	Mar 11, 2012
Alpha I	Dec 6, 2017
Alpha-Beta	Jan 28, 2018
Best Move	May 15, 2017
Beta	Jan 29, 2011
Beta-Cutoff	Oct 22, 2017
Bound	Jan 25, 2017
Chess 0.5	Nov 20, 2016
Chester	Feb 15, 2014
Delta Pruning	Dec 2, 2014
Dictionary	Aug 24, 2017
Exact Score	Dec 28, 2012
Fail-Hard	Dec 2, 2014
Fail-Soft	Jun 2, 2017
FCP	Jun 15, 2013
Futility Pruning	Aug 30, 2017
Heuristic Alpha	Apr 21, 2012
Horizon Node	Sep 13, 2016
Internal Iterative Deepening	Feb 5, 2018
Lazy Evaluation	Sep 1, 2017
Lower Bound	Jan 24, 2017
Mate Threat Extensions	Apr 14, 2012
Max	Dec 23, 2017
MAX (Gillogly)	Sep 1, 2013
Mini Chess	Jun 7, 2013
Murka	Nov 11, 2016
NegaScout	Jul 6, 2016
Null Window	Nov 8, 2016
Onno	Jul 19, 2013
Principal variation	Dec 4, 2017
Principal Variation Search	Oct 22, 2017
Quiescence Search	Aug 19, 2017
Quiescent Node	Feb 10, 2017
Rajah	Sep 12, 2012
Razoring	Oct 5, 2015
Reverse Futility Pruning	Jun 2, 2017
Supra	Jul 24, 2016
Triangular PV-Table	Jun 12, 2017
Upper Bound	Jan 24, 2017

Up one Level

Alpha-Beta

GerdIsenberg — Sun, 28 Jan 2018 08:10:02 GMT

Home * Search * Alpha-Beta

		The Alpha-Beta algorithm (Alpha-Beta Pruning, Alpha-Beta Heuristic ^[1] ) is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of the game tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Consider the following example...
Alpha Beta ^[2]

How it works

Say it is White's turn to move, and we are searching to a depth of 2 (that is, we are consider all of White's moves, and all of Black's responses to each of those moves.) First we pick one of White's possible moves - let's call this Possible Move #1. We consider this move and every possible response to this move by black. After this analysis, we determine that the result of making Possible Move #1 is an even position. Then, we move on and consider another of White's possible moves (Possible Move #2.) When we consider the first possible counter-move by black, we discover that playing this results in black winning a Rook! In this situation, we can safely ignore all of Black's other possible responses to Possible Move #2 because we already know that Possible Move #1 is better. We really don't care exactly how much worse Possible Move #2 is. Maybe another possible response wins a Queen, but it doesn't matter because we know that we can achieve at least an even game by playing Possible Move #1. The full analysis of Possible Move #1 gave us a lower bound. We know that we can achieve at least that, so anything that is clearly worse can be ignored.

The situation becomes even more complicated, however, when we go to a search depth of 3 or greater, because now both players can make choices affecting the game tree. Now we have to maintain both a lower bound and an upper bound (called Alpha and Beta.) We maintain a lower bound because if a move is too bad we don't consider it. But we also have to maintain an upper bound because if a move at depth 3 or higher leads to a continuation that is too good, the other player won't allow it, because there was a better move higher up on the game tree that he could have played to avoid this situation. One player's lower bound is the other player's upper bound.

Savings

The savings of alpha beta can be considerable. If a standard minimax search tree has x nodes, an alpha beta tree in a well-written program can have a node count close to the square-root of x. How many nodes you can actually cut, however, depends on how well ordered your game tree is. If you always search the best possible move first, you eliminate the most of the nodes. Of course, we don't always know what the best move is, or we wouldn't have to search in the first place. Conversely, if we always searched worse moves before the better moves, we wouldn't be able to cut any part of the tree at all! For this reason, good move ordering is very important, and is the focus of a lot of the effort of writing a good chess program. As pointed out by Levin in 1961, assuming constantly b moves for each node visited and search depth n, the maximal number of leaves in alpha-beta is equivalent to minimax, b ^ n. Considering always the best move first, it is b ^ ceil(n/2) plus b ^ floor(n/2) minus one. The minimal number of leaves is shown in following table which also demonstrates the odd-even effect:

	number of leaves with depth n and b = 40
depth	worst case	best case
n	$b^n$	$b^{\lceil n / 2 \rceil} + b^{\lfloor n / 2 \rfloor} - 1$
0	1	1
1	40	40
2	1,600	79
3	64,000	1,639
4	2,560,000	3,199
5	102,400,000	65,569
6	4,096,000,000	127,999
7	163,840,000,000	2,623,999
8	6,553,600,000,000	5,119,999

History

Alpha-Beta was invented independently by several researchers and pioneers from the 50s ^[3], and further research until the 80s, most notable by

John McCarthy proposed the idea of Alpha-Beta in 1955 at the Dartmouth Conference ^[4]
Allen Newell and Herbert Simon Approximation in 1958
Arthur Samuel Approximation in 1959
Daniel Edwards and Timothy Hart, Description in 1961 ^[5]
Alexander Brudno, Description in 1963
Samuel Fuller, John Gaschnig, James Gillogly, Analysis 1973 ^[6]
Donald Knuth, Analysis in 1975
Knuth and Moore's famous Function F2, aka AlphaBeta
Knuth already introduced an iterative solution, see Iterative Search
Knuth's node types
Gérard M. Baudet, Analysis in 1978

Quotes

McCarthy

Quote by John McCarthy from Human-Level AI is harder than it seemed in 1955 ^[7]:

Chess programs catch some of the human chess playing abilities but rely on the limited effective branching of the chess move tree. The ideas that work for chess are inadequate for go. Alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers - Turing, Shannon, Pasta and Ulam, and Bernstein. We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by Samuel, Newell and Simon, McCarthy. Proved equivalent to minimax by Hart and Levin, independently by Brudno. Knuth gives details.

Ershov and Shura-Bura

Quote from The Early Development of Programming in the USSR by Andrey Ershov, Mikhail R. Shura-Bura ^[8]

At the end of the 1950's a group of Moscow mathematicians began a study of computerized chess. Sixteen years later, the studies would lead to victory in the first world chess tournament for computer programs held in Stockholm during the 1974 IFIP Congress. An important component of this success was a deep study of the problems of information organization in computer memory and of various search heuristics. G. M. Adelson-Velsky and E. M. Landis invented the binary search tree ("dichotomic inquiry") and A. L. Brudno, independent of J. McCarthy, discovered the (α,β)-heuristic for reducing search times on a game tree.

Knuth

Quote by Knuth ^[9] :

It is interesting to convert this recursive procedure to an iterative (non-recursive) form by a sequence of mechanical transformations, and to apply simple optimizations which preserve program correctness. The resulting procedure is surprisingly simple, but not as easy to prove correct as the recursive form.

Implementation

Max versus Min

A C-like pseudo code implementation of the alpha-beta algorithm with distinct indirect recursive routines for the max- and min-player, similar to the minimax routines. Making and unmaking moves is omitted, and should be done before and after the recursive calls. So called beta-cutoffs occur for the max-play, alpha-cutoffs for the min-player.

int alphaBetaMax( int alpha, int beta, int depthleft ) {
   if ( depthleft == 0 ) return evaluate();
   for ( all moves) {
      score = alphaBetaMin( alpha, beta, depthleft - 1 );
      if( score >= beta )
         return beta;   // fail hard beta-cutoff
      if( score > alpha )
         alpha = score; // alpha acts like max in MiniMax
   }
   return alpha;
}
 
int alphaBetaMin( int alpha, int beta, int depthleft ) {
   if ( depthleft == 0 ) return -evaluate();
   for ( all moves) {
      score = alphaBetaMax( alpha, beta, depthleft - 1 );
      if( score <= alpha )
         return alpha; // fail hard alpha-cutoff
      if( score < beta )
         beta = score; // beta acts like min in MiniMax
   }
   return beta;
}

With this call from the Root:

   score = alphaBetaMax(-oo, +oo, depth);

Alpha-beta search tree with two alpha-cuts at min nodes ^[10]

Negamax Framework

Inside a negamax framework the routine looks simpler, but is not necessarily simpler to understand. Despite negating the returned score of the direct recursion, alpha of the min-player becomes minus beta of the max-player and vice versa, and the term alpha-cutoff or alpha-pruning is somehow diminished.

int alphaBeta( int alpha, int beta, int depthleft ) {
   if( depthleft == 0 ) return quiesce( alpha, beta );
   for ( all moves)  {
      score = -alphaBeta( -beta, -alpha, depthleft - 1 );
      if( score >= beta )
         return beta;   //  fail hard beta-cutoff
      if( score > alpha )
         alpha = score; // alpha acts like max in MiniMax
   }
   return alpha;
}

Note #1: Notice the call to quiesce(). This performs a quiescence search, which makes the alpha-beta search much more stable.

Note #2: This function only returns the score for the position, not the best move. Normally, a different (but very similar) function is used for searching the root node. The SearchRoot function calls the alphaBeta function and returns both a score and a best move. Also, most search functions collect the principal variation not only for display purposes, but for a good guess as the leftmost path of the next iteration inside an iterative deepening framework.

Fail hard

Since alpha and beta act as hard bounds of the return value if depth left is greater zero in the above code samples, this is referred to a fail-hard-framework.

Outside the Bounds

Fail-Soft Alpha-Beta ^[11] may return scores outside the bounds, that is either greater than beta or less than alpha. It has to keep track of the best score, which might be below alpha.

int alphaBeta( int alpha, int beta, int depthleft ) {
   int bestscore = -oo;
   if( depthleft == 0 ) return quiesce( alpha, beta );
   for ( all moves)  {
      score = -alphaBeta( -beta, -alpha, depthleft - 1 );
      if( score >= beta )
         return score;  // fail-soft beta-cutoff
      if( score > bestscore ) {
         bestscore = score;
         if( score > alpha )
            alpha = score;
      }
   }
   return bestscore;
}

Enhancements

The alpha-beta algorithm can also be improved. These enhancements come from the fact that if you restrict the window of scores that are interesting, you can achieve more cutoffs. Since move ordering is so much important, a technique applied outside of the search for this is iterative deepening boosted by a transposition table, and possibly aspiration windows. Other enhancements, applied within the search function, are further discussed.

Obligatory

Selectivity

Scout and Friends

Alpha-Beta goes Best-First

Videos

Selected Publications

1958 ..

Allen Newell, Cliff Shaw, Herbert Simon (1958). Chess Playing Programs and the Problem of Complexity. IBM Journal of Research and Development, Vol. 4, No. 2, pp. 320-335. Reprinted (1963) in Computers and Thought (eds. Edward A. Feigenbaum and Julian Feldman), pp. 39-70. McGraw-Hill, New York, N.Y., pdf
Arthur Samuel (1959). Some Studies in Machine Learning Using the Game of Checkers. IBM Journal July 1959

1960 ...

Daniel Edwards, Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at MIT. Retrieved on 2006-12-21.
Alexander Brudno (1963). Bounds and valuations for shortening the search of estimates. Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241
James R. Slagle (1963). Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure. Artificial Intelligence Group Report 3, UCRL-4671, University of California
James R. Slagle, John K. Dixon (1969). Experiments With Some Programs That Search Game Trees. Journal of the ACM, Vol. 16, No. 2: 189-207, pdf

1970 ...

Samuel Fuller, John Gaschnig, James Gillogly (1973). An Analysis of the Alpha-Beta Pruning Algorithm. Technical Report, Carnegie Mellon University, pdf
Donald Knuth, Ronald W. Moore (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3, pdf
Arnold K. Griffith (1976). Empirical Exploration of the Performance of the Alpha-Beta Tree-Searching Heuristic. IEEE Transactions on Computers, Vol. C-25, No. 1
Gérard M. Baudet (1978). An Analysis of the Full Alpha-Beta Pruning Algorithm. STOC 1978: 296-313
Gérard M. Baudet (1978). On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence, Vol. 10
Patrick Winston (1978). Dealing with Adversaries. Personal Computing, Vol. 2, No. 11, pp. 30, November 1978 » Alpha-Beta
Gary Lindstrom (1979). Alpha-Beta Pruning on Evolving Game Trees. Technical Report UUCCS 79-101, University of Utah, UScholar Works
Ward Douglas Maurer (1979). Alpha-Beta Pruning. BYTE, Vol. 4, No. 11, pp. 84-96

1980 ...

David Levy (1980). Intelligent Games. Creative Computing, Vol. 6, No. 4, hosted by the Internet Archive
Judea Pearl (1981). Heuristic search theory: A survey of recent results. IJCAI-81, pdf
Igor Roizen (1981). On the Average Number of Terminal Nodes examined by Alpha-Beta. Technical Report UCLA-ENG-CSL-8108, University of California at Los Angeles, Cognitive Systems Laboratory
Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8
Peter W. Frey (1983). The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning. Computer Game-Playing (ed. Max Bramer), pp. 285-289. Ellis Horwood Limited
John Philip Fishburn (1983). Another optimization of alpha-beta search. SIGART Bulletin, Issue 84, pdf » Fail-Soft
John Hughes (1984). Why Functional Programming Matters. 5 An Example from Artificial Intelligence, Chalmers Tekniska Högskola, Göteborg, pdf,
Stephen F. Wheeler (1985). A performance benchmark of the alpha-beta procedure on randomly ordered non-uniform depth-first game-trees generated by a chess program. M.Sc. thesis, East Texas State University
Toshihide Ibaraki (1986). Generalization of Alpha-Beta and SSS* Search Procedures. Artificial Intelligence, Vol. 29
Matthew Huntbach, F. Warren Burton (1988). Alpha-beta search on virtual tree machines. Information Sciences, Vol. 44, No. 1

1990 ...

Ingo Althöfer, Bernhard Balkenhol (1992). A Game Tree with Distinct Leaf Values which is Easy for the Alpha-Beta Algorithm. Artificial Intelligence, Vol. 52, No. 2
Alois Heinz, Christoph Hense (1993). Bootstrap learning of α-β-evaluation functions. ICCI 1993, pdf
Van-Dat Cung (1993). Parallelizations of Game-Tree Search. PARCO 1993, pdf hosted by CiteSeerX
Alois Heinz (1994). Efficient Neural Net α-β-Evaluators. pdf
Ernst A. Heinz (1999). Scalable Search in Computer Chess. Morgan Kaufmann, ISBN 3-528-05732-7

2000 ...

Matthew L. Ginsberg, Alan Jaffray (2002). Alpha-Beta Pruning Under Partial Orders. in Richard J. Nowakowski (ed.) More Games of No Chance. Cambridge University Press, pdf
Todd W. Neller (2002). Information-Based Alpha-Beta Search and the Homicidal Chauffeur. HSCC 2002, in Claire J. Tomlin, Mark R. Greenstreet (eds.) (2002). Hybrid Systems: Computation and Control. Lecture Notes in Computer Science 2289, Springer ^[12]
Jacek Mańdziuk, Daniel Osman (2004). Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function. ICGA Journal, Vol. 27, No. 1, pdf
Hendrik Baier (2006). Der Alpha-Beta-Algorithmus und Erweiterungen bei Vier Gewinnt. Bachelor's thesis (German), TU Darmstadt, advisor Johannes Fürnkranz, pdf

2010 ...

Damjan Strnad, Nikola Guid (2011). Parallel Alpha-Beta Algorithm on the GPU. CIT. Journal of Computing and Information Technology, Vol. 19, No. 4 » GPU, Parallel Search, Reversi
Abdallah Saffidine, Hilmar Finnsson, Michael Buro (2012). Alpha-Beta Pruning for Games with Simultaneous Moves. AAAI 2012
Daniel S. Abdi (2013). Analysis of pruned minimax trees. pdf » Late Move Reductions, Null Move Pruning
Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, Chia-Hui Chang (2015). Job-Level Alpha-Beta Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 1
Bojun Huang (2015). Pruning Game Tree by Rollouts. AAAI » MCTS, MT-SSS*, Rollout Paradigm ^[13]
Hendrik Baier (2017). A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta. Computer Games » MCαβ, Monte-Carlo Tree Search

Forum Posts

1993 ...

computer chess by Paul W Celmer, rgc, September 10, 1993
Re: Computer Chess (LONG) by Andy Walker, rgc, September 16, 1993
Computer Chess and alpha-beta pruning by Rickard Westman, rgc, September 21, 1993
Re: Computer Chess and alpha-beta pruning by Johannes Fürnkranz, rgc, September 22, 1993 » Iterative Deepening
alpha-beta pruning != brute force by Feng-hsiung Hsu, rgc, September 22, 1993 » Brute-Force
Re: Computer Chess and alpha-beta pruning by Robert Hyatt, rgc, September 25, 1993
Alpha-beta inconsistencies by Chua Kong Sian, rgc, February 19, 1994

1995 ...

Alpha-Beta explained? by Brian, rgcc, October 15, 1996
New improvement to alpha/beta + TT? by Heiner Marxen, rgcc, January 13, 1997 » Fail-Soft
Re: Argument against Alpha-Beta searching by Robert Hyatt, rgcc, March 19, 1997
computer chess "oracle" ideas... by Robert Hyatt, rgcc, April 1, 1997 » Oracle
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 3, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997
Basic alpha-beta question by John Scalo, CCC, January 06, 1998
alpha-beta is silly? by Werner Inmann, CCC, June 02, 1998
Re: Basic questions about alpha beta by Bruce Moreland, CCC, September 28, 1998

2000 ...

Another Alpha-Beta algorithm question by Jeff Anderson, CCC, February 18, 2000
A Question on simple Alpha-Beta versus PVS/Negascout by Andrei Fortuna, CCC, March 21, 2000 » Principal Variation Search, NegaScout
outline for alpha beta by John Coffey, CCC, May 12, 2000
Alpha-Beta explanation on Heinz's book? by Severi Salminen, CCC, October 05, 2000 ^[14]
Who invented the Alpha-Beta-algorithm? by Rafael B. Andrist, CCC, April 09, 2001
The Alpha-Beta search! by Sune Fischer, CCC, August 14, 2001
An Idiot's Guide to Minimax, Alpha/Beta, etc... by Mike Carter, CCC, February 03, 2003
Fail soft alpha-beta by Russell Reagan, CCC, September 08, 2003 » Fail-Soft
Complexity Analyses of Alpha-Beta by Renze Steenhuisen, CCC, October 07, 2003
Mixing alpha-beta with PN search by Tord Romstad, CCC, January 18, 2004 » Proof-Number Search
Question for Hyatt about Alpha/Beta by Bob Durrett, CCC, February 05, 2004

2005 ...

Iterative alpha-beta search? by Andrew Wagner, CCC, January 11, 2006 » Iterative Search
Trivial alfa-beta question by Jouni Uski, CCC, February 18, 2006

2010 ...

Dumb question about alpha-beta by Daylen Yang, CCC, March 04, 2014

2015 ...

Search algorithm in it's simplest forum by Mahmoud Uthman, CCC, February 25, 2015
Negative alpha/beta windows: Are they useful? by Thomas Dybdahl Ahle, CCC, March 06, 2015
Stuck on Alphabeta by kuket15, OpenChess Forum, December 07, 2015
Alpha-Beta woes, textbook-like resources, etc. by Meni Rosenfeld, CCC, January 14, 2016
Search by Laurie Tunnicliffe, CCC, June 24, 2016
Alpha-Beta as a rollouts algorithm by Daniel Shawul, CCC, January 25, 2018 » MCαβ, Monte-Carlo Tree Search, Scorpio

External Links

Alpha-beta Pruning from Wikipedia
Branch-and-bound from Wikipedia
Integer programming from Wikipedia ^[15]
The alpha-beta heuristic from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
Alpha-Beta Search from Bruce Moreland's Programming Topics
Lecture notes for April 22, 1997 Alpha-Beta Search by David Eppstein
G13GAM -- Game Theory - alpha-beta pruning by Andy Walker
Alpha-Beta from How Rebel Plays Chess by Ed Schröder
Alpha-Beta search from Paul Verhelst's Computer Chess Sites
The Minimax Algorithm and Alpha-Beta Pruning from The Computer History Museum
Alpha-Beta Slide Show in 18 steps by Mikael Bodén
Alpha Beta - Astral Abuse, 1971, YouTube Video
Alpha Beta are Vilma Lado, Vangelis Papathanassiou, Argyris Koulouris and Giorgio Gomelski

References

^ Arthur Samuel (1967). Some Studies in Machine Learning. Using the Game of Checkers. II-Recent Progress. pdf, IBM Journal - November 1967,
on the name Alpha-Beta Heuristic pp. 602:
So named by Prof. John McCarthy. This procedure was extensively investigated by Prof. John McCarthy and his students at M.I.T. but it has been inadequately described in the literature. It is, of course, not a heuristic at all, being a simple algorithmic procedure and actually only a special case of the more general "branch and bound" technique which was been rediscovered many times and which is currently being exploited in integer programming research.
^ Alpha Beta - Astral Abuse a look at the music of Vangelis Papathanassiou
^ Jaap van den Herik (2001). Science, Competition and Business. ICGA Journal, Vol. 24, No. 4, pdf
^ A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence by John McCarthy, Marvin Minsky, Nathaniel Rochester, Claude Shannon, August 31, 1955
^ Daniel Edwards and Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at MIT. Retrieved on 2006-12-21.
^ Samuel Fuller, John Gaschnig, James Gillogly (1973). An Analysis of the Alpha-Beta Pruning Algorithm. Technical Report, Carnegie Mellon University
^ John McCarthy Human-Level AI is harder than it seemed in 1955
^ Andrey Ershov, Mikhail R. Shura-Bura (1980). The Early Development of Programming in the USSR. in Nicholas C. Metropolis (ed.) A History of Computing in the Twentieth Century. Academic Press, preprint pp. 44
^ Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3
^ McGill University, Winter 1997 Class Notes, Topic #11: Game trees. Alpha-beta search, Diagram by Pui Yee Chan
^ John Philip Fishburn (1983). Another optimization of alpha-beta search. SIGART Bulletin, Issue 84
^ Homicidal chauffeur problem - Wikipedia
^ Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » LCZero
^ Ernst A. Heinz (1999). Scalable Search in Computer Chess. Morgan Kaufmann, ISBN 3-528-05732-7
^ William Cook (2009). Fifty-Plus Years of Combinatorial Integer Programming. pdf

Up one level

APHID

GerdIsenberg — Mon, 26 Jun 2017 13:02:32 GMT

Home * Search * Parallel Search * APHID

		APHID, (Asynchronous Parallel Hierarchical Iterative Deepening) an asynchronous parallel alpha-beta based search algorithm developed and elaborated by Mark Brockington as topic of his Ph.D. thesis at the Department of Computing Science, University of Alberta ^[1], along with his thesis advisor Jonathan Schaeffer. APHID uses repeated depth-limited searches of the top of the search tree to instantiate, update and load balance work lists for other processors. APHID can be seen as a master/slave model, but can be generalized to a hierarchical processor tree. APHID has been programmed as an easy-to-implement, game-independent library ^[2], and was implemented into the chess program The Turk with less than one day of programming effort ^[3]. It was further tested in Crafty in chess, in Chinook in the domain of Checkers, and in Brockington's Othello program Keyano ^[4]. APHID yields reasonable performance on a network of workstations, an architecture where it is extremely difficult to use a shared transposition table effectively. More recently, APHID was used within the ChessBrain project of over 2000 internet connected machines running Beowulf ^[5].
Two adult aphids ^[6]

How it works

The master is responsible for searching the top d' plies of the d-ply tree inside its iterative deepening frame. When the master reaches a leaf of the d'-ply tree, it uses either a (d-d')-ply search result already available from the slave, or the "best available" i.e. using guessed scores from shallower previous searches marked as uncertain. As values get backed up the tree, the master maintains a count of how many uncertain nodes have been visited in a pass of the tree, and has to repeat the root search until all contributing leaves have reliable, certain results. By using the guessed score and expected node types, the master decides which child-nodes are searched sequentially or in parallel.

Location of Parallelism in typical APHID and YBW search trees ^[7]

The slave process essentially executes the same code that a sequential alpha-beta searcher would. It looks in the local copy of the so called APHID table, initially allocated and supplied by the master, to find the highest priority node to search. After finishing the search, it reports the result back to the master, getting an update to its APHID table entry in return.

Publications

Mark Brockington, Jonathan Schaeffer (1996). The APHID Parallel αβ Search Algorithm. Technical Report 96-07, Department of Computing Science, University of Alberta, pdf from CiteSeerX
Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8
Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta, pdf
Mark Brockington, Jonathan Schaeffer (1999). APHID: Asynchronous Parallel Game-Tree Search. Department of Computing Science, University of Alberta, pdf from CiteSeerX

Forum Posts

Chess over LAN revisited - APHID by Gian-Carlo Pascutto, CCC, September 17, 2001
APHID , advances in ICCA #8 by Vincent Diepeveen, CCC, September 18, 2001
Deep Crafty by Donald O. Davis, rgcc, October 29, 2001
asynchronous search by Daniel Shawul, CCC, April 06, 2010
Re: asynchronous search by Daniel Shawul, CCC, April 07, 2010
Re: asynchronous search by Dann Corbit, CCC, April 08, 2010
scorpio can run on 8192 cores by Daniel Shawul, CCC, August 22, 2015 » Scorpio
Re: scorpio can run on 8192 cores by Daniel Shawul, CCC, August 30, 2015

External Links

Game Tree Search

APHID Parallel Game-Tree Search Library

Misc

References

^ Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta, pdf
^ APHID Parallel Game-Tree Search Library
^ Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8, 4. Experiments pp. 83
^ Keyano (Othello) Home Page
^ Colin Frayn, Carlos Justiniano, Kevin Lew (2006). ChessBrain II – A Hierarchical Infrastructure for Distributed Inhomogeneous Speed-Critical Computation. pdf
^ Aphidoidea in Belgium, Image by Luc Viatour, 2008, CC BY-SA 2.5, Wikimedia Commons
^ Image cropped from Figure 4, pp. 6 in Mark Brockington, Jonathan Schaeffer (1996). The APHID Parallel αβ Search Algorithm. Technical Report 96-07, Department of Computing Science, University of Alberta, pdf from CiteSeerX

What links here?

Page	Date Edited
APHID	Jun 26, 2017
ChessBrain	Jun 28, 2017
Gian-Carlo Pascutto	Jan 16, 2018
Mark Brockington	Jun 26, 2017
Othello	Jan 4, 2018
Parallel Search	Dec 30, 2017
Young Brothers Wait Concept	Apr 22, 2018

Up one level

Aspiration Windows

GerdIsenberg — Wed, 01 Nov 2017 08:40:20 GMT

Home * Search * Alpha-Beta * Aspiration Windows

		Aspiration windows are a way to reduce the search space in an alpha-beta search. The technique is to use a guess of the expected value (usually from the last iteration in iterative deepening), and use a window around this as the alpha-beta bounds. Because the window is narrower, more beta cutoffs are achieved, and the search takes a shorter time. The drawback is that if the true score is outside this window, then a costly re-search must be made. Typical window sizes are 1/2 to 1/4 of a pawn on either side of the guess.
The Non-Euclidean Window ^[1]

Gradual Widening

Some programs, such as Crafty, also use a gradual widening on re-searches. For instance, if the window is, in pawns:

$[g - 1/4, g + 1/4]$

and the search fails high, the next search would be

$[g - 1/4, g + 1]$

It's important to note that the bound that didn't fail is unchanged. In a basic alpha-beta without search instability, one could have done the next search on

$[g + 1/4, g + 1]$

instead. However, a fully fledged search is typically full of search instability, and it will often happen that the above re-search will fail low! This is why it is best to only widen the bound that fails, and leave the other bound unchanged.

Modern engines, like Robbolito or Stockfish, start with a rather small aspiration window, and increase the bound that fails in an exponential fashion.

PVS and Aspiration

Using aspiration windows together with the principal variation search (PVS) causes some additional complications.

PVS and Aspiration

Publications

Hermann Kaindl, Reza Shams, Helmut Horacek (1991). Minimax Search Algorithms with and without Aspiration Windows. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 12
Reza Shams, Hermann Kaindl, Helmut Horacek (1991). Using Aspiration Windows for Minimax Algorithms. IJCAI 1991, pdf

Forum Posts

1995 ...

Question about aspiration window by Werner Inmann, CCC, August 14, 1998
aspiration windows by James Long, CCC, November 27, 1998
Aspiration Rules... by Chris Pile, rgcc, February 5, 1999
Aspiration search by James Robertson, CCC, April 20, 1999
Aspiration search by Scott Gasch, CCC, August 13, 1999

2000 ...

Aspiration window by Bas Hamstra, CCC, January 20, 2002
Exact value of second best move in AlphaBeta with aspiration Window by Martin Bauer, CCC, August 01, 2002
Aspiration search, PVS by Russell Reagan, CCC, December 28, 2002
Unstable aspiration search by Sune Fischer, CCC, February 10, 2003
Question about aspiration search by Jaime Benito de Valle Ruiz, CCC, March 23, 2004
What is a common Aspiration window? by Joachim Rang, CCC, March 26, 2004
aspiration search question by Daniel Shawul, CCC, May 13, 2004
Q. Aspiration, PVS, Fail-Soft by David B. Weller, CCC, July 02, 2004
PVS and aspiration windows by Tord Romstad, CCC, August 06, 2004

2005 ...

Aspiration Window sizes by Renze Steenhuisen, CCC, March 14, 2005
Bounds for aspiration window re-search by Sven Schüle, CCC, March 17, 2009
A way to improve PVS by Sergei S. Markoff, CCC, September 07, 2009

2010 ...

Apiration window by Don Dailey, CCC, March 27, 2010
A few general questions... by Bill Henry, CCC, January 29, 2012 » Root, Exact Score
optimal aspiration window for stockfish question by Uri Blass, CCC, March 12, 2012 » Stockfish
Aspiration Windows: Rubbish! by Matthew R. Brades, CCC, July 16, 2012
Aspiration window - effect? Issue with hashtables?! by Jens Bæk Nielsen, CCC, December 28, 2012
Aspiration Windows by Jerry Donald, CCC, January 11, 2013
Aspiration windows by Marco Pampaloni, CCC, May 14, 2013
Your experience with PVS + Aspiration window by Fabio Gobbato, CCC, October 07, 2014 » Principal Variation Search, PVS and aspiration
Solving a fail low situation at the root by Alberto Sanjuan, CCC, November 03, 2014 » Fail-Low

2015 ...

Parallel aspiration windows by Giuseppe Cannella, CCC, July 29, 2015
Restarting iterative deepening by Harm Geert Muller, CCC, December 09, 2015 » Fail-Low, Iterative Deepening

2016

Dynamic aspiration window by Sergei S. Markoff, CCC, May 26, 2016
Aspiration Windows on the root search -- Determining margin by Andrew Grant, CCC, June 08, 2016
Iterative Deepening Question by David Cimbalista, CCC, July 23, 2016 » Iterative Deepening
Aspiration window with TT question by sandermvdb, OpenChess Forum, August 01, 2016 » Transposition Table

2016

Conceptual question on aspiration windows by Jacob Wilkins, CCC, April 09, 2017
(I)ID and PV dropout by Harm Geert Muller, CCC, June 17, 2017 » Fail-Low, Internal Iterative Deepening, Iterative Deepening
Aspiration window problem by Sander Maassen vd Brink, CCC, October 30, 2017

External Links

References

^ Gerhard Hoehme - The Non-Euclidean Window (1964), mixed technique / wood on canvas, Art Museum, Bochum, North Rhine-Westphalia, Germany, part of The Industrial Heritage Trail of the Ruhr area, Photo by Gerd Isenberg, October 30, 2016

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Alarm	Jun 7, 2017
Alberto Sanjuan	Nov 3, 2014
AliBaba	Aug 17, 2014
Alpha-Beta	Jan 28, 2018
Amoeba	Mar 19, 2018
Amundsen	Sep 3, 2013
Andrew Grant	Jan 13, 2018
Android-Chess	Jun 2, 2016
Andscacs	Jan 16, 2018
Arion	Nov 28, 2014
Aspiration Windows	Nov 1, 2017
Atlas (ESP)	Jan 28, 2018
Bas Hamstra	Feb 4, 2018
Belzebub	Oct 20, 2015
Beowulf	May 5, 2017
BigLion	Sep 28, 2016
Bison	Sep 29, 2016
Bobcat	Jun 27, 2017
Brainless	Jun 24, 2017
Carballo	Oct 2, 2016
Celes	May 23, 2014
Cheese	Feb 17, 2018
Cheiron	Jan 7, 2016
Chenard	Sep 5, 2015
Cheng	Jul 30, 2017
Chess 0.5	Nov 20, 2016
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
Chessterfield	Sep 29, 2016
Chezzz	Jan 20, 2013
Cinnamon	Sep 23, 2017
Claudia	Jun 1, 2016
Clubfoot	Sep 8, 2015
Coiled	Mar 12, 2017
Comet	Jan 8, 2016
Critter	Jan 25, 2014
CuckooChess	Jan 17, 2017
Cupcake	May 19, 2016
DanaSah	Oct 9, 2017
David B. Weller	Sep 13, 2015
DayDreamer	Aug 22, 2016
Demolito	Mar 1, 2018
Deuterium	Jun 23, 2014
Diablo	May 17, 2016
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
Don Dailey	Dec 7, 2016
Donna	Aug 17, 2017
DrunkenMaster	Nov 1, 2016
Dumb	Mar 10, 2018
Ethereal	Mar 20, 2018
Eveann	Apr 3, 2017
Exact Score	Dec 28, 2012
Fail-High	Oct 22, 2017
Fail-Low	Jun 23, 2017
FCP	Jun 15, 2013
Fischerle	Aug 21, 2017
Fixafan	Oct 2, 2015
Fizbo	Dec 22, 2017
Flux	Jan 12, 2016
Fortress (Engine)	Oct 19, 2017
Francesca	Jan 7, 2016
Freyr	Mar 6, 2014
GambitVB	Oct 24, 2016
Garbochess-JS	Sep 23, 2017
Gaviota	Jan 21, 2018
GES	Sep 13, 2015
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Gk	Oct 9, 2017
Gogobello	Jul 30, 2017
GullChess	Jun 27, 2017
Gunnar Harms	Feb 15, 2013
Hagrid	Apr 12, 2016
Hakkapeliitta	Apr 26, 2016
HAL	Jun 14, 2016
Harm Geert Muller	Mar 31, 2018
HeavyChess	Feb 14, 2014
Horizon	Mar 17, 2013
Internal Iterative Deepening	Feb 5, 2018
Iterative Deepening	Jun 23, 2017
Jan Renze Steenhuisen	Sep 10, 2017
Jens Bæk Nielsen	Mar 3, 2015
JikChess	Nov 29, 2015
Joachim Rang	Mar 19, 2014
Joanna	Dec 9, 2014
Joker IT	Sep 16, 2017
Kaissa	Apr 9, 2018
Kanguruh	Jan 13, 2013
Kholin	Jan 3, 2018
King of Kings	Sep 4, 2013
KnockOut	Sep 20, 2016
Leftmost Node	May 28, 2011
List (Program)	Jan 7, 2016
MadChess	Jul 4, 2017
Martin Bauer	Apr 3, 2013
Marvin	Feb 10, 2018
Matilde	Jan 1, 2014
Matthew R. Brades	Jun 9, 2017
Mediocre	Feb 27, 2015
MessChess	Mar 6, 2014
Minimax (program)	Dec 27, 2013
Move Ordering	Feb 27, 2018
MTD(f)	Jul 17, 2017
Napoleon	Jun 25, 2017
Natwarlal	Aug 26, 2013
Nemorino	Dec 21, 2017
Nesik	Jan 24, 2014
Neurosis	Dec 23, 2017
Nirvanachess	Sep 30, 2017
NoraGrace	Nov 23, 2014
Null Window	Nov 8, 2016
Nullmover	Jul 21, 2013
Occam	Jan 21, 2016
Octochess	Aug 15, 2017
OliThink	May 19, 2017
Orion	Oct 15, 2017
Paladin	Jan 29, 2017
Pawny	Jun 17, 2015
Phalanx	May 2, 2016
Pharaon	Sep 2, 2017
PolarChess	May 15, 2017
Popochin	Feb 5, 2016
Principal Variation Search	Oct 22, 2017
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Protej	Jul 27, 2014
PVS and aspiration	Oct 8, 2014
Querg	Dec 11, 2013
Rabbit	Oct 5, 2014
RDChess	May 3, 2013
RedQueen	Nov 13, 2017
Requiem	Feb 5, 2018
Reza Shams	Oct 31, 2016
Rodent	Jan 11, 2018
RomiChess	Jan 2, 2018
Root	Sep 26, 2016
Russell Reagan	Aug 31, 2013
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
Search	Feb 1, 2018
Search Explosion	Mar 30, 2017
Search Instability	May 5, 2017
Search Statistics	Jan 16, 2018
Senpai	Nov 10, 2017
Sharper	Jun 6, 2017
Shield	May 17, 2017
Simplex	Mar 6, 2016
Sinobyl	Jul 3, 2014
Sjeng	Aug 17, 2017
Slow Chess	May 17, 2016
Small Potato	Feb 14, 2014
SmarThink	Feb 2, 2018
Snitch	Apr 7, 2016
Soldat	Aug 20, 2017
Stockfish	Apr 7, 2018
Sune Fischer	Apr 7, 2014
Sunsetter	Jun 1, 2017
Sven Schüle	Sep 20, 2016
Tao	Jan 8, 2016
Tech	Apr 20, 2018
TechMate	Aug 23, 2014
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The Turk (TR)	Apr 1, 2017
Thor's Hammer	Nov 23, 2013
Tornado	Dec 14, 2017
TRACE	Feb 14, 2013
Transposition Table	Apr 19, 2018
Triangular PV-Table	Jun 12, 2017
Tucano	Dec 16, 2017
Vanilla Chess	Jan 13, 2013
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
Waxman	Aug 18, 2014
Window	Jun 7, 2017
Wing	Oct 26, 2017
Woodpusher	Dec 12, 2016
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Xpdnt	Sep 13, 2015
ZChess	Jan 8, 2016
Zeus RU	Jun 6, 2015
Ziggurat	Oct 9, 2017
Zurichess	Mar 12, 2018

Up one level

B*

GerdIsenberg — Mon, 27 Nov 2017 22:20:09 GMT

Home * Search * B*

		B, a best-first search algorithm that finds the least-cost path from the root node to any goal node out of one or more possible goals. B was first published by Hans Berliner in 1977 ^[1], it is related to the A* search algorithm. There are things that must be found and things that must be known The value of a position, as calculated by the evaluation function, can’t be trusted unless it is confirmed by some kind of search. That is the “Raison d’être” of the quiescence search. If one replaces the quiescence by a full search with depth one, one gets a better value of this position. The deeper the search, the more reliable the evaluation. The reversal of this argument is to search further as long one can’t trust the backed up evaluation. This is the underlaying idea of B*.
Moonlit Beauties ^[2]

Multiple Values

Threats

Probability based Search

Two Step Search

Comparison: B* versus PVS

Rethinking PB*

Quality of Evaluation

Performance Considerations

Multiple Values

The first approach of this idea is to use three values to describe a position. First the classical static evaluation, and an upper and lower value of what can be achieved, a pessimistic and an optimistic value of the position. The closer these values converge the static evaluation, the better. But they are dependent - the pessimistic value for one player is the optimistic value of the opponent player.

Once separated the "risk factor" from the static evaluation, one can use the evaluation to drive the search. This first trial of B* was not successful. The "risk factor" was not well measured by a static function. The step was to go for a specific search for more reliable values.

Threats

One further idea is to consider threats to drive the search! Resulting from careful thought, one can measure an upper bound of a deep search by a null move search. You play, your opponent pass and you play again, and now do a normal search (alpha-beta or PVS). This is the threat detection used by Andrew James Palay on PB* ^[3] . The two values to drive the search are:

the evaluation issued from a standard search
and an optimistic value from a null move search

Probability based Search

The next major step in the development of PB* is not to use the raw optimistic value to drive the search, but a probability to get a target value. If you select the target value, as the value that will force a change in the best move at root, the probability to get the target value fit the probability that this move will be better than the one selected at root.

Once you evaluate a leaf node you propagate the value and the probability to the root node. As the search evolves, the target value change and the probability also evolve. When there is no hope to get the target, one can terminate the search. Now we can define two logical modes to select a move: The move with best real value and the move with best probability to get the target value (optimism). These two modes must be used alternatively by the two players; otherwise you just get no sense. (You reply to a sac with another sac and then another sac...).

Two Step Search

As we must take this alternate choice into account for both players, we are forced to implement a two phases search. In the first stage we put to use the optimism for the player (Select phase). In the second stage, the opponent exert his optimism (verify phase). In the select phase, the player tries to raise the value for moves not in the principal variation (PV). In the verify phase, the opponent tries to pull down the value of the principal variation (below the second best).

Comparison: B* versus PVS

In the principal variation search (PVS) we can also consider two steps. In the first, you try to exact the value of your principal variation doing a search with an open window. In the second step you just try to demonstrate that nothing is better doing a search with a closed window. In B* these steps are somehow inverted. The first select-phase tries to demonstrate there is nothing better than the PV. The second verify-phase tries to exact the principal variation.

Rethinking PB*

With a lot of abstraction we can think that B* is a search algorithm where some part of the tree search is saved in memory and another part is volatile and done on the fly. Tree values are propagated the “normal” way, which is following minimax. The selectivity is done on the tree in memory.

PB* is a minimax on top of standard alpha-beta or PVS. The rest of the algorithm is just the selectivity added to minimax to choose the node that deserve deeper search. If we disregard the selectivity and explore the tree on a systematic approach we get a brute force algorithm.

Quality of Evaluation

As PB is an algorithm driven by values, the question that emerges is how good this PB*'s evaluation should be? The two values that are used in PB* meet different tasks. The real value determine which move is considered better.

The optimistic value defines the probability that this move is better, and drives the search. The better the optimistic value, the more selective is the search. PB* is based largely in the fact that we can assess, with some reliability, the maximum/minimum value that the position can reach. The criterion of goodness of the optimistic value is the percentage of evaluation (real value) that are inside the optimistic pessimist range. As the evaluation is done by a PVS search,the deeper the PVS search the more readily we meet the criterion with closer values and better selectivity is achieved. A balance between the cost of each expands (depth of PVS evaluation) and the number of expansions needed (selectivity) must be adjusted. If we add a bonus in proportion to the risk taken on each hand (just to fit the criterion), we improve in tactical test set. But this reduce selectivity of the search as we encourage the search of sacs.

Somehow we split the dynamic factors of the position and the more long term (trustable) of the evaluation. The dynamics factors can be explored with a deeper PVS search or with some bonus/penalty on the optimistic evaluation for some tactical weakness (Berliner). The bonus approach get good performance on tactical set, but the deep search get better general result. End game positions require more in-depth search. A minimal number of expands is also required, this is why a fixed nodes approach for each PVS probe search get better overall performance.

Performance Considerations

Suppose there is a PB* program of a similar performance to PVS. For PB* the total number of PVS probe search is:

```
R * Moves * Expands * PVS(ProbeDepth)
```

with

```
Moves = average moves in the position.
R = ratio (average probes per moves from 1 to 2 ) ~1.5
Expands = number of expands
```

For a standard PVS:

```
(BranchFactor ^ PlyEquiv) * PVS(ProbeDepth)
```

The comparison becomes:

```
R * Moves * Expands <=> BranchFactor ^ PlyEquiv
```

A large branching factor favors PB*. PB* is weaker in end game position (low branching factor). PVS improves with BF and PB* reducing the number of expands needed (selectivity). Berliner reported that PB* (with 225 node expansions on average) get a similar performance than alpha-beta with a branching factor of 4.5

Implementations

B* and later PB* was implemented in HiTech. B*HiTech played the ACM 1993. C source code for first own experiments with B* Probability Search was posted by Antonio Torrecillas in CCC ^[4], further implemented in his experimental open source engine Rocinante written in C++ ^[5].

Publications

Hans Berliner (1977). The B* Tree Search Procedure: Best-first Search Combined with Branch and Bound. Computer Science Department. Carnegie Mellon University
Hans Berliner, Richard Greenblatt, Jacques Pitrat, Arthur Samuel, David Slate (1977). Panel on Computer Game Playing. 975-982 5. IJCAI 1977, pdf
Hans Berliner (1979). The B*-Tree Search Algorithm - A Best-First Proof Procedure. Artificial Intelligence, Vol. 12, No. 1, pp. 23-40. ISSN 0004-3702.
Andrew James Palay (1982). The B* Tree Search Algorithm - New Results. Artificial Intelligence, Vol. 19, No. 2, pp. 145-163.
Andrew James Palay (1983). Searching with Probabilities. Ph.D. thesis, Carnegie Mellon University
Hans Berliner, Chris McConnell (1995). B* Probability Based Search. Carnegie Mellon University Computer Science research report, Pittsburgh, PA, available as postscript
Heinz Herbeck (1995). Solving Chess Endgames using the B* Algorithm and the Rule Method. Abstract, CSGP Workshop, Chinese University Hongkong, May 1995.
Hans Berliner, Chris McConnell (1996). B* probability based search. Artificial Intelligence, Vol. 86, No. 1 pp. 97-156. ISSN 0004-3702.

Forum Posts

B* Probability Search (long) by Antonio Torrecillas, CCC, November 04, 2008
B* in QS by Harm Geert Muller, CCC, September 07, 2010
MCTS without random playout? by Antonio Torrecillas, CCC, January 01, 2012 » Monte-Carlo Tree Search

External Links

B* from Wikipedia
A* search algorithm from Wikipedia
Dijkstra's algorithm from Wikipedia
John Coltrane Quartet - My Favorite Things, Belgium, 1965, YouTube Video
McCoy Tyner, Elvin Jones, Jimmy Garrison, John Coltrane

References

^ Hans Berliner (1977). The B* Tree Search Procedure: Best-first Search Combined with Branch and Bound. Computer Science Department. Carnegie Mellon University
^ Moonlit Beauties by Luis Ricardo Falero, Oil on canvas, 19th century, Wikimedia Commons
^ Andrew James Palay (1983). Searching with Probabilities. Ph.D. thesis, Carnegie Mellon University
^ B* Probability Search (long) by Antonio Torrecillas, CCC, November 04, 2008
^ engine Rocinante is available by Antonio Torrecillas, CCC, August 12, 2009

What links here?

Page	Date Edited
Advances in Computer Chess 4	Jan 22, 2018
Aegon 1993	Mar 26, 2017
Algorithms	May 5, 2017
Andrew James Palay	Oct 9, 2012
Antonio Torrecillas	Mar 4, 2016
Asterisk	Mar 24, 2016
B*	Nov 27, 2017
Best-First	Dec 29, 2017
Brian Sheppard	Feb 6, 2017
CAPS	Dec 23, 2017
CC Sapiens	Oct 29, 2014
Chris McConnell	Jan 7, 2016
Hans Berliner	Jun 10, 2017
Heinz Herbeck	Feb 27, 2014
History	Jan 2, 2018
HiTech	Mar 31, 2018
Karlo Bala Jr.	Feb 19, 2017
Mathematician	Apr 9, 2018
MCαβ	Jan 28, 2018
Monte-Carlo Tree Search	Apr 26, 2018
Rocinante	Feb 19, 2018
Score	Apr 14, 2018
Search	Feb 1, 2018
Walter Faxon	Mar 6, 2015
WCCC 1992	Feb 26, 2018

Up one level

BCH Hashing

GerdIsenberg — Mon, 08 May 2017 12:01:51 GMT

Home * Search * Transposition Table * BCH Hashing

		BCH Hashing, a fast incremental Hash function to transform a board position into a number of a set length, quite similar to Zobrist Hashing. It was proposed by Tony Warnock and Burton Wendroff in 1988 ^[1], relying on BCH codes invented by Alexis Hocquenghem in 1959 ^[2], and independently by Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri in 1960 ^[3]. They used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (6412 - 228 + 4 + 8 + 1) bits, which is sufficient to avoid collisions within an 8 ply search. They stored 63 bits of the BCH signature as "lock" inside the table, and used 18 (or more) lower bits as index. Rainer Feldmann elaborates on BCH codes inside his thesis as well ^[4], and refers Elwyn Berlekamp's Algebraic Coding Theory* ^[5] .
Salvador Dalí - Metamorphosis of Narcissus, 1937 ^[6]

Quotes

Tony Warnock

Kathe and Dan Spracklen

Quotes

Tony Warnock

on Search Tables in Computer Chess ^[7] ^[8]:

The following paper describes a method of generating the numbers for a hash table. By using error correcting codes, we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a random set of numbers.

MacWilliams and Sloane's book on error correcting codes ^[9] has the glory details about the theory and programming.

Kathe and Dan Spracklen

excerpt from their Oral History ^[10] :

Well, first explain what a hash table is... You want to spread your positions out over a large data area so you need random numbers that will distribute a Chess position over, you know, a lot of different, you know, memory maps or memory locations. So BCH random numbers were something that some people had developed at the University of New Mexico. Those people had a Chess program. They wrote an article on it and ... I think it's three different people that developed it. Anyway, it's a coding scheme that gives the maximal distance between... Bit adjacent numbers so that you spread your positions over - more uniformly over the hash table area. They don't tend to bunch up as much that way. So, anyway, they wrote an article on how to do that and I had - in fact, I even got the book that they recommended and read it and figured it out how to do it because they didn't really tell you how to do it. They just said that they were using them and they were... So I tried it and, sure enough, they worked a lot better than the old method of getting random numbers.

Publications

Alexis Hocquenghem (1959). Codes correcteurs d'erreurs. Chiffres, Paris 2, pp. 147–156 (French)
Raj Chandra Bose, Dwijendra Kumar Ray-Chaudhuri (1960). On A Class of Error Correcting Binary Group Codes. Information and Control Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, pdf
Elwyn Berlekamp (1968). Algebraic Coding Theory. New York: McGraw-Hill. Revised ed., Aegean Park Press, (1984), ISBN 0894120638. amazon ^[11]
Jessie MacWilliams, Neil Sloane (1981). The Theory of Error-Correcting Codes. North-Holland Mathematical Library, amazon
Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1
Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf
Jean-Christophe Weill (1995). Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche. Ph.D. Thesis. Université Paris 8, Saint-Denis, zipped ps (French) ^[12]
J. P. Grossman, Levente Jakab (2004). Using the BCH construction to generate robust linear hash functions. Information Theory Workshop, 2004. IEEE

Postings

Re: Hash tables----Clash!!!-What happens next? by Tony Warnock, rgcc, March 17, 1994
Re: Hash functions for use with a transition table by Ronald de Man, rgcc, March 7, 1997
How gracefully do BCH codes degrade by Eb Oesch, Science Forum, math, May 20, 2008
Re: Overlapped Zobrist keys array by Rémi Coulom, CCC, October 06, 2009

External Links

BCH codes from Wikipedia
Berlekamp–Massey algorithm from Wikipedia
Berlekamp–Welch algorithm from Wikipedia
Coding theory from Wikipedia
Coding Theory by Andrew Thangaraj, Department of Electronics & Communication Engineering, Indian Institute of Technology Madras, YouTube Videos
Cyclic code from Wikipedia
Error detection and correction from Wikipedia
Finite field from Wikipedia
GF(2) from Wikipedia
Forward error correction from Wikipedia
MinT - Cyclic Codes (BCH-Bound)
Root of unity modulo n from Wikipedia
Hux Flux - Calculus, Cryptic Crunch, YouTube Video

References

^ Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1
^ Alexis Hocquenghem (1959). Codes correcteurs d'erreurs. Chiffres, Paris 2, pp. 147–156 (French)
^ Raj Chandra Bose, Dwijendra Kumar Ray-Chaudhuri (1960). On A Class of Error Correcting Binary Group Codes. Information and Control Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, pdf
^ Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf, BCH Codes at page 22 and page 145 (Appendix A)
^ Elwyn Berlekamp (1968). Algebraic Coding Theory. New York: McGraw-Hill. Revised ed., Aegean Park Press, (1984), ISBN 0894120638. amazon
^ Metamorphosis of Narcissus from Wikipedia
^ Re: Hash tables----Clash!!!-What happens next? by Tony Warnock, rgcc, March 17, 1994
^ Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1
^ Jessie MacWilliams, Neil Sloane (1981). The Theory of Error-Correcting Codes. North-Holland Mathematical Library, amazon
^ Gardner Hendrie (2005). Oral History of Kathe and Dan Spracklen. pdf from The Computer History Museum
^ CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications by Atri Rudra
^ Re: Overlapped Zobrist keys array by Rémi Coulom, CCC, October 06, 2009

What links here?

Page	Date Edited
Algorithms	May 5, 2017
BCH Hashing	May 8, 2017
Chess Game	Mar 28, 2017
Encoding Moves	Mar 27, 2016
Evaluation Hash Table	Dec 4, 2016
Excel	Dec 5, 2016
Fidelity	Jan 7, 2016
Hash Table	Jan 1, 2018
Incremental Updates	Sep 6, 2017
Lachex	Jan 7, 2016
Mathematician	Apr 9, 2018
Move List	Jul 19, 2017
Pawn Hash Table	Feb 1, 2018
Repetitions	Jan 16, 2018
Ronald de Man	Nov 20, 2017
Sargon	Dec 25, 2017
Shared Hash Table	Sep 11, 2017
Transposition Table	Apr 19, 2018
Zobrist Hashing	Jan 22, 2018

Up one Level

Best Move

GerdIsenberg — Mon, 15 May 2017 18:23:18 GMT

Home * Chess * Moves * Best Move

The Best Move is a Search related issue.

The Best Move in the context of search algorithms like Alpha-Beta or Principal Variation Search, is found at the root or any other confirmed PV-node. It is that move which gained the maximum score, which is exact since it exceeds alpha but is still below beta and therefor not good enough to refute opponent's previous move, which may become his best move and part of the principal variation as well.

Best so far

If an alpha increase occurs, the recently searched move is the best so far and needs to be stored on an explicit or implicit stack, which also might be the triangular PV-Table if available.

TT-Entry

After all remaining moves were searched at a PV-node, the best move found is stored inside the transposition table together with its associated values and flags.

PV-Table

If using a triangular PV-table to collect the principal variation, one has to store the best move (so far) anyway - immediately after an alpha increase occurs, to append the PV of ply + 1, which would otherwise void while searching further.

Cut-Node

At Cut-nodes, if a move fails high, it is not necessarily the best move, but a refutation move, good enough to refute opponents previous move. Since it is the best move found so far, in the context of transposition table, it is often flippant mentioned as best move as well.

All-Node

At All-nodes there is no best move found at all, despite all childs were considered if not pruned. While there is a maximum score in the arithmetical sense, all scores below or equal to alpha are upper bounds and not comparable to determine a best move.

Forum Posts

Best move statistics by Matthew Lai, CCC, September 12, 2016 » Search Statistics
Update Best Score and Best Move by Tamás Kuzmics, CCC, May 10, 2017

What links here?

Page	Date Edited
Alpha-Beta	Jan 28, 2018
Arminius	Aug 5, 2017
Best Move	May 15, 2017
BP	Jan 7, 2016
Brainfish	Oct 8, 2017
Chess 0.5	Nov 20, 2016
Clever & Smart	Jan 20, 2017
Crafty	Jan 28, 2018
Debugging	Jan 20, 2018
Encoding Moves	Mar 27, 2016
Fixafan	Oct 2, 2015
Hash Move	Oct 4, 2017
Houdini	Apr 14, 2018
Internal Iterative Deepening	Feb 5, 2018
Lachex	Jan 7, 2016
Last Best Reply	Jul 6, 2013
MChess	Feb 26, 2018
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Null Move	Aug 9, 2017
Paradise	Nov 19, 2014
Principal variation	Dec 4, 2017
PV-Move	Jan 16, 2013
Queen (engine)	Nov 3, 2014
Refutation Move	May 13, 2013
Refutation Table	Mar 27, 2015
Root	Sep 26, 2016
Score	Apr 14, 2018
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
SmarThink	Feb 2, 2018
The King	Jan 21, 2018
The Turk	Apr 1, 2017
Time Management	Mar 20, 2018
Transposition Table	Apr 19, 2018
Triangular PV-Table	Jun 12, 2017

Up one Level

Best-First

GerdIsenberg — Fri, 29 Dec 2017 21:09:36 GMT

Home * Search * Best-First

		Best-First Search is a state space search to traverse nodes of tree-like data structures (i. e. search trees) in breadth-first manner. It is usually implemented with a priority queue instead of the FIFO of breadth-first ^[1] , to expand the most promising node of one level first. Best-first turns a uninformed breadth-first into an informed search. Since all nodes of one level must be saved until their child nodes at the next level have been generated, the space complexity and memory requirement is proportional to the number of nodes at the deepest level. Best-first algorithms like A* are used for path finding in combinatorial search and puzzles. Iterative deepening is a technique to turn depth-first searches into best-first with the advantage space grows linear rather than exponential with increasing search depth, as applied for instance in IDA*.
Breadth-First Node order ^[2]

Two-Player

Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player zero-sum board game players with perfect information:

Publications

1980 ...

Judea Pearl (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley
Alexander Reinefeld, Tony Marsland, Jonathan Schaeffer (1985). Is Best First Search Really Best? Technical Report TR 85-16, Department of Computer Science, University of Alberta.
Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3
Anup K. Sen, Amitava Bagchi (1989). Fast Recursive Formulations for Best-First Search that allow Controlled use of Memory. IJCAI 1989, pdf

1990 ...

Steven Skiena (1990). Breadth-First and Depth-First Search. §3.2.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley
Richard Korf (1993). Linear-Space Best-First Search. Artificial Intelligence, Vol. 62, No. 1, pdf
Richard Korf, Max Chickering (1993). Best-first Minimax Search: First Results. AAAI'93
Weixiong Zhang, Richard Korf (1993). Depth-first vs. best-first search: New results. AAAI'93
Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1995). Best-First Fixed Depth Game Tree Search in Practice. IJCAI-95, Vol. 1, pdf
Richard Korf, Max Chickering (1996). Best-first minimax search. Artificial Intelligence, Vol. 84, Nos 1-2
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pdf
Ayumu Nagai, Hiroshi Imai (1999). Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation

2000 ...

2010 ...

Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, Chia-Hui Chang (2015). Job-Level Alpha-Beta Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 1

Forum Posts

Breadth-first search: revisiting by Sergei S. Markoff, CCC, September 13, 2011
Help with Best-First Select-Formula by Srdja Matovic, CCC, June 23, 2012
Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017 » Perft(15)

External Links

Best-first search from Wikipedia
Gunter Hampel Group + Jeanne Lee - The Capacity of this Room (1969), YouTube Video
Arjen Gorter, Willem Breuker, Pierre Courbois, Gunter Hampel, Jeanne Lee

References

What links here?

Page	Date Edited
Akihiro Kishimoto	Jan 22, 2018
Algorithms	May 5, 2017
Arachne	May 22, 2016
B*	Nov 27, 2017
Best-First	Dec 29, 2017
Centaur	Mar 24, 2017
Chia-Hui Chang	Jul 21, 2017
Conspiracy Numbers	Dec 29, 2017
David McAllester	May 23, 2016
Deniz Yuret	Aug 9, 2016
Depth-First	Jun 25, 2016
Dictionary	Aug 24, 2017
Diep	Jan 28, 2018
Fred Swartz	Jul 19, 2016
GambitVB	Oct 24, 2016
George Stockman	Jul 19, 2013
GPU	Dec 16, 2017
Hans Berliner	Jun 10, 2017
Ira Ruben	Jul 19, 2016
Iterative Deepening	Jun 23, 2017
Jack O’Keefe	Jul 19, 2016
Jay Scott	Dec 1, 2017
Joker NL	Sep 15, 2017
Mark Hersey	Jul 19, 2016
MCαβ	Jan 28, 2018
Memory	Dec 8, 2017
Mike Alexander	Jul 19, 2016
Minimax	Dec 29, 2017
Monte-Carlo Tree Search	Apr 26, 2018
NegaC*	Dec 17, 2016
Perft	Sep 26, 2017
Pioneer	Dec 23, 2017
Proof-number search	Jan 22, 2018
Repetitions	Jan 16, 2018
Richard P. Cochran	Mar 28, 2015
Rocinante	Feb 19, 2018
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
Sharky	Jan 7, 2016
Space-Time Tradeoff	Jun 17, 2015
SSS* and Dual*	Jan 22, 2018
Strategy	Jan 18, 2018
Ting-Han Wei	Jul 19, 2017
Trajectory	Jan 3, 2015
Victor Berman	Jul 19, 2016
William Toikka	Aug 12, 2016
Zeta	Apr 11, 2017

Up one Level

Beta

GerdIsenberg — Sat, 29 Jan 2011 15:33:59 GMT

Home * Search * Score * Beta

β		Beta (β) is the upper bound of a score for the node. If the node value exceeds or equals beta, it means that the opponent will avoid this node, since his guaranteed score (Alpha of the parent node) is already greater. Thus, Beta is the best-score the opponent (min-player) could archive so far - in a Negamax framework from max-players point of view, where beta is the negated value of alpha from the parent node. If a beta-cutoff occurs on the upper bound of a Cut-Node given by Beta, the value returned is a lower bound.

External Links

What links here?

Page	Date Edited
ABDADA	Aug 30, 2017
Alpha	Mar 11, 2012
Alpha-Beta	Jan 28, 2018
Best Move	May 15, 2017
Beta	Jan 29, 2011
Beta-Cutoff	Oct 22, 2017
Bound	Jan 25, 2017
Check	Feb 1, 2018
Chess 0.5	Nov 20, 2016
Dictionary	Aug 24, 2017
Enhanced Forward Pruning	Oct 21, 2014
Fail-Hard	Dec 2, 2014
Fail-Soft	Jun 2, 2017
Futility Pruning	Aug 30, 2017
Horizon Node	Sep 13, 2016
Lazy Evaluation	Sep 1, 2017
Mate Threat Extensions	Apr 14, 2012
Mini Chess	Jun 7, 2013
Multi-Cut	Jul 4, 2016
Naum	Nov 23, 2017
Null Move Pruning	Dec 2, 2017
Null Window	Nov 8, 2016
Onno	Jul 19, 2013
Principal Variation Search	Oct 22, 2017
Quiescence Search	Aug 19, 2017
Quiescent Node	Feb 10, 2017
Reverse Futility Pruning	Jun 2, 2017
Supra	Jul 24, 2016
Upper Bound	Jan 24, 2017
Window	Jun 7, 2017
Winter	Jan 23, 2018

Up one Level

Beta-Cutoff

GerdIsenberg — Sun, 22 Oct 2017 08:08:33 GMT

Home * Search * Alpha-Beta * Beta-Cutoff

		A beta-cutoff occurs in the alpha-beta algorithm, if the score backed up by the search is greater than or equal to beta and fails high. No further moves need to be searched, since one refutation is already sufficient to avoid the move that led to this node or position. Nodes, where a beta-cutoff occurs are then cut-nodes where move ordering was crucial to try the refutation move as early as possible - typically as first move in 90 to 95 per cent of all cases. In max versus min alpha-beta a beta-cutoff can only occur for the max-player, while the min-player cuts if below or equal alpha, called alpha-cutoff. Since the common negamax implementation makes both players maximizers, negamax alpha-beta has beta-cutoffs exclusively for both players.
Cut-off ^[1]

Shallow or Deep

A shallow cutoff occurs if the window was narrowed at the parent node, that is, reduced current beta. A deep cutoff occurs if the window was narrowed closer to the root with an odd ply-distance of at least three to the current node. Deep cutoffs were sometimes omitted in early chess programs if not passing alpha through the recursive call ^[2].


Shallow Cutoff if α >= β		Deep Cutoff if α >= β ^[3]

Forum Posts

cut nodes by Folkert van Heusden, CCC, October 18, 2017 » Cut-Nodes

External Links

cutoff - Wiktionary
cut off - Wiktionary
Cutoff from Wikipedia
Cut-off from Wikipedia
Muhsinah - Cut Off, Track 2 on the EP "M", 2014, YouTube Video

References

^ A Biker's vintage cut-off adorned with club badges, Image by Bullenwächter, December 12, 2004, Cut-off from Wikipedia, Wikimedia Commons
^ Re: What the computer chess community needs to decide by Harm Geert Muller, CCC, February 11, 2011
^ Modified images from Matthew L. Ginsberg, Alan Jaffray (2002). Alpha-Beta Pruning Under Partial Orders. in Richard J. Nowakowski (ed.) More Games of No Chance. Cambridge University Press, pdf

What links here?

Page	Date Edited
Alpha-Beta	Jan 28, 2018
Belle	Jan 18, 2018
Beta	Jan 29, 2011
Beta-Cutoff	Oct 22, 2017
Countermove Heuristic	Oct 1, 2017
Debugging	Jan 20, 2018
Dictionary	Aug 24, 2017
Encoding Moves	Mar 27, 2016
Enhanced Forward Pruning	Oct 21, 2014
Enhanced Transposition Cutoff	May 19, 2017
Fail-High	Oct 22, 2017
Fixafan	Oct 2, 2015
Genie	Feb 7, 2016
Hash Move	Oct 4, 2017
History Heuristic	Jul 19, 2017
Horizon Node	Sep 13, 2016
Hrafn Eiríksson	Jan 8, 2014
Integrated Bounds and Values	Jan 13, 2013
KC Chess	Jan 28, 2012
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
Komodo	Mar 6, 2018
Mate Killers	Feb 4, 2017
Mater	Apr 26, 2016
Multi-Cut	Jul 4, 2016
Node Types	Oct 22, 2017
Null Move Pruning	Dec 2, 2017
Parallel Search	Dec 30, 2017
Principal Variation Search	Oct 22, 2017
Quiescent Node	Feb 10, 2017
Recursion	Nov 18, 2017
Relative History Heuristic	Jun 8, 2015
ROCE	Jun 6, 2017
Search Tree	Dec 23, 2016
Sierżant	Apr 15, 2014
Supra	Jul 24, 2016
Usurpator	Jul 30, 2017
Young Brothers Wait Concept	Apr 22, 2018
Ziggy IS	Sep 6, 2015

Up one Level

Botvinnik-Markoff Extension

GerdIsenberg — Fri, 27 Nov 2015 19:08:39 GMT

Home * Search * Selectivity * Extensions * Botvinnik-Markoff Extension

The Botvinnik-Markoff Extension is an extension proposed by Sergei Markoff ^[1], inspired by Mikhail Botvinnik's work and publications on the program Pioneer, for instance to determine attack/defense targets for further analysis of attack/defense trajectories ^[2]. The extension is based on the threat move detection in null move pruning. If the threat move is the same on two consecutive plies (with one ply in between them to account for the side to move), the threat move is a serious one and the search is extended.

Forum Posts

Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner by Walter Faxon, CCC, June 09, 2003
The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003, introducing the extension
Test match with the Botvinnik-Markoff extension by Tord Romstad, CCC, October 02, 2003
What is Botvinnik-Markov extension? by Maurizio Monge, CCC, October 26, 2005
Botvinnik Markov revisited by Don Dailey, CCC , Jun 24, 2010

References

^ The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003
^ Mikhail Botvinnik (1982). Decision Making and Computers. Advances in Computer Chess 3

What links here?

Page	Date Edited
Botvinnik-Markoff Extension	Nov 27, 2015
Critter	Jan 25, 2014
Extensions	Apr 19, 2018
Mate Threat Extensions	Apr 14, 2012
Maurizio Monge	Nov 27, 2015
Mikhail Botvinnik	Jul 15, 2017
Null Move	Aug 9, 2017
Null Move Pruning	Dec 2, 2017
Selectivity	Jan 12, 2018
Sergei Markoff	Mar 12, 2018
SmarThink	Feb 2, 2018
Texel	Oct 9, 2017
Threat Move	Sep 10, 2017
Trajectory	Jan 3, 2015

Up one level

Bound

GerdIsenberg — Wed, 25 Jan 2017 22:40:15 GMT

Home * Search * Score * Bound

A Bound is a limit imposed on a node value, beyond which changes of the value have no effect on the shape of the search tree.

Forum Posts

Alpha beta fail soft, pruning & hash bounds? by Steve Maughan, CCC, December 14, 2000 » Fail-Soft, Pruning
Using just Upperbounds and Lowerbounds by Alvaro Jose Povoa Cardoso, CCC, February 01, 2001 » Upper Bound, Lower Bound
bound type in PVS ? by Mahmoud Uthman, CCC, January 23, 2017 » Principal Variation Search

External Links

Bound from Wikipedia
Upper and lower bounds from Wikipedia
Branch-and-bound from Wikipedia
Kraan - Overseas Bound (1975), YouTube Video

What links here?

Page	Date Edited
Alpha	Mar 11, 2012
Alpha-Beta	Jan 28, 2018
Alvaro Cardoso	Jan 12, 2018
Aspiration Windows	Nov 1, 2017
Beta	Jan 29, 2011
Betsabe	Jul 23, 2017
Bound	Jan 25, 2017
Crafty	Jan 28, 2018
DayDreamer	Aug 22, 2016
Deep Learning	Feb 12, 2018
Dictionary	Aug 24, 2017
Djinn	Feb 8, 2016
Dynamic Tree Splitting	Apr 10, 2017
Endgame Tablebases	Mar 6, 2018
Fail-Hard	Dec 2, 2014
Fail-Soft	Jun 2, 2017
GiuChess	May 8, 2017
Integrated Bounds and Values	Jan 13, 2013
Interior Node Recognizer	Mar 12, 2018
KC Chess	Jan 28, 2012
Lower Bound	Jan 24, 2017
Mate Distance Pruning	Jun 2, 2017
Multi-Cut	Jul 4, 2016
NegaC*	Dec 17, 2016
NegaScout	Jul 6, 2016
Neural Networks	Mar 12, 2018
Node Types	Oct 22, 2017
Nuchess	Apr 3, 2017
Pawn Endgame	Oct 11, 2017
Principal Variation Search	Oct 22, 2017
Pruning	Jan 1, 2018
Score	Apr 14, 2018
Soldat	Aug 20, 2017
Steve Maughan	Jan 31, 2018
Upper Bound	Jan 24, 2017
Window	Jun 7, 2017
Young Brothers Wait Concept	Apr 22, 2018

Up one Level

Branching Factor

GerdIsenberg — Wed, 28 Jun 2017 21:36:12 GMT

Average Branching Factor

Effective Branching Factor

Mean Branching Factor

Home * Search * Tree * Branching Factor

Average Branching Factor

In chess, in average there are about 35-38 moves per position. One additional cycle of growth expands each leaf so far accordantly. This is called the average branching factor of the game tree.

Effective Branching Factor

The effective branching factor (EBF), related to iterative deepening of depth-first search, is conventionally defined as average ratio of nodes (or time used) revisited of the current iteration N versus the previous iteration N-1 ^[1].

In pure Minimax, the effective branching factor is equal to the average branching factor
In Alpha-Beta, assuming good move ordering, the branching factor is reduced to about square root of the average branching factor ^[2]^[3]
Alpha-beta enhancements, transposition tables, null move pruning and late move reductions further reduce the EBF below three, strong programs even near or below two ^[4]

EBF(N-1) ::= nodes(N-1) / nodes(N-2)
EBF(N)   ::= nodes(N)   / nodes(N-1)

Due to the odd-even effect of Alpha-Beta as described by Michael Levin's Theorem, this is lower if 'N' is even, and higher if 'N' is odd. Due to extensions, reductions and various pruning techniques, this odd-even effect is diminishing accordantly. One may also use the square root of the ratio of two odd or even iterations.

EBF ::= sqrt(nodes(N) / nodes(N-2));

However, with all kind of extensions, reductions, and forward pruning applied to the tree, it is not at all clear that the average branch is searched precisely one ply deeper at iteration N+1 than at iteration N, which makes such an effective branching factor quite useless to compare between programs ^[5], despite some programs even perform ID depth increments of fractions of one ply.

Mean Branching Factor

Steven Edwards made following reasonable proposal of a Mean Branching Factor ^[6]:

MBF ::= count of all nodes / count of non terminal nodes

Publications

Gérard M. Baudet (1978). On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10
Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8

Forum Posts

1997 ...

branching factor question by vince, rgcc, June 04, 1997
Please, say in few words what can reduce the "branching factor" by Leonid, CCC, September 19, 1999

2000 ...

Branching factor, make me confuse more that ever by Leonid, CCC, April 01, 2000
Definition of branching factor? by Severi Salminen, CCC, January 30, 2001
Branching Factor = q/p ? by Matthias Gemuh, CCC, November 23, 2001
Measured min-max branching factor by James Swafford, CCC, October 17, 2002
What's best low BF or good WAC result? by Albert Bertilsson, CCC, March 18, 2003
PVS and MTD(f) branching factor by Russell Reagan, CCC, June 17, 2003 » PVS, MTD(f)
Improvements in BF makes my MoveGen suck =( by Albert Bertilsson, CCC, June 26, 2003 » Move Generation
To Ed: Branching factor formula in Rebel 12 by Federico Corigliano, CCC, August 15, 2003 » Rebel
Question about evaluation and branch factor by Marcus Prewarski, CCC, November 20, 2003 » Evaluation

2005 ...

iterative deepening and branching factor by J. Wesley Cleveland, CCC, July 09, 2007 » Iterative Deepening
Calculation of branching factor by PK-4, CCC, March 23, 2008

2010 ...

effective branching factor of chess programs by Uri Blass, CCC, December 21, 2010
EBF question by Clemens Pruell, CCC, February 01, 2011
EBF definition problem in chess wiki by Daniel Shawul, CCC, May 13, 2011
Node counts at a given depth/iteration in search by BB+, OpenChess Forum, May 23, 2011
Bigger steps when branching factor < 2? by Marcel van Kervinck, CCC, November 05, 2011 » Iterative Deepening
Branching Factor of top engines by Kai Laskos, CCC, June 15, 2013 » Houdini 3, Stockfish 3, Komodo 5 CCT, Shredder 6
Some fun with Komodo 8 by Kai Laskos, CCC, September 23, 2014 » Komodo 8

2015 ...

High branching factor when mate score is found by Sander Maassen vd Brink, CCC, March 16, 2017

External Links

Branching factor from Wikipedia
Combinatorial explosion from Wikipedia
Branching Factor from FGRL by Andreas Strangmüller
Led Zeppelin - How Many More Times (Danish TV 1969) , YouTube Video

References

^ EBF definition problem in chess wiki by Daniel Shawul, CCC, May 13, 2011
^ Gérard M. Baudet (1978). On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10
^ Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8
^ Branching Factor of top engines by Kai Laskos, CCC, June 15, 2013 » Houdini 3, Stockfish 3, Komodo 5 CCT, Shredder 6
^ Re: Calculation of branching factor by Tord Romstad, March 28, 2008
^ Re: Calculation of branching factor by Steven Edwards, March 27, 2008

What links here?

Page	Date Edited
Albert Bertilsson	Jun 6, 2017
Amazons	Aug 12, 2017
Andreas Strangmüller	May 15, 2017
Arimaa	Jan 4, 2017
B*	Nov 27, 2017
Backgammon	Dec 22, 2017
Branching Factor	Jun 28, 2017
Brute-Force	Jul 27, 2017
Chess	Jan 21, 2018
Dave Gomboc	May 6, 2015
Depth	Feb 25, 2018
Dictionary	Aug 24, 2017
Enigma	Feb 9, 2015
Evaluation	Feb 1, 2018
Federico Andrés Corigliano	Feb 13, 2014
Fixafan	Oct 2, 2015
Fruit	Sep 27, 2016
Gerhard Trippen	Jun 8, 2015
Hans Berliner	Jun 10, 2017
Iterative Deepening	Jun 23, 2017
Kai Laskos	Jan 21, 2018
Komodo	Mar 6, 2018
Late Move Reductions	Sep 25, 2017
Leonid Liberman	May 23, 2015
Lines of Action	Feb 5, 2018
LL Chess	May 23, 2015
Marcus Prewarski	May 18, 2016
Mark Watkins	Dec 6, 2017
Matthias Gemuh	Jan 21, 2018
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Node Types	Oct 22, 2017
Odd-Even Effect	May 19, 2017
Parallel Search	Dec 30, 2017
Pawn Endgame	Oct 11, 2017
Playing Strength	Mar 31, 2018
Promotions	Jun 6, 2017
Proof-number search	Jan 22, 2018
Quote McCarthy	Sep 10, 2013
Ryan Hayward	Dec 29, 2017
Search Explosion	Mar 30, 2017
Search Statistics	Jan 16, 2018
Search Tree	Dec 23, 2016
Severi Salminen	May 7, 2015
Sharper	Jun 6, 2017
Shogi	Feb 19, 2018
Singular Extensions	Jan 9, 2018
Sunsetter	Jun 1, 2017
Time Management	Mar 20, 2018
Type A Strategy	Jul 30, 2010

Up one Level

Butterfly Heuristic

GerdIsenberg — Fri, 06 May 2016 20:31:11 GMT

Home * Search * Move Ordering * Butterfly Heuristic

		The Butterfly Heuristic is a dynamic move ordering method based on the number of trials of a given move inside the search, irrespectively from the position in which the move has been made, and in opposition to the History Heuristic, irrespectively whether a move fails high or not.
Butterfly and Chinese wisteriaflowers ^[1]

Thought Experiment

The Butterfly Heuristic was proposed by Dap Hartmann in conjunction with so called Butterfly Boards as a pure thought experiment ^[2] :

No experiments with real game trees in an actual chess-playing programs have been carried out. The main reason for not doing so lies in the author's notion that this method will be far less effective than the History Heuristic ^[3]. Still, the main idea of this thought experiment is worth presenting.

Persistence

Another utilization of Butterfly Boards, as proposed by Hartmann, was to make them persistent, initialized by moves from many Grandmaster and/or Correspondent chess games ^[4] ^[5] . Mark Winands at al. assimilated both, Schaeffer's History Heuristic combined with Hartmann's Butterfly Heuristic, and introduced the Relative History Heuristic ^[6]

Publications

Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
Dap Hartmann (1987). How to Extract Relevant Knowledge from Grandmaster Games. Part 1: Grandmasters have Insights - the Problem is what to Incorporate into Practical Problems. ICCA Journal, Vol. 10, No. 1
Dap Hartmann (1987). How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater. ICCA Journal, Vol. 10, No. 2
Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2006). The Relative History Heuristic. CG 2006, pdf

External Links

Butterfly from Wikipedia
Heuristic from Wikipedia
Flora Purim - Butterfly Dreams (1973), YouTube Video
Joe Henderson, George Duke, David Amaro, Ernie Hood, Stanley Clarke, Airto Moreira

References

^ by Xü Xi (c.886–c.975), painted around 970 during the early Song Dynasty, Butterfly from Wikipedia
^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
^ Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
^ Dap Hartmann (1987). How to Extract Relevant Knowledge from Grandmaster Games. Part 1: Grandmasters have Insights - the Problem is what to Incorporate into Practical Problems. ICCA Journal, Vol. 10, No. 1
^ Dap Hartmann (1987). How to Extract Relevant Knowledge from Grandmaster Games. Part 2: the Notion of Mobility, and the Work of De Groot and Slater. ICCA Journal, Vol. 10, No. 2
^ Mark Winands, Erik van der Werf, Jaap van den Herik, and Jos Uiterwijk (2006). The Relative History Heuristic. CG 2006, pdf

What links here?

Page	Date Edited
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Countermove Heuristic	Oct 1, 2017
Dap Hartmann	Jun 10, 2017
Dappet	Dec 12, 2016
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
Killer Heuristic	Sep 14, 2017
Mark Winands	Sep 19, 2017
Move Ordering	Feb 27, 2018
Relative History Heuristic	Jun 8, 2015

Up one Level

Check Extensions

GerdIsenberg — Thu, 19 Apr 2018 19:10:51 GMT

Home * Search * Selectivity * Extensions * Check Extensions

Check Extensions have two distinct forms: one of them extends when giving check, the other - when evading it. In each case, typical depth to extend is one ply. The reason behind check extension is that we are in a forcing sequence, so that it is desirable to know its outcome with more certainty, and the number of replies to check is limited, so we do not have to be afraid of a search explosion. Also, not extending checks may easily lead to the horizon effect, delaying the threat so far that the program cannot see it. However, some programmers don't extend checks (and captures) with negative SEE or even reduce them. Robert Hyatt claimed a significant gain in Crafty by doing so ^[1] ^[2].

If a program does not consider checks in the quiescence search, then we should take care that it does not enter it while in check. This is also a form of check extension ^[3]. In its most straightforward form, check extension is implemented in TSCP.

Forum Posts

2000 ...

Check Extension by Martin Bauer, CCC, January 03, 2003
What's best low BF or good WAC result? by Albert Bertilsson, CCC, March 18, 2003 » Win at Chess
Buggy check extensions, back to square one =(. by Albert Bertilsson, CCC, March 20, 2003
check extention explosion by Aivaras Juzvikas, CCC, April 03, 2004 » Search Explosion
Checks in QSearch by Dan Honeycutt, Winboard Programming Forum, November 23, 2004 » Checks in Quiescence Search

2005 ...

hashing, check extensions and depth by Mike Adams, CCC, May 27, 2007
Revisiting Check Extensions by Mark Lefler, CCC, June 07, 2007
checks in q-search by Robert Hyatt, CCC, September 02, 2008
check extension by Andrew Short, CCC, August 07, 2008
check extensions by Robert Hyatt, CCC, October 28, 2008
Check extension by Harm Geert Muller, CCC, April 09, 2009

2010 ...

Problem with exploding tree because of extensions by Oliver Brausch, CCC, January 05, 2010
Problems when implementing checks in qsearch by Luca Hemmerich, CCC, February 03, 2010 » Checks in Quiescence Search
Spite checks by Harm Geert Muller, CCC, May 13, 2014
Pointless delays by Harm Geert Muller, CCC, July 25, 2014

2015 ...

Check-extension in QS by Harm Geert Muller, CCC, April 03, 2015 » Checks in Quiescence Search
Is a Check Extension Really a Win? by Steve Maughan, CCC, May 15, 2015
Spite checks, again by Harm Geert Muller, CCC, October 23, 2016
Starting with check extensions by Luis Babboni, CCC, February 28, 2017
Check Extensions by David Cimbalista, CCC, March 02, 2017
Check extension vs LMR by Harm Geert Muller, CCC, April 04, 2017 » LMR
Depth extensions and effect on transposition queries by Kenneth Jones, CCC, April 16, 2018 » Transposition Table

External Links

Extension Techniques in REBEL (checks) from Programmer Corner by Ed Schröder
Check extension from Bruce Moreland's Programming Topics

References

^ Re: move count based pruning by Robert Hyatt, CCC, September 04, 2010
^ search extensions by Robert Hyatt, CCC, November 08, 2014
^ checks in q-search by Robert Hyatt, CCC, September 02, 2008

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Alarm	Jun 7, 2017
Albert Bertilsson	Jun 6, 2017
Amoeba	Mar 19, 2018
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Andscacs	Jan 16, 2018
Atlas (ESP)	Jan 28, 2018
Bagatur	Sep 10, 2016
Betsabe	Jul 23, 2017
Bills Bare Bones Chess	Nov 19, 2015
Bobcat	Jun 27, 2017
Brainless	Jun 24, 2017
Brainstorm	Jun 24, 2017
Bringer	Jul 14, 2014
Capture (program)	Jan 8, 2016
Capture Extensions	Oct 26, 2012
Carballo	Oct 2, 2016
Check	Feb 1, 2018
Check Extensions	Apr 19, 2018
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
Chess Guru	Mar 4, 2017
Chess Wizard	Dec 22, 2014
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Clarabit	Nov 3, 2011
Claudia	Jun 1, 2016
Clubfoot	Sep 8, 2015
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
Crafty	Jan 28, 2018
Cumulus	Jan 7, 2016
Cupcake	May 19, 2016
DanaSah	Oct 9, 2017
Depth	Feb 25, 2018
Diablo	May 17, 2016
Discovered Check	Feb 1, 2018
Djinn	Feb 8, 2016
Dorpsgek	Apr 2, 2018
Double Check	Apr 4, 2013
DrunkenMaster	Nov 1, 2016
Duck	Dec 12, 2016
Dumb	Mar 10, 2018
Échec	Jan 7, 2016
Encoding Moves	Mar 27, 2016
Ethereal	Mar 20, 2018
Eveann	Apr 3, 2017
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Faile	May 27, 2014
Falcon	Sep 2, 2016
FCP	Jun 15, 2013
Ferret	Jan 7, 2016
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Fortress (Engine)	Oct 19, 2017
Garbochess-JS	Sep 23, 2017
Gerbil	Feb 3, 2017
GES	Sep 13, 2015
Gibbon	Dec 23, 2014
Gideon	Feb 26, 2018
Gk	Oct 9, 2017
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Greko	Feb 27, 2018
HAL	Jun 14, 2016
HaQiKi D	Jul 26, 2017
Harm Geert Muller	Mar 31, 2018
HeavyChess	Feb 14, 2014
Horizon	Mar 17, 2013
Horizon Effect	Sep 10, 2017
Ifrit	Feb 7, 2016
Insomniac	Jan 27, 2016
ISA	Apr 2, 2018
Jabba	Sep 10, 2016
Jazz	Oct 4, 2017
JikChess	Nov 29, 2015
Kholin	Jan 3, 2018
KingSlayer	Oct 17, 2016
KnockOut	Sep 20, 2016
Lachex	Jan 7, 2016
Laser	Dec 27, 2017
Late Move Reductions	Sep 25, 2017
Mark Lefler	Nov 23, 2017
Martin Bauer	Apr 3, 2013
Marvin	Feb 10, 2018
Matador	Oct 30, 2015
Matant	Aug 14, 2013
Matilde	Jan 1, 2014
MChess	Feb 26, 2018
Meep	Sep 4, 2016
Move Ordering	Feb 27, 2018
Movei	Jan 7, 2016
Murka	Nov 11, 2016
Muse	May 17, 2016
Nemorino	Dec 21, 2017
NoraGrace	Nov 23, 2014
Now	Jan 7, 2016
Obender	Apr 17, 2016
OliThink	May 19, 2017
One Reply Extensions	Dec 31, 2014
Par Excellence	Mar 23, 2014
Path-Dependency	Oct 16, 2017
Patzer (K)	Jul 18, 2012
Pepito	Nov 27, 2014
Plisk	Dec 31, 2014
PolarChess	May 15, 2017
Popochin	Feb 5, 2016
Prédateur	Nov 11, 2016
ProChess IT	Sep 30, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Pulsar	May 4, 2017
Rajah	Sep 12, 2012
Recapture Extensions	Feb 2, 2013
RedQueen	Nov 13, 2017
Robocide	May 11, 2016
RuyDos	Feb 17, 2018
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
SCP	Jun 16, 2016
Search Explosion	Mar 30, 2017
Selectivity	Jan 12, 2018
SharpChess	Jun 6, 2017
Sharper	Jun 6, 2017
Shield	May 17, 2017
Sierżant	Apr 15, 2014
Singular Extensions	Jan 9, 2018
Sinobyl	Jul 3, 2014
Sjaak (Glebbeek)	Oct 4, 2017
Sloppy	Sep 17, 2016
Slow Chess	May 17, 2016
Smash	May 11, 2016
Soldat	Aug 20, 2017
SOS	Apr 5, 2017
Spector	Nov 11, 2016
Spike	Jan 7, 2016
Stockfish	Apr 7, 2018
Tactics	Jan 12, 2018
Tao	Jan 8, 2016
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The King	Jan 21, 2018
Thor's Hammer	Nov 23, 2013
Tornado	Dec 14, 2017
Touch	Dec 12, 2016
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vajolet	Jan 25, 2018
Vice	Mar 8, 2016
Wappler	Jan 22, 2013
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
Wing	Oct 26, 2017
Witz	Nov 14, 2017
WyldChess	Mar 10, 2018
Xpdnt	Sep 13, 2015
Y!	Sep 10, 2017
Zeus RU	Jun 6, 2015

Up one Level

Cilk

GerdIsenberg — Mon, 28 Oct 2013 21:56:12 GMT

Parallel Chess

Cilk-5 Linguistic Extensions

Home * Programming * Languages * Cilk

Cilk (pronounced "silk") is a C-based, general-purpose programming language designed for multithreaded parallel computing. Cilk started as in the mid 90s as a project at the Supertech research group in the MIT Labroratory headed by Charles E. Leiserson. Important milestones in Cilk technology include the original Cilk-1, which provided a provably efficient work-stealing runtime support but little linguistic support, the later Cilk-5, which provided simple linguistic extensions for multithreading to ANSI C, the commercial Cilk++ by Cilk Arts, which extended the Cilk model to C++, and after Intel acquired Cilk Arts in 2009, Intel Cilk Plus. In November 2010, Intel published a language and an ABI specification to enable other compilers to implement Cilk Plus ^[1].

Parallel Chess

Cilk's testbeds in the 90s were chess programs using a parallel search. *Socrates used the Jamboree algorithm to search game trees in parallel and uses the Cilk 1.0 language and run-time system to express and to schedule the computation. CilkChess was written using the Cilk-5 linguistic extensions.

Cilk-5 Linguistic Extensions

Cilk-5.4.6 is the latest official MIT Cilk released under the GNU General Public License ^[2].

The keyword "cilk" defines a function which can spawned as a new thread, by using the "spawn" keyword. A cilk procedure cannot safely return values of the children it has spawned until it executes a "sync" statement, which acts like a local barrier. Inlets, a kind of local function with access to local variables of its parent frame, are used to return values to its parent with the option to abort all of the already spawned descendants of the procedure to terminate immediately. Inlets are guaranteed to operate atomically with regards to each other and to the parent procedure, thus avoiding the bugs that could occur if the multiple returning procedures tried to update the same variables in the parent frame at the same time.

Parallel Alpha-Beta

This is how an alpha-beta search routine was implemented with Cilk-5 ^[3], using the five keywords cilk, spawn, sync, inlet and abort:

cilk int search( position *prev, int move, int depth ) {
   position cur; int bestscore = -oo, num_moves, mv, sc, cutoff = false;
 
   inlet void catch( int child_sc ) {
      child_sc = -child_sc; /* negamax */
      if ( child_sc > bestscore ) {
         bestscore = child_sc;
         if ( child_sc > cur.alpha ) {
            cur.alpha = child_sc;
            if ( child_sc >= cur.beta ) { 
               cutoff = true;
               abort;
            }
         }
      }
   } /* end inlet */
 
   /* create current position and set up for search */
   make_move( prev, move, &cur );
   if ( depth <= 0 ) return eval( &cur );
   cur.alpha = -prev->beta;  /* negamax */
   cur.beta  = -prev->alpha;
   num_moves = gen_moves( &cur );
 
   /* search the moves */
   for ( mv = 0; !cutoff && mv < num_moves; mv++) {
      catch ( spawn search( &cur, mv, depth-1 ) );
      if ( mv == 0 ) sync; /* young brothers wait */
   }
   sync; /* this sync is outside the loop so that
            older brothers execute in parallel */
   return bestscore;
}

Quote

by Vincent Diepeveen after WCCC 1999 ^[4]:

Actually the big professor who has written so many books that i have in my possession was there too: Leiserson. Lucky i could exchange a few words during the game with him.

Cilk really is a very promising language. In contradiction to all my big efforts to parallellize DIEP, writing in Cilk this goes a lot simpler. Regrettably when starting the parallel version of DIEP, there was no port of CILK to windows (the first demand for something is that it must work both in windows and linux before i can use it; interface is of course something different) otherwise i might have done better in paderborn.

Anyone who still must start his parallel project here gets a free tip from me:
Don't go fiddle with difficult parallellization, simply use CILK, let that language handle the parallellism and keep only busy making a good program!

The alternative to Cilk is years of bugfixing the parallel code.

Talking Cilk at WCCC 1999: Vincent Diepeveen, Don Dailey and Charles Leiserson

Cilk++

MIT licensed Cilk technology to Cilk Arts, Inc., a venture-funded start-up founded by Charles Leiserson and Matteo Frigo. Cilk Arts developed Cilk++, a quantum improvement over MIT Cilk, which includes full support for C++, parallel loops, and superior interoperability with serial code.

Intel Cilk Plus

In July 2009 Intel Corporation acquired Cilk Arts ^[5] ^[6]. Intel Cilk Plus adopts simplifications, proposed by Cilk Arts in Cilk++, to eliminate the need for several of the original Cilk keywords while adding the ability to spawn functions and to deal with variables involved in reduction operations. Intel Cilk Plus differs from Cilk and Cilk++ by adding array extensions, being incorporated in a commercial compiler, and compatibility with existing debuggers ^[7].

Publications

^[8]

Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou (1995). Cilk: An Efficient Multithreaded Runtime System Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) Santa Barbara, California Pg. 207–216, pdf
Philip Andrew Lisiecki (1996). Macro-Level Scheduling in the Cilk Network of Workstations Environment, Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, pdf
Christopher F. Joerg (1996). The Cilk System for Parallel Multithreaded Computing. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, pdf
Matteo Frigo, Charles E. Leiserson, Keith H. Randall (1998). The Implementation of the Cilk-5 Multithreaded Language. Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, Montreal, Quebec, Canada, Pg 212–223, pdf
Don Dailey, Charles E. Leiserson (2001). Using Cilk to Write Multiprocessor Chess Programs, Advances in Computer Games 9, pdf
Vivek Sarkar (2008). Shared-Memory Parallel Programming with OpenMP. Rice University, slides as pdf
Matteo Frigo, Pablo Halpern, Charles E. Leiserson, Stephen Lewin-Berlin (2009 ). Reducers and Other Cilk++ Hyperobjects. Cilk Arts, Inc., pdf
Milind Chabbi (2010). Cilk and Cilk++ Multithreaded Languages. pdf
John Mellor-Crummey (2011). Shared-memory Parallel Programming with Cilk. Rice University, slides as pdf

Manuals

Cilk 5.4.6. Reference Manual (pdf)
Intel® Cilk™ Plus Language Specification (pdf)

Forum Posts

Cilk++ by Gerd Isenberg, CCC, August 30, 2009

External Links

Cilk from Wikipedia
The Cilk Project from MIT
Intel Cilk Plus from Wikipedia
Intel® Cilk™ Plus Specification - Intel® Software Network
Commercializing MIT's Cilk Project by Charles Leiserson, YouTube Video

References

^ Intel® Cilk™ Plus Specification - Intel® Software Network
^ cilk-5.4.6.tar.gz
^ Don Dailey, Charles E. Leiserson (2001). Using Cilk to Write Multiprocessor Chess Programs, Advances in Computer Games 9, pdf
^ DIEP parallel in Paderborn - technical and detailed story by Vincent Diepeveen, CCC, June 28, 1999
^ Intel Acquires Cilk++ Technology, Dr. Dobb's, August 01, 2009
^ Intel Cilk Plus from Wikipedia
^ Cilk from Wikipedia
^ SuperTech Paper Listing

What links here?

Page	Date Edited
ABDADA	Aug 30, 2017
ACM 1994	May 5, 2017
Algorithms	May 5, 2017
Alpha-Beta	Jan 28, 2018
Bradley Kuszmaul	Oct 12, 2016
Charles Leiserson	Oct 12, 2016
Chris Joerg	Oct 11, 2016
Cilk	Oct 28, 2013
Cilkchess	Jan 21, 2016
Connection Machine	Oct 12, 2016
Don Dailey	Dec 7, 2016
Harald Prokop	Nov 29, 2017
Intel	Aug 29, 2015
Jamboree	Jun 15, 2015
Keith H. Randall	Jun 16, 2015
Languages	Nov 26, 2017
Mathematician	Apr 9, 2018
Matteo Frigo	Jan 7, 2016
Michael Halbherr	Jun 15, 2015
Parallel Search	Dec 30, 2017
Recursion	Nov 18, 2017
Robert Blumofe	Jun 15, 2015
Shared Hash Table	Sep 11, 2017
Star Socrates	Oct 12, 2016
Thread	Apr 22, 2018
Vincent Diepeveen	May 5, 2017
WCCC 1999	Jul 13, 2017
Yuli Zhou	Jun 15, 2015

Up one Level

Conspiracy Numbers

GerdIsenberg — Fri, 29 Dec 2017 17:00:05 GMT

Home * Search * Conspiracy Numbers

Conspiracy Numbers of the root or interior nodes of a search tree for some value v are defined as the least number of conspirators, that are leaves that must change their evaluation value to v in order to change the minimax value of the interior node or root ^[1]. Conspiracy Numbers and their possible application for Minimax search within a best-first search algorithm was first described by David McAllester ^[2].

Sample

Minimax Tree

A sample minimax tree T with some arbitrary values of the leaves ^[3]:

root                    ┌───────┐
max node                │   1   │
                        └───────┘
                     /      3      \
           ┌───────┐                 ┌───────┐
min nodes  │  1.1  │                 │  1.2  │
           └───────┘                 └───────┘
          /    2    \               /    3    \
  ┌───────┐       ┌───────┐   ┌───────┐       ┌───────┐
  │ 1.1.1 │       │ 1.1.2 │   │ 1.2.1 │       │ 1.2.2 │
  └───────┘       └───────┘   └───────┘       └───────┘
      5               2           3               4

Conspiracy Numbers

The conspiracy numbers for all possible value of the root of tree T

v	cn(root, v)	conspirators
<= 1	2	(1.1.1 or 1.1.2) and (1.2.1 or 1.2.2)
2	1	(1.2.1 or 1.2.2)
3	0	none
4	1	(1.1.2 or 1.2.1)
5	1	1.1.2
>= 6	2	(1.1.1 and 1.1.2) or (1.2.1 and 1.2.2)

The conspiracy numbers for all possible value of node 1.1 of tree T

v	cn(1.1, v)	conspirators
<= 1	1	(1.1.1 or 1.1.2)
2	0	none
3,4,5	1	1.1.2
>= 6	2	(1.1.1 and 1.1.2)

The conspiracy numbers for all possible value of node 1.2 of tree T

v	cn(1.2, v)	conspirators
<= 2	1	(1.2.1 or 1.2.2)
3	0	none
4	1	1.2.1
>= 5	2	(1.2.1 and 1.2.2)

Recursive Definition

Following recursive definition in pseudo C is based on Van der Meulen's code ^[4]. V(J) represents the minimaxed value of node J. Opposed to McAllester's original definition which deals with pure game theoretic values, Van der Meulen's distinguished non terminal leaves with cn = 1 for values different of v from game theoretic terminal nodes to assign +oo, since it is impossible to change their value, independently been arrived at by Norbert Klingbeil and Jonathan Schaeffer ^[5]:

int cn(CNode J, int v) {
   int c;
   if ( V(J) == v ) {
      c = 0;
   } else if ( isTerminal(J) ) { 
      c = +oo; /* checkmate, stalemate, tablebase score, etc. */
   } else if ( isLeaf(J) ) {
      c = 1; 
   } else if (isMaxNode(J) && v < V(J) ) {
      c = 0;
      for (all childs J.j)
         if (v < V(J.j) ) c += cn(J.j, v); /* sum */
   } else if (isMinNode(J) && v > V(J) ) {
      c = 0;
      for (all childs J.j)
         if (v > V(J.j) ) c += cn(J.j, v); /* sum */
   } else {
      c = +oo;
      for (all childs J.j)
         c = min( cn(J.j, v), c);
   }
   return c;
}

Search Algorithms

McAllester's aim was related to some drawbacks of alpha-beta, at the worst, the decision at the root is based on a single evaluation of one leaf. If that leaf has assigned an erroneous value, the decision may be disastrous ^[6]. The idea of Conspiracy Number Search (cn-search) and its variants is to continue until it is unlikely that the minimax value at the root will change.

Chess Programs

Publications

^[7]

1985 ...

David McAllester (1985). A New Procedure for Growing Minimax Trees. Technical Report, Artificial Intelligence Laboratory, MIT
David McAllester (1988). Conspiracy Numbers for Min-Max Search. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
Ingo Althöfer (1988). Root Evaluation Errors: How they Arise and Propagate. ICCA Journal, Vol. 11, Nos. 2/3
Maarten van der Meulen (1988). Parallel Conspiracy-Number Search. M.Sc. thesis, Faculty of Mathematics and Computer Science, Vrije Universteit, Amsterdam
Norbert Klingbeil (1988). Search Strategies for Conspiracy Numbers. M.Sc. thesis
Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139
Jonathan Schaeffer (1989). Conspiracy Numbers. Advances in Computer Chess 5. » also published
Charles Elkan (1989). Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving. IJCAI 1989, pdf

1990 ...

Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
Norbert Klingbeil, Jonathan Schaeffer (1990). Empirical Results with Conspiracy Numbers. Computational Intelligence, Vol. 6, pp. 1-11, ps
[[#AI|]]Jonathan Schaeffer (1990). Conspiracy Numbers. Artificial Intelligence, Vol. 43, No. 1, pp. 67-84
Maarten van der Meulen, Victor Allis, Jaap van den Herik (1990). A Comment on `Conspiracy-Number Search'. ICCA Journal, Vol. 13, No. 2
Victor Allis, Maarten van der Meulen, Jaap van den Herik (1991). Conspiracy-Number Search. Advances in Computer Chess 6
David McAllester, Deniz Yuret (1993). Alpha-Beta Conspiracy Search. ps (draft)
Lisa Lister, Jonathan Schaeffer (1994). An Analysis of the Conspiracy Numbers Algorithm. Computers & Mathematics with Applications Vol. 27, No. 1, Elsevier, pdf
Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994

1995 ...

Ulf Lorenz, Valentin Rottmann, Rainer Feldmann, Peter Mysliwietz (1995). Controlled Conspiracy-Number Search. ICCA Journal, Vol. 18, No. 3
Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
Ulf Lorenz (1999). Controlled Conspiracy-2 Search. Technical Report, University of Paderborn, ps
Robin Upton (1999). Dynamic Stochastic Control - A New Approach to Game Tree Searching. Ph.D. thesis, University of Warwick

2000 ...

Ulf Lorenz (2000). Controlled Conspiracy-2 Search. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS)
David McAllester, Deniz Yuret (2002). Alpha-Beta Conspiracy Search. ICGA Journal, Vol. 25, No. 1

2010 ...

External Links

Conspiracy Numbers

Conspiracy

Conspiracy (disambiguation) from Wikipedia
Conspiracy theory from Wikipedia
List of conspiracy theories from Wikipedia
Conspiracy theory (disambiguation) from Wikipedia
Jeanne Lee - Sundance, Conspiracy (1975), YouTube Video
feat.: Jack Gregg, Mark Whitecage, Steve McCall, Gunter Hampel, Sam Rivers, Marty Cook
Squire & Sherwood, Conspiracy - Conspiracy, YouTube Video

References

^ Definition, Sample, and Pseudo code taken from Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
^ David McAllester (1988). Conspiracy Numbers for Min-Max Search. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
^ due to Jonathan Schaeffer (1989). Conspiracy Numbers. Advances in Computer Chess 5

Photo by László Lindner, ICCA Journal, Vol. 10, No. 3, pp. 138
^ Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
^ Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139
^ Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
^ ICGA Reference Database(pdf)

What links here?

Page	Date Edited
Advances in Computer Chess 5	Dec 2, 2017
Charles Elkan	Jan 23, 2017
Conspiracy Numbers	Dec 29, 2017
David McAllester	May 23, 2016
Dictionary	Aug 24, 2017
Lisa Lister	Nov 3, 2016
Proof-number search	Jan 22, 2018
Richard P. Cochran	Mar 28, 2015
Root	Sep 26, 2016
Search	Feb 1, 2018
Search Pathology	Nov 26, 2017
Search Tree	Dec 23, 2016
Search with Random Leaf Values	Apr 23, 2018
Ulysses	Nov 1, 2016

Up one Level

Countermove Heuristic

GerdIsenberg — Sun, 01 Oct 2017 08:08:00 GMT

Home * Search * Move Ordering * Countermove Heuristic

The Countermove Heuristic was introduced by Jos Uiterwijk in 1992, which shows some similarities with the killer-, refutation- and history heuristic ^[1] . This heuristic assumes that many moves have a "natural" response, irrespective of the actual position, and is easy to implement either with a 64 * 64 butterfly table or alternatively a more memory friendly 6 * 64 array for each side to move, indexed by [from][to] or by [piece][to] ^[2] of the previous move, containing the counter move. The nature of the countermove heuristic renders it complementary to the killer heuristic, substituting position with same distance to the root with the last move played.

Update

This is how the counter move array is updated, if a beta-cutoff occurs:

   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) )
         counterMove[previousMove.from][previousMove.to] = move;
      ...
      return score;
   }

Move Score

While assigning scores to moves for move ordering, a bonus is earned for the move which matches the countermove of the last move played:

   if ( movelist[i].move == counterMove[previousMove.from][previousMove.to] )
      movelist[i].score += counterMoveBonus;

Butterfly Moves

Independently of Uiterwijk's work, Dap Hartmann and Peter Kouwenhoven reported on the similar technique of Butterfly board moves at Advances in Computer Chess 6, London 1990, being different from the Butterfly heuristic ^[3] . Their aim was to safe move generation by proving only legality of a butterfly move. If both transposition- and killer table fail to supply a move, then 1 in 5 times the butterfly board was able to supply a legal killer which saved the complete move generation ^[4] .

Publications

Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University
Marcel van Kervinck (2002). The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf

Forum Posts

2005 ...

Counter move heuristic by Alvaro Jose Povoa Cardoso, CCC, August 30, 2005

2010 ...

The LBR move ordering heuristic by Steven Edwards, CCC, March 26, 2011 » Last Best Reply
Move ordering idea (old and new?) by Daniel Homan, CCC, Aug 09, 2012
Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
Re: History pruning / move ordering question by Joona Kiiski, CCC, May 12, 2013

2015 ...

countermove heuristic by Folkert van Heusden, CCC, December 31, 2016
Storing Countermoves by Ply by Jason Fernandez, CCC, September 08, 2017

References

^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Paul Lu (1990). Report on the Advances in Computer Chess 6 Conference. ICCA Journal, Vol. 13, No. 3

What links here?

Page	Date Edited
Alvaro Cardoso	Jan 12, 2018
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
ChessBrainVB	Jun 24, 2017
Counter	Nov 13, 2017
Countermove Heuristic	Oct 1, 2017
Crafty	Jan 28, 2018
Dan Homan	Oct 19, 2016
Defenchess	Mar 18, 2018
Don Dailey	Dec 7, 2016
Encoding Moves	Mar 27, 2016
Fixafan	Oct 2, 2015
Freyr	Mar 6, 2014
Gaia	Nov 3, 2015
Galjoen	Mar 19, 2018
Gaviota	Jan 21, 2018
History Heuristic	Jul 19, 2017
iCE	Jan 4, 2016
ICGA Journal	Dec 21, 2017
Joona Kiiski	Aug 31, 2017
Jos Uiterwijk	Aug 11, 2017
Killer Heuristic	Sep 14, 2017
Komodo	Mar 6, 2018
Last Best Reply	Jul 6, 2013
Mathematician	Apr 9, 2018
Move Ordering	Feb 27, 2018
Pharaon	Sep 2, 2017
Refutation Move	May 13, 2013
Refutation Table	Mar 27, 2015
Relative History Heuristic	Jun 8, 2015
Rookie	Jan 7, 2016
Sjaak (Glebbeek)	Oct 4, 2017
Stockfish	Apr 7, 2018
Touch	Dec 12, 2016
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
ZChess	Jan 8, 2016
Zurichess	Mar 12, 2018

Up one Level

Wikispaces : chessprogramming - items matching description

ABDADA

Table of Contents

Recursion

Algorithm

Pseudo Code

Implementations

Frenchess

Smash

See also

Publications

Forum Posts

1997 ...

2000 ...

2010 ...

External Links

Algorithm

Misc

References

What links here?

AEL-Pruning

Table of Contents

Pseudo-Code

References

What links here?

Alpha

See also

External Links

What links here?

Alpha-Beta

Table of Contents

How it works

Savings

History

Quotes

McCarthy

Ershov and Shura-Bura

Knuth

Implementation

Max versus Min

Negamax Framework

Fail hard

Outside the Bounds

Enhancements

Obligatory

Selectivity

Scout and Friends

Alpha-Beta goes Best-First

See also

Videos

Selected Publications

1958 ..

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1993 ...

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

References

APHID

Table of Contents

How it works

See also

Publications

Forum Posts

External Links

Game Tree Search

Misc

References

What links here?

Aspiration Windows

Table of Contents