Wikispaces : chessprogramming - items matching description

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

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

Atak

GerdIsenberg — Tue, 09 Aug 2016 09:20:51 GMT

Home * Engines * Atak

Atak,
a Chess Engine Communication Protocol compatible chess engine by Mateusz Łuksik written in C, initially as part of his Master's thesis from Rzeszów University of Technology in 2002 ^[1], and first public released in September 2005 ^[2]. Early versions were standalone chess programs with an own GUI ^[3]. Atak had its over the board debut at the 1st Polish Computer Chess Championship in 2002 and was regularly participant of subsequent Polish Computer Chess Championship, winning the PCCC 2010. Atak 6.8 played the IGWT 2014, where it lost from later winner Chiron 2.

Photos & Games

PCCC 2010 round 5: Mateusz Łuksik operating Atak versus Butcher ^[4] ^[5]

[Event "PCCC 2010"]
[Site "Warszawa"]
[Date "2010.11.28"]
[Round "5.3"]
[White "Atak"]
[Black "Butcher 1.60n1"]
[Result "1-0"]
 
1.e4 e5 2.f4 exf4 3.Nf3 d6 4.Bc4 g5 5.h4 g4 6.Ng5 Nh6 7.d4 Qe7 8.Bxf4 Nd7 
9.O-O Nb6 10.Bb3 Bg7 11.a4 a5 12.Qd2 Bd7 13.Nc3 O-O 14.Rae1 Qd8 15.e5 d5 
16.Nxd5 Nxd5 17.Bxd5 Bf5 18.Bxb7 Rb8 19.Ne4 Bxe4 20.Bxe4 f5 21.Bc6 Nf7 
22.e6 Bxd4+ 23.Rf2 Qf6 24.Bd5 Nd6 25.e7+ Rf7 26.Bxd6 cxd6 27.e8=Q+ Rxe8 
28.Rxe8+ Kg7 29.Bxf7 Kxf7 30.Rb8 g3 31.Rb7+ 1-0

Forum Posts

Atak 6.2 Released by Mateusz Łuksik, CCC, September 05, 2008
Test tournament starts: Gaviota, Daydreamer, Greko, Atak by Harun Taner, CCC, January 10, 2010 » Gaviota, Daydreamer, GreKo, Atak
Atak 6.5 queen sac by Graham Banks, CCC, April 21, 2009

External Links

References

^ Polski Związek Szachowy - oficjalna strona - 3.1. Program "Atak" Mateusza Łuksika wygrał IX Międzynarodowe Mistrzostwa Polski Programów Komputerowych (Interview with Mateusz Łuksik in Polish)
^ Atak from WBEC Ridderkerk
^ |ndex of /chess/engines/Norbert's collection/Atak (Compilation)/v2.4 (standalone application)/atak_gui/Atak_GUI by Norbert Raimund Leisner hosted by Kirill Kryukov
^ Image from Polski Związek Szachowy - oficjalna strona - 3.1. Program "Atak" Mateusza Łuksika wygrał IX Międzynarodowe Mistrzostwa Polski Programów Komputerowych (Polish)
^ PGN from 9.Mistrzostwa Polski Programów Szachowych 2010

What links here?

Page	Date Edited
Atak	Aug 9, 2016
DayDreamer	Aug 22, 2016
Engines	Mar 10, 2018
Excelsior	Apr 16, 2014
Gaviota	Jan 21, 2018
Greko	Feb 27, 2018
Harun Taner	May 17, 2015
IGWT 2014	Feb 2, 2016
IOPCCC 2007	Nov 19, 2016
Mateusz Łuksik	Aug 9, 2016
Nesik	Jan 24, 2014
PCCC 2002	Mar 14, 2013
PCCC 2003	Mar 13, 2013
PCCC 2005	Jun 26, 2013
PCCC 2006	Mar 12, 2013
PCCC 2009	Mar 11, 2013
PCCC 2010	Aug 9, 2016
Polish Computer Chess Championship	Mar 12, 2013

Up one Level

Chezzz

GerdIsenberg — Sun, 20 Jan 2013 13:23:46 GMT

Home * Engines * Chezzz

		Chezzz, a chess engine by David Rasmussen, which was according to Leo Dijksman ^[1] and Frank Quisinsky ^[2] the 100th WinBoard engine. Chezzz played seven consecutive CCT Tournaments, starting in 2001 with the CCT3, until 2007 the CCT9.
Chezzz Playazzz ^[3]

Thesis Program

Presumably, Chezzz is similar to Rasmussen's thesis program described in detail in his 2004 Master's thesis ^[4] - concerning board representation and the serial search, while the evaluation of the thesis program is very rudimentary relying on material and piece-square tables only. C++ source code given in Appendix B. Interesting for C++ programmers is Appendix B.12 enums.h with DeclareEnumTricks ^[5] and forall Macros.

Bitboards

Bitboards are the basic data structure, rotated bitboards with four line arrays indexed by square and 8-bit line occupancy determine sliding piece attacks. BitScan is done with a 16-bit lookup table and up to four conditional cases. The thesis program applies a population count in the Brian Kernighan's way, while Chezzz uses the MMX Swar Popcount as introduced in the AMD Athlon Processor x86 Code Optimization Guide ^[6], with compatibility issues concerning the 3DNow! psadbw - Packed sum of absolute byte differences - instruction ^[7].

Search

The program features a YBWC parallel search, sharing the lockless hash table as proposed by Robert Hyatt and Tim Mann ^[8]. The iterative deepening framework applies aspiration windows of ±1/3 pawn value, PVS with adaptive null move pruning, and history and killer heuristic with thread local memory. The SEE swap algorithm, borrowed from Crafty, is used in move ordering and to prune losing captures in quiescence search. The search is extended in case of checks, recaptures, and pawn moves to the 7th rank, and single replies.

Selected Games

CCT5

CCT5, Chezzz - Hossa ^[9]

[Event "CCT5"]
[Site "Internet Chess Club"]
[Date "2003.01.18"]
[Round "-"]
[White "Chezzz"]
[Black "Hossa"]
[Result "0-1"]
 
1.e4 c5 2.Nf3 Nc6 3.Nc3 e5 4.Bc4 Be7 5.d3 Nf6 6.Nd2 d6 7.Nf1 Bg4 8.f3 Be6 
9.Ne3 Bxc4 10.dxc4 Nd4 11.Qd3 O-O 12.O-O Qd7 13.Ncd5 Nxd5 14.Nxd5 f5 15.Be3 
fxe4 16.fxe4 Bh4 17.c3 Ne6 18.Rad1 Rxf1+ 19.Rxf1 Rf8 20.Rxf8+ Kxf8 21.Qe2 
Qf7 22.Qg4 Bd8 23.Bd2 h5 24.Qh3 Ke8 25.b4 b6 26.a3 Kd7 27.Qg3 Be7 28.a4 Bd8 
29.Be3 Qe8 30.a5 bxa5 31.bxc5 Qf7 32.cxd6 Kxd6 33.Qe1 Kc6 34.Qb1 Qb7 35.Qd1 
h4 36.Bf2 a6 37.Ne3 Kc7 38.Qd5 Qxd5 39.exd5 Nf4 40.Kf1 a4 41.Nc2 Kd6 42.Ba7 
g5 43.g3 hxg3 44.hxg3 Nh5 45.Kf2 Nf6 46.Ke2 Ne4 47.Ke3 Nf6 48.Nb4 a3 49.Kd3 
Nd7 50.Be3 a5 51.Na2 Nc5+ 52.Kc2 Na4 53.Kb3 Nb2 54.Bg1 g4 55.Be3 Bc7 56.Bg5 
e4 57.Bf4+ Kd7 58.Bxc7 Kxc7 59.c5 Nd3 60.Kc4 Nxc5 61.Kd4 Kb6 62.Ke3 Nb7 
63.Kd4 e3 64.Kxe3 Kc5 65.Kd3 Kxd5 66.c4+ Kc5 67.Nc1 Kb4 68.Kc2 Nc5 69.Kb1 
Kxc4 70.Ne2 Ne4 71.Kc2 a4 72.Kc1 Nc3 73.Nf4 Kb3 74.Ne6 a2 75.Nd4+ Kc4 76.Nc2
a3 77.Na1 Ne2+ 78.Kd2 Nxg3 79.Ke1 Kc3 80.Kd1 Kb2 81.Nc2 a1=Q+ 82.Nxa1 Kxa1 
83.Kc2 Nf5 84.Kc1 g3 85.Kd2 g2 86.Kd3 g1=Q 87.Ke4 Qd4+ 88.Kxf5 Kb1 89.Ke6 a2 
90.Kf5 a1=Q 91.Ke6 Qaa7 92.Kf5 Qag7 93.Ke6 Qgd7# 0-1

CCT7

CCT7, round 5, Quark - Chezzz ^[10]

[Event "CCT7"]
[Site "Internet Chess Club"]
[Date "2005.02.12"]
[Round "5"]
[White "Quark"]
[Black "Chezzz"]
[Result "0-1"]
 
1.e4 c5 2.Nf3 e6 3.d4 cxd4 4.Nxd4 a6 5.Bd3 Nc6 6.Nxc6 dxc6 7.O-O e5 8.Nd2 Be6 
9.Qf3 Qc7 10.Bc4 Qe7 11.Qb3 Bxc4 12.Nxc4 b5 13.Nb6 Rb8 14.Be3 Qc7 15.a4 Rxb6 
16.Bxb6 Qxb6 17.Qc3 Bd6 18.Rfd1 Bb8 19.axb5 axb5 20.Qg3 g6 21.Qh4 Qc7 22.Rd3 
Qc8 23.Ra8 Qc7 24.Rc3 Kf8 25.Ra6 c5 26.Rd3 Kg7 27.Rd8 h6 28.Re8 Qb7 29.Ra1 Bc7 
30.Rea8 g5 31.Qh3 Qxe4 32.Qc8 Bd6 33.Qa6 Be7 34.Qxb5 Qxc2 35.Qb8 e4 36.h3 c4 
37.g3 Qd2 38.Qe5+ Bf6 39.Qe8 e3 40.fxe3 Be7 41.Rf1 Qxe3+ 42.Kg2 Qe4+ 43.Kg1 f6 
44.Rf2 h5 45.Ra7 Qe3 46.Qd7 Qxg3+ 47.Rg2 Qe3+ 48.Rf2 Kh6 49.Qc7 Qxh3 50.Ra6 
Qg4+ 51.Kh2 Qd4 52.Rg2 Bc5 53.Qg3 Kg7 54.Kh1 Nh6 55.Ra1 Ng4 56.Re1 Kg6 57.Qf3 
Rb8 58.Qe4+ Qxe4 59.Rxe4 Nf2+ 60.Rxf2 Bxf2 61.Re2 Bd4 62.Re4 Rd8 0-1

