Wikispaces : chessprogramming - items matching description

10x12 Board

GerdIsenberg — Mon, 19 Feb 2018 20:19:30 GMT

Programs

Sargon

TSCP

Square Mapping

Offset Move Generation

Home * Board Representation * Mailbox * 10x12 Board

The 10x12 Board embeds the 8x8 board array, surrounded by sentinel files and ranks to recognize off the board indices while generating moves using offsets per piece and direction to determine move target squares. Two ranks at the bottom and top are necessary to ensure even knight jumps from the corners result in valid array indices greater or equal zero and less than 120.

Programs

Sargon

In 1978, Sargon by Dan and Kathe Spracklen used a classical 120 Byte array as board ^[1]^[2]:

; *******************************************************
; BOARD    -- Board Array. Used to hold the current position 
; of the board during play. The board itself
; looks like: 
;     FFFFFFFFFFFFFFFFFFFF 
;     FFFFFFFFFFFFFFFFFFFF 
;     FF0402030506030204FF 
;     FF0101010101010101FF 
;     FF0000000000000000FF 
;     FF0000000000000000FF 
;     FF0000000000000060FF 
;     FF0000000000000000FF 
;     FF8181818181818181FF 
;     FF8482838586838284FF 
;     FFFFFFFFFFFFFFFFFFFF 
;     FFFFFFFFFFFFFFFFFFFF 
; The values of FF form the border of the 
; board, and are used to indicate when a piece 
; moves off the board. The individual bits of 
; the other bytes in the board array are as
; follows:
;     Bit 7 -- Color of the piece
;     1 -- Black 
;     0 -- White 
;     Bit 6 -- Not used 
;     Bit 5 -- Not used 
;     Bit 4 --Castle flag for Kings only
;     Bit 3 -- Piece has moved flag
;     Bits 2-0 Piece type 
;         1 -- Pawn 
;         2 -- Knight
;         3 -- Bishop 
;         4 -- Rook 
;         5 -- Queen 
;         6 -- King
;         7 -- Not used
;         0 -- Empty Square
; *******************************************************
BOARD = .-TBASE 
BOARDA: .BLKB 120

TSCP

A textbook example of mailbox board representation is TSCP. The board are two 64 element arrays, containing empty square plus pure piece code, and empty square plus piece color code ^[3]:.

int color[64];  /* LIGHT, DARK, or EMPTY */
int piece[64];  /* PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING, or EMPTY */

Square Mapping

The 10x12 versus 8x8 and vice versa square mapping is applied by mailbox and mailbox64 lookup tables. A comment by Tom Kerrigan describes the implementation as follows ^[4]. However, as pointed out by Harm Geert Muller, not only the embedded 10x12 board, but various implementations are all mailbox, independently from elements in the array for padding that can act as a sentinel value ^[5] :

/* Now we have the mailbox array, so called because it looks like a
   mailbox, at least according to Bob Hyatt. This is useful when we
   need to figure out what pieces can go where. Let's say we have a
   rook on square a4 (32) and we want to know if it can move one
   square to the left. We subtract 1, and we get 31 (h5). The rook
   obviously can't move to h5, but we don't know that without doing
   a lot of annoying work. Sooooo, what we do is figure out a4's
   mailbox number, which is 61. Then we subtract 1 from 61 (60) and
   see what mailbox[60] is. In this case, it's -1, so it's out of
   bounds and we can forget it. You can see how mailbox[] is used
   in attack() in board.c. */
 
int mailbox[120] = {
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
     -1,  0,  1,  2,  3,  4,  5,  6,  7, -1,
     -1,  8,  9, 10, 11, 12, 13, 14, 15, -1,
     -1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
     -1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
     -1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
     -1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
     -1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
     -1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
};
 
int mailbox64[64] = {
    21, 22, 23, 24, 25, 26, 27, 28,
    31, 32, 33, 34, 35, 36, 37, 38,
    41, 42, 43, 44, 45, 46, 47, 48,
    51, 52, 53, 54, 55, 56, 57, 58,
    61, 62, 63, 64, 65, 66, 67, 68,
    71, 72, 73, 74, 75, 76, 77, 78,
    81, 82, 83, 84, 85, 86, 87, 88,
    91, 92, 93, 94, 95, 96, 97, 98
};

Offset Move Generation

In the offset move generation code, testing if a square is on the board looks as follows ^[6] ^[7]:

int side;  /* the side to move */
int xside;  /* the side not to move */
 
BOOL slide[6] = {FALSE, FALSE, TRUE, TRUE, TRUE, FALSE};
int offsets[6] = {0, 8, 4, 4, 8, 8}; /* knight or ray directions */
int offset[6][8] = {
    {   0,   0,  0,  0, 0,  0,  0,  0 },
    { -21, -19,-12, -8, 8, 12, 19, 21 }, /* KNIGHT */
    { -11,  -9,  9, 11, 0,  0,  0,  0 }, /* BISHOP */
    { -10,  -1,  1, 10, 0,  0,  0,  0 }, /* ROOK */
    { -11, -10, -9, -1, 1,  9, 10, 11 }, /* QUEEN */
    { -11, -10, -9, -1, 1,  9, 10, 11 }  /* KING */
};
 
for (i = 0; i < 64; ++i) { /* loop over all squares (no piece list) */
  if (color[i] == side) { /* looking for own pieces and pawns to move */
    p = piece[i]; /* found one */
    if (p != PAWN) { /* piece or pawn */
      for (j = 0; j < offsets[p]; ++j) { /* for all knight or ray directions */
        for (n = i;;) { /* starting with from square */
          n = mailbox[mailbox64[n] + offset[p][j]]; /* next square along the ray j */
          if (n == -1) break; /* outside board */
          if (color[n] != EMPTY) {
            if (color[n] == xside)
              genMove(i, n, 1); /* capture from i to n */
            break;
          }
          genMove(i, n, 0); /* quiet move from i to n */
          if (!slide[p]) break; /* next direction */
        }
      }
    } else { /* pawn moves */ }
  }
}

Publications

Dan Spracklen, Kathe Spracklen (1978). First Steps in Computer Chess Programming. BYTE, Vol. 3, No. 10, pdf from The Computer History Museum
David Levy (1979). Computer and Chess - How the monster thinks. Elektor, January 1979 ^[8]
Robert Hyatt (1981). Checkmate: The Cray-1 Plays Chess. Part 1. Cray Channels, Vol. 3, No. 1. pdf from The Computer History Museum

Forum Posts

Board representation : 0x88 or 10x12 ? by Philippe, Winboard Forum, March 02, 2006 » 0x88
move generation with one dimensional "12 x 10" array by Andrew Short, CCC, August 22, 2008
mailbox & CPW by Harm Geert Muller, CCC, May 31, 2013

External Links

Chess board representations by Robert Hyatt
If - I'm Reaching Out on All Sides, 1970, YouTube Video

References

^ Dan Spracklen, Kathe Spracklen (1978). First Steps in Computer Chess Programming. BYTE, Vol. 3, No. 10, pdf from The Computer History Museum
^ Sargon Z80 assembly listing by Dan and Kathe Spracklen, hosted by Andre Adrian
^ TSCP - data.c
^ TSCP - data.c
^ mailbox & CPW by Harm Geert Muller, CCC, May 31, 2013
^ TSCP - data.c
^ TSCP - board.c, slightly modified
^ Publication Archive from Chess Computer UK by Mike Watters

What links here?

Page	Date Edited
0x88	Nov 28, 2016
10x12 Board	Feb 19, 2018
8x8 Board	Aug 29, 2017
Array	Dec 1, 2016
Atomystica	Oct 2, 2014
Betsabe	Jul 23, 2017
Board Representation	Dec 11, 2017
Caligula PC	Dec 11, 2013
ChessBrainVB	Jun 24, 2017
Christophe Théron	Jan 7, 2016
Counter	Nov 13, 2017
Dappet	Dec 12, 2016
Delfi	Jan 7, 2016
GambitVB	Oct 24, 2016
Glaurung	Mar 14, 2017
Mailbox	Apr 14, 2018
Matador	Oct 30, 2015
Move Generation	Jan 29, 2018
NG-play	Feb 26, 2017
Nirvanachess	Sep 30, 2017
Numpty chess	Oct 21, 2014
Phalanx	May 2, 2016
Pieces	Feb 19, 2018
Proscha	May 20, 2015
ROCE	Jun 6, 2017
Russell Reagan	Aug 31, 2013
Sargon	Dec 25, 2017
Slow Chess	May 17, 2016
Spike	Jan 7, 2016
Table-driven Move Generation	Feb 19, 2017
TSCP	Feb 5, 2016
Vector Attacks	Dec 15, 2017
Vice	Mar 8, 2016
Waxman	Aug 18, 2014

Up one Level

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

Abyss

GerdIsenberg — Sat, 05 Aug 2017 19:27:34 GMT

Home * Engines * Abyss
Home * Games * Chinese Chess Engines * Abyss

		Abyss, a Chinese Chess program by Chun Ye and Tony Marsland, written in C under Unix aka SunOS. A X Window GUI was written in C++ by Haiying Wang ^[1]. The program was subject of Chun Ye's 1992 master thesis at University of Alberta ^[2] on the topic of selectivity and extension heuristics in the domain of Chinese Chess. Not only Ye's advisor, Tony Marsland, contributed to the development of the program, but also Don Beal - at that time visiting professor at University of Alberta - in particular concerning null move quiescence search. Abyss participated at all three Computer Olympiads which took place in Maastricht, winning the gold medal (shared) at the 3rd Computer Olympiad, 1991, while the 1999 version played in 2001 and 2002, respectively.
At the Edge of the Abyss ^[3]

Abyss' ICGA Tournaments

Description

The framework of Abyss ^[4] was based on the Western experimental Chess program Parabelle by Fred Popowich and Tony Marsland ^[5].

Move Generation

Abyss' board is represented as Mailbox - a one-dimensional array of 90 computer words, indexed by 0 .. 89. Pieces are encoded by ±1 for red and black pawns until ±7 for red and black kings, empty squares are represented by zero. To detect the edges of the board and palace during move generation, board arrays of pre-computed 12-bit direction masks consisting of four groups for each orthogonal direction of 3 bits each are utilized. Only the empty intersection of the move direction with the mask of the target square indicates target on board or inside palace, followed by piece specific tests to generate pseudo legal moves or to continue a direction loop for rook or cannon. Detection of strictly legal moves, i.e. it does not expose the own king in check, or does not oppose both kings on the same file with no pieces intervening, is delayed until the move is actually made for efficiency reasons - since not all generated pseudo legal moves are examined.

Search

The search procedure of Abyss was subject of Chun Ye's thesis concerning selectivity, in particular extensions which are combined in various experiments, and further elaborated in two additional papers along with Tony Marsland ^[6] ^[7]. Abyss already featured recursive null move pruning with depth reduction of 1 ^[8], and further Don Beal's null move quiescence search ^[9]. A piece evading move extension was motivated by threat detection concerning the complicated repetition rules of Chinese Chess.

Basics

Move Ordering

Selectivity

Evaluation

Material Balance with Point Values

Piece	Opening	Endgame
King	7000
Rook	1800
Cannon	900	800
Horse	800	900
Elephant	300
Advisor	300
Pawn	100

Piece-Square Tables
Square Control
King Safety
Attacking King Zone
Penalty for King on rank or file of opponent's Cannon

Misc

Opening Book

Abyss' ICGA Tournaments

^[10]

Edition	Version	Ranking	Participants
3rd Computer Olympiad, Maastricht 1991		1	2
6th Computer Olympiad, Maastricht 2001	Abyss '99	3	3
7th Computer Olympiad, Maastricht 2002	Abyss '99	4	4

Publications

Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2, pdf
Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3, pdf

External Links

Engine

Abyss' ICGA Tournaments

Misc

References

^ Haiying Wang (1994). An application-oriented user interface model and development system. Ph.D. thesis, University of Alberta, pdf, see 6.2 Chinese Chess Program pp. 101.
^ Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
^ Lysefjord, Norway- a man standing on Preikestolen at the edge of the Abyss, Image by Mercy, August 2008, CC BY-SA 3.0, Wikimedia Commons
^ Description is based on Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
^ Fred Popowich, Tony Marsland. (1983) Parabelle: Experience with a Parallel Chess Program. Technical Report 83-7. Computing Science Department, University of Alberta, pdf
^ Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2, pdf
^ Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3, pdf
^ Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
^ Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, A revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702.
^ Abyss' ICGA Tournaments

What links here?

Page	Date Edited
3rd Computer Olympiad	Jul 25, 2017
6th Computer Olympiad	Jul 22, 2017
7th Computer Olympiad	Jul 23, 2017
Abyss	Aug 5, 2017
Chun Ye	Jul 25, 2017
Engines	Mar 10, 2018
GUI	Mar 16, 2018
Haiying Wang	Jul 27, 2017
Null Move Pruning	Dec 2, 2017
Parabelle	Jul 28, 2017
Tony Marsland	Nov 27, 2017
University of Alberta	Feb 20, 2018

Up one Level

ACM 1973

GerdIsenberg — Fri, 19 Jan 2018 12:17:01 GMT

Home * Tournaments * ACM North American Computer Chess Championship * ACM 1973
< Prev Next >

		The ACM's Fourth North American Computer Chess Championship (NACCC) was held from August 26 to 28, 1973 at the Hyatt Regency Hotel, Atlanta, Georgia, USA.
Hyatt Regency Atlanta ^[1]

Final Standing

^[2]

#	Program	1	2	3	4	P	SOS	Playoff
1	Chess 4.0	7w1	5b½	8w1	2b1	3½	8½
2	CHAOS	12w1	10b1	6b1	1w0	3	7	3b1,4w0
3	Ostrich	8b0	11b1	10w1	6w1	3	5½	2w0,4w0
4	Tech 2	10b0	12b1	5w1	9w1	3	5	3w1,2b1
5	Dartmouth CP	9b1	1w½	4b0	8w½	2	9½
6	Tech	11w1	8b1	2w0	3b0	2	8½
7	T. Belle	1b0	9w½	12w½	10w1	2	6½
8	Coko 4	3w1	6w0	1b0	5b½	1½	10½
9	Ga Tech CP	5w0	7b½	11w1	4b0	1½	8
10	The Fox	4w1	2w0	3b0	7b0	1	11
11	USC CP	6b0	3w0	9b0	12w1	1	7
12	Ches	2b0	4w0	7b½	11b0	½	9

SOS: Sum of Opponent Scores

Participants

^[3]

Program	Team	Hardware	Language
CHAOS	Ira Ruben, Fred Swartz, Joe Winograd, Victor Berman	UNIVAC 1108	Fortran
Ches	David Barton, Craig Barnes, Peter Rowe	HP 3000
Chess 4.0	Larry Atkin, Keith Gorlen, David Slate	CDC 6400	COMPASS
Coko 4	Dennis Cooper, Ed Kozdrowicki	UNIVAC 1108	Fortran
Dartmouth CP	Warren Montgomery, Larry Harris	GE-635	GCOS Assembly
Ga Tech CP	Lawrence Futrell	Burroughs B-5500
Ostrich	George Arnold, Monroe Newborn	SuperNOVA	Assembly
T. Belle	Ken Thompson	PDP-11	C
Tech	Jim Gillogly	PDP-10	BLISS
Tech 2	Alan Baisley	PDP-10	Assembly
The Fox	Charlie Wilkes, Charles F. Wilkes	IBM 370/145	APL
USC CP	Albert Zobrist, Frederic Roy Carlson, Charles Kalme	IBM 370/155

The Tournament

		The defending champions had completely rewritten their program using Shannon's type A strategy and renamed it Chess 4.0. They did it again, but not with a 100% score - after winning three ACM tournaments and ten consecutive tournament games, it only managed to draw from Dartmouth CP in round 2 - being in trouble most of the game, Dartmouth CP repeated the position for the third time while one pawn ahead. In the third round Tech 2 defeated Dartmouth CP, Chess 4.0 defeated Coko 4 and CHAOS won its third straight game to take the lead in the tournament. The last round pitted Chess 4.0 against CHAOS - the winner would win the tournament. The game was a highly tactical one in which the large trees examined by Chess were too much for CHAOS to handle. On the last evening of the tournament, after the Chess 4.0 versus CHAOS game was completed, Charles Kalme played both programs in a simultaneous exhibition with a Queen handicap. He won the game against CHAOS (and a $100 side bet) but lost from Chess 4.0 ^[4] .
Hyatt Regency Atrium ^[5]

Selected Games

Round 4, CHAOS - Chess 4.0

[Event "ACM 1973"]
[Site "Atlanta USA"]
[Date "1973.08.28"]
[Round "4"]
[White "CHAOS"]
[Black "Chess 4.0"]
[Result "0-1"]
 
1.d4 d5 2.c4 dxc4 3.Nf3 Nf6 4.e3 e6 5.Bxc4 c5 6.O-O a6 7.Qe2 b5 8.Bb3 Bb7
9.Nc3 Nbd7 10.Bd2 Bd6 11.Rfe1 cxd4 12.exd4 O-O 13.Bg5 Qb6 14.Bc2 Bxf3 15.Qxf3
Qxd4 16.Rad1 Qb4 17.g3 Qxb2 18.Re2 Qa3 19.Qc6 Bb4 20.Rxd7 Rac8 21.Rc7 Rxc7
22.Qxc7 Qxc3 23.Qb7 Qc4 24.Bd1 Rd8 25.Re5 Rxd1+ 26.Kg2 Qf1+ 27.Kf3 Qh1+ 28.Ke2
Re1+ 29.Kd3 Qf1+ 30.Kd4 Qc4# 0-1

Game and short analyze on Lichess.org : https://en.lichess.org/kVgFAOTq

Tournament Director

David Levy

Publications

Steve Coles (1973). Fourth United States computer chess championship from ACM73 news release. ACM SIGART Bulletin, No. 41
Ben Mittman, Monty Newborn (1973). Results of the fourth annual U.S. computer chess tournament. ACM SIGART Bulletin, No. 42
Richard Fikes (1974). Fourth U.S. Computer Chess Championship. ACM SIGART Bulletin, No. 44, 45
Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. ISBN 0-125-17250-8.
Chapter IX. The Fourth United States Computer Chess Championship

External Links

ACM 1973 CSVN site
Proceedings of the ACM annual conference
Shawn Lane, Jonas Hellborg, Jeff Sipe - Improvisation, Atlanta Drums & Percussion, August 19, 1996, YouTube Video

North American Computer-Chess Championships, complete History of Tournament Results by Theo van der Storm
Important games hosted by Ed Schröder
ACM COMPUTER CHESS by Bill Wall

References

^ View of the Hyatt Regency Atlanta from the Marriott Marquis, Wikimedia Commons, November 04, 2007, by Connor.carey, Hyatt Regency Atlanta from Wikipedia
^ ACM 1973 CSVN site
^ Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. Chapter IX. The Fourth United States Computer Chess Championship
^ Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. Chapter IX. The Fourth United States Computer Chess Championship
^ Atrium of the Hyatt Regency Hotel, Downtown Atlanta, Portman's first atrium (1967), Wikimedia Commons, November 18, 2010, by StanSatin, Hyatt Regency Atlanta from Wikipedia

What links here?

Page	Date Edited
ACM 1972	Dec 22, 2017
ACM 1973	Jan 19, 2018
ACM 1974	Jan 19, 2018
ACM North American Computer Chess Championship	Jun 13, 2015
Alan Baisley	Jan 7, 2016
Albert Zobrist	Jun 12, 2016
Ben Mittman	Jan 2, 2017
CHAOS	Dec 28, 2017
Charles F. Wilkes	Oct 6, 2014
Charlie Wilkes	Oct 6, 2014
Ches	Jan 3, 2018
Chess (Program)	Dec 22, 2017
Craig Barnes	Jan 8, 2016
Danny Kopec	Oct 1, 2016
Dartmouth CP	Jan 19, 2018
Dennis Cooper	Aug 18, 2014
Ed Kozdrowicki	Aug 18, 2014
Engine Testing	Feb 1, 2018
Frederic Roy Carlson	Oct 19, 2013
Ga Tech CP	Oct 8, 2014
Hal Terrie	Feb 19, 2015
Larry Harris	Apr 3, 2013
Lawrence Futrell	Jul 11, 2012
Match Statistics	Mar 31, 2018
Monroe Newborn	Dec 23, 2017
Paul Rushton	Jan 12, 2015
Playing Strength	Mar 31, 2018
Richard Fikes	May 23, 2016
Tech	Apr 20, 2018
The Fox	Feb 27, 2017
Tony Marsland	Nov 27, 2017
USC CP	Aug 10, 2016
Warren Montgomery	Feb 19, 2015

Up one level

ACM 1980

GerdIsenberg — Mon, 25 Dec 2017 18:45:49 GMT

Home * Tournaments * ACM North American Computer Chess Championship * ACM 1980
< Prev Next >

		The ACM's Eleventh North American Computer Chess Championship (NACCC) was held from October 26 to 28, 1980 at the Opryland Hotel, Nashville, Tennessee, adjacent to the famous Grand Ole Opry ^[1].
Cascade Atrium, Opryland Hotel ^[2]

Final Standing

^[3]

#	Program	CC	1	2	3	4	P	SOS	SoDOS
1	Belle	US	6w1	5b1	2w1	3b1	4	9½	9½
2	CHAOS	US	7b1	9w1	1b0	5w1	3	8½	4½
3	Chess Challenger X	US	4w½	7b1	9b1	1w0	2½	9	3¾
4	Bebe	US	3b½	6b1	5w0	9w1	2½	7½	4¼
5	Cray Blitz	US	8w1	1w0	4b1	2b0	2	11	4
6	MyChess	US	1b0	4w0	8b1	10b1	2	8	1½
7	Ostrich 81	CA	2w0	3w0	10b1	8w½	1½	7	¾
8	Cube 2.0	US	5b0	10w1	6w0	7b½	1½	5½	¾
9	Awit	CA	10w1	2b0	3w0	4b0	1	8	0
10	Clash	US	9b0	8b0	7w0	6w0	0	6	0

Participants

^[4]

Program	CC	Team	Hardware	Language
Awit	CA	Tony Marsland	AMDAHL 470V/7	Algol-W
Bebe	US	Tony Scherzer	Bit Slice Chess hardware	Assembly
Belle	US	Ken Thompson, Joe Condon	PDP-11/23, LSI-11 with custom boards	C
CHAOS	US	Fred Swartz, Mike Alexander, Jack O’Keefe, Victor Berman	AMDAHL 470	Fortran
Chess Challenger X	US	Dan Spracklen, Kathe Spracklen, Ron Nelson, Ed English, Frank Duason	6502 based System	Assembly
Clash	US	Chris Peters	TI-990	Fortran IV
Cray Blitz	US	Robert Hyatt, Albert Gower, Dave Darling, Derek Robb	Cray-1	Fortran IV
Cube 2.0	US	Lloyd L. Lank, James A. Lank	Cray-1	Fortran
MyChess	US	David Kittinger	Z80 Cromemco T-2D	Assembly
Ostrich 81	CA	Monroe Newborn	Nova 4	Assembly

Photos & Games

Round 2

Cray Blitz vs. Belle, Robert Hyatt in the back and confident Ken Thompson ^[5].

[Event "ACM 1980"]
[Site "Nashville USA"]
[Date "1980.10.26"]
[Round "2"]
[White "Cray Blitz"]
[Black "Belle"]
[Result "0-1"]
 
1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.Ng5 d5 5.exd5 Na5 6.Bb5+ c6 7.dxc6 bxc6 8.Be2 h6 
9.Nf3 e4 10.Ne5 Bd6 11.f4 exf3 12.Nxf3 O-O 13.O-O Qc7 14.d4 c5 15.Nc3 a6 16.dxc5 
Bxc5+ 17.Kh1 Bb7 18.Qe1 Rae8 19.Qh4 Ne4 20.Bf4 Qc6 21.Nxe4 Qxe4 22.Bd3 Qe6 23.Qh5 
Qb6 24.Qf5 g6 25.Qh3 h5 26.Bh6 Qxb2 27.Bxf8 Bxf8 28.Qd7 Re7 29.Qa4 Qc3 30.Qf4 Bd5 
31.Bxa6 Qxc2 32.Rfc1 Qb2 33.Qd2 Qxd2 34.Nxd2 Bg7 35.Rab1 Bxa2 36.Rb6 Re6 37.Rb8+ 
Kh7 38.Bf1 Bh6 39.Rb2 Bxd2 40.Rxd2 Nb3 41.Rxa2 Nxc1 42.Rd2 Kg7 43.g3 Nb3 44.Rd5 
Rc6 45.Kg2 Rc2+ 46.Kh3 Kf6 47.Rd6+ Ke5 48.Rd8 Nd4 49.Bd3 Rf2 50.Rc8 g5 51.Rh8 Nf3 
52.Rxh5 f5 53.Bxf5 Kxf5 54.g4+ Kf4 55.Rh6 Rxh2# 0-1

Round 3

Clash vs. Ostrich 81, Chris Peters and Monty Newborn chat, while Ostrich ponders 6... e6
Tournament Director David Levy scans the other games

[Event "ACM 1980"]
[Site "Nashville USA"]
[Date "1980.10.27"]
[Round "3"]
[White "Clash"]
[Black "Ostrich 81"]
[Result "0-1"]
 
1.e4 d5 2.Nc3 Nf6 3.Nxd5 Nxe4 4.Nc3 Nxc3 5.dxc3 Qxd1+ 6.Kxd1 Bf5 7.Bd3 e6 8.Bf4 Bc5 
9.Ke2 Bxd3+ 10.cxd3 Na6 11.Be5 O-O 12.b4 f6 13.bxc5 fxe5 14.d4 exd4 15.cxd4 e5 16.dxe5 
Nxc5 17.Rd1 Ne4 18.Nf3 Nc3+ 19.Ke3 Nxd1+ 20.Rxd1 c5 21.Rd7 b6 22.e6 Rae8 23.e7 Rf7 
24.Rxa7 Rexe7+ 25.Rxe7 Rxe7+ 26.Kd3 Ra7 27.h3 Rxa2 28.Ke3 c4 29.g4 b5 30.Ne5 Ra3+ 
31.Ke4 Rxh3 32.f3 c3 33.Kd4 c2 34.Nd3 Rxf3 35.Ne1 Rf4+ 36.Ke5 c1=Q 37.Nd3 Qe3+ 38.Kd6 
Qxd3+ 39.Kc6 Rxg4 40.Kc7 Rg6 41.Kb8 Qd8+ 42.Kb7 Rb6+ 43.Ka7 Qb8# 0-1

Round 4

Kathe Spracklen and Ken Thompson operating their programs, Ron Nelson and others watching.
In Chess Challenger X versus Belle, with 48.a4, having delayed mate as long as possible, Challenger
finally ran out of checks, but then a bug appeared in Belle ... ^[6]