Publications

David Rasmussen (2004). Parallel Chess Searching and Bitboards. Master's thesis, ps

Forum Posts

2001

Congrats to David Rasmussen by Leo Dijksman, Winboard Forum, May 23, 2001
*** 100 *** Chezzz 0.88 by David Rasmussen (Denmark) is available by Frank Quisinsky, Winboard Forum, May 23, 2001

2002

Position from Sjeng - Chezzz by David Rasmussen, CCC, January 21, 2002 » Sjeng
Quiescence Explosion by David Rasmussen, CCC, November 26, 2002

2003

Chezzz-Postmodernist - What plan? by David Rasmussen, CCC, January 15, 2003 » PostModernist
Chezzz - Hossa CCT5 by David Rasmussen, CCC, January 18, 2003 » CCT5, Hossa
Test Position : Chezzz - Hossa by David Rasmussen, CCC, January 19, 2003
Chezzz @ CCT5 - First Day by David Rasmussen, CCC, January 25, 2003 » CCT5
Chezzz 1.0b released by David Rasmussen, CCC, February 03, 2003
Chezzz 1.0.1 released by David Rasmussen, CCC, February 04, 2003
Re: Chezzz 1.0.1 - problem solved - for David Rasmussen by David Rasmussen, CCC, February 05, 2003 » Population Count, MMX
Chezzz's proudest moment (?) by Darren, Winboard Forum, February 09, 2003 » CCT5
Chezzz 1.0.2 released by David Rasmussen, Winboard Forum, February 11, 2003
Chezzz and EGTB's by Gábor Szõts, Winboard Forum, February 12, 2003
Example Chezzz cfg file by David Rasmussen, Winboard Forum, February 14, 2003
Chezzz 1.0.3 released and books tweaked by David Rasmussen, Winboard Forum, February 20, 2003
chezzz by Andy, Winboard Forum, February 27, 2003
New books for Chezzz by David Rasmussen, CCC, February 27, 2003
Terra - Chezzz ... Nice Game by David Rasmussen, Winboard Forum, June 04, 2003 » Terra

2004 ...

Find The Bug - C / C++ by David Rasmussen, bytes.com, July 22, 2005

External Links

Index of /chess/engines/Norbert's collection/Chezzz (Compilation) by Norbert Raimund Leisner, hosted by Kirill Kryukov
Chezzz 1.0.3 in CCRL 40/4
Chezzz 1.0.3 in CCRL 40/40
Chezzz from WBEC Ridderkerk

References

^ Congrats to David Rasmussen by Leo Dijksman, Winboard Forum, May 23, 2001
^ *** 100 *** Chezzz 0.88 by David Rasmussen (Denmark) is available by Frank Quisinsky, Winboard Forum, May 23, 2001
^ Flickr: photostream by PhunkePixie
^ David Rasmussen (2004). Parallel Chess Searching and Bitboards. Master's thesis, ps
^ Find The Bug - C / C++ by David Rasmussen, bytes.com, July 22, 2005
^ AMD Athlon Processor x86 Code Optimization Guide (pdf) Efficient 64-Bit Population Count Using MMX™ Instructions Page 184
^ Re: Chezzz 1.0.1 - problem solved - for David Rasmussen by David Rasmussen, CCC, February 05, 2003
^ Robert Hyatt and Tim Mann (2002). A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1, pp. 63-72
^ Chezzz - Hossa CCT5 by David Rasmussen, CCC, January 18, 2003
^ CCT7 replay-zone

What links here?

Page	Date Edited
CCT3	Feb 14, 2013
CCT4	Apr 22, 2013
CCT5	Feb 22, 2013
CCT6	May 29, 2014
CCT7	Dec 16, 2017
CCT8	Apr 6, 2013
CCT9	Aug 25, 2013
Chezzz	Jan 20, 2013
Cpp	Oct 24, 2017
David Rasmussen	Dec 16, 2017
Engines	Mar 10, 2018
MMX	Jun 5, 2016

Up one Level

Fixafan

GerdIsenberg — Fri, 02 Oct 2015 21:20:52 GMT

Home * Engines * Fixafan

		Fixafan, (Fix a Fan) the thesis chess program by Eric Thé, published in appendix D of his 1992 Master's thesis as subject of an analysis of move ordering on the efficiency of alpha-beta search. Fixafan was written in C on a Solbourne 5/600 dual SPARC processor machine running Unix. It used a two-dimensional 8x8 board array, and, focusing on move ordering, a material only evaluation, and iterative deepening with aspiration windows of ± 2 pawns ^[1].
Fan Moved by Mechanism ^[2]

Move Ordering

Eight move ordering heuristics were implemented and examined, in isolation and combination - beside the chess dependent MVV/LVA ordering of captures, seven variations of the killer heuristic, aka countermove heuristic or history heuristic, including the best move probed from the transposition table (BEST_TT). Opposed to static move ordering applied during generation time, dynamic move ordering heuristic reorders remaining moves after searching early ones, by looking whether new killers appeared two plies ahead, still to try inside the movelist, now considering next.

Experiments

The experiments were made using the 24 positions of the Bratko-Kopec Test searching on the depth of 6 or 7 (midgame) and 9 (endgame) plies, comparing performance by measuring of node counts, CPU time, average branching factor (ABF), and a "Killer average" (KA), which is the ratio of number of "kills" versus number of reordered nodes per level. A kill is when a cutoff occurs within the subset of moves reordered at a node. If a certain heuristic or combination of heuristics reordered N moves at the front of a node's movelist, and a cutoff occurs after searching one of the N moves, then a kill is registered. One should consider the fact that Fixafan evaluates only material balance at all leaf nodes, and therefor the last level of all iterations is not expanded and searched thoroughly as with all previous levels. Instead, the highest capture is immediately taken as the best move and all other moves are ignored. The consequence of this shortcut is that the ABF for the last level of every iteration can never exceed 1.00.

Results

BEST_TT was clearly the most effective heuristic reducing the tree size by 70% and search time by 75% on average compared to a null test (no ordering heuristic at all, quiet sliding moves generated before captures), followed by MVV/LVA captures, which also raises the efficiency when combined with any of the other heuristics not dependent on the properties of chess. The history heuristic consumed just 4.5% less execution time than the null test. Although HH had a high Killer average, most of the cutoffs seemed to happen too late to be effective. Small improvements in BEST_TT + Captures were noticed when complemented with countermove and the level dependent killer heuristic. Using two killer slots was slightly advantageous, while dynamic re-ordering reduced the tree size with disappointing time results.

Publications

Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University, advisor Monroe Newborn

External Links

References

^ Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University, advisor Monroe Newborn
^ Patent drawing of Fan Moved by Mechanism by James Barron, November 27, 1830. The original drawing for this patent was destroyed by a fire in the Patent Office in 1836. The coverage date is the original patent date. This drawing is a restoration created in 1837 or shortly thereafter, Mechanical fan from Wikipedia, Wikimedia Commons

What links here?

Page	Date Edited
Engines	Mar 10, 2018
Eric Thé	Oct 2, 2015
Fixafan	Oct 2, 2015
Killer Heuristic	Sep 14, 2017
McGill University	Feb 12, 2018
Move Ordering	Feb 27, 2018

Up one Level

Giraffe

GerdIsenberg — Mon, 08 Jan 2018 21:42:15 GMT

Home * Engines * Giraffe

		Giraffe, an experimental open source chess engine by Matthew Lai under the GNU General Public License, compliant to the Chess Engine Communication Protocol, written in C++11 and based on deep learning, which is topic of his Master's thesis in August 2015 ^[1] ^[2] . Giraffe uses the Eigen linear algebra library ^[3] , and Pradyumna Kannan's magic move generator ^[4] ^[5]. As employee of Google DeepMind, Matthew Lai announced the discontinuation of the Giraffe project in January 2016 ^[6].
Salvador Dalí - The Burning Giraffe ^[7]

Description

Giraffe's evaluation function is a deep neural network trained by TDLeaf ^[8] . Its feature representation includes a map of static exchange evaluations for all squares and sides ^[9] , a structure already proposed by Russell M. Church and Kenneth W. Church in Plans, Goals, and Search Strategies for the Selection of a Move in Chess ^[10] . Probability-based evaluation scores are not in centipawns nor linear to material , and span a +-10,000 range, with mate scores of +- 30,000. The search recently changed from traditional depth-based iterative deepening to assigning number of nodes (or time) to child nodes ^[11] . Node budget allocation will also become neural network based.

Publications

Matthew Lai (2015). Giraffe: Using Deep Reinforcement Learning to Play Chess. M.Sc. thesis, Imperial College London, arXiv:1509.01549v1
Jonathan Rosenthal (2016). Deep Learning for Go. B.Sc. thesis, ETH Zurich

Forum Posts

2015

*First release* Giraffe, a new engine based on deep learning by Matthew Lai, CCC, July 08, 2015
SEE Map by Matthew Lai, CCC, July 20, 2015 » Static Exchange Evaluation
Time assignment to children by Matthew Lai, CCC, July 26, 2015
Giraffe 20150801 by Matthew Lai, CCC, August 01, 2015
Giraffe, new release (Aug 17) by Matthew Lai, CCC, August 17, 2015
New Giraffe (Aug 28) by Matthew Lai, CCC, August 28, 2015
Giraffe dissertation, and now open source by Matthew Lai, CCC, September 08, 2015
New Giraffe (Sept 8) by Matthew Lai, CCC, September 08, 2015