[Event "ACM 1980"]
[Site "Nashville USA"]
[Date "1980.10.28"]
[Round "4"]
[White "Chess Challenger X"]
[Black "Belle"]
[Result "0-1"]
 
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Nxe4 6.d4 b5 7.Bb3 d5 8.dxe5 Be6
9.c3 Bc5 10.Be3 Bxe3 11.fxe3 Rb8 12.Nbd2 Nc5 13.Qe1 Nd3 14.Qg3 O-O 15.Rab1
Qe7 16.Bc2 Qc5 17.Ng5 Ncxe5 18.Nxh7 Rfd8 19.Nf6+ Kf8 20.Bxd3 Nxd3 21.Nh5 g6
22.Nf6 Bf5 23.Qg5 b4 24.Nh7+ Ke8 25.Nf6+ Kf8 26.Nb3 Qc4 27.Nh7+ Ke8 28.cxb4
Rxb4 29.Nf6+ Kf8 30.Ng4 Rd6 31.Nh6 Qe4 32.Rxf5 gxf5 33.Qg8+ Ke7 34.Qxf7+ Kd8
35.Nxf5 Rc6 36.h4 Rc2 37.Qf8+ Kd7 38.Qf7+ Kc8 39.Qg6 Kb7 40.Na5+ Ka8 41.Qxa6+
Kb8 42.Qg6 Ne5 43.Qg8+ Ka7 44.Rf1 Rbxb2 45.Kh1 Rxg2 46.Nc6+ Nxc6 47.Qa8+ Kxa8
48.a4 Kb8 49.a5 Ka8 50.a6 Ka7 51.h5 Kb6 52.a7 Rg1+ 53.Kxg1 Qg2# 0-1

Game and short analyze on Lichess.org : https://en.lichess.org/jjjlazo2

Tournament Director

David Levy

Publications

The Eleventh ACM's North American Computer Chess Championship, pdf from The Computer History Museum
Ben Mittman (1980). The Eleventh ACM's North American Computer Chess Championship. ICCA Newletter, Vol. 3, No. 3
The Twelfth ACM's North American Computer Chess Championship, pdf from The Computer History Museum (covers ACM 1980)
Evan Katz (1981). The Eleventh North American Computer Chess Championship. Personal Computing, Vol. 5, No. 2, pp. 87 ^[7]
Evan Katz (1981). The Eleventh North American Computer Chess Championship - Part II. Personal Computing, Vol. 5, No. 3, pp. 71

External Links

ACM 1980 CSVN site
The Grand Ole Opry on Radio Luxembourg 1980, YouTube Video
Audio from the historic first satellite broadcast of the WSM Grand Ole Opry

North American Computer-Chess Championships, complete History of Tournament Results by Theo van der Storm
Important games hosted by Ed Schröder
ACM COMPUTER CHESS by Bill Wall

References

^ Evan Katz (1981). The Eleventh North American Computer Chess Championship. Personal Computing, Vol. 5, No. 2, pp. 87
^ Cascade Atrium, Gaylord Opryland Resort & Convention Center, formerly known as Opryland Hotel, Nashville, Tennessee, Photo by Bobak Ha'Eri, October 12, 2007, Wikimedia Commons, Gaylord Opryland Resort & Convention Center - Wikipedia
^ ACM 1980 CSVN site
^ Ben Mittman (1980). The Eleventh ACM's North American Computer Chess Championship. ICCA Newletter, Vol. 3, No. 3
^ Images from Evan Katz (1981). The Eleventh North American Computer Chess Championship. Personal Computing, Vol. 5, No. 2, pp. 87
^ Ben Mittman (1980). The Eleventh ACM's North American Computer Chess Championship. ICCA Newletter, Vol. 3, No. 3, game analysis by David Levy
^ Applied Concepts - Morphy Edition Master Chess (module) (pdf) by Hein Veldhuis

What links here?

Page	Date Edited
ACM 1979	Apr 3, 2017
ACM 1980	Dec 25, 2017
ACM 1981	Jan 19, 2018
ACM North American Computer Chess Championship	Jun 13, 2015
Alan Mead	Mar 23, 2014
Applied Concepts	Dec 25, 2017
Awit	Dec 22, 2017
Bebe	Dec 23, 2017
Belle	Jan 18, 2018
Ben Mittman	Jan 2, 2017
Blitz	Dec 23, 2017
Boris	Dec 25, 2017
Chess Challenger	Dec 27, 2017
Chris Peters	Oct 13, 2014
Clash	May 19, 2016
Computerworld	Sep 9, 2017
Creative Computing	Dec 19, 2013
Cube	Apr 23, 2017
David Darling	Aug 23, 2017
Derek Robb	Aug 23, 2017
Great Game Machine	Dec 20, 2017
ICGA Journal	Dec 21, 2017
James A. Lank	Jun 13, 2015
John Aker	Dec 26, 2017
Lloyd L. Lank	Nov 30, 2017
MCC 1980	Dec 27, 2017
MyChess	Dec 25, 2017
Ostrich	Dec 28, 2017
Personal Computing	Dec 27, 2017
WCCC 1980	Dec 25, 2017
WMCCC 1980	Dec 25, 2017

Up one level

Advances in Computer Chess 1

GerdIsenberg — Thu, 22 Oct 2015 10:13:58 GMT

Home * Conferences * Advances in Computer Chess 1
Next >

		The Advances in Computer Chess 1 conference was held in March 1975 at Balliol College, Oxford, England, and was organized by the Atlas Computer Laboratory and the Society for the Study of Artificial Intelligence and Simulation of Behaviour (SSAISB). Proceedings were published in 1977, edited by Mike Clarke. It was already the second conference on computer chess, after a conference meeting on chess playing by computer in May 1973 at Atlas Computer Laboratory ^[1].
Balliol College, Oxford ^[2]

Proceedings

Advances in Computer Chess 1
M.R.B. Clarke, Editor, 1977
Edinburgh University Press, Edinburgh.
ISBN 0-852-24292-1, amazom

Lectures

Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program. pdf
Ron Atkin (1977). Positional Play in Chess by Computer. ^[3]
Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board.
Soei T. Tan (1977). Describing Pawn Structures.
John Birmingham, Peter Kent (1977). Tree-searching and tree-pruning techniques.
Mike Clarke (1977). A quantitative study of KPK.

Reviews

Alex Bell (1975).Techniques for playing the end game. Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)
Jack Good (1978). Review of "Advances in Computer Chess, Volume 1. by M.R.B. Clarke"; University Press, 1977. ACM SIGART Bulletin, Issue 66

The Forerunner

The first conference meeting on computer chess took place at the Atlas Computer Laboratory May 1973. It was the forerunner of the later Advances in Computer Chess conferences. Alex Bell about the arisen of the conference ^[4] :

In 1972 I was back in England again and met John Scott, who was doing a PhD, and his tutor Dr. Alan Bond. Naturally we talked about chess programs and the recent happenings in the American ACM tournaments. As we talked it became fairly obvious that in the intervening 4 years a number of new ideas had appeared on the scene. One idea was called refutation, a technique which (like alpha-beta) could vastly speed up the tree searching without any loss of information (see Chapter 9 - Machine Technique).

Even more mysterious was a paper Multi Dimensional Structure in the Game of Chess by Ron Atkin ^[5] , a maths lecturer at Essex University. Up to this point all chess programs had evaluation functions which were decidedly ad hoc, the programmers had a feeling in their water that certain features, material, mobility, control of the centre, king safety, pawn structure, etc., were the most important and accordingly stuck them in the program with very little idea of their precise effect. Now here was a mathematician who, with lots of squiggly things, appeared to have a precise mathematical evaluation function. Unfortunately neither John nor I could understand the paper - so why not get Atkin to talk about it. There were a few other new ideas I did not understand - a new, knowledge approach to solving end games and some psychological theories about how chess players think - so why not have a conference? If nothing else I might get some idea of what was going on.

The first Computer Chess Conference took place at the Atlas Computer Laboratory in May 1973. Apart from inviting the speakers it was also obvious that the conference would have to demonstrate a chess program in some form and it is at this point in time that MASTER really got started.
--
From then on the operators played more carefully and revealed that the program, because it still only had a shallow search, still suffered badly from horizon effect. Nevertheless it did win a few more games and it was decided to use it as the demonstration program at the conference.

Well it didn't win a game, hardly surprising since it was up against much stronger players. Nevertheless several people noticed that the program was usually achieving its main aim of controlling the centre squares; in other words, it was quite successful in doing what little it had been told to do but, from then on, it had no further direction other than a vague idea of advancing its own pawns and blocking its opponent's. Peter improved its sense of purpose by making the program, as the game progressed, put less emphasis on controlling the fixed centre squares and more and more emphasis on controlling the squares around the enemy king, wherever he may be. Because of mini-max this also caused the program to protect the squares around its own king far more effectively.

ACC1

The conference on computer chess took place at Balliol College, Oxford in March 1975. It was organized by Atlas Computer Laboratory and the Society for the Study of Artificial Intelligence and Simulation of Behaviour (SSAISB), and was later declared as Advances in Computer Chess 1 conference. Proceedings were published by Mike Clarke from Queen Mary College. Some excerpt from co-organizer, Alex Bell's report in Computer Weekly, April 10, 1975, Techniques for playing the end game ^[6] :

AFICIONADOS of the arts of chess and computing gathered at Balliol College, Oxford, last month for the second conference on computer chess organised by the Atlas Computer Laboratory and the Artificial Intelligence and Simulation of Behaviour study group.

A number of experts were invited to give papers. on their work, including Dr Mikhail Donskoy of the USSR, one of the authors of the world champion program, KAISSA. Unfortunately Donskoy was unable to attend, a disappointment only mitigated by the presence from the US of Dr Hans Berliner, of Carnegie-Mellon. Berliner is the world correspondence chess champion and has also spent the last eight or nine years programming computers to play the game. To most people in the practical, model building side of the subject, ie making a program play the computer game, Berliner is THE expert. Although full of good, implementable ideas he has no illusions as to the limitations of such chess programs.
--
The conference itself lasted one and a half days and the papers (depending on the listener) ranged from the profound to the puerile. I have no desire to repeat my own personal views, indeed as one of the organisers I helped to provide a platform for speakers whose views I found astonishing. What did seem evident to me was that the majority of the audience fell into one of three categories. One group is the artificial intelligentsia. They fully understand the difficulties of the problem and are still thinking about how to solve it. The second group are the let's get on and program something crunchers, the model makers, the people who can make big computers float round the room whistling God save the Queen. These people absolutely refuse to put anything remotely resembling knowledge, chess or otherwise, into their programs if they can avoid it, believing that if the result plays good chess then it can be more easily adapted to attempt other, more useful, decision making problems. The third group is the most important, these are the people who are new to the subject, the people who say, It sounds like a fascinating problem and I'd like to know what's going on.

Hans Berliner fits into two of these categories, his talk covered the AI approach and the crunchers, but he is hardly a newcomer. He was the first speaker and the domain of his talk was chess tactics with emphasis on recognising situations and dealing with them explicitly. He is full of good ideas and techniques which are relevant to the problem of selecting the right move in a game of chess and, more important, showed clearly how each idea and technique could be implemented in a computer.

The next paper by Ron Atkin, of Essex University, was more profound. Atkin has developed a mathematically valid approach to positional play in chess and also described a method of simulating the hierarchical method used by the chess master. His ideas have an intuitive appeal; one feels he must be right but the problem of implementing the ideas in a computer, are enormous and, as yet, unsolved. Another problem was that not a single person in the audience was sufficiently competent to stand up and say, "This is all very well but your approach will not handle this situation in a chess game, a tactic which often shoots down the simple minded crunch programs".

The final talk on the first day was given by Professor Donald Michie of the Machine Intelligence Research Unit, Edinburgh, who dealt with mechanisation of the King, Rook versus King end game. The first machine to play this end game was built by Torres y Quevado c. 1900. Hardly anything was published about it and Michie made an interesting reconstruction of the machine, and I have to admit that Michie had got most of it right.

The next day the speakers included Dr Soei Tan, also of Edinburgh, who dealt with pawn structures; John Birmingham and Peter Kent partially described how MASTER operates; and Mike Clarke, of Queen Mary College, talked about the King, Pawn versus King ending. Clarke's approach is much more scientific than the crunch programs; he has enumerated all possible positions of the K, P v K end game (there are 906,545,760 of them) and discovered which are wins and which are draws. He has done a similar enumeration for the King, Rook v King ending and should, with a little more effort. be able to scientifically work backwards to the 16 pawns, 16 pieces end game.

As can be seen a great deal of time was spent on this King, Rook v King ending. This is interesting because if this ending can cause such difficulty then it is intuitively obvious that the full game must be at least an order of magnitude more difficult. This is intuitively obvious but difficult to prove, nevertheless it appears to be true in the real world. I certainly have great difficulty obtaining a draw with the lone King. Finally, Max Bramer has offered to demonstrate his K,R v K and K,P v K programs to anyone who is interested. He can be contacted at the Open University.

Forum Posts

Re: Whatever happened to Neural Network Chess programs? by Andy Walker, rgcc, March 28, 2000 » Ron Atkin

External Links

Small Faces - Itchycoo Park, Beat-Club, September 23, 1967, YouTube Video

References

^ Alex Bell (ed.) (1973). Computer Chess. Proceedings May 1973 Meeting on chess playing by computer. Science Research Council, Atlas Computer Laboratory
^ Oxford - Balliol College, One of my favourite views, across the appropriately-named Broad Street, May 30 2009, Photographer Peter Trimming, source geograph.org.uk
^ Re: Whatever happened to Neural Network Chess programs? by Andy Walker, rgcc, March 28, 2000
^ Alex Bell (1978). MASTER at IFIPS. Excerpt from: The Machine Plays Chess? Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)
^ Ron Atkin (1972). Multi-Dimensional Structure in the Game of Chess. In International Journal of Man-Machine Studies, 4 pp. 341-362
^ Alex Bell (1975).Techniques for playing the end game. Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)

What links here?

Page	Date Edited
Advances in Computer Chess 1	Oct 22, 2015
Advances in Computer Chess 2	Dec 25, 2017
Alan H. Bond	Oct 7, 2014
Alex Bell	Mar 1, 2017
Andy Walker	Dec 9, 2016
Atlas Computer Laboratory	Feb 10, 2015
CAPS	Dec 23, 2017
Conferences	Dec 18, 2017
Connectivity	Mar 6, 2016
Donald Michie	Dec 23, 2017
El Ajedrecista	Feb 25, 2015
Evaluation	Feb 1, 2018
Georgy Adelson-Velsky	Apr 9, 2018
Hans Berliner	Jun 10, 2017
Jack Good	Dec 22, 2017
John Birmingham	Jan 7, 2016
Kaissa	Apr 9, 2018
KPK	May 12, 2016
KRK	Nov 26, 2016
Master	Dec 28, 2017
Mike Clarke	May 23, 2016
Mikhail Donskoy	Dec 23, 2017
Neural Networks	Mar 12, 2018
Pawn Structure	Oct 2, 2017
Peter Kent	Jan 7, 2016
Pruning	Jan 1, 2018
Razoring	Oct 5, 2015
Ron Atkin	Oct 26, 2016
Soei Tan	Oct 27, 2012
Tactics	Jan 12, 2018
Vladimir Arlazarov	May 20, 2016

Up one Level

Alarm

GerdIsenberg — Wed, 07 Jun 2017 11:42:43 GMT

Home * Engines * Alarm

		Alarm, (Deamon) a WinBoard compliant chess engine by Benny Antonsson and Erik Robertsson, written in C++. Alarm, the Diabolic Chess Engine ^[1], was first released in July 2003 ^[2], and was first mentioned in 2001 formerly called Deamon ^[3]. Alarm played four CCT Tournaments from 2003 to 2006, the CCT5, CCT6, CCT7 and the CCT8.
The Alarm ^[4]

Features

^[5]

Board Representation

Search

Evaluation

Misc

Opening Book from PGN-file

Forum Posts

Loggo for Deamon by Benny Antonsson, CCC, November 28, 2001
St.Andersen vs. Deamon 0.87A by Benny Antonsson, CCC, November 30, 2001 » StAndersen
Another Nordic seems to grow (especially to Odd Gunnar) by Günther Simon, Winboard Forum, December 01, 2001
Swedish programs by Benny Antonsson, CCC, December 04, 2001
Winboard engine Alarm is released by Benny Antonsson, CCC, July 16, 2003
Winboard engine Alarm is released by Benny Antonsson, Winboard Forum, July 16, 2003
Updated engine: Alarm 0.92.4 by Benny Antonsson, Winboard Forum, August 05, 2003
Testposition of Matador-Alarm CCT6 by Stefan Knappe, CCC, February 03, 2004 » CCT6
New version of Alarm by Benny Antonsson, CCC, May 12, 2004

External Links

Chess Engine

Misc

alarm - Wiktionary
Alarm - Wiktionary
alarm - Wiktionary (Swedish)
Alarm - Wiktionary (Swedish)
Alarm (disambiguation) from Wikipedia
Barcode Quartet at A L‘Arme!, Berlin 2013, YouTube Video
Elisabeth Harnik, Alison Blunt, Annette Giesriegl, Josef Klammer

References

^ Alarm - WinBoard Engine (Internet Archive)
^ Winboard engine Alarm is released by Benny Antonsson, CCC, July 16, 2003
^ Swedish programs by Benny Antonsson, CCC, December 04, 2001
^ Indian Alarm - 1884 · bronze sculpture showing an Ottawa Indian family on the move, halting as if alert to some imminent danger; located in Lincoln Park, Chicago at 3000 N. Four incised granite tablets at the base depict scenes from Ottawa life: "The Peace Pipe - The Corn Dance - Forestry - The Hunt." Sculptor: John J. Boyle, Photo by Alanscottwalker, April 29, 2011, CC BY-SA 3.0, Wikimedia Commons
^ Features based on Alarm - Technical and Alarm/Deamon - Revision log (Internet Archive)

What links here?

Page	Date Edited
Alarm	Jun 7, 2017
Benny Antonsson	Aug 17, 2014
CCT5	Feb 22, 2013
CCT6	May 29, 2014
CCT7	Dec 16, 2017
CCT8	Apr 6, 2013
Czolgista	Apr 20, 2013
Embracer	Jun 7, 2017
Engines	Mar 10, 2018
Erik Robertsson	Aug 17, 2014
StAndersen	Aug 17, 2014

Up one Level

Albatross

GerdIsenberg — Fri, 05 May 2017 22:36:45 GMT

Home * Engines * Albatross

		Albatross, a chess program by Michael Parker written in Z80 assembly. Albatross participated at the WMCCC 1980 ^[1], the European MCC 1981 and European MCC 1983, running on a Nascom 1 computer.
Short-tailed Albatross ^[2]

Don't shoot the Albatross

Don't shoot the Albatross

^[3] ^[4] ^[5]
Quote by Tony Harrington on the Albatross during the 4th European MCC 1983 ^[6]

Mike Parker's program, Albatross, which finished the Tournament with one and a half points - much to its author's delight - turned out to be vulnerable to spectators. Someone took a flashlight photo rather too close to it and the Nascom 1, on which the Albatross was running, promptly had a seizure. This prompted cries of 'Don't shoot the Albatross' for the next seven rounds whenever anyone with a camera appeared on the scene.

Selected Games

WMCCC 1980 round 1: Sargon 2.0 - Albatross ^[7] ^[8]

[Event "WMCCC 1980"]
[Site "London, United Kingdom"]
[Date "1980.09.04"]
[Round "1"]
[White "Sargon 2.0"]
[Black "Albatross"]
[Result "0-1"]
 
1.d4 e6 2.Nf3 d5 3.Nc3 Be7 4.e4 dxe4 5.Nxe4 Qd5 6.Nc3 Nc6 7.Nxd5 exd5 8.Bf4 Bd6 
9.Bxd6 Bf5 10.Bxc7 a5 11.Bd3 Be4 12.O-O Nf6 13.Be5 h6 14.Bxf6 O-O 15.Be5 Nb4 
16.Bxe4 dxe4 17.Nd2 b5 18.Nxe4 f6 0-1 {time}

External Links

Chess Program

Albatross' ICGA Tournaments

Misc

Albatross fom Wikipedia
Albatross (disambiguation) fom Wikipedia
Albatross (metaphor) fom Wikipedia
Brickbat Books: Featured: The Albatross Continental Library
Passport - Albatross Song, album Cross-Collateral (1975) ^[9], YouTube Video
lineup: Klaus Doldinger, Curt Cress, Wolfgang Schmid, Kristian Schultze

References

^ Albatross' ICGA Tournaments
^ Short-tailed Albatross taken by - James Lloyd, Place - Eastern Island, Midway Atoll, March 2007, Short tailed Albatross.jpg photo - James photos at pbase.com, Albatross from Wikipedia
^ Jonathan Eyers (2011). Don't Shoot the Albatross!: Nautical Myths and Superstitions. ISBN 978-1-4081-3131-2
^ Why?:Shoot the albatross - Uncyclopedia, the content-free encyclopedia
^ The Rime of the Ancient Mariner from Wikipedia
^ Tony Harrington (1983). Chess Tournament - 4th European Microcomputer Chess Championship. Personal Computer World, December 1983
^ London 1980 - Chess - Round 1 - Game 7 (ICGA Tournaments)
^ Kevin O’Connell (1980). World Microcomputer Chess Championship. Personal Computer World, November 1980
^ Cross-collateralization from Wikipedia

What links here?

Page	Date Edited
Albatross	May 5, 2017
Engines	Mar 10, 2018
European MCC 1981	May 22, 2016
European MCC 1983	May 22, 2016
WMCCC 1980	Dec 25, 2017

Up one Level

Algorithms

GerdIsenberg — Fri, 05 May 2017 17:44:04 GMT

Home * Programming * Algorithms

		In mathematics and computer science, an algorithm is an method for solving a problem expressed as a finite sequence of instructions. The term “algorithm” is derived from the name of Muḥammad ibn Mūsā al-Khwārizmī (born approximately 780 in Khwarezm, died between 835 and 850), the Persian mathematician, astronomer, geographer, and scholar in the House of Wisdom in Baghdad, from the Khorasan province of present-day Uzbekistan ^[1] .
Muḥammad ibn Mūsā al-Khwārizmī ^[2]

General Concepts

Sorting and Searching

Enumeration and Backtracking

Mathematical Optimization

Combinatorial

Publications

1960 ...

Donald E. Knuth (1968 ...). The Art of Computer Programming (TAOCP) ^[3]
Volume 1 - Fundamental Algorithms (1968)
Volume 2 - Seminumerical Algorithms (1969)
Volume 3 - Sorting and Searching (1973)
Volume 4 - Combinatorial Algorithms in preparation (five fascicles have been published as of April 2009)
Volume 4A - Enumeration and Backtracking
Volume 4B - Graph and Network Algorithms
Volume 4C and possibly 4D - Optimization and Recursion
Volume 5 - Syntactic Algorithms, planned (as of August 2006, estimated in 2015).

1970 ...

Niklaus Wirth (1976). Algorithms + Data Structures = Programs.
Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1979). Algorithms of adaptive search. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 373-384. Ellis Horwood, Chichester

1980 ...

Andrei P. Ershov, Donald Knuth (Eds.) (1981). Algorithms in Modern Mathematics and Computer Science. Proceedings, Urgench, Uzbek SSR, September 16-22, 1979. Lecture Notes in Computer Science, Vol. 122, Springer » Ershov Archive
Michel Gondran, Michel Minoux, Steven Vajda (1984). Graphs and Algorithms. John Wiley & Sons, google, amazon
Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1988). Algorithms for Games. Springer, amazon.com

1990 ...

John Tromp (1993). Aspects of Algorithms and Complexity. Ph.D. thesis, University of Amsterdam, advisor Paul Vitányi
Warren D. Smith, Kevin J. Lang (1994). Values of the merging function and algorithm design as a game. NEC Research Institute, ps
Leen Ammeraal (1996). Algorithms and Data Structures in C++. Chichester: John Wiley
Steven Skiena (1998). The Algorithm Design Manual. 2nd Edition 2008
Harald Prokop (1999). Cache-Oblivious Algorithms. Masters thesis, Department of Electrical Engineering and Computer Science, MIT, pdf

2000 ...

Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102
R. C. T. Lee, S. S. Tseng, R. C. Chang, Y. T. Tsai (2005). Introduction to the Design and Analysis of Algorithms, a Strategic Approach. McGraw-Hill, amazon
Jill Cirasella (2006). Classical and Quantum Algorithms for Finding Cycles. slides as pdf
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (2006). Algorithms. McGraw-Hill, amazon
Jacques Bahi, Sylvain Contassot-Vivier, Raphaël Couturier (2007). Parallel Iterative Algorithms: From Sequential to Grid Computing. Chapman & Hall/CRC Numerical Analysis and Scientific Computing Series
David J. Stracuzzi (2007). Randomized Feature Selection. in Huan Liu, Hiroshi Motoda (eds.) Computational Methods of Feature Selection. CRC Press, pdf
Steven Skiena (2008). The Algorithm Design Manual. Springer, 2nd Edition
Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer
Michel Gondran, Michel Minoux (2008, 2010). Graphs, dioids and semirings - New Models and Algorithms. Springer New York, from google, amazon.com, 2nd edition from alibris.com ^[4]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to Algorithms, 3rd Edition.

2010 ...

Donald Knuth (2010). Selected Papers on Design of Algorithms. CSLI lecture notes series 191, Cambridge University Press
Berthold Vöcking et al. (eds.) (2011). Algorithms Unplugged. Springer
Katja Grace (2013). Algorithmic Progress in Six Domains. Technical report 2013-3, Machine Intelligence Research Institute, Berkeley, CA, pdf, 5 Game Playing, 5.1 Chess, 5.2 Go, 9 Machine Learning

External Links

Algorithms

Algebra and Calculus

Graphics

Linear Programming

Sorting and Searching

Complexity

Misc

References

^ Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer, Appetizer: Integer Arithmetics (pdf)
^ A stamp issued September 6, 1983 in the Soviet Union, commemorating Al-Khwārizmī's (approximate) 1200th birthday
^ The Art of Computer Programming from Wikipedia
^ Ordinal optimization from Wikipedia

What links here?