2016

Death of Giraffe, but hopefully not ML in chess! by Matthew Lai, CCC, January 21, 2016
Re: Deep Learning Chess Engine ? by Matthew Lai, CCC, August 04, 2016 ^[12]
Beginner's guide to graphical profiling by Matthew Lai, CCC, September 10, 2016 » Profiling
New Giraffe by Matthew Lai, CCC, October 23, 2016

2017...

Is AlphaGo approach unsuitable to chess? by Mel Cooper, CCC, May 27, 2017 » AlphaGo, Deep Learning
Re: Is AlphaGo approach unsuitable to chess? by Peter Österlund, CCC, May 31, 2017 » Texel
Re: Why is it so hard for comps to play like people? by Ben Redic, Hiarcs Forum, June 03, 2017
Giraffe on Threadripper + newest GPUs by John Margusen, CCC, August 19, 2017 ^[13]

External Links

Chess Engine

waterreaction / Giraffe — Bitbucket
Deep learning from Wikipedia
Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at International Master Level by Emerging Technology From the arXiv, MIT Technology Review, September 14, 2015 ^[14]
This Chess Engine Learns How to Beat Humans by Playing Against Itself by Rollin Bishop, Popular Mechanics, September 15, 2015
Computer Learns to Hack Chess by Al Williams, Hackaday, October 02, 2015 ^[15]
The Chess Engine that Died So AlphaGo Could Live by Rollin Bishop, Motherboard, March 14, 2016 » AlphaGo
Giraffe 20150908 64-bit in CCRL 40/4

Misc

References

^ Matthew Lai (2015). Giraffe: Using Deep Reinforcement Learning to Play Chess. M.Sc. thesis, Imperial College London, arXiv:1509.01549v1
^ *First release* Giraffe, a new engine based on deep learning by Matthew Lai, CCC, July 08, 2015
^ Eigen, a C++ template library for linear algebra: matrices, vectors, numerical solvers, and related algorithms
^ Fastest Magic Move Bitboard Generator ready to use by Pradu Kannan, Winboard Forum, August 25, 2006
^ Pradyumna Kannan (2007). Magic Move-Bitboard Generation in Computer Chess. pdf
^ Death of Giraffe, but hopefully not ML in chess! by Matthew Lai, CCC, January 21, 2016
^ Salvador Dalí - The Burning Giraffe, 1937, Oil on panel, Kunstmuseum Basel, The Burning Giraffe from Wikipedia
^ Jonathan Baxter, Andrew Tridgell, Lex Weaver (1998). TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search. Australian Journal of Intelligent Information Processing Systems, Vol. 5 No. 1, arXiv:cs/9901001
^ SEE Map by Matthew Lai, CCC, July 20, 2015
^ Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine
^ Time assignment to children by Matthew Lai, CCC, July 26, 2015
^ Rectifier (neural networks) from Wikipedia
^ Ryzen from Wikipedia (Threadripper)
^ Awful paper) by Sergei S. Markoff, CCC, February 18, 2016
^ Chess hackery by Steven Edwards, CCC, October 02, 2015

What links here?

Page	Date Edited
AlphaZero	Feb 10, 2018
Deep Learning	Feb 12, 2018
Engine releases	Apr 23, 2018
Engines	Mar 10, 2018
Giraffe	Jan 8, 2018
Jonathan Rosenthal	Jan 9, 2018
Learning	Feb 20, 2018
Matthew Lai	Dec 6, 2017
Neural Networks	Mar 12, 2018
Optimization	Feb 28, 2018
Patrick Winston	Dec 21, 2017
Profiling	Sep 15, 2016
Reinforcement Learning	Feb 12, 2018
Temporal Difference Learning	Feb 20, 2018
Texel	Oct 9, 2017

Up one Level

Golch

GerdIsenberg — Thu, 07 Dec 2017 22:16:07 GMT

Home * Engines * Golch

		Golch, an experimental chess engine by Artem Pyatakov. Initially written in early 2001 ^[1] during his freshman year at Princeton University, it was a conventional chess program written in C, using a 0x88 board representation ^[2], alpha-beta, iterative deepening, transposition table ^[3], killer- and history heuristic, along with all the domain dependent tricks in move ordering (i.e searching captures first), selectivity and evaluation. In 2001, Golch was active at ICC ^[4]. The program was later used as test-bed for Pyatakov's senior thesis Improving Computer Chess through Machine Learning ^[5] under advisor Robert Schapire ^[6]. The aim was to narrow the claimed gap between artificial intelligence methods and computer chess methods and tricks, manifested as human-generated, domain dependent ideas that happened to work without a good theoretical justification and cannot be easily generalized to other games ^[7].
Perceptron ^[8]

Perceptron

The online-learning approach to replace classical evaluation by a single layer perceptron, combining a feature vector, representing the board, with a set of adjustable weights, trained by supervised move adaption with some test-positions such as the Bratko-Kopec Test produced slightly disappointing results. The feature-vector used had 64 binary elements of an occupied bitboard, and a 16x16 attack map ^[9], which hopefully distinguished attacked but sufficiently defended pieces or pawns from pieces or pawns en prise.

History Heuristic

More promising results was due to an advanced implementaion of history heuristic, where a table was not only indexed by its [from][to] coordinates of a move, but a much larger table with additional context of the moving piece along with a bitmask of pieces attacking the from square, which was reported to work about 3% better than the pure history heuristic in terms of node counts on the Bratko-Kopec problems ^[10]:

history[piece][from][to][attack_bit_vector] += (1 << depth);

Publications

Artem Pyatakov (2004). Improving Computer Chess through Machine Learning. Senior thesis, Princeton University, advisor Robert Schapire ^[11]

Forum Posts

Fastest Conversion from 0x88 board to 8x8 board representation by Artem Pyatakov, CCC, July 06, 2001 » 0x88
Question about Gerbil by Artem Pyatakov, CCC, July 11, 2001
Bitfields and Crafty by Artem Pyatakov, CCC, July 11, 2001
Artificial Intelligence in Computer Chess by Artem Pyatakov, CCC, March 28, 2004 » Artificial Intelligence
Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised by Artem Pyatakov, CCC, March 28, 2004 » History Heuristic
Killer modifications reduced tree size by 8% (with identical results) by Artem Pyatakov, CCC, March 31, 2004 » Killer Heuristic

External Links

Finger golch at Internet Chess Club

References

^ Question about Gerbil by Artem Pyatakov, CCC, July 11, 2001
^ Fastest Conversion from 0x88 board to 8x8 board representation by Artem Pyatakov, CCC, July 06, 2001
^ Question about Gerbil by Artem Pyatakov, CCC, July 11, 2001
^ Finger golch at Internet Chess Club
^ Artificial Intelligence in Computer Chess by Artem Pyatakov, CCC, March 28, 2004
^ Princeton - Independent Project Presentation Schedule
^ Artificial Intelligence in Computer Chess by Artem Pyatakov, CCC, March 28, 2004
^ The appropriate weights are applied to the inputs, and the resulting weighted sum passed to a function that produces the output y, image created by mat_the_w, based on raster image Perceptron.gif by 'Paskari', using Inkscape 0.46 for OSX, Wikimedia Commons, Perceptron from Wikipedia
^ Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised by Artem Pyatakov, CCC, March 28, 2004
^ Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised by Artem Pyatakov, CCC, March 28, 2004
^ Artificial Intelligence in Computer Chess by Artem Pyatakov, CCC, March 28, 2004

What links here?

Page	Date Edited
Artem Petakov	Jan 14, 2017
Engines	Mar 10, 2018
Golch	Dec 7, 2017
History Heuristic	Jul 19, 2017
Learning	Feb 20, 2018
Neural Networks	Mar 12, 2018

Up one level

HAL

GerdIsenberg — Tue, 14 Jun 2016 15:21:29 GMT

Home * Engines * HAL

		HAL, (Heuristic Associative Linear-algorithm, HAL-9000, HAL9000) an open source chess program by Stephen F. Wheeler, also dubbed HAL-9000 as pun of HAL 9000, the fictional character in Arthur C. Clarke's Space Odyssey series, first appearing in 2001: A Space Odyssey ^[1] ^[2]. HAL was written in Turbo Pascal to run under the MS-DOS command line, and was part of Wheeler's Ph.D. research during the late 80s and early 90s ^[3], specifically on linear symbolic problem-solving systems and natural language processing. A slightly modified and bug fixed version was published with source in December 2015 at Chess.com ^[4].
HAL 9000 ^[5]

Description

User Interface

HAL has a command line interface, and supports an interactive English dialogue between the opponent and itself to receive and report its moves and to receive directives, such as skill level. The directives are given to HAL in the form of English sentences, which can be rather free-form in structure, and will even allow for slight misspellings in certain situations. HAL utilizes the long algebraic notation ^[6] ^[7].

Board Representation

HAL's board is represented by an incremental updated 8x8 board, a two-dimensional array of board cells, and a piece-list as array of piece cells indexed by side (1..2) and man index 1..16.

Search

The search algorithm is pure alpha-beta implemented as recursive negamax with fail-soft bounds inside the iterative deepening framework with aspiration windows. Move ordering is improved by the refutation table based on the triangular PV-table, and a sophisticated killer heuristic with up to four killers per ply. Selectivity is due to check extensions and depth limited quiescence search.

Evaluation

Evaluation considers material balance, a material exchange heuristic, and positional heuristic terms for development, king attack, defence, threats, mobility, advancement, captures and checks.

Postings

Off-topic: HAL by Dave Gomboc, CCC, July 19, 2000
Frank Poole v HAL 9000 -- or is it CM9000? by John Merlino, CCC, July 10, 2002 » Chessmaster
HAL9000 Levels of Play by Stephen F. Wheeler, Chess.com, May 22, 2010
HAL9000 Chess Rating? by Stephen F. Wheeler, Chess.com, May 28, 2010