Page	Date Edited
Alan Turing	Feb 8, 2017
Alexander Szabo	Nov 10, 2012
Algorithms	May 5, 2017
Automated Tuning	Feb 27, 2018
Backtracking	Dec 16, 2017
Bill Gosper	Aug 20, 2014
Complexity to include	Jun 16, 2011
Creative Computing	Dec 19, 2013
Data	Nov 26, 2017
David Eppstein	Oct 10, 2013
De Bruijn Sequence Generator	Dec 1, 2016
Deep Learning	Feb 12, 2018
Denis Xavier Charles	Nov 5, 2013
Djinn	Feb 8, 2016
Donald Knuth	Aug 29, 2016
Dorky	Oct 10, 2016
Dynamic Programming	Feb 11, 2018
Edouard Bonnet	Aug 13, 2017
Evgeniy Korniloff	Nov 22, 2015
Florian Jamain	Aug 11, 2017
Fredrik Niemelä	Dec 29, 2016
Games	Feb 20, 2018
Iteration	May 5, 2017
Jay Scott	Dec 1, 2017
Jill Cirasella	Apr 16, 2015
Joe Culberson	Dec 13, 2016
John Romein	Aug 5, 2016
John Tromp	Jan 6, 2017
Kazunori Yamaguchi	Jun 20, 2016
Larry Wagner	Dec 22, 2017
Linked List	Oct 11, 2016
Mathematician	Apr 9, 2018
Memory	Dec 8, 2017
Neural MoveMap Heuristic	Sep 24, 2015
Oliver Vornberger	Oct 23, 2015
Optimization	Feb 28, 2018
Parallel Prefix Algorithms	Jun 22, 2016
Persistent Hash Table	Dec 31, 2017
Peter Sanders	May 23, 2016
Petr Baudiš	Dec 9, 2017
Playing Strength	Mar 31, 2018
Programming	Dec 16, 2017
Protocols	Jan 20, 2018
Pseudorandom number generator	May 11, 2017
Recursion	Nov 18, 2017
Retrograde Analysis	Mar 21, 2017
Richard C. T. Lee	May 13, 2015
Richard Lang	Jan 7, 2016
Robert A. Wagner	Oct 28, 2013
Shun-Shii Lin	Jan 21, 2017
Simulated Annealing	May 8, 2017
Sloppy	Sep 17, 2016
Space-Time Tradeoff	Jun 17, 2015
SPSA	May 8, 2017
Strategy	Jan 18, 2018
Thomas Sauerwald	May 7, 2014
Toshinori Munakata	Feb 12, 2016
Traversing Subsets of a Set	Oct 14, 2016
Trial and Error	Feb 11, 2018
UCT	Jan 22, 2018
Warren D. Smith	Sep 12, 2015
Wee Chong Oon	Jul 16, 2015
Wojciech Wieczorek	Mar 17, 2015

Up one Level

AliBaba

GerdIsenberg — Sun, 17 Aug 2014 09:44:53 GMT

Home * Engines * AliBaba

		AliBaba, an experimental chess engine by Dennis Breuker written for testing various hashing algorithms and replacement schemes as subject of his Ph.D. thesis Memory versus Search in Games ^[1]. With the permission of the author, a modified open source version was made available by Dann Corbit ^[2], later adopted to WinBoard by Jim Ablett ^[3]. AliBaba uses a 16x12 board and applies PVS alpha-beta with late move reductions within the obligatory iterative deepening framework with aspiration windows.
Ali Baba ^[4]

Forum Posts

Alibaba test bed (by Dennis Breuker) by Dann Corbit, CCC, March 28, 2000
Nunn test positions in Alibaba format by Pete Galati, CCC, March 30, 2000
Alibaba (Dennis Breuker - 1995) with winboard support by Jim Ablett, CCC, December 31, 2008

External Links

Chess Engine

Alibaba compiled by Jim Ablett, hosted by Kirill Kryukov

Misc

Ali Baba from Wikipedia
Ali Baba (disambiguation) from Wikipedia
Alibaba Group from Wikipedia
Kraan - Kraan Arabia, 1972, YouTube Video

References

^ Dennis Breuker (1998). Memory versus Search in Games. Ph.D. thesis, Maastricht University, pdf via Dennis Breuker's page
^ Alibaba test bed (by Dennis Breuker) by Dann Corbit, CCC, March 28, 2000
^ Alibaba (Dennis Breuker - 1995) with winboard support by Jim Ablett, CCC, December 31, 2008
^ Ali Baba by Maxfield Parrish, 1909, One Thousand and One Nights, Ali Baba from Wikipedia

What links here?

Page	Date Edited
AliBaba	Aug 17, 2014
Dennis Breuker	Dec 19, 2016
Disney's Aladdin Chess Adventures	May 15, 2014
Engines	Mar 10, 2018
Maastricht University	May 15, 2017

Up one Level

Alice

GerdIsenberg — Wed, 20 May 2015 20:46:41 GMT

Home * Engines * Alice

		Alice, an experimental open source chess engine under the GNU General Public License written by Sven Reichard in C++, compliant with the Chess Engine Communication Protocol. Alice is an object oriented program developed under GCC and Linux. The board is a vector of 64 pointers to pieces, while piece is an abstract class, with intermediate subclasses for common piece properties such as sliding versus none sliding pieces, and finally instantiable subclasses for the concrete pieces, like Pawn, Rook, etc., and "null pieces" for the empty squares ^[1]. Jim Ablett provides recent compiles for 32/64-bit Windows and Linux ^[2].
Alice in Wonderland ^[3]

Bitboards

Alice is an object oriented Bitboard engine, applying Rotated Bitboards to determine sliding piece attacks. Size of of the encapsulated Bitboard class is 8 by unsigned long long number ^[4].

namespace Alice
{
  class BitboardIterator;
  class Bitboard
  {
  public:
    typedef BitboardIterator Iterator;
    Bitboard( unsigned long long n = 0ull);
    ~Bitboard();
    //operator unsigned long long() const;
    Bitboard& operator|=( const Bitboard& b );
    Bitboard& operator&=( const Bitboard& b );
    Bitboard operator~( ) const;
    ...
  private:
    unsigned long long number;
    static std::vector<unsigned long long> setMask;
    static std::vector<unsigned long long> clearMask;
    ...
    static Bitboard fileAttacks[256][64];
    static Bitboard rankAttacks[256][64] ;
    static Bitboard upDiagonalAttacks[256][64];
    static Bitboard downDiagonalAttacks[256][64] ;
    ...
  };
};

Forum Posts

Gestatten: Alice by Sven Reichard, CCC, June 23, 2002
First draw against GnuChess by Sven Reichard, CCC, November 26, 2003
Alice new Winboard engine by Pablo, Winboard Forum, March 18, 2005
Alice: A reintroduction by Sven Reichard, CCC, July 15, 2011
Sorry guys, I have to ask for another engine: Alice by Arturo Ochoa, CCC, December 03, 2012

External Links

Chess Engine

Index of /chess/engines/Jim Ablett/ALICE by Jim Ablett, hosted by Kirill Kryukov

Misc

References

^ Re: Gestatten: Alice by Sven Reichard, CCC, June 25, 2002
^ Re: Sorry guys, I have to ask for another engine: Alice by Jim Ablett, CCC, December 08, 2012
^ Jessie Willcox Smith's illustration of Alice surrounded by the characters of Wonderland. (1923), Alice's Adventures in Wonderland from Wikipedia
^ Index of /chess/engines/Jim Ablett/ALICE by Jim Ablett, hosted by Kirill Kryukov, Src/include/Bitboard.h
^ Lewis Carroll's diagram of the story as a chess game, Through the Looking-Glass - Chess
^ Glen Robert Downey (1998). The Truth About Pawn Promotion: The Development of the Chess Motif in Victorian Fiction. Ph.D. thesis, University of Victoria pdf » Promotions
^ Lewis Carroll's chess problem | ChessVibes, July 14, 2008

What links here?

Page	Date Edited
Alice	May 20, 2015
Arturo Ochoa	May 4, 2017
Engines	Mar 10, 2018
iCE	Jan 4, 2016
La Dame Blanche	Oct 15, 2015
Mathematician	Apr 9, 2018
Promotions	Jun 6, 2017
RedQueen	Nov 13, 2017
Sven Reichard	Dec 28, 2016
Traversing Subsets of a Set	Oct 14, 2016

Up one Level

All Shortest Paths

GerdIsenberg — Tue, 21 Jan 2014 21:59:47 GMT

Home * Board Representation * Bitboards * King Pattern * All shortest Paths

The All shortest Paths algorithm was introduced by Steffan Westcott ^[1]:

The Algorithm

The following routine determines if a path of set bits in 'path' 8-way connect (ie. king move) any set bit in sq1 with any set bit in sq2 (this is the same as Squares Are Connected). Also, it will return an array of bitboards showing all possible shortest paths - This is probably best explained by showing an example:

Setting sq1 to contain e4, sq2 to have both a1 and h8, and mask to be ~0 yields this all shortest paths array of bitboards:

. . . . . . . .   . . . . . . . .     . . . . . . . .   . . . . . . . .   . . . . . . . 1
. . . . . . . .   . . . . . . . .     . . . . . . . .   . . . . . . 1 1   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . . . . 1 1 .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . 1 1 . .     . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . 1 . . .   . . . 1 . . . .     . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . 1 . . . .     . . 1 . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . 1 . . . . .   . 1 . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .     . . . . . . . .   . 1 . . . . . .   1 . . . . . . .

The king needs 4 moves to reach either a1 or h8, so both possibilities are shown in the last bitboard. Also, the king has a choice of squares along the way, meaning there are many shortest paths.

/////////////////////////////////////////////////////////////////////////
//
// Returns length of shortest path of set bits present in 'path' that
// 8-way connect any set bit in sq1 to any set bit of sq2. 0 is returned
// if no such path exists. Also fills a sequence of bitboards asp[length]
// that describes all such shortest paths.
 
int allShortestPaths(U64 sq1, U64 sq2, U64 path, U64* asp)
{
    // Do an 8-way flood fill with sq1, masking off bits not in path and
    // storing the fill frontier at every step. Stop when fill reaches
    // any set bit in sq2 or quit if fill cannot progress any further.
    // Then do 8-way flood fill from reached bits in sq2, ANDing the
    // frontiers with those from the first fill in reverse order.
 
    if (!(sq1 &= path) || !(sq2 &= path)) return 0;
                        // Drop bits not in path
                        // Early exit if sq1 or sq2 not on any path
    int i = 1;
    asp[0] = sq1;
 
    while(1)  // Fill from all set bits in sq1, to any set bit in sq2
    {
        if (sq1 & sq2) break;                     // Found good path
        U64 temp = sq1;
        sq1 |= eastOne(sq1) | westOne(sq1);       // Set all 8 neighbours
        sq1 |= soutOne(sq1) | nortOne(sq1);
        sq1 &= path;                              // Drop bits not in path
        if (sq1 == temp) return 0;                // Fill has stopped
        asp[i++] = sq1 & ~temp;                   // Store fill frontier
    }
 
    int length = i;                               // Remember path length
    asp[--i] = (sq2 &= sq1);                      // Drop unreached bits
 
    while(i)  // Fill from reached bits in sq2
    {
        U64 temp = sq2;
        sq2 |= eastOne(sq2) | westOne(sq2);       // Set all 8 neighbours
        sq2 |= soutOne(sq2) | nortOne(sq2);
        sq2 &= path;                              // Drop bits not in path
        asp[--i] &= sq2 & ~temp;                  // Intersect frontiers
    }
    return length;
}

As a reminder - one step only.

So far we've just mentioned 8-way flood filling for king/queen moves, and diagonal or rank/file 4-way filling for bishop or rook moves. A simple variant exists for knight moves too, which is handy for calculating knight mobility, and helping solve "Knight's Tour" type puzzles. Its even useful for pawns too, for quick determination of outposts outside all enemy pawn "attack cones", for example.

A fill iteration need not just go one square in each direction. With appropriate bitboard manipulation, it may extend the full ray of a sliding piece, for example. Examining the filled bitboard for 1 or 2 iterations will enable design of piece mobility terms with some simulated ply.

Optimization

Edmund Moshammer proposed following optimization with an inlined king fill routine ^[2]:

// Set all up to eight neighbours
// inline
U64 fillKing(U64 b) {
    b |= eastOne(b) | westOne(b);   
    b |= soutOne(b) | nortOne(b);
    return b;
}
 
int allShortestPaths(U64 sq1, U64 sq2, U64 path, U64* asp) {
    int i, length;
    asp[0] = sq1;
    for (i=0; !(asp[i] & sq2); i++)
        if (!(asp[i+1] = fillKing(asp[i]) & path &~asp[i])) return 0;
    length = i;
    asp[i] = sq2;
    for (; i; i--) 
       asp[i-1] &= fillKing(asp[i]) & path;
    return length;
}

External Links

Pathfinding from Wikipedia
Remember Shakti ^[3], Finding the way, part 1, YouTube Video
Zakir Hussain, U. Srinivas, John McLaughlin, V. Selvaganesh

References

^ All shortest paths & other flood-fill based algorithms by Steffan Westcott, CCC, September 13, 2002
^ Discussion about this page
^ Shakti from Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
All Shortest Paths	Jan 21, 2014
Edmund Moshammer	Sep 23, 2017
Fill Algorithms	Nov 6, 2013
Helmut Horacek	Oct 31, 2016
King Pattern	Nov 15, 2013
Mobility	Jan 17, 2018
PawnKing	Sep 5, 2014
Steffan Westcott	Jan 21, 2014
Trajectory	Jan 3, 2015

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

AlphaZero

GerdIsenberg — Sat, 10 Feb 2018 08:23:53 GMT

Home * Engines * AlphaZero

		AlphaZero, a chess and Go playing entity by Google DeepMind based on a general reinforcement learning algorithm with the same name. On December 5, 2017, the DeepMind team around David Silver, Thomas Hubert, and Julian Schrittwieser along with former Giraffe author Matthew Lai, reported on their generalized algorithm, combining Deep learning with Monte-Carlo Tree Search (MCTS) ^[1] . A 100 game match versus Stockfish 8 using 64 threads and a transposition table size of 1GiB, was won by AlphaZero using a single machine with 4 Tensor processing units (TPUs) with +28=72-0. Despite a possible hardware advantage of AlphaZero and criticized playing conditions ^[2], this seems a tremendous achievement.
The Krampus has come ^[3] ^[4]

Description

Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved a superhuman level of play in the games of chess and Shogi as well as in Go. The algorithm is a more generic version of the AlphaGo Zero algorithm that was first introduced in the domain of Go ^[5] . AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation as used in classical chess programs. This neural network takes the board position as input and outputs a vector of move probabilities. The MCTS consists of a series of simulated games of self-play whose move selection is controlled by the neural network. The search returns a vector representing a probability distribution over moves, either proportionally or greedily with respect to the visit counts at the root state.

Network Architecture

The network is a deep residual convolutional neural network ^[6] ^[7] with many layers of spatial NxN planes - 8x8 board arrays for chess. The input describes the chess position from side's to move point of view - that is color flipped for black to move. Each square cell consists of 12 piece-type and color bits, e.g. from the current bitboard board definition, and to address graph history and path-dependency - times eight, that is up to seven predecessor positions as well - so that en passant, immediate repetitions, or some sense of progress is implicit. Additional inputs, redundant inside each square cell to be conform to the convolution net, consider castling rights, halfmove clock, total move count and side to move.

The deep hidden layers connect the pieces on different squares to each other due to consecutive 3x3 convolutions, where a cell of a layer is connected to the correspondent 3x3 receptive field of the previous layer, so that after 4 layers, each square is connected to every other cell in the original input layer ^[8]. The output of the neural network is finally represented as an 8x8 board array as well, for every origin square up to 73 target square possibilities (NRayDirs x MaxRayLength + NKnightDirs + NPawnDirs * NMinorPromotions), encoding a probability distribution over 64x73 = 4,672 possible moves, where illegal moves were masked out by setting their probabilities to zero, re-normalising the probabilities for remaining moves.

Training

AlphaZero was trained in 700,000 steps or mini-batches of size 4096 each, starting from randomly initialized parameters, using 5,000 first-generation TPUs ^[9] to generate self-play games and 64 second-generation TPUs ^[10] ^[11] ^[12] to train the neural networks ^[13] .

Publications

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, Demis Hassabis (2017). Mastering the game of Go without human knowledge. Nature, Vol. 550, pdf
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815

Forum Posts

2017

Google's AlphaGo team has been working on chess by Peter Kappler, CCC, December 06, 2017
Historic Milestone: AlphaZero by Miguel Castanuela, CCC, December 06, 2017
AlphaZero beats AlphaGo Zero, Stockfish, and Elmo by Carl Lumma, CCC, December 06, 2017
AlphaZero vs Stockfish by Bigler, CCC, December 06, 2017
Deepmind drops the bomb by Leebot, FishCooking, December 06, 2017
AlphaZero beats Stockfish 8 by 64-36 by Venator, Rybka Forum, December 06, 2017
Alpha Zero by BB+, OpenChess Forum, December 06, 2017
AlphaGo Zero And AlphaZero, RomiChess done better by Michael Sherwin, CCC, December 07, 2017 » RomiChess
BBC News; 'Google's ... DeepMind AI claims chess crown' by pennine22, Hiarcs Forum, December 07, 2017
Press Release Stockfish vs. AlphaZero by Michael Whiteley, FishCooking, December 08, 2017
AlphaZero reinvents mobility and romanticism by Chris Whittington, Rybka Forum, December 08, 2017 » Alpha Zero's "Immortal Zugzwang Game"
Reactions about AlphaZero from top GMs... by Norman Schmidt, CCC, December 08, 2017 » Reactions From Top GMs, Stockfish Author
AlphaZero is not like other chess programs by Dann Corbit, CCC, December 08, 2017
Re: AlphaZero is not like other chess programs by Rein Halbersma, CCC, December 09, 2017
Photo of Google Cloud TPU cluster by Norman Schmidt, CCC, December 09, 2017
Cerebellum analysis of the AlphaZero - Stockfish Games by Thomas Zipproth, CCC, December 11, 2017 » Cerebellum
Open letter to Google DeepMind by Michael Stembera, FishCooking, December 12, 2017
recent article on alphazero ... 12/11/2017 ... by Dan Ellwein, CCC, December 14, 2017
An AlphaZero inspired project by Truls Edvard Stokke, CCC, December 14, 2017
AlphaZero - Tactical Abilities by David Rasmussen, CCC, December 16, 2017
In chess,AlphaZero outperformed Stockfish after just 4 hours by Ed Schroder, CCC, December 18, 2017
AlphaZero - Youtube Videos by Christoph Fieberg, CSS Forum, December 18, 2017
AlphaZero Chess is not that strong ... by Vincent Lejeune, CCC, December 19, 2017
David Silver (Deepmind) inaccuracies by Ed Schroder, CCC, December 21, 2017
AZ vs SF - game 99 by Rebel, Rybka Forum, December 23, 2017
AlphaZero performance by Martin Sedlak, CCC, December 25, 2017
A Simple Alpha(Go) Zero Tutorial by Oliver Roese, CCC, December 30, 2017
AlphaZero: The 10 Top Shots by Walter Eigenmann, CCC, December 30, 2017

2018

SF was more seriously handicapped than I thought by Kai Laskos, CCC, January 02, 2018
Chess World to Google Deep Mind..Prove You beat Stockfish 8! by AA Ross, CCC, January 11, 2018
Article:"How Alpha Zero Sees/Wins" by AA Ross, CCC, January 17, 2018 » How AlphaZero Wins
Connect 4 AlphaZero implemented using Python... by Steve Maughan, CCC, January 29, 2018 » Connect Four, Python
Seeing Alphazero in perspective ... by Dan Ellwein, CCC, February 10, 2018

External Links

AlphaZero from Wikipedia
AlphaGo Zero - AlphaZero from Wikipedia
Keynote David Silver NIPS 2017 Deep Reinforcement Learning Symposium AlphaZero, December 06, 2017, YouTube Video ^[14]
A Simple Alpha(Go) Zero Tutorial by Surag Nair, Stanford University, December 29, 2017 ^[15]
GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)

Reports

DeepMind’s AI became a superhuman chess player in a few hours, just for fun by James Vincent, The Verge, December 06, 2017
Entire human chess knowledge learned and surpassed by DeepMind's AlphaZero in four hours by Sarah Knapton, and Leon Watson, The Telegraph, December 06, 2017
Google's 'superhuman' DeepMind AI claims chess crown, BBC News, December 06, 2017 ^[16]
DeepMind’s AlphaZero crushes chess by Colin McGourty, Chess24.com, December 06, 2017
One Small Step for Computers, One Giant Leap for Mankind by Dana Mackenzie, Dana Blogs Chess, December 06, 2017
Google's AlphaZero Destroys Stockfish In 100-Game Match by Mike Klein, Chess.com, December 06, 2017
The future is here – AlphaZero learns chess by Albert Silver, ChessBase News, December 06, 2017
AlphaZero: Reactions From Top GMs, Stockfish Author by Peter Doggers, Chess.com, December 08, 2017 » Stockfish, Tord Romstad ^[17]
Is AlphaZero really a scientific breakthrough in AI? by Jose Camacho Collados, Medium, December 11, 2017 ^[18]
Alpha Zero: Comparing "Orangutans and Apples" by André Schulz, ChessBase News, December 13, 2017
Kasparov on Deep Learning in chess by Frederic Friedel, ChessBase News, December 13, 2017

Stockfish Match

AlphaZero vs Stockfish Games • lichess.org
The chess games of AlphaZero (Computer) from chessgames.com
Cerebellum AlphaZero Analysis » Cerebellum ^[19]
Deep Mind Alpha Zero's "Immortal Zugzwang Game" against Stockfish by Antonio Radic, December 07, 2017, YouTube Video ^[20] ^[21] » Zugzwang
Deep Mind AI Alpha Zero Dismantles Stockfish's French Defense by Antonio Radic, December 08, 2017, YouTube Video
How AlphaZero Wins by Dana Mackenzie, Dana Blogs Chess, December 15, 2017 ^[22]

Misc

How to build your own AlphaZero AI using Python and Keras by David Foster, January 26, 2018 » Connect Four, Python ^[23]
Can - Halleluwah, from Tago Mago 1971, YouTube Video
lineup: Irmin Schmidt, Michael Karoli, Holger Czukay, Damo Suzuki, Jaki Liebezeit

References

^ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815
^ Alpha Zero by BB+, OpenChess Forum, December 06, 2017
^ Krampus at Perchtenlauf in Klagenfurt, Image by Anita Martinz, December 02, 2006, CC BY 2.0, Wikimedia Commons
^ "5th of December - The Krampus has come" was suggested by Michael Scheidl in AlphaZero by Peter Martan, CSS Forum, December 06, 2017, with further comments by Ingo Althöfer
^ AlphaGo Zero: Learning from scratch by Demis Hassabis and David Silver, DeepMind, October 18, 2017
^ The principle of residual nets is to add the input of the layer to the output of each layer. With this simple modification training is faster and enables deeper networks, see Tristan Cazenave (2017). Residual Networks for Computer Go. IEEE Transactions on Computational Intelligence and AI in Games, Vol. PP, No. 99, pdf
^ Residual Networks for Computer Go by Brahim Hamadicharef, CCC, December 07, 2017
^ Re: AlphaZero is not like other chess programs by Rein Halbersma, CCC, December 09, 2017
^ First In-Depth Look at Google’s TPU Architecture by Nicole Hemsoth, The Next Platform, April 05, 2017
^ Photo of Google Cloud TPU cluster by Norman Schmidt, CCC, December 09, 2017
^ First In-Depth Look at Google’s New Second-Generation TPU by Nicole Hemsoth, The Next Platform, May 17, 2017
^ Under The Hood Of Google’s TPU2 Machine Learning Clusters by Paul Teich, The Next Platform, May 22, 2017
^ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815
^ AlphaZero explained by one creator by Mario Carbonell Martinez, CCC, December 19, 2017
^ A Simple Alpha(Go) Zero Tutorial by Oliver Roese, CCC, December 30, 2017
^ BBC News; 'Google's ... DeepMind AI claims chess crown' by pennine22, Hiarcs Forum, December 07, 2017
^ Reactions about AlphaZero from top GMs... by Norman Schmidt, CCC, December 08, 2017
^ recent article on alphazero ... 12/11/2017 ... by Dan Ellwein, CCC, December 14, 2017
^ Cerebellum analysis of the AlphaZero - Stockfish Games by Thomas Zipproth, CCC, December 11, 2017
^ AlphaZero reinvents mobility and romanticism by Chris Whittington, Rybka Forum, December 08, 2017
^ Immortal Zugzwang Game from Wikipedia
^ Article:"How Alpha Zero Sees/Wins" by AA Ross, CCC, January 17, 2018
^ Connect 4 AlphaZero implemented using Python... by Steve Maughan, CCC, January 29, 2018

What links here?

Page	Date Edited
Albert Silver	Feb 25, 2018
Alpha I	Dec 6, 2017
AlphaZero	Feb 10, 2018
Arthur Guez	Dec 6, 2017
Chess	Jan 21, 2018
Chris Whittington	Dec 9, 2017
Connect Four	Jan 31, 2018
Dana Mackenzie	Jan 18, 2018
Dann Corbit	Dec 9, 2017
David Rasmussen	Dec 16, 2017
David Silver	Feb 11, 2018
Deep Learning	Feb 12, 2018
DeepMind	Dec 9, 2017
Demis Hassabis	Dec 8, 2017
Dharshan Kumaran	Dec 9, 2017
Engines	Mar 10, 2018
Frederic Friedel	Jan 6, 2018
Go	Jan 24, 2018
Ioannis Antonoglou	Dec 6, 2017
Julian Schrittwieser	Dec 7, 2017
Karen Simonyan	Dec 10, 2017
Laurent Sifre	Dec 7, 2017
LCZero	Apr 18, 2018
Learning	Feb 20, 2018
Marc Lanctot	Jan 10, 2018
Mark Watkins	Dec 6, 2017
Martin Sedlak	Dec 25, 2017
Mathematician	Apr 9, 2018
Matthew Lai	Dec 6, 2017
Michael Sherwin	Dec 18, 2017
Monte-Carlo Tree Search	Apr 26, 2018
Neural Networks	Mar 12, 2018
Othello	Jan 4, 2018
Peter Kappler	Feb 4, 2018
Python	Jan 31, 2018
Reinforcement Learning	Feb 12, 2018
RomiChess	Jan 2, 2018
Shogi	Feb 19, 2018
Steve Maughan	Jan 31, 2018
Stockfish	Apr 7, 2018
Test-Positions	Feb 25, 2018
Thomas Hubert	Dec 7, 2017
Thore Graepel	Jan 10, 2018
Timothy Lillicrap	Dec 9, 2017
Tord Romstad	Dec 9, 2017
University of Toronto	Dec 8, 2017
Zugzwang	Dec 8, 2017

Up one Level

Alybadix

GerdIsenberg — Tue, 26 Apr 2016 19:59:05 GMT

Home * Engines * Alybadix

Alybadix,
a set of programs for solving orthodox (Matebadix, Sidebadix, ...) and heterodox (Fairybadix) ^[1] chess problems and tools, developed by Ilkka Blom since 1980 initially for Apple II and later for PCs running DOS. The solver AP.exe is completely written in x86 assembly language using the DJGPP suite ^[2]. Alybadix supports the problem genres checkmate, stalemate, helpmate, helpstalemate, selfmate, selfstalemate, reflexmates, and seriesmover in N moves, and further Circe chess, maximummers ^[3] ^[4], and many Fairy types ^[5]. Alybadix is supported by Paul Wiereyn's Windows GUI APwin. It comes with a large problem collection and features quality printing supporting Ghostscript 9.00 or newer ^[6].

Forum Posts

Can Alybadix or Gustav solve this studies by Uri Blass, CCC, December 10, 1998
CHEST vs. ALYBADIX by Jouni Uski, CCC, October 23, 2002 » Chest