External Links

Chess Program

HAL-9000 by sfwheeler, Chess.com

Fictional Character

References

^ Murray Campbell (1997). "An Enjoyable Game": How HAL Plays Chess. in David G. Stork (ed.), Hal's Legacy - 2001's Computer as Dream and Reality. MIT-Press, pdf
^ An interesting link by Steven Edwards, CCC, March 29, 2004
^ Stephen F. Wheeler, Senior Professor, College of Engineering & Information Sciences, Irving, TX Campus | DeVry University Newsroom
^ HAL-9000 by sfwheeler, Chess.com
^ The famous red eye of HAL 9000, the fictional character in Arthur C. Clarke's Space Odyssey series. Image by Cryteria, October 1, 2010, Wikimedia Commons
^ HAL-9000, HAL-9000.zip/HALDOC.DOC
^ HAL-9000, HAL-9000.zip/CP3.pas

What links here?

Page	Date Edited
Chessmaster	Jan 21, 2018
Engines	Mar 10, 2018
HAL	Jun 14, 2016
SAL	Dec 7, 2017
Stephen F. Wheeler	Jun 13, 2016

Up one level

Huberman

GerdIsenberg — Fri, 09 Aug 2013 19:57:56 GMT

Home * Engines * Huberman

Huberman, (Huberman's program)
the Ph.D. thesis program by Barbara Liskov (née Huberman) written in 1968 at Stanford University, under supervision of John McCarthy, to play certain chess endgames with pieces versus the lonesome king. Barbara Huberman used heuristics to drive the lonesome king away from the center and for K,B,N into the right corner, and most notably already proposed the Killer Heuristic for early refutations of the alpha-beta search ^[1]. She further elaborated on the implications of these endings with different board sizes, even an infinite board.

Quotes

Alex Bell in Games Playing with Computers on Huberman's program ^[2]:

A philosophic program was written by Barbara Huberman to specifically play end games. It was a research project on translating book descriptions of problem solving methods into program heuristics. It is well known that the following minimum combinations of pieces have a certain win against a lone king:

K,Q
K,R
K,B,B
K,B,N
K,N,N,N

The K,Q can be considered equivalent to the K,R.

Huberman followed descriptions (by Capablanca and Fine) of how to execute all but the case of K,N,N,N. The cases of K,R and K,B,B are feasible using the minimax technique. This is not true for the K,B,N. The difficulty here is that bishops and rooks can force mate on any size of board but the knight has a limited mobility (from a centre square there are five squares which each require four moves to be reached by the knight).

Consequently the K,B,N mate is not possible on a board of side > 8. Even allowing for the black king being against a side there is no way in which the K,B,N can be arranged and played that will systematically force the black king along the edge of an infinite board. Because of this weakness the actual mating can take up to forty moves. Huberman's model for the problem was a forcing tree co-ordinated with two functions (better and worse) which were able to compare positions. Roughly speaking the program had two sub-goals (apart from not losing a piece, giving stalemate , etc). First drive the king away from the centre and second, when the king is at the edge, drive him towards a corner of the bishop's colour.

Huberman's program is the only one which can perform this mating sequence for any starting position. It would be a useful addition to Greenblatt's program, being easily extended to solve other end games and hence giving the more general program a selection of sub-goals equivalent to winning the game. The problem of K,N,N,N is unlikely to occur; nevertheless it is of interest to the theorists. One surprising fact is that the combination can systematically drive the black king along the edge of an infinite board, and therefore the mating sequence is much easier to program.

Publications

Barbara J. Huberman (1968). A Program to Play Chess End Games. Technical Report no. CS-106, Ph.D. thesis. Stanford University, Computer Science Department
Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227, Chess programs: Huberman
John McCarthy (1990). Chess as the Drosophila of AI. Computers, Chess, and Cognition, pp. 227-237 ^[3]

Forum Posts

evaluating KNNN-K by Rafael B. Andrist, CCC, November 18, 2001

References

^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1, pp. 8, The killer heuristic
^ Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227, Chess programs: Huberman
^ John McCarthy (1997). Chess as the Drosophila of AI. Computer Science Department, Stanford University, condensed version of the 1990 paper, pdf

What links here?

Page	Date Edited
Barbara Liskov	Oct 30, 2014
Engines	Mar 10, 2018
Huberman	Aug 9, 2013
KBNK Endgame	Nov 26, 2016
KRK	Nov 26, 2016
Mathematician	Apr 9, 2018
Stanford University	Dec 7, 2017

Up one Level

Kholin

GerdIsenberg — Wed, 03 Jan 2018 15:32:29 GMT

Home * Engines * Kholin

		Kholin, an UCI compliant open source chess engine by Emil Fredrik Østensen, written in C as part of his 2016 Master's thesis ^[1]. Kholin is licensed under the GPL 3 ^[2], and focuses on parallel search, in particular Lazy SMP.
Glyph for House Kholin ^[3]

Features

Board Representation

Search

Evaluation

Misc

Perft

Publications

Emil Fredrik Østensen (2016). A Complete Chess Engine Parallelized Using Lazy SMP. M.Sc. thesis, University of Oslo, pdf

External Links

Chess Engine

GitHub - emilfo/master - Kholin Chess Engine

Misc

References

^ Emil Fredrik Østensen (2016). A Complete Chess Engine Parallelized Using Lazy SMP. M.Sc. thesis, University of Oslo, pdf
^ GitHub - emilfo/master - Kholin Chess Engine
^ The Alethi glyph for House Kholin by Isaac Stewart, The Stormlight Archive - The Coppermind - 17th Shard

What links here?

Page	Date Edited
Emil Fredrik Østensen	Jan 3, 2018
Engines	Mar 10, 2018
Kholin	Jan 3, 2018
Lazy SMP	Jan 4, 2018

Up one Level

Mater

GerdIsenberg — Tue, 26 Apr 2016 21:01:58 GMT

Home * Engines * Mater

		Mater, a chess mating combinations program, developed in the mid 60s by George Baylor and Herbert Simon, which was subject of Baylor's Masters thesis at Carnegie Mellon University ^[1]. It was an early pioneering attempt in finding forced checkmates, employing "Artificial Intelligence" rather than "Brute-Force" ^[2]. Only moves which either put the enemy king in check (Mater I), or threaten mate in one (Mater II) were generated for the attacking side, searching those moves first which leave the minimum number of defensive replies, to eventually reduce the defender's mobility to zero.
Astrolabe, Mater and Tympan ^[3]

Abstract

This page is based on the description of Mater by George Baylor and Herbert Simon, 1966, A chess mating combinations program ^[4]:

The program reported here is not a complete chess player; it does not play games. Rather, it is a chess analyst limited to searching for checkmating combinations in positions containing tactical possibilities. A combination in chess is a series of forcing moves with sacrifice that ends with an objective advantage for the active side. A checkmating combination, then, is a combination in which that objective advantage is checkmate. Thus the program described here - dubbed MATER - given a position, proceeds by generating that class of forcing moves that put the enemy King in check or threaten mate in one move, and then by analyzing first those moves that appear most promising.

History

The original mating combination program, as conceived by Herbert Simon and his son Peter Simon in 1962 ^[5], was a hand simulation setting forth a strategy of search. It discovered mating combinations in 52 of the 129 positions collected in Fine's chapter of the mating attack from The Middlegame in Chess. Newell's and Prasad's IPL program ^[6], which could set up a chessboard, recorded positions, generated and made moves and testing their legality, was base of Mater I and in 1964 the revised Mater II programs. According to Monroe Newborn, Mater was ported to Fortran and incorporated into Cooper-Kozdrowicki program by Dennis Cooper and Ed Kozdrowicki ^[7]:

MATER is written by George Baylor and Simon in FORTRAN. It is able to search to great depths for checkmates. MATER is presently part of the Cooper-Kozdrowicki program. While MATER is an interesting program in its own right, the opportunity to checkmate one's opponent plays a relatively small computational part of the game of chess, and its inclusion in the Cooper-Kozdrowicki program does not seem to add measurably to the program's strength.

Mater I

		Only check giving moves were generated in Mater I for the attacking side and check evasions for the defending side, for each ply level put into a try-list. For the attacker, the list is ordered by the fewest-reply heuristic, highest priority goes to moves with the fewest number of legal replies, while checking moves with more than four legal replies are pruned entirely. Ties are broken by giving priority to double checks and then to checks with no capturing replies. Search only continues down a particular path so long as the opponent's mobility is on the decline, which implies a maximum search depth of 9 plies. The defender's side considers captures in MVV/LVA order first, followed by king moves and interpositions. In A chess mating combinations program, the beta-cutoff was mentioned as "killing reply" ^[8], also with a footnote ^[9] on McCarthy.'s killer heuristic referring Alan Kotok's 1962 paper ^[10], covering alpha-beta. Reuben Fine's position from The Middlegame in Chess served as one example of Mater's ability ^[11] ^[12].

Mater II

		At its first level of search, Mater II also generates moves threatening mate in one. After generation and trying checking moves without success, but triggered after collecting useful informations of "nearly" mate with only one legal reply, Mater II considers none checking moves which put additional pressure to the enemy king's sector, that is moves which directly or indirectly (x-ray) attack squares around the king. In this respect it resembles what Adriaan de Groot has called a "sample variation" ^[13], a kind of trial balloon sent up for the express purpose of gathering information to direct subsequent investigations. A further condition to finally add the move into the try-list is that after the move is internally made followed by a defender's null move, the resulting position is mate in one. Now, the defender's move ordering heuristic needs to prefer moves that defend the mating square. Fine's diagram 97 ^[14] was given as example of the abilities of Mater II.

Board Representation

Mater was written in IPL V with its primary data structure of a list, and kept lists with a header (name) and attribute-value pairs for each square and piece to represent the board, where values for piece and square attributes are addresses (cells) of lists again, yielding in an extensive network of relations among squares and pieces:

Name	Attribut	Value
H1	Man on square	M8
	North	H2
	West	G1
	WNW	F2
	NW	G2
	NNW	G3
...	...	...
M8	Man on what square	H1
	Type of man	Rook
	Color of man	White
	Move directions	list of directions
	Capture directions	list of directions
...	...	...

Move Generation

In A chess mating combinations program, Baylor and Simon further elaborate on move generation, with two tacks, corresponding to a one-many or many-one approach. In trying to find all checking moves, one could either radiate out from the enemy king, and for each square, search for a piece that can get there and check (one-many), or converge from the squares along the move directions of each attacking piece onto the enemy king's square (many-one). If there are many pieces on the board, the former tends to be more effective, if few, the latter.

Processing Speed

Mater was written in an interpretive language IPL, without any attempts to provide a special machine-language representation for primitive board manipulation. The most difficult mates, requiring the examination of about 100 positions, were achieved in about 3 minutes on an IBM 7090 ^[15].

Namesake

Mater by Valentin Albillo ^[16]

Publications

Herbert A. Simon, Peter A. Simon (1962). Trial and Error Search in Solving Difficult Problems: Evidence from the Game of Chess. Behavioral Science, Vol. 7, No. 4, pp. 425-429
George W. Baylor (1965). Report on a Mating Combinations Program. SDC Paper, No. SP-2150, System Development Corporation, Santa Monica, Calif.
George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press, pp. 181-200, in David Levy (ed.) (1988). Computer Chess Compendium.
George W. Baylor (1966). A Computer Model of Checkmating Behaviour in Chess. in Adriaan de Groot, Walter R. Reitman (eds.) (1966). Heuristic Processes in Thinking. International Congress of Psychology, Nauka, Moscow
Herbert Simon (1973). Lessons from Perception for Chess-Playing Programs (and Vice Versa). Computer Science Research Review 1972-73, pdf
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
Max Bramer (1982). Finding Checkmates. Computer & Video Games, Spring 1982, pdf hosted by Mike Watters

External Links

References

^ George Baylor in All Remembrance of Herbert A. Simon
^ Max Bramer (1982). Finding Checkmates. Computer & Video Games, Spring 1982, pdf hosted by Mike Watters
^ One of four extant brass astrolabes manufactured by the workshop of Georg Hartmann in Nuremberg in 1537. This one part of the Scientific Instruments Collection of Yale University's Peabody Museum of Natural History, Yale's Hartmann astrolabe.jpg - Wikimedia Commons
^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
^ Herbert A. Simon, Peter A. Simon (1962). Trial and Error Search in Solving Difficult Problems: Evidence from the Game of Chess. Behavioral Science, Vol. 7, No. 4, pp. 425-429
^ Allen Newell, N. S. Prasad (1963). IPL-V Chess Position Program. Internal Memo No. 63, Carnegie Mellon University
^ Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. p. 26
^ "this (Move ordering) is an attempt to clip unnecessary proliferations in the move tree: if there is a "killing" reply to a checking move, further analysis of that checking move would seem futile" from 4. The Executive and Heuristics of Search in George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
^ "This is the minimax assumption: namely that the opponent will make his strongest reply at every opportunity. McCarthy.'s killer heuristic (see Kotok, 1962) assumes that a killing reply to one checking move may be a killing reply to other checking moves and thus should be looked at first" from 4. The Executive and Heuristics of Search in George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences
^ Alan Kotok (1962). Artificial Intelligence Project - MIT Computation Center: Memo 41 - A Chess Playing Program. pdf
^ Reuben Fine (1952). The Middlegame in Chess. McKay
^ r1bk2nr/p2p1pNp/n2B4/1p1NP2P/6P1/3P1Q2/P1P1K3/q5b1 w - - 0 1 ; Fine 1952, chess/BWTC.PGN at master · wspeirs/chess · GitHub
^ Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam, advisor Géza Révész; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6.
^ r1b2qrk/pp3p1p/4pPpQ/8/8/5N2/P4PPP/3R2KR w - - 0 1 ; Fine 1952, chess/BWTC.PGN at master · wspeirs/chess · GitHub
^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences - Processing Speed
^ MATER === A simple Mate Searching Program by José Antônio Fabiano Mendes, CCC, January 24, 2001

What links here?

Page	Date Edited
Carnegie Mellon University	Feb 12, 2018
Checkmate	Apr 13, 2018
CHREST	May 6, 2016
Coko	Jul 13, 2015
Engines	Mar 10, 2018
George Baylor	Sep 22, 2014
Herbert Simon	Feb 11, 2016
IBM 7090	Jan 19, 2018
MAPP	Jan 30, 2016
Mate Search	Oct 22, 2016
Mate-in-two	Oct 14, 2016
Mater	Apr 26, 2016
Max Bramer	May 20, 2014
Michael Barenfeld	Oct 2, 2014
MVV-LVA	Oct 26, 2017
NSS	Jul 14, 2015
Null Move Pruning	Dec 2, 2017
Perceiver	Nov 21, 2017
Threat Move	Sep 10, 2017

Up one Level

MBChess

GerdIsenberg — Sat, 29 Sep 2012 22:31:17 GMT

Hardware vs. Software

Home * Engines * MBChess

MBChess,
a chess program by Marc Boulé, written in C. It was primarily used as test-bed for hardware based FPGA move generation, which was subject of Boulé's Masters thesis in 2002 ^[1]. The FPGA approach performs a Belle like move generation method with find victim and find aggressor cycles in MVV-LVA manner. The move generator includes a PCI interface to connect it to the PC running MBChess. Communication is done via different commands, such as to instruct the move generator to undo the currently stored move, generate and return the next move and execute that move on its internal FPGA board representation. In total, 10,804 out of 18,816 logic cells of a Xilinx XCV800 ^[2] were used, 10,104 as LUT, 700 as RAM ^[3].

A block diagram of a chess square with transmitter (TX) and the receiver (RX) ^[4]

Hardware vs. Software

MBChess is a very basic chess program, without opening book, only rudimentary evaluation, i.e. almost no king safety, and without null move pruning. The reported ratings obtained on FICS are 1844 and 1692 for MBChess+FPGA and MBChess respectively ^[5]. Marc Boulé further concluded a bit disappointing results ^[6]. Even though the pure move generation speed is almost 5 times faster, when using full heuristics, this drops to about 2 times faster. He found that his FPGA move generator, can at best, make/unmake 10M moves a second, which due to PCI bus saturation, will not even transfer from FPGA to PC. Crafty could already make/unmake 30M moves a second on that machine, which implies the only way to speedup Crafty would be to make an FPGA with search and evaluation.

Publications

Marc Boulé (2002). An FPGA Move Generator for the Game of Chess. Masters thesis, McGill University, (Supervisor: Zeljko Zilic, Co-Supervisor: Monty Newborn), pdf
Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. McGill University,pdf
Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. ICGA Journal, Vol. 25, No. 2, pdf

Forum Posts

A Response From Marc Boule by Slater Wold, CCC, April 02, 2002
Re: Thesis by Marc Boule by Marc Boulé, CCC, September 07, 2002
Re: Thesis by Marc Boule by Marc Boulé, CCC, September 08, 2002

External Links

FICS Games Database - Statistics for mbchess

References

^ Marc Boulé (2002). An FPGA Move Generator for the Game of Chess. Masters thesis, McGill University, (Supervisor: Zeljko Zilic, Co-Supervisor: Monty Newborn), pdf
^ Re: Attention - Slater Wold by Marc Boulé, CCC, April 10, 2003
^ Re: Thesis by Marc Boule by Marc Boulé, CCC, September 08, 2002
^ Marc Boulé (2002). An FPGA Move Generator for the Game of Chess. Masters thesis, McGill University, (Supervisor: Zeljko Zilic, Co-Supervisor: Monty Newborn), pdf
^ Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. ICGA Journal, Vol. 25, No. 2, pp. 8, pdf
^ A Response From Marc Boule by Slater Wold, CCC, April 02, 2002

What links here?

Page	Date Edited
Belle	Jan 18, 2018
Engines	Mar 10, 2018
FPGA	Jul 9, 2016
Marc Boulé	Feb 17, 2015
MBChess	Sep 29, 2012
McGill University	Feb 12, 2018
MVV-LVA	Oct 26, 2017

Up one Level

Meep

GerdIsenberg — Sun, 04 Sep 2016 12:57:55 GMT

Home * Engines * Meep

		Meep, an experimental chess engine as subject of research on machine learning techniques and automated tuning, written by Joel Veness, supported by David Silver, William Uther, and Alan Blair, as elaborated in their 2009 research paper this page is based on ^[1] , and in Joel Veness' Ph.D. thesis ^[2] . Meep is based on the UCI compliant tournament chess engine Bodo, where the hand-crafted evaluation function is replaced by a weighted linear combination of 1812 features. Given a position s, a feature vector Φ(s) can be constructed from the 1812 numeric values of each feature. The majority of these features are binary. Φ(s) is typically sparse, with approximately 100 features active in any given position. Five wellknown, chess specific feature construction concepts, material, piece square tables, pawn structure, mobility and king safety were used to generate the 1812 distinct features. In a training mode with various search frameworks, Meep learns from self-play to adjust the weights of its evaluation function towards the value of the deep search. A tournament mode is later used to verify the strength of a trained weight configuration.
Strapped woman ^[3]

BootStrap

In contrast to temporal difference methods such as TD-Leaf ^[4] as used in KnightCap ^[5] , where the target search is performed at subsequent time-steps, after a real move and response have been played, Meep performs various bootstrapping techniques during training, dubbed RootStrap and TreeStrap, to adjust the weights at every time-step inside either a minimax or alpha-beta search.

With the heuristic evaluation function as linear combination of

$\displaystyle {H_\theta}(s) = \Phi(s)^T \theta$

where Φ(s) is a vector of features of position s, and θ is a parameter vector specifying the weight of each feature in the linear combination, following backup rules are given, using V as backed up value of the minimax or alpha-beta search (left arrow theta (←θ) denotes the operator that updates the heuristic function towards some target value):

Algorithm		Backup
TD		$\displaystyle {H_\theta}(s_t) \; {\leftarrow^{\!\!\!\! \theta}} \; {H_\theta}(s_{t+1})$
TD-Root		$\displaystyle {H_\theta}(s_t) \; {\leftarrow^{\!\!\!\! \theta}} \; {V_{s_{t+1}}^D}(s_{t+1})$
TD-Leaf		$\displaystyle {H_\theta}(l^D(s_t)) \; {\leftarrow^{\!\!\!\! \theta}} \; {V_{s_{t+1}}^D}(s_{t+1})$
RootStrap(minimax)		$\displaystyle {H_\theta}(s_t) \; {\leftarrow^{\!\!\!\! \theta}} \; {V_{s_t}^D}(s_t)$
TreeStrap(minimax)		$\displaystyle {H_\theta}(s) \; {\leftarrow^{\!\!\!\! \theta}} \; {V_{s_t}^D}(s), \forall s \in T_{s_t}^D$
TreeStrap(αβ)		$\displaystyle {H_\theta}(s) \; {\leftarrow^{\!\!\!\! \theta}} \; \big[{b_{s_t}^D}(s), {a_{s_t}^D}(s)\big], \forall s \in T_{s_t}^{\alpha\beta}$


TD, TD-Root and TD-Leaf backups		RootStrap and TreeStrap(minimax) backups ^[6]

RootStrap

RootStrap(minimax) or the identical RootStrap(αβ) adjust the weights by stochastic gradient descent ^[7] on the squared error between the static evaluation and the minimax (or alpha-beta) search value of the root.

$\displaystyle \delta_{t} = {V_{S_t}^D}(S_t) - {H_\theta}(S_t)$

$\displaystyle \Delta\theta = -\frac{\eta}{2} {\nabla_\theta} {\delta_{t}^2} = \eta\delta_{t} {\nabla_\theta} {H_\theta}(S_t)$

where η is a step size constant.

TreeStrap

TreeStrap(mm) also considers all interior nodes of the search tree for the stochastic gradient descent on the squared error. The minimax algorithm used for TreeStrap(mm), keeps the entire tree in memory. TreeStrap(αβ) applies a generic implementation, that uses only a few enhancements, transposition table, killer and history heuristics, and check extensions.

Bounds computed by alpha-beta can be exploited by using a one-sided loss functions. If the static evaluation is larger than alpha, then it is reduced towards alpha. If the value from the heuristic evaluation is smaller than beta, then it is increased respectively.

Results

A tournament of ~16,000 games of 1 minute per game plus 1 second per move Fischer time between different trained Meep versions and a reference player with randomly initialised weights and arbitrarily assigned rating of 250 was played. Training was previously done by self-play with the same time, using a small opening book to maintain diversity. The target values were determined by at least one ply of full-width search, plus a varying amount of quiescence search. All Elo values are calculated relative to the reference player, the best performance with 95% confidence intervals given ^[8] :

Algorithm		Elo
Untrained		250 ± 63
TD-Leaf		1068 ± 36
RootStrap(αβ)		1362 ± 59
TreeStrap(mm)		1807 ± 32
TreeStrap(αβ)		2157 ± 31

Publications

Joel Veness, David Silver, William Uther, Alan Blair (2009). Bootstrapping from Game Tree Search. pdf ^[9]
Joel Veness (2011). Approximate Universal Artificial Intelligence and Self-Play Learning for Games. Ph.D. thesis, University of New South Wales, supervisors: Kee Siong Ng, Marcus Hutter, Alan Blair, William Uther, John Lloyd; pdf
István Szita (2012). Reinforcement Learning in Games. in Marco Wiering, Martijn Van Otterlo (eds.). Reinforcement learning: State-of-the-art. Adaptation, Learning, and Optimization, Vol. 12, Springer

Forum Posts

A paper about parameter tuning by Rémi Coulom, CCC, January 12, 2010
Re: A paper about parameter tuning by Joel Veness, CCC, January 15, 2010
Re: A paper about parameter tuning by Joel Veness, CCC, January 15, 2010

External Links

Bootstrapping from Game Tree Search, video presentation by Joel Veness, from VideoLectures - exchange ideas & share knowledge, December 2009
Meep from Wikipedia
Urban Dictionary: meep
Bootstrapping from Wikipedia
Bootstrapping (disambiguation) from Wikipedia
Bootstrap aggregating from Wikipedia
Strapping from Wikipedia
Strapse from Wikipedia.de (German)
Wearing suspenders or garter belts from Wikipedia
Volker Kriegel - Three Or Two In One, Lift!, 1973, YouTube Video
feat: Eberhard Weber, John Marshall, Stan Sulzmann, John Taylor, Cees See, Zbigniew Seifert

References

^ Joel Veness, David Silver, William Uther, Alan Blair (2009). Bootstrapping from Game Tree Search. pdf
^ Joel Veness (2011). Approximate Universal Artificial Intelligence and Self-Play Learning for Games. Ph.D. thesis, University of New South Wales, supervisors: Kee Siong Ng, Marcus Hutter, Alan Blair, William Uther, John Lloyd; pdf
^ Cover of Bizarre, Vol. 3 from 1946, depicting a chained woman, and a devil with tailoring tools promising torments due to the wasp-waisted "Fashions of 1946". by John Willie, Wikimedia Commons
^ Jonathan Baxter, Andrew Tridgell, Lex Weaver (1998). TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search. Australian Journal of Intelligent Information Processing Systems, Vol. 5 No. 1, arXiv:cs/9901001
^ Jonathan Baxter, Andrew Tridgell, Lex Weaver (1998) Knightcap: A chess program that learns by combining td(λ) with game-tree search. Proceedings of the 15th International Conference on Machine Learning
^ Images cropped from Joel Veness, David Silver, William Uther, Alan Blair (2009). Bootstrapping from Game Tree Search. pdf, Figure 1, pp. 2
^ Nabla operator from Wikipedia
^ Joel Veness, David Silver, William Uther, Alan Blair (2009). Bootstrapping from Game Tree Search. pdf
^ A paper about parameter tuning by Rémi Coulom, CCC, January 12, 2010

What links here?

Page	Date Edited
Automated Tuning	Feb 27, 2018
Bodo	Oct 6, 2016
Engines	Mar 10, 2018
Joel Veness	Dec 8, 2017
Learning	Feb 20, 2018
Mathematician	Apr 9, 2018
Meep	Sep 4, 2016
Neural Networks	Mar 12, 2018
Temporal Difference Learning	Feb 20, 2018

Up one level

N.N.

GerdIsenberg — Sat, 20 Jan 2018 16:20:32 GMT

Home * Engines * N.N.

N.N.		N.N., an experimental chess system to select reasonable moves in quiet middlegame positions, developed by Bernd Owsnicki and Kai von Luck at University of Hamburg, written in LISP as subject of their Ph.D. theses ^[1], further introduced 1984 at the Advances in Computer Chess 4 conference ^[2]. N.N. is based on hierarchically structured chess knowledge, conceptional divided into three main components, the knowledge bases, the planning system, and various dynamic data structures. The knowledge bases represent positional knowledge and associate classes of pawn structure with plans and actions. The planning system directs the evaluation of plans. Each plan is associated with some specific formation and has to be verified dynamically in a concept tree in order to overcome problems resulting from erroneous assumptions about the character of the position. At the conference, two distinct areas of planning were demonstrated, minority attack and the elementary endgame KPK ^[3]. Three typical areas of possible errors were mentioned - each with its own cause and each with a different level of solvability ^[4], errors in a particular knowledge base, errors from design decisions, typically about the interaction of distinct instances in the concept tree, and errors in the semantic of planning.

Dynamic Behavior

A sketch of N.N.'s dynamic behavior, considerably simplified ^[5]:

  Knowledge Bases           Processes           Knowledge Bases
 ┌────────────────┐     ╓────────────────╖     ┌────────────────┐
 │  Prototype     │     ║  Net           ║     │ Discrimination │
 │  Frames        │  ┌─►║  Interpreter   ║◄────│ Net            │
 └────────────────┘  │  ╙────────────────╜     └────────────────┘
     model           │      classes of           classification
     knowledge       │       a given             knowledge
         .           │      position
         .           │          ║
         ▼           │          ▼
 ┌────────────────┐  │  ╓────────────────╖     ┌────────────────┐
 │  Instance      │──┘  ║  Task          ║◄────│ Action         │
 │  Frames        │◄─┐  ║  Scheduler     ║  ┌──│ Scripts        │
 └────────────────┘  │  ╙────────────────╜  │  └────────────────┘
     position        │     trigger of       │     plan
     knowledge       │     appropriate      │     knowledge
                     │     scripts          │
                     │          ║           │
                     │          ▼           │
                     │  ╓────────────────╖  │  ┌────────────────┐
                     └─►║  Task          ║◄─┘  │ Concept        │
                        ║  Scheduler     ║────►│ Tree           │
                        ╙────────────────╜     └────────────────┘
                          concretization          concrete plan
                          of scripts

──► information flow
══► control flow
··► inheritance

Etymology

"N. N." is commonly used in the notation of chess games ^[6], not only when one participant's name is genuinely unknown but when an untitled player faces a master, as in a simultaneous exhibition. Another reason is to protect a known player from the insult of a painful defeat ^[7] .

Publications

Kai von Luck, Bernd Owsnicki (1981). Structures for Knowledge-Based Chess Programs. in Siekmann (Ed.), Proc. of GWAI-81
Kai von Luck, Bernd Owsnicki (1982). N.N.: A View of Planning in Chess. in Wahlster (Ed.), Proc. of GWAI-82
Bernd Owsnicki (1985). Repräsentation von positionellem Schachwissen mit Techniken der künstlichen Intelligenz. Ph.D. thesis, University of Hamburg (German)
Kai von Luck (1985). Aspekte wissensgestützter Planung. Ph.D. thesis, University of Hamburg (German)
Bernd Owsnicki, Kai von Luck (1986). N.N.: A Case Study in Chess Knowledge Representation. Advances in Computer Chess 4

External Links

References

^ Alexander Reinefeld (1985). Kai von Luck: Aspekte wissensgestützter Planung. Bernd Owsnicki: Repräsentation von positionellem Schachwissen mit Techniken der künstlichen Intelligenz. ICCA Journal, Vol. 8, No. 4
^ Bernd Owsnicki, Kai von Luck (1986). N.N.: A Case Study in Chess Knowledge Representation. Advances in Computer Chess 4
^ Jaap van Oosterwijk Bruyn (1984). The Fourth Conference on Advances in Computer Chess. ICCA Journal, Vol. 7, No. 2
^ Dap Hartmann (1987). Book review: Advances in Computer Chess 4 from ACM Portal
^ Diagram edited from Kai von Luck, Bernd Owsnicki (1982). N.N.: A View of Planning in Chess. in Wahlster (Ed.), Proc. of GWAI-82, Fig. 1, pp. 93
^ David Hooper, Kenneth Whyld (1992). The Oxford Companion to Chess. 2nd ed., Oxford University Press, p. 274
^ Nomen nescio from Wikipedia

What links here?

Page	Date Edited
Advances in Computer Chess 4	Jan 22, 2018
Bernd Owsnicki-Klewe	Jan 20, 2018
Engines	Mar 10, 2018
Kai von Luck	Jan 20, 2018
N.N.	Jan 20, 2018
Planning	Feb 12, 2018
University of Hamburg	Jan 20, 2018

Up one Level

Prophet

GerdIsenberg — Sat, 30 Sep 2017 20:54:11 GMT

Home * Engines * Prophet

		Prophet, a Chess Engine Communication Protocol compliant open source chess engine under the GNU General Public License, written by James Swafford in C++ as a better C. As successor of Galahad, Prophet is a traditional bitmap based program. Prophet was used in experiments with TD-Leaf ^[1] when James Swafford was undergraduate at East Carolina University ^[2], and testbed for parallel search algorithms as topic of its author's Masters project ^[3]. In September 2017, Prophet3 was released as open source under the MIT License, using magic bitboards ^[4].
Nostradamus ^[5]

Description

Bitboard Infrastructure

Description

Bitboard Infrastructure

Rotated Bitboards

Prophet2 uses rotated bitboards with 1/2 MiB lookup tables, indexed by square and 8-bit line occupancy, to determine sliding piece attacks, ignoring the possible fourfold reduction excluding the redundant outer squares ^[6].

Bitmap diag_a1h8_attacks[64][256];
Bitmap diag_h1a8_attacks[64][256];
Bitmap file_attacks[64][256];
Bitmap rank_attacks[64][256];
 
Bitmap GenBishopMap(Position* p,int sq) {
  Bitmap b=0;
  // find index for a1->h8 diagonal
  int ind = (p->allpieces45 >> diag_a1h8_shift[sq]) & diag_a1h8_mask[sq];
  b = diag_a1h8_attacks[sq][ind];
  // find index for h1->a8 diagonal
  ind = (p->allpieces315 >> diag_h1a8_shift[sq]) & diag_h1a8_mask[sq];
  b |= diag_h1a8_attacks[sq][ind];
  return b;    
}

BitScan & PopCount

Similar to Amundsen, the memory bacchanal is attended by population count, bitscan forward (GetLSBFast) and reverse (GetMSBFast) with three 16-bit indexed, 64K lookup tables of double word integers, another 3/4 MiB competing for the caches ^[7]:

int  num_bits[65536];
int  lsb[65536];
int  msb[65536];
 
/*****************************************************************************
 *                                                                           *
 * int GetLSBFast(Bitmap b)                                                  *
 *                                                                           *
 * Returns the least significant bit in a bitmap (1-64), or 0 if no bit set. *
 * Assumes lsb[] is initialized.  Much faster than GetLSBSlow().             *
 *                                                                           *
 *****************************************************************************/
 
int GetLSBFast(Bitmap b) {
  int r = lsb[(int)(b & 65535)];
  if (r) return r;
  b >>= 16;
  r = lsb[(int)(b & 65535)];
  if (r) return r+16;
  b >>= 16;
  r = lsb[(int)(b & 65535)];
  if (r) return r+32;
  b >>= 16;
  r = lsb[(int)b];
  if (r) return r+48;
  return 0;
}

Search

Prophet's search is alpha-beta PVS with transposition table inside an iterative deepening framework with fractional plies and aspiration windows of ± 1/3 pawn value. Selectivity is due to adaptive null move pruning, futility and extended futility pruning, and fractional extensions on checks, single replies, passed pawn advances and recaptures. Beside TT and keeping a linked list of PVs on the Stack, Move ordering considers killer and history heuristic, as well as MVV-LVA and SEE for captures.

Evaluation

The evaluation in centipawn resolution determines a score based on material balance and piece-square tables, and further considers various positional features, such as development, mobility, king safety and pawn structure, and trapped pieces.

Tournament Play

Prophet played five CCT Tournaments, from CCT7 in 2005, until CCT11 in 2009, three ACCA Americas' Computer Chess Championships, ACCA 2006, ACCA 2007 and ACCA 2008, and the WCRCC 2008 Second Annual ACCA World Computer Rapid Chess Championship.

Selected Games

CCT11, round 2, Prophet - NoonianChess ^[8]

[Event "CCT11"]
[Site "Internet Chess Club"]
[Date "2009.03.21"]
[Round "2"]
[White "Prophet"]
[Black "NoonianChess"]
[Result "1-0"]
 
1.c4 g6 2.Nc3 Bg7 3.g3 c5 4.Bg2 Nc6 5.Nf3 d6 6.O-O Nf6 7.d4 cxd4 8.Nxd4 
Bd7 9.Nc2 O-O 10.b3 a6 11.Bb2 Ng4 12.h3 Nh6 13.Rb1 Bf5 14.e4 Be6 15.Nd5 
f6 16.a4 Re8 17.Qd2 Bf7 18.Bc3 g5 19.a5 Rb8 20.Nb6 Bh5 21.Kh1 e5 22.Ne3 
Qe7 23.f4 gxf4 24.gxf4 Qd8 25.Ned5 Kh8 26.Bf3 Bxf3+ 27.Rxf3 f5 28.exf5 
Nxf5 29.fxe5 Nh4 30.Rf7 Nxe5 31.Bxe5 Rxe5 32.Nd7 Qe8 33.Nxe5 dxe5 34.Rbf1
Qe6 35.Qe3 Ng6 36.R1f6 Qc8 37.Rd6 e4 38.Rdd7 Ne5 39.Rxg7 Qxd7 40.Rxd7 Nxd7 
41.Qd4+ Kg8 42.Ne7+ Kf7 43.Qxd7 Rf8 44.Nf5+ Kf6 45.Qe7+ Kxf5 46.Qxf8+ Kg5 
47.Qf1 e3 48.c5 e2 49.Qxe2 Kf4 50.Qe7 h6 51.Qxb7 h5 52.Kg2 Ke3 53.Qd5 Ke2 
54.c6 Ke3 55.c7 Kf4 56.Kh1 Ke3 57.c8=Q Kf2 58.Qd4+ Ke2 59.Qxa6+ Ke1 
60.Qe6+ Kf1 61.Qdf6# 1-0

Publications

James Swafford (2002). Optimizing Parameter Learning using Temporal Differences. AAAI-02, Student Abstracts, pdf
James Swafford (2008). A Survey of Parallel Search Algorithms over Alpha-Beta Search Trees using Symmetric Multiprocessor Machines. Masters Project, East Carolina University, advisor Ronnie Smith, pdf

Forum Posts

It's Prophet by James Swafford, CCC, February 04, 2005 » CCT7
Re: Speedup with bitboards on 64-bit CPUs by James Swafford, CCC, April 28, 2007
pthread weirdness by James Swafford, CCC, May 29, 2007
Prophet ACCA PanAm 2008 tournament notes by James Swafford, CCC, November 10, 2008 » ACCA 2008
prophet3 released with source code by James Swafford, CCC, September 30, 2017

External Links

Chess Engine

Misc

Prophet from Wikipedia
Prophet (disambiguation) from Wikipedia
Prophecy from Wikipedia
Prophecy (disambiguation) from Wikipedia
Nostradamus: The Last Prophecy from Wikipedia
Jazz is Dead - Estimated Prophet, Fox Theatre, Boulder, Colorado, April 13, 1999, YouTube Video
lineup: Jimmy Herring, T Lavitz, Alphonso Johnson, Billy Cobham

References

^ James Swafford (2002). Optimizing Parameter Learning using Temporal Differences. AAAI-02, Student Abstracts, pdf
^ prophet | James Swafford
^ James Swafford (2008). A Survey of Parallel Search Algorithms over Alpha-Beta Search Trees using Symmetric Multiprocessor Machines. Masters Project, East Carolina University, advisor Ronnie Smith, pdf
^ prophet3 released with source code by James Swafford, CCC, September 30, 2017
^ The Portrait of Michel de Nostredame (Nostradamus), a French Renaissance Medicine & Astrologer, painted by his son César de Nostredame (1553-1630?) about 1614 A.D. 16cm x 18cm. (cf. Jean Boyer, “Deux peintres oubliés du XVIe siècle: Etienne Martellange et César de Nostredame”, Bulletin de la Société de l’Histoire de l’art français, Année 1971 (1972), pp.13-20)
^ prophet-20b1-ja.zip, globals.cpp, bitmaps.cpp
^ prophet-20b1-ja.zip, globals.cpp, bitmaps.cpp
^ CCT11 results and games

What links here?

Page	Date Edited
ACCA 2006	Jul 14, 2014
ACCA 2007	Jul 14, 2014
ACCA 2008	Jul 14, 2014
BitScan	Sep 10, 2017
CCT10	May 5, 2013
CCT11	Feb 17, 2015
CCT7	Dec 16, 2017
CCT8	Apr 6, 2013
CCT9	Aug 25, 2013
chess4j	Jan 1, 2018
Engine releases	Apr 23, 2018
Engines	Mar 10, 2018
Galahad	Jan 8, 2015
James Swafford	Jan 1, 2018
Prophet	Sep 30, 2017
WCRCC 2008	Nov 21, 2016

Up one level

Rajah

GerdIsenberg — Wed, 12 Sep 2012 08:22:59 GMT

Home * Engines * Rajah

Rajah (RajahX),
a chess program by Valavan Manohararajah. Its development started from scratch in early 1996. Rajah played the DOCCC 1996 and the Aegon 1997, and its design, like many programs influenced by Chess 4.5 ^[1], was described in ICCA Journal, Vol. 20, No. 2 ^[2]. Rajah is a leaf-evaluator and performs no pre-processing at the root or interiour of the tree. Rajah was further subject of research in the authors Master's Thesis on Parallel Search in 2001 from University of Toronto ^[3].

Photos

Peng Zhaoqin facing Rajah by Valavan Manohararajah, Aegon 1997 ^[4]

Search

Rajah uses a full width Principal Variation Search followed by Quiescence Search ^[5], where the move generator only generates captures and promotions to a queen, where a first layer in pruning removes any capture that fails to bring the material score above a value based on alpha ^[6]. A second layer in QS performs SEE, to prune all moves with a SEE values less than zero ^[7]. Additionally, Rajah applies Null Move Pruning similar as described by Donninger in 1993 ^[8] with a depth reduction of two. It extends checks, recapturers and passed pawn moves to the 7th and 8th rank. Extension are switched off, when the search depth exceeds two times the current iteration depth.

The Transposition table is used in both full width and quiescence search, the replacement strategy is the one given by Dennis Breuker et al. in 1994 ^[9]. The killer and history heuristic is used in the full-width search only.

0x88

Rajah's board representation is 0x88 ^[10], to take advantage of testing those two bits in target square traversal of move generation ^[11], and specially for the unique square difference property for attack detection. In his article, Valavan gives the C source snippet of a typical inner loop in move generation, e.g. a white bishop moving diagonally up:

target_sq = current_sq;
while (1) {
  target_sq += 15; /* the move up and left */
  if ( target_sq & 0x88 ) break; /* check for out of bounds condition */
  if ( board[target_sq] == empty) {
    /* add a non-capture move to the move list */
  } else {
    if ( board[target_sq] & black_piece {
       /* add a capture move to the move list */
    }
    break;
  }
}

Publications

Jaap van den Herik (1997). Augmentes Ideas. Editorial ICCA Journal, Vol. 20, No. 1, pp. 1-2 ^[12] ^[13]
Valavan Manohararajah (1997). Rajah: The Design of a Chess Program. ICCA Journal, Vol. 20, No. 2, pp. 87-91
Valavan Manohararajah (2001). Parallel Alpha-Beta Search on Shared Memory Multiprocessors. Masters Thesis, pdf

Forum Posts

X88 board representations by Valavan Manohararajah, rgcc, April 17, 1996 » 0x88
Computer Chess Hardware Design by Valavan Manohararajah, rgcc, March 30, 1997
Misinformation about RAJAH in the ICCA by Valavan Manohararajah, rgcc, April 5, 1997
Re: Computerised Chess Games by Valavan Manohararajah, rgcc, April 07, 1997
Re: Mobility in evaluation functions- how much is it worth? by Valavan Manohararajah, rgcc, June 08, 1997 » Mobility
Re: GNU Chess for Pilot? by Valavan Manohararajah, rgcc, July 09, 1997 » GNU Chess
Anyone want to represent Rajah at the WMCCC? by Valavan Manohararajah, rgcc, August 14, 1997

References

^ David Slate and Larry Atkin (1977). Chess 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
^ Valavan Manohararajah (1997). Rajah: The Design of a Chess Program. ICCA Journal, Vol. 20, No. 2, pp. 87-91
^ Valavan Manohararajah (2001). Parallel Alpha-Beta Search on Shared Memory Multiprocessors. Masters Thesis, pdf
^ Aegon 1996-97 Photos by Thorsten Czub
^ Tony Marsland (1986). A Review of Game-Tree Pruning. ICCA Journal, Vol. 9, No. 1, pp. 3-19. pdf
^ Günther Schrüfer (1989). A Strategic Quiescence Search. ICCA Journal, Vol. 12, No. 1, pp. 3-9.
^ mvv/lva vs SEE capture ordering test results by Robert Hyatt, rgcc, August 10, 1995
^ Chrilly Donninger. (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3, pp. 137-143.
^ Dennis Breuker, Jos Uiterwijk and Jaap van den Herik (1994). Replacement Schemes for Transposition Tables. ICCA Journal, Vol. 17, No. 4, pp. 183-193
^ X88 board representations by Valavan Manohararajah, rgcc, April 17, 1996
^ see Vector Attacks - Increment Vectors why the cheap looking 0x88 test is not so "smart", 0x88 is not so smart by Christophe Théron, CCC, June 13, 2000
^ Misinformation about RAJAH in the ICCA by Valavan Manohararajah, rgcc, April 5, 1997
^ Re: Misinformation about RAJAH in the ICCA - APOLOGY by Jaap van den Herik, rgcc, April 8, 1997

What links here?

Page	Date Edited
0x88	Nov 28, 2016
Aegon 1997	Apr 7, 2017
DOCCC 1996	Jun 7, 2016
Engines	Mar 10, 2018
Gunda-1	Jan 8, 2016
Historical Examples	Jan 16, 2017
ICGA Journal	Dec 21, 2017
Move Generation	Jan 29, 2018
Rajah	Sep 12, 2012
University of Toronto	Dec 8, 2017
Valavan Manohararajah	May 4, 2017

Up one level

SAL

GerdIsenberg — Thu, 07 Dec 2017 22:22:36 GMT

Home * Engines * SAL

		SAL, (Search and Learn) a general game playing and learning open source program for any two-player board game of perfect information, written by Michael Gherrity as subject of his Ph.D. thesis A Game Learning Machine ^[1]. SAL is written in ANSI C ^[2].
HAL 9000 ^[3]

Description

The rule of the game is defined by subroutines for generating legal moves, as already provided for Tic-tac-toe, Connect Four, and Chess in the source files ttt.c, connect4.c, and chess.c. One of them, or an appropriate implementation of another game, needs to be copied to game.c for building SAL to play that game.

Search

For all games, SAL performs a two-ply, full-width alpha-beta search plus consistency search ^[4], which is a generalized quiescence search as proposed by Don Beal ^[5].

Evaluation

The game independent evaluation is implemented as neural network for each side. The inputs to the network are features representing the board, the number of pieces of each type on the board, the type of piece just moved, the type of piece just captured (if any), and several features considering pieces and squares under attack. The neural network evaluator is trained by temporal difference learning to estimate the outcome of the game, given the current position ^[6].

Results

In Tic-tac-toe, SAL learned to play perfectly after 20,000 games
In Connect four, SAL learned to defeat an opponent program about 80% of the time after 100,000 games
In Chess, after 4200 games against GNU Chess, SAL evolved from a random mover to a reasonable, but still weak chess player

Publications

Michael Gherrity (1993). A Game Learning Machine. Ph.D. thesis, University of California, San Diego, advisor Paul Kube, pdf, pdf

Forum Posts

Subject: Re: Game Learning by Mike Gherrity, ai-repository, July 1, 1994 ^[7]
Sal or neurochess by ethan ara, CCC, September 06, 2011

External Links

Game Player

SAL from Machine Learning in Games by Jay Scott
SAL source code

Misc

Sal (disambiguation) from Wikipedia
SAL 9000 fictional computer in 2010: Odyssey Two

References

^ Michael Gherrity (1993). A Game Learning Machine. Ph.D. thesis, University of California, San Diego, advisor Paul Kube, pdf, pdf
^ SAL source code
^ The famous red eye of HAL 9000, the fictional character in Arthur C. Clarke's Space Odyssey series. Image by Cryteria, October 1, 2010, Wikimedia Commons - A game sequence between Frank Poole and HAL 9000 is given in the preface of Michael Gherrity's thesis
^ Consistency search from Machine Learning in Games by Jay Scott
^ 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
^ SAL from Machine Learning in Games by Jay Scott
^ Barney Pell (1993). Strategy Generation and Evaluation for Meta-Game Playing. Ph.D: thesis, Trinity College, Cambridge, pdf

What links here?

Page	Date Edited
Automated Tuning	Feb 27, 2018
Engines	Mar 10, 2018
Golch	Dec 7, 2017
HAL	Jun 14, 2016
Learning	Feb 20, 2018
Mathematician	Apr 9, 2018
Michael Gherrity	May 8, 2015
Neural Networks	Mar 12, 2018
SAL	Dec 7, 2017
Temporal Difference Learning	Feb 20, 2018

Up one level

Wikispaces : chessprogramming - items matching description

Abyss

Table of Contents

Description

Basics

Misc

Abyss' ICGA Tournaments

See also

Publications

External Links

Engine

Misc

References

What links here?

AliBaba

Table of Contents

See also

Forum Posts

External Links

Chess Engine

Misc

References

What links here?

Atak

Table of Contents

Photos & Games

Forum Posts

External Links

References

What links here?

Chezzz

Table of Contents

Thesis Program

Bitboards

Search

Selected Games

CCT5

CCT7

See also

Publications

Forum Posts

2001

2002

2003

2004 ...

External Links

References

What links here?

Fixafan

Table of Contents

Move Ordering

Experiments

Results

Publications

External Links

References

What links here?

Giraffe

Table of Contents

Description

See also

Publications

Forum Posts

2015

2016

2017...

External Links

Chess Engine

Misc

References

What links here?

Golch

Table of Contents

Perceptron

History Heuristic

See also

Publications

Forum Posts

External Links

References