External Links

Alybadix chess solving programs
Alybadix chess solving program - AP.exe
Alybadix Chess | Facebook
Alybadix - from Software for handling chess problems, Wikipedia
apwin
Alybadix 2005 and (fairy) chess endgames by Václav Kotěšovec, April 23.2005
GUSTAV - fastest program for orthodox selfmates and moremovers by Václav Kotěšovec, October 6, 2009 » Gustav - Compare with ALYBADIX
Brand X - Unorthodox Behaviour, Live at Ronnie Scott's Jazz Club, September 1976, YouTube Video

References

What links here?

Page	Date Edited
Alybadix	Apr 26, 2016
APwin	Oct 12, 2017
Chest	Mar 3, 2015
Engines	Mar 10, 2018
Gustav	May 14, 2016
Ilkka Blom	Mar 3, 2015
Paul Wiereyn	Jun 4, 2015
Popeye	Oct 11, 2017

Up one level

Anaconda

GerdIsenberg — Sat, 04 Jul 2015 13:29:55 GMT

Home * Engines * Anaconda

		Anaconda, a Chessbase compliant chess engine by Frank Schneider and Kai Skibbe and a successor of their GromitChess program, written in C++ with a 0x88 board representation, an improved evaluation and time-management, and some new search heuristics, which allow it to search deeper but more selective. GromitChess was renamed to Anaconda in 2003 to prevent copyright infringements with Wallace and Gromit by Aardman Animations ^[1] . The new name also devotes the positional playing style of the program, to slowly restrict its opponent mobility. Anaconda played the IPCCC 2003, IPCCC 2004, and IPCCC 2005, and as Chess960 compliant engine, the second Livingston Chess960 Computer World Championship.
John Collier - Lilith ^[2]

Forum Posts

Anaconda 1.0 (ex-GromitChess) available as CB-native by Kai Skibbe, CCC, March 08, 2003
the reason why Anaconda can´t draw against Hydra... by Thomas Lagershausen, CCC, March 01, 2005 » Hydra
Anaconda Strategy by BWater, Chess.com, September 22, 2009

External Links

Chess Engine

Misc

References

^ Anaconda 1.0 (ex-GromitChess) available as CB-native by Kai Skibbe, CCC, March 08, 2003
^ Lilith by John Collier, 1892, Oil on canvas, The Atkinson Art Gallery, Southport, England, Wikimedia Commons, Lilith from Wikipedia

What links here?

Page	Date Edited
Anaconda	Jul 4, 2015
Chess960CWC 2006	Sep 25, 2014
Eigenmann Endgame Test	Jun 1, 2017
Engines	Mar 10, 2018
Frank Schneider	Jan 7, 2016
Ginkgo	Jul 13, 2016
Gromit	Apr 5, 2017
IPCCC 2003	Aug 17, 2016
IPCCC 2004	Dec 1, 2014
IPCCC 2005	Aug 21, 2015
Kai Skibbe	Jan 7, 2016
PocketGrandmaster	Sep 17, 2015

Up one level

Analog Evaluation

GerdIsenberg — Fri, 27 Oct 2017 08:04:25 GMT

Home * Hardware * Analog Evaluation

		Analog Evaluation, (Analogue Evaluation) a hypothetical dedicated special purpose hardware to evaluate a chess position using analog circuits such as resistive networks, operational amplifier (op-amps), and in particular the analogous FPGA counterparts FPAA, to map digital or discrete input signals, representing the board or aspects of the board, to an analog output representing an evaluation score along with some noise as input of an analog-to-digital converter. Jonathan Allen, Edward Hamilton, and Robert Levinson mentioned a method to convert a chess mobility graph to a resistive network which could be computed using the residual resistance property of interconnected chips within their Morph III project ^[1]. Using memristors, memistors, or even a kind of motorized potentiometers ^[2] as used in closed loop control and servomechanisms, would allow the implementation of physical neural networks as analog evaluation device with machine learning features ^[3].
Summing amplifier ^[4]

Summing Amplifier

A summing amplifier using an operational amplifier with feedback resistor Rf sums several (weighted by input resistors 1..n) voltages to an negated output ...

$V_{\text{out}} = -R_{\text{f}} \left( \frac{V_1}{R_1} + \frac{V_2}{R_2} + \cdots + \frac{V_n}{R_n} \right)$

... and may be used to implement a classical evaluation function as linear combination of independent features (F) and associated weights (W):

$\displaystyle Eval = \sum_{i=1}^{n} {F_i * W_i}$

Publications

Jonathan Allen, Edward Hamilton, Robert Levinson (1997). New Advances in Adaptive Pattern-Oriented Chess. Advances in Computer Chess 8
Amir Yazdanbakhsh, Renée St. Amant, Bradley Thwaites, Jongse Park, Hadi Esmaeilzadeh, Arjang Hassibi, Luis Ceze, Doug Burger (2014). Toward General-Purpose Code Acceleration with Analog Computation. ACM SIGARCH Computer Architecture News - ISCA '14, Vol. 42, No. 3, pdf

Forum Posts

Discussion of Special Purpose hardware for chess search by Rick Fadden, CCC, April 25, 2008
Re: Discussion of Special Purpose hardware for chess search by Gerd Isenberg, CCC, April 25, 2008
How can you create an analog sigmoid voltage transfer function (from simple parts)?, AskElektonics, Reddit, March 24, 2014

External Links

References

^ Jonathan Allen, Edward Hamilton, Robert Levinson (1997). New Advances in Adaptive Pattern-Oriented Chess. Advances in Computer Chess 8
^ Motorized potentiometers for high precision proportional controls
^ SciDAC Review - HARDWARE: Cortical Computing with Memristive Nanodevices
^ A circuit diagram of a Summing amplifier made using an operational amplifier, made by Inductiveload, January 26 2009, Wikimedia Commons
^ Rätsel - Wiikipedia.de (German) » Riddle from Wikipedia

What links here?

Page	Date Edited
Analog Evaluation	Oct 27, 2017
Arduino	Feb 21, 2018
Evaluation	Feb 1, 2018
Hardware	Jan 20, 2018
Neural Networks	Mar 12, 2018
PIC Microcontroller	Oct 27, 2017

Up one Level

Andscacs

GerdIsenberg — Tue, 16 Jan 2018 10:28:17 GMT

Home * Engines * Andscacs

		Andscacs, an UCI compliant chess engine by Daniel José Queraltó. Its development started in September 2013, and the first release was published in February 2014 ^[1]. Andscacs soon evolved to a top engine, becoming runner-up at the IGWT III losing the final from Chiron with the narrowest margin of 4½ - 5½, but taking revenge one year later at the IGWT IV, this time with 6½ - 5½ to its favour. At the Tenth Annual ACCA World Computer Rapid Chess Championship 2016, Andscacs emphasized its ambitions, and became runner-up without losing a single game, but 12 wins and 3 draws, and thus the only program preventing later winner Komodo from a 100% score.
Andscacs Logo ^[2]

Description

Being a bitboard engine, Andscacs determines sliding piece attacks ray-wise, quite similar to the classical approach ^[3]. Since version 0.70, Andscacs uses magic bitboards to speed the attack calculations ^[4].

Search

Andscacs applies a principal variation search with tranposition table inside an iterative deepening framework with aspiration windows ^[5]. Beside quiescence, selectivity is due to adaptive null move pruning, late move reductions, check extensions, singular extensions, razoring and futility pruning. Move ordering is further improved by the killer heuristic, IID and static exchange evaluation, the latter also used to prune bad captures in quiescence and futile moves near the horizon. Since version 0.70, a hash move is tried in quiescence search even if it’s a quiet move. Trying only captures and promotions was clearly weaker ^[6]. Version 0.80 in Apil 2015 introduced a threaded parallel search ^[7], a Lazy SMP approach ^[8].

Evaluation

The evaluation considers material imbalances, and has piece-square tables for middlegame and endgame, piece values adapted by type of positions (open, closed), different types of piece mobility, king safety and sophisticated pawn structure evaluation with focus on passed pawns, most features smoothed out between game phases by a tapered eval. Since version 0.62u, evaluation scores are cached with a small evaluation hash table ^[9].

Tuning

The about 200 evaluation features were tuned with 750.000 positions to minimize the standard deviation of Stockfish's and Andscacs' static evaluation, which initially added a nice Elo boost to Andscacs ^[10], without playing too similar.

Forum Posts

2014

New engine - Andscacs by Daniel José Queraltó, CCC, February 06, 2014
Andscacs - New version by Daniel José Queraltó, CCC, February 09, 2014
Andscacs - New version by Daniel José Queraltó, CCC, March 03, 2014
Andscacs - New version 0.62w by Daniel José Queraltó, CCC, April 10, 2014
Andscacs - New version 0.62x by Daniel José Queraltó, CCC, May 05, 2014
Andscacs - New version 0.64 by Daniel José Queraltó, CCC, June 07, 2014
Andscacs - New version 0.70 by Daniel José Queraltó, CCC, November 05, 2014
Changes in Andscacs 0.70 by Daniel José Queraltó, CCC, November 08, 2014
Andscacs - New version 0.71 by Daniel José Queraltó, CCC, December 17, 2014
Changes in Andscacs 0.71 by Daniel José Queraltó, CCC, December 19, 2014

2015

Andscacs - New version 0.72 by Daniel José Queraltó, CCC, February 01, 2015
Andscacs - Test version 74024 by Daniel José Queraltó, CCC, April 09, 2015
Trying to improve lazy smp by Daniel José Queraltó, CCC, April 11, 2015 » Lazy SMP
Empirical results with Lazy SMP, YBWC, DTS by Kai Laskos, CCC, April 16, 2015 » Lazy SMP, YBWC, DTS
Andscacs - New version 0.80 by Daniel José Queraltó, CCC, April 17, 2015
Andscacs - New version 0.81 by Daniel José Queraltó, CCC, June 20, 2015
Andscacs - New version 0.81 - Detailed changes by Daniel José Queraltó, CCC, June 20, 2015
Andscacs - New version 0.82 by Daniel José Queraltó, CCC, August 16, 2015
Andscacs - New version 0.83 by Daniel José Queraltó, CCC, November 10, 2015
Andscacs - New version 0.84 by Daniel José Queraltó, CCC, December 07, 2015
Re: Why computing K that minimizes the sigmoid func. value? by Daniel José Queraltó, CCC, December 07, 2015 » Texel's Tuning Method

2016

Andscacs - New version 0.85 by Daniel José Queraltó, CCC, January 22, 2016
Andscacs - New version 0.86 by Daniel José Queraltó, CCC, March 24, 2016
Singular extension by Daniel José Queraltó, CCC, June 11, 2016 » Singular Extensions
Andscacs 0.86.196 BMI2 is available ... by Frank Quisinsky, June 15, 2016 » BMI2
Andscacs - New version 0.87 by Daniel José Queraltó, CCC, June 19, 2016
Andscacs - New version 0.872 by Daniel José Queraltó, CCC, July 23, 2016
Detailed changes in Andscacs from 0.86 to 0.872 by Daniel José Queraltó, CCC, July 25, 2016
Andscacs, developing version by Daniel José Queraltó, CCC, October 22, 2016
Andscacs - New version 0.88 by Daniel José Queraltó, CCC, October 28, 2016

2017

Andscacs - New version 0.90 by Daniel José Queraltó, CCC, March 25, 2017
Andscacs - New version 0.91 by Daniel José Queraltó, CCC, May 09, 2017
Andscacs new PH feature: first impressions by Rodolfo Leoni, CCC, July 08, 2017 » Persistent Hash Table
Andscacs - New version 0.92 by Daniel José Queraltó, CCC, September 17, 2017
Andscacs - New version 0.921 with source by Daniel José Queraltó, CCC, November 04, 2017
Re: Andscacs - New version 0.921 with source by Jon Dart, CCC, November 09, 2017 » TCEC Season 10
Re: Andscacs - New version 0.921 with source by Ronald de Man, CCC, November 11, 2017
Andscacs, test version by Daniel José Queraltó, CCC, December 31, 2017

2018

Andscacs - New version 0.93 by Daniel José Queraltó, CCC, January 14, 2018

External Links

Chess Engine

Misc

Jorge Retamoza Cuarteto - La Cachila, Andorra Jazz Hivern Fest 2013, YouTube Video
Claudio Constantini, Alejandro Di Costanzo, Hernán Hock, Jorge Retamoza

References

^ New engine - Andscacs by Daniel José Queraltó, CCC, February 06, 2014
^ Andscacs Logo with Flag of Andorra, Andscacs Homepage
^ Re: Andscacs - New version by Daniel José Queraltó, CCC, March 03, 2014
^ Andscacs - New version 0.70 by Daniel José Queraltó, CCC, November 05, 2014
^ New engine - Andscacs by Daniel José Queraltó, CCC, February 06, 2014
^ Changes in Andscacs 0.70 by Daniel José Queraltó, CCC, November 08, 2014
^ Andscacs - New version 0.80 by Daniel José Queraltó, CCC, April 17, 2015
^ Trying to improve lazy smp by Daniel José Queraltó, CCC, April 11, 2015
^ Andscacs Homepage
^ Re: New engine - Andscacs by Daniel José Queraltó, CCC, February 06, 2014

What links here?

Page	Date Edited
Andscacs	Jan 16, 2018
Daniel José Queraltó	Dec 31, 2017
Engine releases	Apr 23, 2018
Engines	Mar 10, 2018
IGT 2017	Oct 2, 2017
IGWT III	May 15, 2017
IGWT IV	May 17, 2017
Italian Computer Chess Championship	Sep 24, 2017
Komodo	Mar 6, 2018
Lazy SMP	Jan 4, 2018
Persistent Hash Table	Dec 31, 2017
Shield	May 17, 2017
Singular Extensions	Jan 9, 2018
TCEC Season 10	Jan 3, 2018
TCEC Season 11	Apr 18, 2018
TCEC Season 9	Nov 6, 2017
Texel's Tuning Method	Dec 2, 2017
WCRCC 2016	Jun 27, 2017

Up one level

Anechka

GerdIsenberg — Thu, 20 Mar 2014 13:11:20 GMT

Home * Engines * Anechka

Anechka, (Анечка, Anya)
an UCI compliant chess engine by Sergei Nefedov, written in Delphi. The program was developed incrementally, starting with board representation, generation, make and unmake move, alpha-beta search, and rudimentary evaluation, published in 2003, further improving in subsequent versions. Version 0.05 disabled checks in quiescence search and had a slightly modified evaluation function, yielding in a significant increase in playing strength on short time controls ^[1]. Latest version is Anechka 0.08, released in July 2006 ^[2]. This version played the CCCCISC 2008 in Moscow with 3½/7, and the IOPCCC 2008 in Łódź.

Selected Games

IOPCCC 2008, round 2, Tytan - Anechka ^[3]

[Event "IOPCCC 2008"]
[Site "Lodz"]
[Date "2008.06.27"]
[Round "2"]
[White "Tytan"]
[Black "Anechka"]
[Result "1/2-1/2"]
 
1.d4 Nf6 2.Nf3 g6 3.c4 Bg7 4.g3 d5 5.cxd5 Nxd5 6.Bg2 Nb6 7.O-O Nc6 8.e3 O-O 9.Nc3 Re8 
10.d5 Ne5 11.Nxe5 Bxe5 12.a4 a5 13.Nb5 Rb8 14.Bd2 Nxd5 15.Bxa5 e6 16.e4 b6 17.Bd2 Ne7 
18.Qc1 Ba6 19.Rd1 Qc8 20.Bf4 Bxf4 21.Qxf4 Bxb5 22.axb5 Rd8 23.Rdc1 Rd7 24.Bf3 Qd8 25.Qe5 
Ra8 26.Ra3 Rc8 27.Rac3 Rd6 28.Bg4 Qd7 29.Qf4 Qd8 30.R3c2 Rd7 31.R2c4 Rd6 32.Qf6 h6 
33.R1c2 Rd7 34.Qe5 Kh7 35.Qf4 Ng8 36.e5 Ra8 37.Qc1 Ra7 38.R4c3 Ne7 39.Ra3 Rb7 40.Bf3 Rb8 
41.Ra7 Rc8 42.Ra1 Nd5 43.Rc4 Qh8 44.Rh4 Qg7 45.Ra7 Re8 46.Qe1 Rde7 47.Rha4 Qh8 48.Qe2 Rd8 
49.Rc4 Rdd7 50.Ra1 Re8 51.Rh4 Ra8 52.Rxa8 Qxa8 53.Qd2 Qf8 54.Qc1 Qg7 55.Re4 Ne7 56.Qc3 Qf8 
57.Rd4 Qd8 58.Rxd7 Qxd7 59.Kg2 Kg7 60.Bc6 Qd8 61.Be4 Kh7 62.Qd3 Qe8 63.Kf3 Kg7 64.h3 Kh7 
65.g4 Kg7 66.h4 Kg8 67.Ke3 Kh8 68.f4 Ng8 69.Bc6 Qe7 70.g5 Qc5+ 71.Qd4 Qc2 72.Qd2 Qf5 73.Qd7 
Qh3+ 74.Bf3 Qxh4 75.Qxc7 Qe1+ 76.Be2 Qg3+ 77.Ke4 Qf2 78.Bf3 Qe1+ 79.Kd3 Qg3 80.Ke4 hxg5 
81.Qxf7 g4 82.Be2 Qg2+ 83.Ke3 Qh3+ 84.Kd4 g3 85.Bf3 g2 86.Bxg2 Qxg2 87.Qxe6 Qxb2+ 88.Ke3 
Qc3+ 89.Ke2 Qc2+ 90.Kf3 Qd3+ 91.Kg2 Qxb5 92.Qxg6 Qe2+ 93.Kg3 Qe3+ 94.Kg2 Qxf4 95.Qxb6 Qxe5 
96.Qb4 Nh6 97.Qh4 Qe2+ 98.Qf2 Qe4+ 99.Qf3 Qg6+ 100.Kf1 Nf5 101.Ke1 Qg5 102.Kf2 Qd2+ 103.Qe2 
Qd4+ 104.Kf3 Nh4+ 105.Kg3 Ng6 106.Qf2 Qh4+ 107.Kf3 Ne5+ 108.Kg2 Qe4+ 109.Kf1 Qc4+ 110.Qe2
Qc1+ 111.Qe1 Qg5 112.Qf2 Kh7 113.Qh2+ Kg7 114.Qg1 Ng4 115.Qd4+ Kg6 116.Qe4+ Kf6 117.Qf3+ 
Ke7 118.Qb7+ Kd8 119.Qh7 Qf4+ 120.Ke2 Qf2+ 121.Kd3 Ne5+ 122.Kc3 Qe3+ 123.Kc2 Qd4 124.Kb1 
Nc4 125.Qb7 Qc3 126.Ka2 Ke8 127.Qc6+ Ke7 128.Qc5+ Ke6 129.Qc6+ Ke5 130.Qc7+ Ke4 131.Qb7+ Kf5 
132.Qf7+ Kg4 133.Qd7+ Kf4 134.Qf7+ Kg3 135.Qg6+ Kh4 136.Qh7+ Kg5 137.Qg8+ Kh6 138.Qf8+ Kg6 
139.Qg8+ 1/2-1/2

External Links

Chess Engine

Anechka by Сергей Нефедов, Russia from sdchess.ru
Anechka 0.08 in CCRL 40/40
Anechka 0.08 in KCEC
Anechka from WBEC Ridderkerk

Misc

List of minor planets: 10001–11000 - 10456 Anechka - Wikipedia
discovered by Nikolai Chernykh, Crimean Astrophysical Observatory, August 8, 1978
DMPN: (10456) Anechka
Anechka | meaning of Anechka | name Anechka
Anya from Wikipedia
Винтаж (Vintage) - Амстердам, Анечка (альбом) (2011), YouTube Video

References

What links here?

Page	Date Edited
Anechka	Mar 20, 2014
CCCCISC 2008	Jan 19, 2014
Engines	Mar 10, 2018
IOPCCC 2008	Feb 23, 2014
Sergei Nefedov	Mar 20, 2014

Up one level

AnMon

GerdIsenberg — Fri, 17 Nov 2017 20:37:38 GMT

Home * Engines * AnMon

		AnMon, a chess program by Christian Barreteau, one of the first engines which supported WinBoard aka the Chess Engine Communication Protocol, later also UCI. AnMon was available as Young Talent by ChessBase running under the Fritz6 GUI ^[1] , and is Arena partner engine ^[2] . It is a tactically very strong MTD(f) searcher. AnMon participated at various French Computer Chess Championships and had its debut at the FCCC 1995, further the WMCCC 1997 in Paris, and multiple Massy French Programmers Tournaments, winning Massy 2000, Massy 2005 and Massy 2006.
Floor mosaic of Chigi Chapel ^[3] ^[4]

Photos & Games

Massy 2002, GNU Chess - AnMon, Pascal Tang, Dominique Longbien, Christian Barreteau, Jean-Philippe Louguet ^[5]

[Event "Massy 2002"]
[Site "Massy, France"]
[Date "2002.05.26"]
[Round "1"]
[White "GNU Chess"]
[Black "AnMon521_UCI"]
[Result "0-1"]
 
1.e4 e5 2.Nf3 Nc6 3.Bb5 g6 4.c3 d6 5.d4 Bd7 6.Qb3 Na5 7.Bxd7+ Qxd7 8.Qd5 Nc6
9.dxe5 dxe5 10.Qxd7+ Kxd7 11.O-O Nf6 12.Nbd2 a5 13.Nc4 Re8 14.Re1 h6 15.a4 Kc8
16.b3 Nd7 17.Nfd2 Nc5 18.Ba3 Nd3 19.Re3 Rd8 20.Rf3 Bxa3 21.Rxa3 Nc5 22.Ra1 Rhf8
23.Rh3 Rd7 24.f3 h5 25.Rg3 Ne6 26.Ra2 Rd3 27.Rc2 Rfd8 28.Nf1 h4 29.Rg4 h3
30.Rh4 hxg2 31.Kxg2 Nf4+ 32.Kf2 R3d1 33.Rh7 Nd3+ 34.Kg1 Ne1 35.Rf2 Rf8 36.Ncd2 Nd3
37.Rg2 Rc1 38.c4 Nd4 39.Rg4 Rc3 40.Rgh4 Ne1 41.R4h3 Nexf3+ 42.Kg2 Ne1+ 43.Kh1 Nd3
44.R7h8 Rxh8 45.Rxh8+ Kd7 46.Rf8 Ke6 47.Re8+ Kf6 48.Kg2 Nc5 49.h4 c6 50.h5 gxh5
51.Rh8 Ncxb3 52.Nxb3 Nxb3 53.Ng3 Rxc4 54.Rh6+ Kg5 55.Rh7 h4 56.Rg7+ Kf6 0-1

Description

given in 1997 from the ICGA site ^[6] :

The program AnMon (half ANgel, half deMON) is written in C and run under Windows NT. It was developed as a hobby for 8 years. AnMon participated in the 1995, and 1996 French Microcomputer Chess Championship. It is based on MTD(f) and uses null-move pruning, selective extensions, transposition tables, killer heuristic, and quiescence search. AnMon is a tactical program.

AnMon uses an opening book containing about 100.000 positions. It was established by the program. AnMon search about 50.000 nodes per second on a Pentium 2 at 233 MHz.

Forum Posts

AnMon 4.25 download ! by Frank Quisinsky, CCC, June 22, 1999
Anmon is Really Very Strong by Fernando Villegas, CCC, June 22, 1999
Anmon question ! Is anmon using alpha-beta ? by Thorsten Czub, CCC, August 16, 1999
AnMon 5.06 for Download by Đorđe Vidanović, CCC, February 01, 2000
ANMON won the computer chess tourney in Massy ! by Frank Quisinsky, Winboard Forum, May 23, 2000
UCI AnMon 5.19 by Christian Barreteau available! by Frank Quisinsky, CCC, February 26, 2002
Re: SCOTD (AnMon 5.21) by Kurt Utzinger, CCC, October 11, 2003
AnMon 5.40 by Christian Barreteau is available ... long text! by Frank Quisinsky, CCC, August 14, 2004
Changes in AnMon ... by Frank Quisinsky, CCC, August 15, 2004
AnMon 5.60 UCI available by Michael Diosi, CCC, January 30, 2006
New version of AnMon since 3 years ... by Leo Dijksman, CCC, February 03, 2009
AnMon 5.66 : 2436 by Patrick Buchmann, CCC, February 04, 2009
AnMon 5.75 : 2452 by Patrick Buchmann, CCC, July 24, 2009

External Links

Chess Engine

Misc

References

^ Support - ChessBase, May 28th, 2000
^ Arena Chess GUI 3.0 - AnMon
^ Santa Maria del Popolo in Rome, Italy: Chigi Chapel. Incrustated floor with the coats of arms of the House of Chigi hold by the Death, Photo by Bernd Brägelmann, Agostino Chigi from Wikipedia
^ Angels & Demons from Wikipedia
^ Massy 2002/05/26 - Tournoi de programmes d'Echecs from LUDOCHESS - Les jeux d'Echecs 100% pur Java by Stéphane Nguyen
^ AnMon's ICGA Tournaments

What links here?

Page	Date Edited
Amyan	Dec 10, 2013
AnMon	Nov 17, 2017
Arena	Mar 16, 2018
Bernard Brioit	Jan 10, 2015
Capture (program)	Jan 8, 2016
ChessBase	Nov 25, 2017
Christian Barreteau	Jan 8, 2016
Eigenmann Endgame Test	Jun 1, 2017
Engines	Mar 10, 2018
FCCC 1995	Jul 27, 2015
FCCC 1996	Jul 25, 2014
FCCC 1998	Oct 22, 2012
FCCC 1999	Jan 29, 2013
FCCC 2000	Jan 26, 2013
FCCC 2004	Jun 16, 2013
Fernando Villegas	Aug 15, 2016
French Programmers Tournament	Jan 26, 2013
Fruit	Sep 27, 2016
Massy 2001	Jan 28, 2013
Massy 2002	Jan 2, 2018
Massy 2004	Oct 27, 2016
Massy 2005	Jan 29, 2013
Massy 2006	Jan 29, 2013
WMCCC 1997	Apr 4, 2017

Up one Level

Wikispaces : chessprogramming - items matching description

10x12 Board

Table of Contents

Programs

Sargon

TSCP

Square Mapping

Offset Move Generation

See also

Publications

Forum Posts

External Links

References

What links here?

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?

Abyss

Table of Contents

Description

Basics

Misc

Abyss' ICGA Tournaments

See also

Publications

External Links

Engine

Misc

References

What links here?

ACM 1973

Table of Contents

Final Standing

Participants

The Tournament

Selected Games

Tournament Director

Publications

External Links

References

What links here?

ACM 1980

Table of Contents

Final Standing

Participants

Photos & Games

Round 2

Round 3

Round 4

See also

Tournament Director

Publications

External Links

References

What links here?

Advances in Computer Chess 1

Table of Contents

Proceedings

Lectures

Reviews

The Forerunner

ACC1

Forum Posts

External Links