Wikispaces : chessprogramming - items matching description

Aegon 1993

vincentlejeune — Sun, 26 Mar 2017 11:37:35 GMT

Final Standing

Home * Tournaments * Aegon Tournaments * Aegon 1993
< Prev Next >

The 8th Aegon Man-Machine tournament took place from May 5 to 7, and 10 to 12, 1993, at Aegon Headquarters in The Hague, Netherlands.

Final Standing

^[1]

#	Name	C	1	2	3	4	5	6	P	SOS	SoDOS
1	David Bronstein		13w1	25b1	45w1	7b1	3w½	9b1	5½	23	20½
2	John Nunn		57w1	20b1	44w1	17b1	8w1	3b½	5½	20	17½
3	The King II	1	38w1	26b1	50w1	4w1	1b½	2w½	5	24	18½
4	Herman Grooten		16w1	8b1	18w1	3b0	17w1	22b1	5	23½	18½
5	Vlastimil Hort		52b1	9w½	29b½	20w1	12b1	18w1	5	20	16½
6	Ad van den Berg		17b½	43w½	58b1	29w1	23b1	10w½	4½	18	13
7	Saitek Sparc	2	64b1	63w1	27b½	1w0	28b1	19w1	4½	15½	8½
8	The King I	3	19b1	4w0	34b1	27w1	2b0	30w1	4	23	12½
9	Drei Hirn	4	21w1	5b½	41w½	50b1	30w1	1w0	4	21½	12¼
10	Mephisto RISC	5	26w0	15w1	33b½	31b1	32w1	6b½	4	20½	13¾
11	Gert Ligterink		29b½	23w½	36b1	18b½	25w1	16w½	4	20	13
12	MChess	6	28b½	31w1	32w½	41b1	5w0	26b1	4	19½	11½
13	Socrates	7	1b0	19w0	38w1	63b1	34b1	35w1	4	18½	9½
14	Fritz	8	42w½	30b½	21w½	26b½	33w1	32b1	4	18	12
15	Lex Jongsma		25w0	10b0	55w1	47b1	36b1	39w1	4	17½	10½
16	Genius	9	4b0	62w1	64b1	42w½	24w1	11b½	4	16	7¾
17	Zugzwang	10	6w½	42b1	28w1	2w0	4b0	41w1	3½	23	10¼
18	Rebel	11	35b1	51w1	4b0	11w½	41w1	5b0	3½	21½	9½
19	Nana Ioseliani		8w0	13b1	37w1	25b½	45w1	7b0	3½	21	11
20	Mephisto 68030	12	33b1	2w0	51b1	5b0	50w1	21w½	3½	21	8¾
21	Nico Kuijf		9b0	52w1	14b½	45b½	40w1	20b½	3½	19	10
22	Saitek Brute Force	13	31b0	35w1	46b½	51w1	27b1	4w0	3½	18½	9¼
23	Quest	14	61w½	11b½	24w½	59b1	6w0	42b1	3½	17	8¼
24	Roberto Cifuentes		36b0	47w1	23b½	57w1	16b0	43w1	3½	17	8¼
25	B*HiTech	15	15b1	1w0	31b1	19w½	11b0	27w½	3	23	10¼
26	Loewenthal/Legemaat		10b1	3w0	43b½	14w½	44b1	12w0	3	22	9¾
27	Jos de Waard		39w1	37b1	7w½	8b0	22w0	25b½	3	21	9¾
28	Wim Wolthuis		12w½	49b1	17b0	43w1	7w0	29b½	3	20	8½
29	Gideon 3	16	11w½	61b1	5w½	6b0	42b½	28w½	3	20	8¼
30	Michiel Wind		43b½	14w½	53b1	44w1	9b0	8b0	3	19	7¾
31	Jannes van der Wal		22w1	12b0	25w0	10w0	57b1	45b1	3	18½	7½
32	Henk Arnoldus		58b½	60w1	12b½	39w1	10b0	14w0	3	18	7¼
33	Peewee van Voorthuijsen		20w0	57b½	10w½	48w1	14b0	52b1	3	17½	7¼
34	Heleen de Greef		55w1	44b0	8w0	37b1	13w0	53b1	3	17½	7
35	Max Pam		18w0	22b0	49w1	52b1	53w1	13b0	3	17½	6½
36	Saitek RISC 2500	17	24w1	41b0	11w0	61b1	15w0	50b1	3	17	6½
37	Dappet	18	46b1	27w0	19b0	34w0	51b1	54w1	3	16	6½
38	Tim Krabbé		3b0	53w0	13b0	60w1	58b1	55w1	3	16	5
39	Now	19	27b0	54w1	63b1	32b0	46w1	15b0	3	15	5
40	Check Check	20	51b0	46w½	54b½	64w1	21b0	59w1	3	11½	3¾
41	Alexander Münninghoff		47b1	36w1	9b½	12w0	18b0	17b0	2½	20½	7½
42	Klaas Steijn		14b½	17w0	60b1	16b½	29w½	23w0	2½	19½	7
43	Gideon WK	21	30w½	6b½	26w½	28b0	59w1	24b0	2½	18½	6¾
44	Nimzo	22	62b1	34w1	2b0	30b0	26w0	46b½	2½	18	5¼
45	Kallisto	23	54b1	64w1	1b0	21w½	19b0	31w0	2½	17½	3¾
46	Ed Voortmeijer		37w0	40b½	22w½	55b1	39b0	44w½	2½	17	6½
47	Ananse	24	41w0	24b0	62b1	15w0	61b½	63w1	2½	12½	2
48	Cumulus	25	56w1	50b0	59w½	33b0	54w0	62b1	2½	11½	3¾
49	Schach	26	63b½	28w0	35b0	62w0	64b1	61w1	2½	8½	1¼
50	Jessica Harmsen		53b1	48w1	3b0	9w0	20b0	36w0	2	20	4½
51	Hebert Perez Garcia		40w1	18b0	20w0	22b0	37w0	57w1	2	18	4½
52	Zarkov 2	27	5w0	21b0	56b1	35w0	62b1	33w0	2	17½	3
53	Zarkov 3	28	50w0	38b1	30w0	56b1	35b0	34w0	2	16	5
54	Sylvia de Vries		45w0	39b0	40w½	58w½	48b1	37b0	2	15½	4¾
55	Hiarcs	29	34b0	56w1	15b0	46w0	63w1	38b0	2	15	2½
56	Henny Maliangkay		48b0	55b0	52w0	53w0	60b1	58w1	2	11½	3
57	TASC R30	30	2b0	33w½	61w1	24b0	31w0	51b0	1½	18	2½
58	LChess	31	32w½	59b½	6w0	54b½	38w0	56b0	1½	16	3¼
59	Henk de Kleijnen		60b½	58w½	48b½	23w0	43b0	40b0	1½	14½	2¾
60	Goldbar	32	59w½	32b0	42w0	38b0	56w0	64w1	1½	12	¾
61	Wim van der Wijk		23b½	29w0	57b0	36w0	47w½	49b0	1	16	3
62	Parson/Rebattu		44w0	16b0	47w0	49b1	52w0	48w0	1	16	2½
63	Jos Timmer		49w½	7b0	39w0	13w0	55b0	47b0	½	18½	1¼
64	Martin Voorn		7w0	45b0	16w0	40b0	49w0	60b0	0	18	0

SOS: Sum of Opponent Scores
SoDOS: Sum of Defeated Opponent Scores

Selected Games

^[2]

Bronstein

[Event "8th AEGON man-mach"]
[Site "The Hague NED"]
[Date "1993.05.05"]
[Round "01"]
[White "David Bronstein"]
[Black "Socrates"]
[Result "1-0"]
 
1.e4 e5 2.Bc4 Nf6 3.d3 c6 4.Nf3 d5 5.Bb3 Bb4+ 6.c3 Bd6 7.Bc2 O-O
8.Bg5 h6 9.Bh4 Bg4 10.Nbd2 Nbd7 11.h3 Bh5 12.g4 Bg6 13.Bg3 Qb6
14.Rb1 Qa6 15.O-O Qxa2 16.Nh4 Bh7 17.exd5 Qxd5 18.Nc4 Rfe8 19.Ne3 Qe6
20.Nhf5 Rad8 21.Re1 Nd5 22.Nxd5 Bxf5 23.gxf5 Qxd5 24.Bb3 Qc5 25.Qh5 Rf8
26.Bh4 Be7 27.d4 Qd6 28.dxe5 Nxe5 29.Bxe7 Qxe7 30.f6 Qxf6 31.Qxe5 Qg6+
32.Qg3 Qxg3+ 33.fxg3 Rfe8 34.Rxe8+ Rxe8 35.Kf2 Re5 36.Rd1 Kf8
37.Bc4 Ke7 38.Kf3 a5 39.Rd4 b5 40.Ba2 f5 41.Bb1 c5 42.Rd1 c4 43.h4 g6
44.Bc2 g5 45.Rd2 Rc5 46.Rh2 Rd5 47.Ke3 Ke6 48.hxg5 hxg5 49.Rh6+ Kf7
50.Ra6 a4 51.Rh6 Kg7 52.Rh1 Kf6 53.Rf1 Re5+ 54.Kd2 Ke6 55.Re1 Rxe1
56.Kxe1 Ke5 57.Ke2 Ke6 58.Kf3 Kf6 59.Ke3 Ke5 60.Bd1 Ke6 61.Kd4 Kd6
62.Bh5 Kc6 63.Bd1 Kd6 64.Bf3 f4 65.g4 Kc7 1-0

Game and short analyze on Lichess.org : https://fr.lichess.org/MgGc36iX

[Event "8th AEGON man-mach"]
[Site "The Hague NED"]
[Date "1993.05.06"]
[Round "02"]
[White "B*Hitech"]
[Black "David Bronstein"]
[Result "0-1"]
 
1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.e5 c5 5.a3 Bxc3+ 6.bxc3 Ne7 7.Qg4 Nf5 8.Bd3 h5
9.Qh3 c4 10.Bxf5 exf5 11.Ne2 f4 12.Qf3 g5 13.Bxf4 Bg4 14.Bxg5 Qxg5
15.Qxd5 Nc6 16.Ng3 Be6 17.Qf3 O-O-O 18.O-O Qg4 19.Qf6 h4 20.f3 Qg6
21.Qxg6 fxg6 22.Ne4 Kc7 23.Rab1 b6 24.Rfe1 Ne7 25.Rb4 Rhf8 26.Ng5 Bd5
27.Nh7 Rf5 28.Nf6 h3 29.Nxd5+ Nxd5 30.Rxc4+ Kd7 31.f4 Rxf4 32.e6+ Kd6
33.gxh3 a5 34.e7 Nxe7 35.Kg2 Rdf8 36.Rb1 Nd5 37.Re1 Rf2+ 38.Kg1 R2f3
39.h4 Ne3 40.Rxe3 Rxe3 0-1

Game and short analyze on Lichess.org : https://fr.lichess.org/x5knjJDx

Quadruple pawns

As mentioned by Marcel van Kervinck ^[3] , former Draughts World Champion Jannes van der Wal arranged to get the seldom case of a Quadruple pawn versus HiTech, the machine by former Correspondence chess World Champion Hans Berliner performing B*:

[Event "8th AEGON man-mach"]
[Site "The Hague NED"]
[Date "1993.05.07"]
[Round "03"]
[White "Jannes van der Wal"]
[Black "B*HiTech"]
[Result "0-1"]
 
1.d4 d5 2.c3 Nf6 3.Bg5 Ne4 4.Bh4 g5 5.Bg3 h5 6.e3 h4 7.Be5 f6 8.f3 fxe5
9.fxe4 dxe4 10.Be2 Bg7 11.Bh5+ Kf8 12.d5 Nd7 13.Bg4 Nc5 14.Be2 e6
15.d6 cxd6 16.Nh3 d5 17.O-O+ Kg8 18.c4 Qb6 19.Bh5 Rh6 20.Qg4 Qxb2
21.Qxg5 Bd7 22.Nd2 Kh7 23.Nb3 Nxb3 24.axb3 Bf6 25.Rxf6 Rxf6
26.Qxf6 Qxa1+ 27.Kf2 Qb2+ 28.Be2 Kg8 29.Qg6+ Kf8 30.Qf6+ Kg8
31.Qg6+ Kf8 32.Qh7 d4 33.Ng5 dxe3+ 34.Kg1 Ke8 35.Qg8+ Ke7 36.Qf7+ 0-1

r4k2/pp1b3Q/4p3/4p1N1/2P1p2p/1P2p3/1q2BKPP/8 w - - 0 34

Reports

Bart Verbaan, Cock de Gorter (1993). The 8th AEGON Man-Machine Tournament. ICCA Journal, Vol. 16, No. 2

External Links

References

^ AEGON Man-Machine Tournaments, old CSVN site
^ CSVN Downloads Games Aegon Tournaments
^ Quadruple pawns by Marcel van Kervinck, rgc, April 18, 1994

What links here?

Page	Date Edited
Aegon 1992	Jan 22, 2017
Aegon 1993	Mar 26, 2017
Aegon 1994	Mar 26, 2017
Aegon Tournaments	Jan 22, 2017
Ananse	Jan 8, 2016
Bart Verbaan	Nov 3, 2015
Cock de Gorter	Nov 3, 2015
Cumulus	Jan 7, 2016
David Bronstein	Oct 28, 2014
ICGA Journal	Dec 21, 2017
Jessica Harmsen	Jul 29, 2012
John Nunn	Dec 9, 2017
RISC 2500	Jan 7, 2016
Saitek Brute Force	Oct 9, 2015
Schach	Jan 7, 2016
Tasc R30	Sep 7, 2017
Walter Bannerman	Jan 8, 2016

Up one Level

Alexander Szabo

GerdIsenberg — Sat, 10 Nov 2012 16:17:43 GMT

Selected Publications

Home * People * Alexander Szabo

Alexander (Alex) Szabo,
a computer scientist, physicist, chess player, at times professional computer chess programmer, and along with Barbara Szabo conducting a computer programming services company, located in San Antonio, New Mexico ^[1]. In the 80s they were active in computer chess business and research, Szabo Software located in Borrego Springs, California, distributed their commercial chess program TechMate for the Atari ST. Alex Szabo holds a M.Sc. in physics, 1980, and a M.Sc. in CS, 1984, both from University of British Columbia, Vancouver, British Columbia, Canada.

Tech 3

In his 1984 thesis Computer-Chess Tactics and Strategy, Alex Szabo elaborates on tactics and strategy exemplified by his thesis chess program Tech 3. In the spirit of the original Tech program by James Gillogly, he claims that knowledge is best applied at the top of the search tree as positional presort rather than at the leaf nodes using complex evaluation.

Tech3's performance on Reinfeld's Win at Chess (WAC) problem set is 274/300, which compares favourable with Belle's, considering machine power. He developed a technology curve as a tool for measuring the effectiveness of knowledge encoding, and found in this respect Nuchess as the best chess program of that time ^[2].

TechMate

		During the mid 80s, Alex Szabo developed TechMate for the Atari ST. It was derived from Tech 3 with the addition of a simple strategic component, a more profound evaluation function. TechMate was commercially market by Szabo Software ^[3].
TechMate Screen ^[4] ^[5]

The Technology Curve

As published in their 1988 ICCA Journal paper ^[6], Alex and Barbara Szabo revisited the technology curve by playing 6882 games between copies of TechMate set at different time rates, with the conclusion that the advantage of improved technology rapidly decreases when machines and algorithms become more powerful. Ernst A. Heinz in his self-play memo on the experiment of the Szabos ^[7]:

The Szabos determined the technology curve of their chess program TechMate that self-played 6,882 games on two Atari ST computers. The number of games per match between longer and shorter searching versions of the program varied strongly from a minimum of 32 to a maximum of 1367. The gain in playing strength averaged at 156 rating points per doubling of available search time (computing power). The experimental data indicated slight diminishing returns at longer search times. However, the Szabos simply did not play enough games at long times to draw reliable conclusions.

WAC 230

		In a 2001 CCC forum post, Alex Szabo proposed several corrections on Win at Chess, in particular that in WAC 230, a position from Hans Kmoch vs Aron Nimzowitsch ^[8], Bad Niendorf, 1927 ^[9], 50... Rb4 does not win ^[10]: #230 [Rb4 does not win. The main line is, 1... Rb4!? 2.cxb4 a4 3.b5+ Kxb5 4.Ba3 c3 5.Re2! Kc4 6.f4 Kxd4 7.f5 exf5 8.e6 Kd3 9.e7 Bd7 10.Kf3 d4 11.Rh2 Kc4 12.Rh8 b2 13.Rb8 d3 14.Bxb2 cxb2 15.Rxb2 a3 16.Rb7 Be8 17.Ra7 Kb3 18.Ke3 a2 19.Kxd3 Kb2 20.Rb7+ Kc1 21.Ra7 =] Ra7, Rb6, Rb5, Rd7, Rf7, Rg7, Rh7, Bd7, Kd7, Kb6, Kb5, a4, and Rc7 are just as good as the book solution Rb4 -- they all hold the game. In August 2010, Dann Corbit posted an allegedly refutation of Szabo's refutation found by Stockfish 1.8 ^[11].
2b5/1r6/2kBp1p1/p2pP1P1/2pP4/1pP3K1/1R3P2/8 b - -

In a 2001 CCC forum post, Alex Szabo proposed several corrections on Win at Chess, in particular that in WAC 230, a position from Hans Kmoch vs Aron Nimzowitsch ^[8], Bad Niendorf, 1927 ^[9], 50... Rb4 does not win ^[10]:

#230    [Rb4 does not win.  The main line is,  1... Rb4!? 2.cxb4 a4
        3.b5+ Kxb5 4.Ba3 c3 5.Re2! Kc4 6.f4 Kxd4 7.f5 exf5 8.e6 Kd3
        9.e7 Bd7 10.Kf3 d4 11.Rh2 Kc4 12.Rh8 b2 13.Rb8 d3
        14.Bxb2 cxb2 15.Rxb2 a3 16.Rb7 Be8 17.Ra7 Kb3 18.Ke3 a2
        19.Kxd3 Kb2 20.Rb7+ Kc1 21.Ra7 =]
 
        Ra7, Rb6, Rb5, Rd7, Rf7, Rg7, Rh7, Bd7, Kd7, Kb6, Kb5, a4, and Rc7
        are just as good as the book solution Rb4 -- they all hold the game.

In August 2010, Dann Corbit posted an allegedly refutation of Szabo's refutation found by Stockfish 1.8 ^[11].

2b5/1r6/2kBp1p1/p2pP1P1/2pP4/1pP3K1/1R3P2/8 b - -

Selected Publications

^[12]

Alexander Szabo (1980). The Co Distribution Around l=30°, b=0°. M.Sc. Thesis, University of British Columbia, pdf
Alexander Szabo (1984). Computer-Chess Tactics and Strategy. M.Sc. Thesis, University of British Columbia, pdf
Alexander Szabo, Barbara Szabo (1988). The Technology Curve Revisited. ICCA Journal Vol. 11, No. 1

Forum Posts

WAC Corrections by Alex Szabo, CCC, April 12, 2001
WAC 230 and Alexander Szabo's refutation revisted by Dann Corbit, CCC, August 01, 2005
WAC.230 revisited yet again by Dann Corbit, CCC, July 11, 2009
Stockfish 1.8 demolishes WAC.230 by Dann Corbit, CCC, August 02, 2010

External Links

References

^ Alexander Szabo of Alexander And Barbara A Szabo - San Antonio, NM 87832
^ Alexander Szabo (1984). Computer-Chess Tactics and Strategy. M.Sc. Thesis, University of British Columbia
^ Gregg Pearlman (1986). ST New Products. Antic Vol. 5, No. 8
^ TechMate Chess for Atari ST - The Video Games Museum
^ Christopher Chabris (1987). Reviews: The Game of Kings - START's First Chess Tournament. STart Vol. 2, No. 2
^ Alexander Szabo, Barbara Szabo (1988). The Technology Curve Revisited. ICCA Journal, Vol. 11, No. 1
^ Ernst A. Heinz (2000). A New Self-Play Experiment in Computer Chess. Massachusetts Institute of Technology, Laboratory of Computer Science, Technical Memo No. 608, zipped ps, pdf
^ Hans Kmoch vs Aron Nimzowitsch (1927) from chessgames.com
^ Bad Niendorf 1927 - 365Chess.com Tournaments
^ WAC Corrections by Alex Szabo, CCC, April 12, 2001
^ Stockfish 1.8 demolishes WAC.230 by Dann Corbit, CCC, August 02, 2010
^ ICGA Reference Database (pdf)

What links here?

Page	Date Edited
Alexander Szabo	Nov 10, 2012
Atari ST	Dec 7, 2016
Barbara Szabo	Nov 10, 2012
Depth	Feb 25, 2018
Engines	Mar 10, 2018
ICGA Journal	Dec 21, 2017
People	Feb 28, 2018
Playing Strength	Mar 31, 2018
Strategy	Jan 18, 2018
Szabo Software	May 3, 2013
Tactics	Jan 12, 2018
Tech	Apr 20, 2018
TechMate	Aug 23, 2014
Win at Chess	Sep 25, 2017

Up one level

Alexandre Linhares

GerdIsenberg — Sat, 10 Nov 2012 20:07:46 GMT

Home * People * Alexandre Linhares

		Alexandre Linhares, a Brazilian computer scientist, research professor of public and business administration at Escola Brasileira de Administração Pública e de Empresas, Fundação Getúlio Vargas (FGV), Rio de Janeiro ^[1] , and currently director-general of the Brazilian Chapter of the Club of Rome. His research interests include cognition in chess, where he is a critique of Chase and Simon's heavily quoted work Perception in chess ^[2] , controversial debated by Fernand Gobet et al. ^[3] ^[4] .
Alexandre Linhares ^[5]

The Nature of Chunks

See also

Selected Publications

External Links

References

What links here?

The Nature of Chunks

The debate is about the nature of chess chunks. One possibility states that chunks are built by encoding particular combinations of pieces-on-squares (POSs), and that chunks are formed mostly by “close” pieces (in a “Euclidean” sense). A complementary hypothesis, as proposed by Alexandre Linhares and Paulo Brum ^[6] , is that chunks are encoded by abstract, semantic information such as given in following positions, the Fool's mate and its “most economical” representation, as given by Jenő Bán ^[7] :


rnb1kbnr/pppp1ppp/8/4p3/6Pq/5P2/PPPPP2P /RNBQKBNR w KQkq -		8/8/8/8/8/6b1/2k1P3/4KB2 w - -

Selected Publications

^[8]

Alexandre Linhares (2005). An Active Symbols Theory of Chess Intuition. Minds and Machines, Vol. 15, No. 2
Alexandre Linhares, Paulo Brum (2007). Understanding our understanding of strategic scenarios: What role do chunks play. Cognitive Science, 31, 989-1007. pdf
Merim Bilalić, Fernand Gobet (2007). They do what they are told to do: The influence of instruction on (chess) expert perception - Commentary on Linhares and Brum (2007). Cognitive Science. pdf
Alexandre Linhares, Paulo Brum (2009). How Can Experts See the Invisible? Reply to Bilalic and Gobet. Cognitive Science, Vol 33, No. 5
Alexandre Linhares, Anna Elizabeth T. A. Freitas (2010). Questioning Chase and Simon's (1973) “Perception in chess”: The “experience recognition” hypothesis. New Ideas in Psychology, Vol. 28, No. 1
Peter Lane, Fernand Gobet (2011). Perception in chess and beyond: Commentary on Linhares and Freitas (2010). New Ideas in Psychology, Vol. 29, No. 2
Neil Charness (2012). Patterns of theorizing about chess skill - Commentary on Linhares and Freitas (2010) and Lane and Gobet (2011). New Ideas in Psychology, Vol. 30, No. 3
Alexandre Linhares, Anna Elizabeth T. A. Freitas, Alexandre Mendes, Jarbas S. Silva (2012). Entanglement of perception and reasoning in the combinatorial game of chess: Differential errors of strategic reconstruction. Cognitive Systems Research, Vol. 13, No 1, 72-86

External Links

References

^ linhares - www
^ William Chase, Herbert Simon (1973). Perception in chess. Cognitive Psychology, Vol. 4, No. 1, pdf
^ The Human Intuition Project: Chase and Simon (1973) Perception in chess, Cognitive Psychology 4:55-81. A scientific blunder by Alexandre Linhares, October 01, 2007
^ Peter Lane, Fernand Gobet (2011). Perception in chess and beyond: Commentary on Linhares and Freitas (2010). New Ideas in Psychology, Vol. 29, No. 2
^ Associate Member | THE CLUB OF ROME
^ Alexandre Linhares, Paulo Brum (2007). Understanding our understanding of strategic scenarios: What role do chunks play. Cognitive Science, Vol. 31, 989-1007. pdf
^ Jenő Bán (1997). The tactics of endgames. Dover Publications, ISBN-13: 978-0486297057, amazon.com
^ DBLP: Alexandre Linhares

What links here?

Page	Date Edited
Alexandre Linhares	Nov 10, 2012
Anna Elizabeth T. A. Freitas	Nov 7, 2012
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Fernand Gobet	May 11, 2017
Herbert Simon	Feb 11, 2016
Merim Bilalić	Oct 2, 2014
Neil Charness	Oct 2, 2014
Paulo Brum	Nov 7, 2012
People	Feb 28, 2018
Peter Lane	Jan 1, 2016
William Chase	Jan 21, 2016

Up one level

Backward Pawns (Bitboards)

GerdIsenberg — Fri, 05 May 2017 10:28:18 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Backward Pawns

Stops with negative SEE

Kmoch's definition of a backward pawn or straggler: A half-free pawn on the second or third rank whose stop square lacks pawn protection but is controlled by a sentry. The definition of a backward pawn seems a bit ambiguous. May an isolated pawn also be a backward one? Or an pawn on a closed file? What about a backward ram or faked candidates or even levers?

Backward

We may use a more general definition of backwardness, to consider certain subsets independently. All pawns, which stop is not member of own front-attackspans but controlled by a sentry are backward:

U64 wBackward(U64 wpawns, U64 bpawns) {
   U64 stops = wpawns << 8;
   U64 wAttackSpans = wEastAttackFrontSpans(wpawns)
                    | wWestAttackFrontSpans(wpawns);
   U64 bAttacks     = bPawnEastAttacks(bpawns)
                    | bPawnWestAttacks(bpawns);
   return (stops & bAttacks & ~wAttackSpans) >> 8;
}

Straggler

Stragglers are the intersection of backward with open pawns and the second or third rank:

U64 wStraggler(U64 wpawns, U64 bpawns) {
   return wBackward (wpawns, bpawns)
        & wOpenPawns(wpawns, bpawns)
        & 0xffff00; // rank 2,3
}

In the strict sense, we still need to exclude levers. On the other hand, levers are subject of quiescence search anyway.

Telestop Weakness

As pointed out by Sam Hamilton ^[1] considering stop squares might be insufficient for pawns which may actually push, but have a permanent weakened telestop, f.i.:

8/5p2/6p1/p1p3P1/P1P5/7P/1P6/8 w - -

On the other hand, such a backward prospective pawn has a vital tempo, which is often decisive in certain pawn endings, so one should be careful to don't make the penalty too worse. Anyway, one may either apply the above wBackward algorithm with so far movable pawns shifted one rank up, or alternatively determine a backward square area, which is the black attack span of all black attacks which are outside the white front attack spans:

white pawns         black pawns
. . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . . . . 1 .
. . . . . . 1 .     1 . 1 . . . . .
1 . 1 . . . . .     . . . . . . . .
. . . . . . . 1     . . . . . . . .
. 1 . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .
 
~white front     &  black attacks    -> stop squares
attackspans                             dominated by black 
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . 1 . 1 .     . . . . 1 . . .
. . . . 1 1 . 1     . . . . . 1 . 1     . . . . . 1 . 1
. 1 . 1 1 1 . 1  &  . 1 . 1 . . . .     . 1 . 1 . . . .
. 1 . 1 1 1 1 1     . . . . . . . .     . . . . . . . .
1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .
1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .
stop squares
dominated by black
filled down
-> white         &  white pawns      -> backward pawns
backward area
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . . 1 1 . 1     . . . . . . 1 .     . . . . . . . .
. 1 . 1 1 1 . 1  &  1 . 1 . . . . .     . . . . . . . .
. 1 . 1 1 1 . 1     . . . . . . . 1     . . . . . . . 1
. 1 . 1 1 1 . 1     . 1 . . . . . .     . 1 . . . . . .
. 1 . 1 1 1 . 1     . . . . . . . .     . . . . . . . .

Dynamic Backwardness

A further Pass

Another issue is that some pawns or their stop squares are statically member of their own attack spans, but those spans could not be realized, since their pawns are either backward or rammed (or both). Those pawns (f.i. white pawn c4, and mutually black pawn a4 in the diagram) may determined in a second pass, only considering attack spans of movable pawns.

8/8/1p6/8/p1P1p3/3pP3/1P1P4/8 w - -

Stops with negative SEE

A more sophisticated definition of backwardness was given by Vincent Diepeveen ^[2], even a member of a pawn duo may be backward, if its stop square has a negative SEE score, also considering pieces. Here b7 is considered backward, no matter whether the other friendly pawn is on c7 or c6, since it's stop square b6 has a negative SEE in both cases.

8/1pp5/8/2P5/8/8/8/1R6 w - -

Publications

Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6

Forum Posts

WHAT is the definition of a backward pawn? by Bas Hamstra, CCC, December 23, 2002
Backward Pawns by Mark Lefler, CCC, March 24, 2008
Doubled and Backward Pawn Engine "Definitions" by Brian Richardson, CCC, September 07, 2009
What is a backward pawn? by Lyudmil Tsvetkov, CCC, May 12, 2014

External Links

Backward pawn from Wikipedia

References

^ Re: Doubled and Backward Pawn Engine "Definitions" by Sam Hamilton, CCC, September 13, 2009
^ Re: WHAT is the definition of a backward pawn? by Vincent Diepeveen, CCC, December 24, 2002

What links here?

Page	Date Edited
Backward Pawn	May 5, 2017
Backward Pawns (Bitboards)	May 5, 2017
Bas Hamstra	Feb 4, 2018
Dartmouth CP	Jan 19, 2018
Design Principles	Jan 17, 2018
Hans Kmoch	Nov 11, 2017
Lyudmil Tsvetkov	Mar 28, 2018
Murka	Nov 11, 2016
Open Pawns (Bitboards)	Aug 24, 2017
Pawn Attacks (Bitboards)	Mar 4, 2010
Pawn chain	Jan 17, 2018
Pawn Pattern and Properties	Nov 11, 2017
PawnKing	Sep 5, 2014
Weak Pawns	Dec 19, 2013

Up one Level

Behting Study

GerdIsenberg — Sun, 01 Feb 2015 16:11:23 GMT

Forum Posts

External Links

What links here?

Home * Engine Testing * Test-Positions * Behting Study

The famous Behting study, first published in the magazine Bohemia in 1906.

Behting Study 1.Kc6! draws

8/8/7p/3KNN1k/2p4p/8/3P2p1/8 w - -

Forum Posts

Behting position by Enrique Irazoqui, CCC, August 30, 1998
Stockfish 6 is impressive in Behting study by Jouni Uski, CCC, January 31, 2015 » Stockfish

External Links

Christmas Puzzles 2005 Behting study from ChessBase
C. Behting Lösungen (c) 2006 Siegfried Hornecker, German
Can we still deceive computers in chess? by Kiyoshi Takahashi, ChessBase News, July 17, 2012
The Behting study – solution and a search for cooks, ChessBase News, August 7, 2012
'The Behting study is sound' by John Nunn, ChessBase News, October 05, 2012

What links here?

Page	Date Edited
Behting Study	Feb 1, 2015
Chess Problems, Compositions and Studies	Feb 19, 2018
John Nunn	Dec 9, 2017
Patzer	Apr 5, 2017
Stockfish	Apr 7, 2018
Test-Positions	Feb 25, 2018

Up one level

Bill Gosper

GerdIsenberg — Wed, 20 Aug 2014 13:59:38 GMT

Home * People * Bill Gosper

		Ralph William (Bill) Gosper, Jr., an American mathematician and computer scientist, along with Richard Greenblatt considered the co-founder of the hacker community ^[1] . In the 60s, affiliated with MIT, he worked for Project MAC (Machine-Aided Cognition), where his contributions to computational mathematics and Bit-Twiddling include HAKMEM and Maclisp. He helped Greenblatt with his chess program Mac Hack VI, and operated the PDP-6 when Robert Q played its first tournament game versus Carl Wagner. In the 70s, Bill Gosper moved to Stanford University for some years, where he lectured and helped Donald Knuth to write volume II of The Art of Computer Programming. He has worked at or consulted for Xerox PARC, Symbolics, Wolfram Research, the Lawrence Livermore National Laboratory, and Macsyma ^[2]. Bill Gosper created numerous packing problem puzzles such as the Twubblesome Twelve ^[3], and was interested in the Conway's Game of Life, where he found the Glider Gun and originated the Hashlife algorithm to speed up the computation of Life patterns ^[4].
Bill Gosper 2006 ^[5]

Selected Publications

External Links

References

What links here?

Robert Q

Allen Moulton and R. William Gosper operating "Robert Q" on a PDP-6 ^[6] ^[7]

HAKMEM

HAKMEM, alternatively known as AI Memo 239, is a February 1972 "memo" (technical report) of the MIT AI Lab by Gosper et al. that describes a wide variety of hacks, primarily useful and clever algorithms ^[8], and even a chess position ^[9] ^[10]. A few samples, referred elsewhere:

HAKMEM 70

HAKMEM 70 ^[11], A neat chess problem, swiped from Chess for Fun and Chess for Blood, by Edward Lasker ^[12]. White mates in three moves:

5B2/6P1/1p6/8/1N6/kP6/2K5/8 w - -

HAKMEM 169

HAKMEM 169, to count the ones in a PDP-6/PDP-10 36-bit word, written in Assembly ^[13] ^[14]:

   LDB   B,[014300,,A]     ;or MOVE B,A then LSH B,-1
   AND   B,[333333,,333333]
   SUB   A,B
   LSH   B,-1
   AND   B,[333333,,333333]
   SUBB  A,B               ;each octal digit is replaced by number of 1's in it
   LSH   B,-3
   ADD   A,B
   AND   A,[070707,,070707]
   IDIVI A,77              ;casting out 63.'s

HAKMEM 175

HAKMEM 175 - next higher number with the same number of one bits (Snoob), by Bill Gosper, PDP-6 Assembly ^[15]:

   MOVE  B,A
   MOVN  C,B
   AND   C,B
   ADD   A,C
   MOVE  D,A
   XOR   D,B
   LSH   D,-2
   IDIVM D,C
   IOR   A,C

Gosper's Glider Gun

Gosper's Glider Gun in action — a variation of Conway's Game of Life ^[16]

Selected Publications

Michael Beeler, Bill Gosper, Rich Schroeppel (1972). HAKMEM, Memo 239, Artificial Intelligence Laboratory, Massachusetts Institute of Technology ^[17]
Bill Gosper (1977). Decision procedure for indefinite hypergeometric summation. Proc. Natl. Acad. Sci. USA, Vol. 75, No. 1, pdf ^[18]

External Links

References

^ Hackers: Heroes of the Computer Revolution
^ Bill Gosper from Wikipedia
^ Twubblesome Twelve - a difficult puzzle by Bill Gosper
^ Gosper's Algorithm (Hashlife) explained
^ Mathematician Bill Gosper in March, 2006 at the Seventh Gathering for Gardner (G4G7) in Atlanta, Georgia, 16 March 2006, Photographer Thane Plambeck
^ MIT Computer Loses to Human in Chess. Sun Journal (Lewiston), January 23, 1967, Google News
^ AP :: Images :: Search Results :: Carl Wagner, 1967, MIT Chess
^ HAKMEM from Wikipedia
^ Michael Beeler, Bill Gosper, Rich Schroeppel (1972). HAKMEM, Memo 239, Artificial Intelligence Laboratory, Massachusetts Institute of Technology
^ HAKMEMC -- HAKMEM Programming hacks in C by Alan Mycroft
^ HAKMEM - GAMES: ITEM 70
^ Edward Lasker (1942,1962) Chess for Fun and Chess for Blood. Dover Publications; 2 edition, ISBN-13: 978-0486201467, amazon
^ HAKMEM 169 by Gosper, Mann, Lenard, [Root and Mann], HAKMEM
^ PDP-10 Machine Language
^ HAKMEM 175 by Bill Gosper
^ Bill Gosper's Glider Gun in action — a variation of Conway's Game of Life. This image was made by using Life32 v2.15 beta by Johan G. Bontes, 2005, Gun (cellular automaton) from Wikipedia
^ Web-available by Henry Baker
^ Gosper's algorithm from Wikipedia

What links here?

Page	Date Edited
Alan Baisley	Jan 7, 2016
Assembly	Sep 3, 2017
Bill Gosper	Aug 20, 2014
Bit-Twiddling	Nov 6, 2017
Hash Table	Jan 1, 2018
Lawrence Livermore National Laboratory	Feb 7, 2017
Mac Hack	Apr 20, 2018
Massachusetts Institute of Technology	Jan 24, 2017
PDP-10	Apr 20, 2018
PDP-6	Jan 19, 2018
People	Feb 28, 2018
Population Count	Sep 3, 2017
Promotions	Jun 6, 2017
Richard Greenblatt	Jan 19, 2016
Stanford University	Dec 7, 2017
Test-Positions	Feb 25, 2018
Traversing Subsets of a Set	Oct 14, 2016
WCCC 1992	Feb 26, 2018

Up one level

Blockage Detection

GerdIsenberg — Thu, 19 Oct 2017 11:34:20 GMT

Home * Evaluation * Game Phases * Endgame * Pawn Endgame * Blockage Detection

4k3/8/3pPp2/1p1P1P1p/1P5P/5P2/3K4/8 w - -

Blockage Detection,
a pattern recognition technique to statically discover rammed positions in pawn endgames, and permanently prevented kings from penetrating into opponent's camp. In those positions material advantage is not sufficient to win such games, otherwise only recognizably by a very deep search, when a draw by fifty-move rule rises the horizon. Best not only applied in leaf node evaluation, but as interior node recognizer within the search, a detected blockade either prunes forward or narrows the search window.

Search Application

Ram Fence

Blockage with Dynamic Pawns

Search Application

Blockage detection is only applied for the side with advantage, proving its upper bound is a draw score ^[1]:

int search(int alpha, int beta, ...) {
  ...
  /* blockade detection */
  if ( beta > DRAW_SCORE ) {
    if ( blockage() ) {
      if ( alpha >= DRAW_SCORE )
        return DRAW_SCORE;
      beta = DRAW_SCORE; 
    }    
  }
  /* continue regular search */
}

Ram Fence

Following sample assumes White the "winning" side to move

The blockage requires a fence consisting of own fixed pawns and opponent pawn attacks, to divide the board into two disconnected regions. There are various algorithms to deal with fence detection, and fixed and dynamic pawns, following fill based proposal deals with bitboards and should only take none lever pawns into account to prove the fence is impenetrable. First cheap condition is the presence of at least three rams. Further own pawns blocked by own rams are included successively into the fence set, and finally opponent pawn attacks. The precondition, the defending king has at least one vacant square to avoid zugzwang issues, is omitted.

A king flood starts at its base rank (1st rank for White) over the board (ignoring black passers on the 2rd rank), or all bits below the fence' least significant one bit, the potential fence as flood stopping obstruction. If, after a few cycles, the flood reaches the above area, the fence is penetrable, and the blockage test failed. Each time, the king flood drowns (undefended) opponent pawns, the ram-fence is re-calculated with the drown pawns "captured". If the flood does not grow anymore, the fence is detected.

see One Step, Population Count and BitScan

bool forms_fence4white(U64 wPawns, U64 bPawns, U64 &fence, U64 &flood) {
  fence = wPawns & soutOne( bPawns ); 
  if (popCount( fence ) < 3)
    return false;
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= bPawnAttacks( bPawns );
  flood = RANK1BB | allBitsBelow[BitScanForward( fence )];
  U64 above = allBitsAbove[BitScanReverse( fence )];
  while ( true ) {
    U64 temp = flood;
    flood |= eastOne( flood ) | westOne( flood ); /* Set all 8 neighbors */
    flood |= soutOne( flood ) | nortOne( flood );
    flood &= ~fence;
    if (flood == temp) 
      break; /* Fill has stopped, blockage? */
    if (flood & above) /* break through? */
      return false; /* yes, no blockage */
    if (flood & bPawns) {
      bPawns &= ~flood;  /* "capture" undefended black pawns */
      fence = wPawns & soutOne( bPawns ); 
      if (popCount( fence ) < 3)
        return false;
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= bPawnAttacks( bPawns );
    }
  } 
  return true;
}

In order to ensure that White cannot penetrate the fence, the white kings must reside in the below flood set, and the defending, black king outside the below set. If all pawns of the "winning" side are rammed without any lever, the most obvious case of a blockage is recognized.

. . . k . . . .         a a a a a a a a
. . . . . . . .  above  a a a a a a a a
. . . . . . . .         a a a a a a a a
. b . . b . . b         a a a a a a a a
. w . . w . . w  fence  F_F_F_F_F_F_F_F
. w . . . . . .         b f b b b b b b
. . . K . . . .  below  b b b b b b b b
. . . . . . . .  flood  b b b b b b b b

Blockage with Dynamic Pawns

Otherwise, one has to consider dynamic pawns of the "winning" side, able to push forward or to capture, in particular above the fence, as member of the fence (levers) and below the fence (from White's point of view). For instance, one (protected) passed pawn, with the defending king on its front span, is not sufficient to break the blockage. Similar holds for pawns below the fence not able to lever, and becoming rammed if moving forward, or with some care, most backward pawns.

. . . . k . . .         a a a a a a a a
. . . . . . . .  above  a a a a a a a a
. . . b w b . .         a a a a a a a a
. b . w . w . b         a a F_F_F_F_F a
. w . . . . . w  fence  F_F_F b b b F_F
. . . . . w . .         b b b b b b b b
. . . K . . . .  below  b b b b b b b b
. . . . . . . .  flood  b b b b b b b b

More complicated cases for a successful blockage detection also with levers involved are elaborated in Omid David's et al. 2004 ICGA Journal paper ^[2], also published as code of Chiron by Ubaldo Andrea Farina in CCC ^[3].

Publications

Peter W. Frey, Larry Atkin (1979). Creating a Chess-Player, Part 4: Thoughts on Strategy. In Blaise W. Liffick (ed.), The Byte Book of Pascal, pp. 143-155. Byte Publications, also BYTE, Vol. 4, No. 1
Omid David, Ariel Felner, Nathan S. Netanyahu (2004). Blockage Detection in Pawn Endings. CG 2004, pdf
Omid David, Ariel Felner, Nathan S. Netanyahu (2004). Blockage Detection in Pawn Endgames. ICGA Journal, Vol. 27, No. 3

Forum Posts

Endgame Blockage Positions by Omid David, CCC, December 06, 2002
Jeremiah's Wall Detection by Renze Steenhuisen, CCC, April 28, 2005
Code of Chiron for Detection of Pawn Blockages by Ubaldo Andrea Farina, CCC, October 13, 2011
To users of Chiron by Richard Vida, CCC, January 02, 2012
Details about Critter 1.4a. by Jesús Muñoz, CCC, February 10, 2012 » Critter

References

^ Code snippet from Omid David, Ariel Felner, Nathan S. Netanyahu (2004). Blockage Detection in Pawn Endings. CG 2004, pdf
^ Omid David, Ariel Felner, Nathan S. Netanyahu (2004). Blockage Detection in Pawn Endgames. ICGA Journal, Vol. 27, No. 3
^ Code of Chiron for Detection of Pawn Blockages by Ubaldo Andrea Farina, CCC, October 13, 2011

What links here?

Page	Date Edited
BlackMamba	Nov 26, 2016
Blockade	Oct 19, 2017
Blockade of Stop	Oct 11, 2016
Blockage Detection	Oct 19, 2017
Chiron	Sep 24, 2017
Critter	Jan 25, 2014
Draw	Apr 14, 2018
Draw Evaluation	Mar 12, 2018
Endgame	Sep 18, 2017
Falcon	Sep 2, 2016
Fortress	Feb 1, 2018
Hossa	Jan 7, 2016
Interior Node Recognizer	Mar 12, 2018
Jan Renze Steenhuisen	Sep 10, 2017
Mate Search	Oct 22, 2016
Pawn Endgame	Oct 11, 2017
Pawn Rams (Bitboards)	Nov 11, 2017
Pawn Structure	Oct 2, 2017
Vajolet	Jan 25, 2018

Up one level

Candidate Passed Pawn

GerdIsenberg — Sat, 11 Nov 2017 09:32:23 GMT

Home * Evaluation * Pawn Structure * Candidate Passed Pawn

		Candidate passed pawn, a pawn on a half-open file, which, if the board had only pawns on it, would eventually become a passed pawn by moving forward. Whereas this definition is obvious for a human, in a form presented above it would require no less than a separate recursive search routine. For that reason, computers have to use approximations of that rule. One possibility is to define a pawn as a candidate, if no square on its path is controlled by more enemy pawns than own pawns. However, this simple heuristics rules out an early recognition of a candidate passed pawns. For example with white pawns on a4 and b5 and black pawn on a7, the b5 pawn would be viewed as a candidate passer only after a4-a5.
White and Black candidates (b5, g5)

Forum Posts

How to define a candidate passer by Jan Willem de Kort, CCC, January 03, 2006
Outside passer and candidate passer: definition wanted! :-) by Alessandro Scotti, CCC, February 27, 2006
Improving evaluation of passed pawns by Ben-Hur Carlos Vieira Langoni Junior, CCC, January 22, 2011 » Passed Pawn

External Links

References

^ Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6

What links here?

Page	Date Edited
More Links
Alessandro Scotti	Feb 27, 2014
Ben-Hur Carlos Vieira Langoni Junior	Dec 17, 2013
Bismark	Apr 22, 2015
Candidate Passed Pawn	Nov 11, 2017
Candidates (Bitboards)	Nov 11, 2017
Chexa	Feb 18, 2014
Clarabit	Nov 3, 2011
Coiled	Mar 12, 2017
Dartmouth CP	Jan 19, 2018
Dictionary	Aug 24, 2017
Doubled Pawn	Mar 27, 2017
Faker	Nov 11, 2017
Garbochess	Sep 23, 2017
Hans Kmoch	Nov 11, 2017
Hidden Passed Pawn	Nov 11, 2017
ISA	Apr 2, 2018
Nebula	Feb 7, 2015
Open Pawns (Bitboards)	Aug 24, 2017
Outside passed pawn	Jun 7, 2012
Passed Pawn	Oct 11, 2017

Up one Level

CHAOS

GerdIsenberg — Thu, 28 Dec 2017 08:49:00 GMT

Home * Engines * CHAOS

		CHAOS was one of the leading programs since it first appeared at ACM 1973 until the mid 80s. CHAOS, which stands facetiously for Chess Heuristics And Other Stuff, has participated in twelve ACM tournaments ^[1] and four world championships ^[2] , runner up in 1974 behind Kaissa, defeating favorite Chess 4.0. In 1980 at the 3rd WCCC, CHAOS was close to becoming champion but lost the playoff against Belle. Its last tournament was the 16th AMC 1985 when it lost two games in a very strong field.
Boldriaan - CHAOS (2006) ^[3]

Duel on the Chessboard

History

CHAOS started in the late 1960s at RCA Systems Programming division in Cinnaminson, NJ with Ira Ruben, Fred Swartz, Victor Berman, Joe Winograd, and William Toikka as first authors. In January 1972, Sperry Univac (1986 Unisys) officially took over the RCA Computer Systems Division and eventually moved everything to Blue Bell, Pennsylvania. Later the program has been affiliated with the Computing Center of the University of Michigan where most of its programmers were staff members ^[4] .

Knowledge vs Search

CHAOS was written in Fortran and required in excess of 3,000,000 words of memory to execute, using most of it for storing the tree. It examines only about 50 nodes/sec (1985 70 nodes/sec ^[5] ) or about 10,000 per move. The reason why CHAOS evaluated so slowly — their programmers did a better job of evaluation! Because every minimax decision is made based on a single evaluation, it seemed plausible that the more accurate this number is, the better the quality of tree searching. However, that comes at the cost of missing deep combinations from brute force search, but CHAOS's strength/nodes-evaluated ratio was impressive. The program carried out a selective search with iterative widening, a bit different from the others. Its book contains about 10,000 lines.

Quotes

Alex Bell

Alex Bell on the CHAOS - Chess 4.0 game 1974 ^[6] :

CHAOS played 16 NxP!! - a move which has been acclaimed as the finest ever made by a computer. White evaluates that his domination of open lines is compensation for a piece. This judgement is absolutely correct. Of course the piece is not sacrificed entirely and play continues in a very similar fashion to MASTER's sacrifice of a bishop to TELL.

rq2k2r/3n1ppp/p2bpnb1/8/Np1N4/1B3PP1/PP2Q2P/R1BR2K1 w kq - 1 16

Duel on the Chessboard

Quote from Computer vs. computer: Duel on the Chessboard ^[7] on ACM 1979:

The biggest and most powerful computers do that very well. In one second, they can examine thousands of possible moves. The problem is, they stop to consider lousy moves that a human player wouldn't waste a fraction of a second on. On the other side of the fence are the slower but "smarter" computer programs. They can't think about zillions of chess moves, so they need a lot of information about chess plugged into them. CHAOS is one of these latter, pumped with chess information from John J. O’Keefe, one of Michigan's top players.

Authors

1973 ^[8]	1976 ^[9]	1978 ^[10]	1983 ^[11]
	Mike Alexander	Mike Alexander	Mike Alexander
Victor Berman	Victor Berman	Victor Berman	Victor Berman
			Mark Hersey
		Tom McBride
			Jack O’Keefe
Ira Ruben	Ira Ruben
Fred Swartz	Fred Swartz	Fred Swartz	Fred Swartz
William Toikka	William Toikka	William Toikka
Joe Winograd	Joe Winograd	Joe Winograd

Photos & Games

CHAOS Team

CHAOS Team circa 1972 with UNIVAC 1108 Computer in Cinnaminson, NJ
From left, Fred Swartz (rear), Vic Berman (front), Bill Toikka, Ira Ruben (seated), Joe Winograd ^[12]

WCCC 1974

Slate, Swartz, and Berman in CHAOS vs Chess 4.0, WCCC 1974 ^[13] ^[14]

[Event "WCCC 1974"]
[Site "Stockholm, Sweden"]
[Date "1974.08.06"]
[Round "2"]
[White "Chaos"]
[Black "Chess 4.0"]
[Result "1-0"]
 
1.d4 d5 2.c4 dxc4 3.Nf3 Nf6 4.e3 e6 5.Bxc4 c5 6.Qe2 a6 7.O-O b5 8.Bb3 Bb7
9.Rd1 Nbd7 10.Nc3 Bd6 11.e4 cxd4 12.Nxd4 Qb8 13.g3 b4 14.Na4 Bxe4 15.f3 Bg6
16.Nxe6 fxe6 17.Qxe6+ Be7 18.Re1 Qd8 19.Bf4 Kf8 20.Rad1 Ra7 21.Rc1 Ng8 22.Rcd1
a5 23.Bd6 Bxd6 24.Qxd6+ Ne7 25.Nc5 Bf5 26.g4 Qe8 27.Ba4 b3 28.gxf5 bxa2 29.Bxd7
a1=Q 30.Rxa1 Ra6 31.Nxa6 Qd8 32.Kf2 Kf7 33.Qe6+ Kf8 34.Qxe7+ Qxe7 35.Rxe7 Kxe7
36.Nc5 Rb8 37.Rxa5 Rxb2+ 38.Kg3 g6 39.fxg6 hxg6 40.Ra6 Rc2 41.Re6+ Kf8 42.Re5 Rc1
43.Rg5 Kf7 44.Be6+ Kf6 45.h4 Rxc5 46.Rxc5 Kxe6 47.Rg5 Kf6 48.Kg4 Kf7 49.Rc5 Ke6
50.Kg5 Kd6 51.Ra5 Kc6 52.f4 Kb6 53.Ra1 Kc5 54.Rd1 Kb4 55.Kxg6 Kc3 56.Rd8 Kb4
57.Rc8 Kb5 58.h5 Kb6 59.Rc1 Kb5 60.h6 Ka4 61.Rb1 Ka3 62.f5 Ka2 63.Rb8 Ka3 64.f6
Ka4 65.Rb7 Ka5 66.Rb8 Ka4 67.Rb1 Ka3 68.Rb7 Ka4 69.Rb8 Ka5 70.Kg7 Ka4 71.Rb7 Ka5
72.Rb2 Ka4 73.Rb8 Ka5 74.Kg8 Ka4 75.h7 Ka5 76.h8=Q Ka4 77.Qh4+ Ka5 78.Qb4+ Ka6
79.Qa4# 1-0

WCCC 1980

Belle vs CHAOS, WCCC 1980, Thompson, Friedel, Berman ^[15] , Swartz, Donskoy ^[16] ^[17]

[Event "WCCC 1980"]
[Site "Linz, Austria"]
[Date "1980.09.29"]
[Round "5 (playoff)"]
[White "Belle"]
[Black "Chaos"]
[Result "1-0"]
 
1.e4 Nf6 2.e5 Nd5 3.d4 d6 4.Nf3 dxe5 5.Nxe5 g6 6.g3 Bf5 7.c4 Nb4 8.Qa4+ N4c6
9.d5 Bc2 10.Qb5 Qd6 11.Nxc6 Nxc6 12.Nc3 Bg7 13.Qxb7 O-O 14.Qxc6 Qb4 15.Kd2 Be4
16.Rg1 Rfb8 17.Bh3 Bh6+ 18.f4 Qa5 19.Re1 f5 20.Qe6+ Kf8 21.b3 Bg7 22.Bb2 Bd4
23.g4 Rb6 24.Qd7 Rd6 25.Qa4 Qb6 26.Ba3 Bxc3+ 27.Kxc3 Rdd8 28.Rad1 Qf2 29.gxf5
Qc2+ 30.Kd4 gxf5 31.Qc6 Qf2+ 32.Ke5 Kg8 33.Rg1+ Kh8 34.Bxe7 Qb2+ 35.Rd4 Qg2
36.Qf6+ Kg8 37.Bxg2 Rxd5+ 38.Ke6 h6 39.Qxh6 Re5+ 40.fxe5 Rf8 41.Bf3# 1-0

Forum Posts

Old programs CHAOS and USC by Eugene Piercy, CCC, July 11, 2015

External Links

Chess Program

Misc

Chaos in a Miniature by Edward Winter
Chaos (cosmogony) from Wikipedia
Chaos theory from Wikipedia
Sun Ra - Cosmic Chaos, from The Heliocentric Worlds of Sun Ra, Vol. 2 (1965), YouTube Video

References

^ North American Computer-Chess Championships, complete History of Tournament Results and Games, prepared by Theo van der Storm, Nov. 23rd, 2002, secretary of the CSVN
^ Chaos' ICGA Tournaments
^ Schaakkunst van Boldriaan
^ The Eleventh ACM's North American Computer Chess Championship as pdf reprint from The Computer History Museum
^ David .E. Welsh (1986). ACM's Sixteenth North American Computer Chess Championship. ICCA Journal, Vol. 8, No. 4.
^ Alex Bell (1978). MASTER at IFIPS. from Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL), excerpt from A. G. Bell (1978). The Machine Plays Chess. Pergamon Press, ISBN-13: 978-0080212227, from amazon
^ Computer vs. computer: Duel on the Chessboard, Boca Raton News - November 27. 1979 from Google News on ACM 1979
^ Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. Chapter IX. The Fourth United States Computer Chess Championship » ACM 1973
^ pp. 52, Table I. History of the ACM Tournaments from
Ben Mittman, Monroe Newborn (1980). Computer chess at ACM 79: the tournament and the man vs. man and machine match. Communications of the ACM, Vol. 23, Issue 1, pdf from The Computer History Museum » ACM 1976
^ David Levy (1978). ACM '78. ICCA Newsletter, Vol. 1, No. 1 » ACM 1978
^ Chaos' ICGA Tournaments
^ Photo courtesy Joe Winograd
^ Photo by Monroe Newborn from The Computer History Museum
^ Stockholm 1974 - Chess - Round 2 - Game 6 (ICGA Tournaments)
^ Militärischer Wert Der Spiegel 24/1982, pdf (German)
^ Photo by Monroe Newborn from The Computer History Museum
^ Linz 1980 - Chess - Round 5 - Game 1 (ICGA Tournaments)

What links here?

Page	Date Edited
ACM 1973	Jan 19, 2018
ACM 1974	Jan 19, 2018
ACM 1975	Jan 19, 2018
ACM 1976	Dec 27, 2017
ACM 1977	Dec 22, 2017
ACM 1978	Dec 23, 2017
ACM 1979	Apr 3, 2017
ACM 1980	Dec 25, 2017
ACM 1981	Jan 19, 2018
ACM 1982	Jul 19, 2016
ACM 1984	Jul 19, 2016
ACM 1985	Jun 21, 2017
AMDAHL 470	Jul 19, 2016
Awit	Dec 22, 2017
Belle	Jan 18, 2018
Carey Bloodworth	Jul 19, 2016
CHAOS	Dec 28, 2017
Ches	Jan 3, 2018
Chess (Program)	Dec 22, 2017
Dart	Jan 19, 2018
David Cahlander	Dec 22, 2017
David Levy	Jan 3, 2017
Duchess	Dec 22, 2017
Engines	Mar 10, 2018
Evaluation Overlap	Jul 19, 2016
Fred Swartz	Jul 19, 2016
Frederic Friedel	Jan 6, 2018
Freedom	Dec 28, 2017
Ira Ruben	Jul 19, 2016
Jack O’Keefe	Jul 19, 2016
Jerusalem CC Tournament 1978	Jan 3, 2018
Joe Winograd	Jul 19, 2016
Mark Hersey	Jul 19, 2016
Mike Alexander	Jul 19, 2016
Nuchess	Apr 3, 2017
Shy	Jul 19, 2016
SPOC	Jun 21, 2017
Tom Truscott	Dec 22, 2017
Type B Strategy	Jul 19, 2016
UNIVAC 1100	Jul 21, 2016
University of Michigan	Jul 19, 2016
Victor Berman	Jul 19, 2016
WCCC 1974	Jan 19, 2018
WCCC 1977	Dec 22, 2017
WCCC 1980	Dec 25, 2017
WCCC 1983	Jan 20, 2018
William Toikka	Aug 12, 2016

Up one level

Chess Champion Super System III

GerdIsenberg — Thu, 17 Sep 2015 10:27:22 GMT

Home * Engines * Chess Champion Super System III

		Chess Champion Super System III, (Chess System III, Super System III, ChessMaster) Novag's third dedicated chess computer released in 1979, at about the time that the Novag / SciSys split took place. After the early sales period different SciSys and Novag versions of the Super System III emerged, the early Chess System III, the later SciSys ChessMaster, and the Chess Champion Super System III by Novag ^[1]. The chess computer had a 6502 CPU with a Philidor Software program written by Mike Johnson, supported by David Levy with expertise in search heuristics, also providing the opening library. The program and book was stored in 8 KiB of ROM, and used 1 KiB of RAM. It was a kind of modular system with a computer unit, and optionally, a pluggable printer and the very first LCD-chessboard.
Super System III with LCD Display ^[2]

Oversight

During the 1980 Chess Tournament in Bad Kissingen, Germany ^[3], sponsored by Horten, a German department store chain and primary German Novag distributor ^[4], Anatoly Karpov played 25 Super System IIIs in a simultaneous exhibition. In one game he was rather lucky that the program, a rook up, uncorked 32... Rfd8 overlooking mate in one, instead of Qb8 ^[5] ^[6]:

[Event "Karpov Simultaneous"]
[Site "Bad Kissingen"]
[Date "1980.01.??"]
[Round "?"]
[White "Anatoly Karpov"]
[Black "Super System III"]
[Result "1-0"]
 
1.c4 e5 2.Nc3 Nc6 3.g3 Bc5 4.Bg2 Nf6 5.Nf3 O-O 6.O-O d6 7.d3 Be6 
8.a3 a5 9.h3 Qe7 10.Rb1 Bf5 11.Bg5 Kh8 12.Nd5 Qd8 13.b4 axb4 
14.axb4 Ba7 15.Ra1 h6 16.Bxf6 gxf6 17.Qd2 Kh7 18.Nh4 Be6 19.Be4+ 
Kg7 20.g4 Nd4 21.Kh2 Nb3 22.Qb2 Nxa1 23.e3 c6 24.Nc3 d5 25.cxd5 
cxd5 26.Bg2 d4 27.Nb5 Qb6 28.Nxa7 Qxa7 29.f4 dxe3 30.fxe5 fxe5 
31.Qxe5+ Kg8 32.Ng6 Rfd8 33.Qh8# 1-0

r4rk1/qp3p2/4b1Np/4Q3/1P4P1/3Pp2P/6BK/n4R2 b - - 2 32

Publications

Novag - Chess Champion Super System III pdf by Hein Veldhuis
Schachcomputer: Markt und Müll, Der Spiegel 49/1979, December 03, 1979, (German) pdf
John F. White (1981). Survey-Chess Games. Your Computer, August/September 1981

External Links

Chess Computer

Chess Champion Super System III from Chess Computer UK by Mike Watters
Scisys and Novag : The Early Years from Chess Computer UK by Mike Watters
Novag SS 3 by Hein Veldhuis
Novag Chess Champion Super System MK III from Schachcomputer.info - Wiki (German)

Misc

References

^ Scisys and Novag : The Early Years from Chess Computer UK by Mike Watters
^ Close UP Of SSIII LCD Display | Flickr - Fotosharing by Chewbanta
^ Bad Kissingen 1980 - 365Chess.com Tournaments
^ Horten macht's möglich: Schach-Computer für 250 Mark, October 13, 1978 Computerwoche 42/1978 (German)
^ Chess Champion Super System III from Chess Computer UK by Mike Watters
^ Anatoly Karpov vs Super System III from chessgames.com

What links here?

Page	Date Edited
Chess Champion Mark IV	Dec 9, 2012
Chess Champion MK I	Jul 31, 2015
Chess Champion MK II	Jul 30, 2015
Chess Champion Super System III	Sep 17, 2015
Chess-Master	Sep 7, 2017
Chessmaster	Jan 21, 2018
Engines	Mar 10, 2018
Intelligent Chess	Apr 14, 2013
MCC 1980	Dec 27, 2017
Mike Johnson	Jan 7, 2016
Novag	Aug 19, 2015
Philidor Software	Sep 18, 2014
Saitek	Jun 11, 2016
Supra	Jul 24, 2016

Up one level

Chunker

GerdIsenberg — Wed, 13 Jul 2016 06:57:10 GMT

Home * Engines * Chunker

Chunker,
a chess program by Murray Campbell and Hans Berliner in the domain of certain pawn endgames, using chunked knowledge. Chunks were defined as groups of pawns and king that can be handled relatively independently of each other. Chunker parses a position into chunks, and reasons about the position using information obtained from chunk libraries. There are several chunk libraries, each corresponding to a fixed group of pieces (a chunk type). Each chunk type has certain properties, and each chunk instance (a particular configuration of the chunk type) has values attached to the properties. These are used both in evaluation, by allowing reasoning with chunk property values to produce an evaluation of the whole position, and in move selection, to facilitate reaching positions where this is possible.

Some types of chunks that could occur are so complex and rare that to build libraries for all possibilities would require unrealistically large memories. Fur such chunks (containing double pawns for instance) it will be necessary to do the analysis to produce properties on the fly. However, once such an analysis is done, these properties can be retained in a temporary chunk library for the duration of the solution process ^[1].

Szén Position

Due to its chunk library of king versus three connected passers, Chunker is an expert in playing the Szén position, popularized by the Hungarian chess player József Szén in the first half of the nineteenth century, with a lineage dating from Gioacchino Greco two centuries before with wK and bK on e1 and e8 respectively ^[2] ^[3] ^[4]:

4k3/5ppp/8/8/8/8/PPP5/3K4 w - -

Abstract

Using Chunking to Solve Chess Pawn Endgames ^[5]:

CHUNKER is a chess program that uses chunked knowledge to improve its performance. Its domain is a subset of king and pawn endings in chess that has been studied for over 300 years. CHUNKER has a large library of chunk instances where each chunk type has a property list and each instance has a set of values for these properties. This allows CHUNKER to reason about positions that come up in the search that would otherwise have to be handled by means of additional search. Thus the program is able to solve the most difficult problem of its present domain (a problem that would require 45 ply of search and on the order of 1013 years of CPU time to be solved by the best of present day chess programs) in 18 ply and one minute of CPU time. Further, CHUNKER is undoubtedly the world's foremost expert in its domain, and has discovered 2 mistakes in the literature and has been instrumental in discovering a new theorem about the domain that allows the assessing of positions with a new degree of ease and confidence. In this paper we show how the libraries are compiled, how CHUNKER works, and discuss our plans for extending it to play the whole domain of king and pawn endings.

Publications

Murray Campbell, Hans Berliner (1983). A Chess Program That Chunks. AAAI 1983 49-53, pdf
Hans Berliner, Murray Campbell (1984). Using Chunking to Solve Chess Pawn Endgames. Artificial Intelligence, Vol. 23, No. 1, pp. 97-120. ISSN 0004-3702
Murray Campbell (1988). Chunking as an Abstraction Mechanism. Ph.D. thesis, Carnegie Mellon University

External Links

Shallow parsing from Wikipedia
The Lounge Lizards - Voice of Chunk, on Night Music in 1988, YouTube Video
John Lurie, Evan Lurie, Roy Nathanson, Curtis Fowlkes, Marc Ribot, Dougie Bowne, Erik Sanko, E.J. Rodriguez

References

^ Murray Campbell, Hans Berliner (1983). A Chess Program That Chunks. AAAI 1983 49-53, pdf
^ Jon Speelman (1983). The Szen Position. EG73, pdf
^ At a glance you may think this is a draw. White wins by Robert Flesher, CCC, May 26, 2013
^ Now Szén position solved in 15 seconds by regular Stockfish! by Vincent Lejeune, CCC, July 12, 2016
^ Hans Berliner, Murray Campbell (1984). Using Chunking to Solve Chess Pawn Endgames. Artificial Intelligence, Vol. 23, No. 1, pp. 97-120. ISSN 0004-3702, Abstract

What links here?

Page	Date Edited
Chump	Jan 31, 2016
Chunker	Jul 12, 2016
Chunking	Jun 12, 2017
Engines	Mar 10, 2018
Hans Berliner	Jun 10, 2017
Murray Campbell	Jun 2, 2017
Pattern Recognition	Sep 8, 2017
Pawn Endgame	Oct 11, 2017
Pawn Race	Dec 16, 2017
PawnKing	Sep 5, 2014
Peasant	May 21, 2015
Test-Positions	Feb 25, 2018
Unstoppable Passer	Jun 21, 2016

Up one Level

Coko

GerdIsenberg — Tue, 14 Jul 2015 06:15:09 GMT

Home * Engines * Coko

Coko,
a chess program by Dennis Cooper and Ed Kozdrowicki which competed the first four ACM North American Computer Chess Championships, ACM 1970, ACM 1971, ACM 1972 (Coko III) and ACM 1972 (Coko IV). Coko, the Cooper-Kozdrowicki chess program was written in Fortran as a highly selective tree searcher in the spirit of a Shannon Type B program using a tree pruning system (TPS) consists of a set of commands designed for programming heuristic tree searches ^[1]. As described by Cooper in the 1971 Panel ^[2], Coko III does not use Alpha-Beta:

Although the alpha-beta procedure is a great time saving method, it is unclear at this stage of program development what the full significance of applying such a method to a tactical-strategical game tree would be. Coko III does save the chess tree with periodic pruning to allow for the addition of more branches.

Descriptions

ACM

Communications of the ACM, Vol. 16, 7 ^[3]

COKO III is a chess player written entirely in Fortran. On the IBM 360-65, COKO III plays a minimal chess game at the rate of .2 sec cpu time per move, with a level close to lower chess club play. A selective tree searching procedure controlled by tactical chess logistics allows a deployment of multiple minimal game calculations to achieve some optimal move selection. The tree searching algorithms are the heart of COKO's effectiveness, yet they are conceptually simple. In addition, an interesting phenomenon called a tree searching catastrophe has plagued COKO's entire development just as it troubles a human player. Standard exponential growth is curbed to a large extent by the definition and trimming of the Fisher set. A clear distinction between tree pruning and selective tree searching is also made. Representation of the chess environment is described along with a strategical preanalysis procedure that maps the Lasker regions. Specific chess algorithms are described which could be used as a command structure by anyone desiring to do some chess program experimentation. A comparison is made of some mysterious actions of human players and COKO III.

Man-Machine Studies

International Journal of Man-Machine Studies ^[4]

The performance capabilities of the best computer chess programs are compared with their human counterparts with emphasis being placed on machine behavior limits. A grandmaster usually spends a lifetime collecting knowledge or information about the game. Some of this knowledge is given to COKO in the form of a 12 000-line FORTRAN program. Using this knowledge COKO plays very poorly but at the super rate of approximately one move/see. The use of a brute-force selective tree-searching procedure yields an order of magnitude improvement in performance at the standard rate of 3 min/move. Perhaps three orders of magnitude additional improvement is needed to defeat the world champion, a gap which must be bridged, if ever, by programming more chess knowledge into the machine. This paper discusses the “tree-searching catastrophe” as a natural phenomenon that plagues selective tree searching for both man and machine. In addition so-called “interminimal-game communication” is considered as a natural, powerful procedure frequently used by humans to guide their selective search and as a point of emphasis for future development. It is concluded that COKO's development is just beginning, with no immediate barriers to progress, and no lack of ideas for improvement. At present COKO combines brilliant solutions to individual board position puzzles with unimaginable blunders.

Mate in one?

During the ACM 1971, Coko III offered a pawn versus Genie which, if accepted, would permit a mating sequence 17 plies deep. The pawn was taken, mate was announced, and the predicted line was followed, until ... ^[5]

8/pp6/2p2p2/6p1/1P6/2Q1P3/k1K2PPP/5B1R w - - 0 38

Apparently due to a bug, Coko III found other moves better than mate in one and threw the win ...

38. Kc1 f5 39. Kc2 f4 40. Kc1 g4 41. Kc2 f3 42. Kc1 fxg2 43. Kc2 gxh1=Q 44. Kc1 Qxf1+ 
and resigned later 0-1

Mater

According to Monroe Newborn in 1975, the chess mating combinations program Mater by George Baylor and Herbert Simon, initially written in IPL V, was ported to Fortran and incorporated into Coko ^[6] :

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.

Publications

Edward W. Kozdrowicki, John S. Licwinko, Dennis W. Cooper (1971). Algorithms for a minimal chess player: A blitz player. International Journal of Man-Machine Studies, Vol 3, 2
Edward W. Kozdrowicki, Dennis W. Cooper (1973). COKO III: the Cooper-Koz chess program, Communications of the ACM, Vol. 16, 7
Edward W. Kozdrowicki, Dennis W. Cooper (1973). COKO III and the future of inter-snap judgment communication. Proceedings of the ACM annual conference
Paul Rushton, Tony Marsland (1973). Current Chess Programs: A Summary of their Potential and Limitations. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, pdf
Edward W. Kozdrowicki, Dennis W. Cooper (1974). COKO III: The Cooper-Kozdrowicki chess program. International Journal of Man-Machine Studies Vol. 6, 6

External Links

ACM COMPUTER CHESS by Bill Wall
Classic Computer Chess - ... The programs of yesteryear by Carey, hosted by the Internet Archive ^[7]

References

^ Edward W. Kozdrowicki (1968). An adaptive tree pruning system: A language for programming heuristic treesearches. Proceedings of the 1968 23rd ACM national conference
^ Ben Mittman (1971). Computer Chess Programs (Panel). pdf from The Computer History Museum
^ Edward W. Kozdrowicki, Dennis W. Cooper (1973). COKO III: the Cooper-Koz chess program. Communications of the ACM, Vol. 16, 7
^ Edward W. Kozdrowicki, Dennis W. Cooper (1974). COKO III: The Cooper-Kozdrowicki chess program. International Journal of Man-Machine Studies Vol. 6, 6
^ George Atkinson (1998). Chess and Machine Intuition. (Intellect Ltd.) pp 63
^ Monroe Newborn (1975). Computer Chess. Academic Press, New York, N.Y. p. 26
^ Re: Old programs CHAOS and USC by Dann Corbit, CCC, July 11, 2015

What links here?

Page	Date Edited
0x88	Nov 28, 2016
ACM 1970	Jun 13, 2015
ACM 1971	Jul 19, 2016
ACM 1972	Dec 22, 2017
ACM 1973	Jan 19, 2018
Coko	Jul 13, 2015
Daly CP	Jul 13, 2015
Dennis Cooper	Aug 18, 2014
Ed Kozdrowicki	Aug 18, 2014
Engine Testing	Feb 1, 2018
Engines	Mar 10, 2018
Genie	Feb 7, 2016
IBM 360	Jan 2, 2016
J. Biit	Jan 17, 2017
Jacques Dutka	Jul 7, 2012
Keith Gorlen	May 23, 2016
Mater	Apr 26, 2016
MSU CP	Jul 19, 2016
Paul Rushton	Jan 12, 2015
SOMA	Mar 25, 2015
Steven M. Bellovin	Dec 14, 2017
Tech	Apr 20, 2018
UNIVAC 1100	Jul 21, 2016

Up one level

Color Flipping

GerdIsenberg — Wed, 17 May 2017 14:32:17 GMT

Book Transpositions

Flipping an 8x8 Board

Home * Chess * Position * Color Flipping

Color Flipping a chess position refers to the vertical flipping or mirroring of all pieces along the horizontal axis between the 4th and 5th rank also swapping the color of the flipped pieces from White to Black and vice versa, the side to move, the castling rights and the rank of a possible en passant target square from six to three or vice versa accordantly. The resulting position is mirror equivalent, pawn and pieces have the same span length or home rank relation. A white pawn on the light square c2 becomes a black pawn on the dark square c7. Color flipping a vertical symmetrical or mirror position (same castling rights, no en passant possible) results in the same position as if the side to move performed a null move:

Giuoco Piano		Giuoco Piano Symmetrical

r1bqk1nr/pppp1ppp/2n5/2b1p3/2B1P3/5N2/PPPP1PPP/RNBQK2R w KQkq -		r1bqk2r/pppp1ppp/2n2n2/2b1p3/2B1P3/2N2N2/PPPP1PPP/R1BQK2R w KQkq -

rnbqk2r/pppp1ppp/5n2/2b1p3/2B1P3/2N5/PPPP1PPP/R1BQK1NR b KQkq -		r1bqk2r/pppp1ppp/2n2n2/2b1p3/2B1P3/2N2N2/PPPP1PPP/R1BQK2R b KQkq -

Book Transpositions

During the opening, in some lines, White may intentionally lose a tempo, to transpose into a color flipped position of an opening White likes to play the "Black" side, which might be considered in chess programs book access code, see for instance WMCCC 1988, Pandix-Y!88.

Flipping an 8x8 Board

An 8x8 Board with a rank-file mapping, needs to perform an exclusive or with 56 (A8 in LERF) to vertically flip square coordinates. Assuming piece color is least significant bit and empty square is zero, a pure 8x8 Board may be color flipped that way in C:

int board[64], sq, s, f;
 
for (sq = 0; sq < 32; ++sq) {
    s = board[sq];
    f = board[sq^56];
    board[sq] = f ^ (f != 0);
    board[sq^56] = s ^ (s != 0);
}

Looking for Bugs

A side to move relative, bug free static evaluation should have the same score for both positions. Search is a different issue, since move ordering might be slightly different for instance in bitboard programs due to different order in bitboard serialization if one doesn't use a symmetrical bitscan by side to move. Similar to the butterfly effect in chaos theory a minor initial difference might amplify to enormous effects during the search. However, if the search behavior of a tactical test position of a most deterministic chess engine (e.g. no parallel search), varies by magnitudes in solution depth and time between original and color flipped position, one may take a closer look performing some logging and/or debugging.

Monochrome

An idea to unify and simplify move generation and to get rid of order dependencies, is to perform a color flip of the position and its internal board representation directly after making a move, to make the engine white to move only, that is only generating white moves, or similar, to keep a normal and flipped board to update them incrementally.

MicroChess

Jennings' approach with MicroChess was similar ^[1], but instead of vertical flipping (xor 56) he reversed or rotated the board by 180 degrees (xor 63), like players changing places and looking the board alternately from White's or Black's point of view, with some considerations of the additional horizontal mirroring, concerning castling and en passant.

Quad-Bitboards

Gerd Isenberg proposed a make move - color flipping approach using Quad-Bitboards ^[2] . The black Zobrist keys were the byte-swapped white Zobrist keys from the vertically flipped squares (xor 56). In symmetrical positions this gains some additional hits while probing the transposition table. But symmetrical mirror positions, or symmetrical subsets have the property, their xored hashkey has only 32 distinct bits since hashkey equals flipVertical(hashkey), for instance:

  01020304|50607080  // white pieces
^ 80706050|04030201  // black pieces of a mirror position
= 81726354|54637281

Six-Two Bitboards

The common six piece kind and two color bitboard board representation takes eight byte swaps to color flip the whole board.

Keeping two Boards

Rather than flipping the board after each make, Reinhard Scharnagl proposed monochrome move generation by keeping a normal and a color flipped board, both incremental updated ^[3] . He further suggested asymmetrical piece coding with less piece codes (only one or two) for the pieces of the side not to move. His approach has also the advantage to keep independent Zobrist keys for all squares and pieces.

Publications

Fernand Gobet (1993). A Computer Model of Chess Memory. Proceedings of the 15th Annual Meeting of the Cognitive Science Society, pp. 463-468.

Forum Posts

Conversion to dual positions for EPD testsuites? by Leen Ammeraal, CCC, November 26, 2001
fen to fen functions by Uri Blass, CCC, May 21, 2007
Comparison data of Crafty vs Rybka that I promised 2 days ago by Les, CCC, June 01, 2007
color-flipped perft by Gerd Isenberg, November 04, 2007
Board without color flags by Fritz Reul, CCC, October 31, 2009
Position flipping by Steven Edwards, CCC, August 05, 2013
Black/White symmetry in move generation by Jeffery A Esposito, CCC, November 25, 2014 » Move Generation
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
reversed-color transpositions by John Fishburn, CCC, March 11, 2016
FEN - Flipper for Windows by Matthias Gemuh, CCC, May 17, 2017 » FEN, EPD

External Links

References

^ Peter Jennings (1976). MicroChess, a Chess playing program for the 6502 Microcomputer. pdf, Courtesy of Peter Jennings, The Computer History Museum
^ color-flipped perft by Gerd Isenberg, November 04, 2007
^ Computerschach mit monochromen Methoden ? by Reinhard Scharnagl, OpenChess - Deutsches Forum, January 27, 2011 (German)

What links here?

Page	Date Edited
6502	Dec 25, 2017
AlphaZero	Feb 10, 2018
Bitboard Board-Definition	Jun 23, 2014
Bitboard Serialization	Dec 24, 2014
Chess Position	Sep 10, 2017
Chessmaps Heuristic	Aug 27, 2015
Color	Mar 12, 2014
Color Flipping	May 17, 2017
CTG	Aug 22, 2016
Debugging	Jan 20, 2018
Diagonal Mirroring	Jun 29, 2013
DirGolem	Jun 5, 2016
ECO	Nov 2, 2017
Excel	Dec 5, 2016
Extended Position Description	Dec 2, 2017
Flipping Mirroring and Rotating	Oct 14, 2016
Forsyth-Edwards Notation	Sep 10, 2017
Fritz Reul	Nov 28, 2016
Horizontal Mirroring	Jun 29, 2013
Incremental Updates	Sep 6, 2017
John Philip Fishburn	May 3, 2017
Leen Ammeraal	Nov 3, 2014
Matthias Gemuh	Jan 21, 2018
MicroChess	Jul 14, 2015
Move Generation	Jan 29, 2018
Opening Book	Feb 26, 2018
Pawn chain	Jan 17, 2018
Phalanx	May 2, 2016
Pigeon	Nov 2, 2016
Quad-Bitboards	Jan 30, 2017
Side to move	Oct 29, 2017
Teki	Mar 29, 2018
Transposition	Jun 8, 2015
Vertical Flipping	Oct 10, 2013
Vice	Mar 8, 2016
WMCCC 1988	Oct 27, 2016

Up one Level

Diagonal Mirroring

GerdIsenberg — Sat, 29 Jun 2013 11:31:45 GMT

Sample Position

Mirroring an 8x8 Board

See also

External Links

What links here?

Home * Chess * Position * Diagonal Mirroring

Diagonal mirroring mirrors all pieces along the main diagonal or main anti-diagonal. It is applicable in pawn-less endgames with castling no longer possible. Along with horizontal and/or vertical flipping, diagonal mirroring is used in pawn-less endgame tablebases to restrict a white king to the 10 squares of the a1-d4-d1 triangle of the board.

Sample Position

Original		Diagonal Mirror		Anti-Diagonal

k7/8/NK2B3/8/8/8/8/8 w - -		8/8/8/5B2/8/8/5K2/5N1k w - -		k1N5/2K5/8/8/2B5/8/8/8 w - -

Mirroring an 8x8 Board

An 8x8 Board with a rank-file mapping needs to swap rank and file. A pure 8x8 Board may be mirrored along the main diagonal that way in C:

int board[64], f, r, sm, sq, s;
 
for (f = 1; f < 8; ++f)
for (r = 0; r < f; ++r)
{
  sq = 8*r + f;
  sm = 8*f + r;
  s = board[sq];
  board[sq] = board[sm];
  board[sm] = s;
}

External Links

What links here?

Page	Date Edited
Chess Position	Sep 10, 2017
Color Flipping	May 17, 2017
Diagonal Mirroring	Jun 29, 2013
Edwards' Tablebases	Sep 26, 2016
Flipping Mirroring and Rotating	Oct 14, 2016
Horizontal Mirroring	Jun 29, 2013
Thompson's Databases	Dec 24, 2014
Vertical Flipping	Oct 10, 2013

Up one Level

Donald Michie

GerdIsenberg — Sat, 23 Dec 2017 09:20:09 GMT

Home * People * Donald Michie

		Donald Michie, (November 11, 1923 – July 7, 2007 ^[1] ^[2] ^[3] ) was a British researcher and pioneer in artificial intelligence and game theory. During World War II, Michie worked with Alan Turing at Bletchley Park, with Jack Good and Shaun Wylie et al. in the section Newmanry headed by Max Newman, contributing to crack the German Lorenz cipher ^[4] ^[5]. In 1947-48, along with Wylie, Michie designed Machiavelli, a rival of Turing's Turochamp program ^[6] ^[7]. Michie was head of the University of Edinburgh's Department of Machine Intelligence from 1965 until 1985 ^[8] , when he left to found the Turing Institute in Glasgow ^[9]. Michie researched on game theory and computer games and chess. He was a close friend of David Levy and involved in the famous Levy Bet with John McCarthy, which occurred during an AI-workshop in Edinburgh ^[10] , where Michie affirmed McCarthy to take the challenge by David Levy and even want to share the bet on McCarthy's site ^[11] .
Donald Michie ^[12]

Selected Publications

Photos



Jean Hayes Michie and Donald Michie, Edinburgh 1984 ^[13]

Donald Michie receiving his honorary degree from Stirling University in 2003 ^[14]

Machine Learning

Michie began his first experiments in machine learning in 1960. His tic-tac-toe machine MENACE (Machine Educable Noughts And Crosses Engine) demonstrated the basic principle of a self-reinforcing learning mechanism. MENACE employed Michie's conceptually simple general-purpose learning algorithm BOXES ^[15] ^[16] ^[17] ^[18] ^[19] which could also discover robust control strategies for the pole balancing problem ^[20] ^[21] , but was soon employed industrially to evolve strategies for automatic control, such as controlling a steel mill ^[22].

Self build MENACE by James Bridle ^[23]
in the traditions of Heath Robinson and Charles Babbage ^[24] ^[25]

The Need for Search

In King and Rook Against King: Historical Background and a Problem on the Infinite Board at the first Advances in Computer Chess conference ^[26] , Donald Michie shows two positions, that are identical except one pawn, to demonstrate the need for search ^[27] .

rn3rk1/p1q1nppp/bp2p3/2ppP3/P2P4/2PB1N2/2P2PPP/R1BQK2R w KQ - ; bm Bxh7

rn3rk1/p1q1nppp/bp2p3/2ppP3/P2P4/2PB1N2/1P3PPP/R1BQK2R w KQ - ; am Bxh7

Chess Endgames

Quote by Maarten van Emden in I remember Donald Michie ^[28]:

In 1980 I spent another summer in Edinburgh as a guest of Donald Michie. Since the low point of 1975, thanks to assiduous and inventive joint pursuit of funding possibilities by Donald and Jean, the Machine Intelligence Research Unit was alive with work focused on chess endgames. There were students, including Tim Niblett and Alen Shapiro. Danny Kopec was there, perhaps formally as a student, but de facto as the resident chess consultant. Ivan Bratko visited frequently. Alen was the administrator of the dream computing environment of that time: a small PDP-11 running Unix. ...

Donald Michie demonstrated the Human Window phenomenon with chess end games. He proposed a form of describing end-game knowledge that he called “advice” and described a formal language, Advice Language One ^[29] , for expressing such advice. The language could be translated into a form that guided a computer to play the end-game at the level of skill of a chess expert. Soei Tan, Ivan Bratko and Danny Kopec were chess experts who used this framework to implement specific end games.

Once again, I did not get it. I could not help acting in my then usual role of Prolog evangelist and wanted to demonstrate that the beauty of Prolog was that it rendered superfluous things like Advice Language One. Accordingly I wrote a Prolog program that played an end game using Advice in DM’s sense. DM generously allowed me my say in a paper in the Tenth Machine Intelligence workshop. It’s a nice paper, but it does not get it.

Solving Chess?

Quote by Kathleen Spracklen on Donald Michie and their experiments, excerpt from Oral History of Kathe and Dan Spracklen ^[30]:

One of the most thrilling times of my entire life was the month that Dr. Donald Michie spent with us in San Diego. And he, of course, is - was head of the computer science department at Oxford, I believe, for decades. He was on the original team with Turing that broke the Enigma code. And already he was quite an elderly gentleman when he came to work with us but that wasn't stopping him from having a very full schedule as the head of the I think it was the Turing Institute in Glasgow that headed up. Quite, totally an amazing human being.

Delightful and totally amazing. And he had this concept that he wanted to try out that he thought might possibly solve computer chess. And we spent a month exploring it. It was the idea of reaching a steady state. The idea was that you would establish a number of parameters of positional analysis and your program would score, independently score vast arrays of positions using this set of known parameters. And then the program would basically perform a cluster analysis and so you'd do it on a number of positions and on game after game after game of Grand Master Chess. You submitted we just we used hundreds of thousands of positions.

And then what it did was it took the evaluation that known chess theories said this position is worth this much. So we had an external evaluation because it came out of known Master Chess games. And then we had all of these parameters that our program was capable of evaluating and then you used this data to tune your weighing of the parameters. And you could also tune the weighting for different stages of the game. So at the opening, you could use a certain weight, mid-game, you could use a certain weight, in the midst of your king being attacked, could use a set of weights, when you're pressing an attack, you could use a set of weights, when they're past pawns on the board, you know, there were several different stages of the game that could have different weightings. And we used a program called Knowledge Seeker that helped you to determine these relative weightings. And so after a month of training the program, what you basically did was you take your total set of positions and you would use something like 80% of them as a training set and then the last 20 as the test set. And you'd find out, well, how did the program do in evaluating these positions it had never seen based on these that it had seen. And it did just a breathtaking job of determining the correct worth of the positions. And so we were so excited. We were going to turn it loose on its first play a game of chess. We were going to use this as the positional evaluator.

Yeah. It was, like, oh, it was breathtaking. And we watched the program play chess. It was- you could gasp for breath. No computer program ever played a game of chess like that. It looked like an incredibly promising seven-year-old. We lost the game in just a few moves but it lost it brilliantly. <laughter> It got its queen out there, it maneuvered its knight, it launched a king side attack, it sacrificed its queen. <laughter> Well, of course it sacrificed its queen. Do you realize, in every single Grand Master game of chess, when you sacrifice your queen, it's phenomenally brilliant. You are winning the game. So if you can find a way to get your queen out there and sacrifice her, well, you've won.

AI as Sport

Quote by John McCarthy from AI as Sport ^[31]^[32]:

Besides AI work aimed at tournament play, particular aspects of the game have illuminated the intellectual mechanisms involved. Barbara Liskov demonstrated that what chess books teach about how to win certain endgames is not a program but more like a predicate comparing two positions to see if one is an improvement on the other. Such qualitative comparisons are an important feature of human intelligence and are needed for AI. Donald Michie, Ivan Bratko, Alen Shapiro, David Wilkins, and others have also used chess as a Drosophila to study intelligence. Newborn ignores this work, because it is not oriented to tournament play.

Selected Publications

^[33] ^[34]

1945

Jack Good, Donald Michie, Geoffrey Timms (1945). General Report on Tunny from The Turing Archive for the History of Computing

1960 ...

Donald Michie (1961). Trial and Error. Penguin Science Survey
John Maynard Smith, Donald Michie (1961). Machines that play games. New Scientist, 12, 367-9. google books ^[35]
Jim Doran, Donald Michie (1966). Experiments with the Graph Traverser Program. Proc. Roy. Soc. (A), Vol. 294, pp. 235-259.
Donald Michie (1966). Game Playing and Game Learning Automata. Advances in Programming and Non-Numerical Computation, Leslie Fox (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: Rules of SOMAC by John Maynard Smith, introduces Expectiminimax tree ^[36]
Donald Michie, Roger A. Chambers (1968). Boxes: An experiment on adaptive control. In E. Dale and D. Michie, editors, Machine Intelligence 2, Edinburgh: Oliver & Boyd, pp. 137-152, pdf

1970 ...

Donald Michie (1974). On Machine Intelligence. Edinburgh: University Press, ISBN 10: 085224262X, ISBN 13: 9780852242629, abebooks.com, alibris.com, biblio.com
Donald Michie (1976). AL1: a package for generating strategies from tables. ACM SIGART Bulletin, Issue 59
Donald Michie (1976). An Advice-Taking System for Computer Chess. Computer Bulletin, Ser. 2, Vol. 10, pp. 12-14. ISSN 0010-4531.
Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board. Advances in Computer Chess 1
Donald Michie, Ivan Bratko (1978). Advice Table Representations of Chess End-Game Knowledge. Proceedings 3rd AISB/GI Conference, pp. 194-200.
Ivan Bratko, Danny Kopec, Donald Michie (1978). Pattern-Based Representation of Chess Endgame Knowledge. The Computer Journal, Vol. 21, No. 2, pp. 149-153. available as pdf reprint
Donald Michie (1979). The Computer Attacks Moravec Problem. Personal Computing, Vol. 3, No. 10, pp. 73 ^[37]

1980 ...

Donald Michie (1980). Chess with Computers. Interdisciplinary Science Reviews. Vol. 5, No. 3, pp. 215-227. ISSN 0308-0188.
Ivan Bratko, Donald Michie (1980). An Advice Program For a Complex Chess Programming Task. Computer Journal, Vol. 23, No. 4, pp. 350-353.
Ivan Bratko, Donald Michie (1980). A Representation of Pattern-Knowledge in Chess Endgames. Advances in Computer Chess 2
Donald Michie (1981). A Theory of Evaluative Comments in Chess with a Note on Minimaxing. The Computer Journal, Vol. 24, No. 3, pp. 278-286. reprinted in Computer Chess Compendium
Jaap van den Herik (1981). Computer Chess Today and Tomorrow: An Interview with Donald Michie. Advances in Computer Chess 3, Computer Chess Digest Annual 1984
Donald Michie (1982). Chess with computers. Machine Intelligence and Related Topics. Gordon and Breach Science Publishers.
Donald Michie (1982). Information and Complexity in Chess. Advances in Computer Chess 3
Danny Kopec, Donald Michie (1983). Mismatch between machine representations and human concepts: dangers and remedies. FAST series No. 9 report. European Community, Brussels.
Donald Michie (1986). The superarticulacy phenomenon in the context of software manufacture. Proc. Roy. Soc. (A).
Donald Michie (1986). Towards a Knowledge Accelerator. Advances in Computer Chess 4
Alen Shapiro, Donald Michie (1986). A Self-commenting Facility for Inductively Synthesised Endgame Expertise. Advances in Computer Chess 4
Donald Michie, Ivan Bratko (1987). Ideas on Knowledge Synthesis Stemming from the KBBKN Endgame. ICCA Journal, Vol. 10, No. 1
Donald Michie, Ivan Bratko (1987). Ideas on Knowledge Synthesis - a Correction. ICCA Journal, Vol. 10, No. 2
Donald Michie (1989). Automating the Discovery of Structure in Time-Varying Data. Workshop on New Directions in Game-Tree Search
Donald Michie (1989). Brute Force in Chess and Science. ICCA Journal, Vol. 12, No. 3
Donald Michie, Michael Bain (1989). Machines That Learn and Machines That Teach. SCAI 1989
Stephen Muggleton, Michael Bain, Jean Hayes Michie, Donald Michie (1989). An Experimental Comparison of Human and Machine Learning Formalisms. 6. ML 1989, pdf

1990 ...

Donald Michie (1990). Brute Force in Chess and Science. Computers, Chess, and Cognition
Donald Michie, Ivan Bratko (1991). Comments to `Chunking for Experience'. ICCA Journal, Vol. 14, No. 1
Jean Hayes Michie, Donald Michie (1998). Simulator-Mediated Acquisition of a Dynamic Control Skill. AI & Sociaty Vol. 12 No. 1

External Links

Donald Michie from Wikipedia
The Mathematics Genealogy Project - Donald Michie
Curriculum Vitae - Professor Donald Michie
The Machine Intelligence series
Turing Trust - Historical Note by Donald Michie
Turing 1990 - Final Reminder From: Turing Conference
Artificial Intelligence - Recollections of the Pioneers

References

^ Professor Donald Michie, Telegraph.co.uk July 09, 2007
^ Obituary - Donald Michie by Stephen Muggleton, The Guardian, Tuesday July 10 2007
^ David Levy (2007). Obituary Donald Michie (1923-2007). ICGA Journal, Vol. 30 No. 3
^ Jack Good, Donald Michie, Geoffrey Timms (1945). General Report on Tunny from The Turing Archive for the History of Computing
^ From Codebreaking to Computing - Video from The Computer History Museum
^ Maynard Smith, J., Michie D. (1961). Machines that play games. New Scientist, 12, 367-9.
^ Chronology of Computing compiled by David Singmaster
^ Artificial Intelligence at Edinburgh University : a Perspective
^ Turing Trust - Historical Note by Donald Michie: "In association with the University of Strathclyde, the Turing Institute hosted seven public lectures in the period 1985-93"
^ Machine Intelligence Volume 4
^ Oral History of David Levy from The Computer History Museum
^ Donald Michie Home Page
^ László Lindner, A SZÁMÍTÓGÉPES SAKK KÉPEKBEN című melléklete - The pictures of the Beginning of Chess Computers
^ Donald Michie Home Page
^ Donald Michie (1961). Trial and Error. Penguin Science Survey
^ Martin Gardner (1969, 1991). The Unexpected Hanging and Other Mathematical Diversions. Simon & Schuster, University Of Chicago Press, Chapter 8: A Matchbox Game-Learning Machine
^ Donald Michie, Roger A. Chambers (1968). Boxes: An experiment on adaptive control. In E. Dale and D. Michie, editors, Machine Intelligence 2, Edinburgh: Oliver & Boyd, pp. 137-152
^ Alex Bell (1972). Games Playing with Computers. 1.3 NOUGHTS AND CROSSES, Allen & Unwin
^ UU/IT/AI exercise: Implementing MENACE, Uppsala University
^ Controller-less Driver For the Cart-Pole Problem
^ Q-Learning Controller for the Cart-Pole Problem
^ D. Michie CV
^ A New Theory of Awesomeness and Miracles by James Bridle
^ Menace - Flickr Photo stream
^ Mechanical computer uses matchboxes and beans to learn Tic-Tac-Toe - Boing Boing
^ Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board. Advances in Computer Chess 1
^ Michael Gherrity (1993). A Game Learning Machine. Ph.D. Thesis, University of California, San Diego, available as zipped postscript, page 13, 14
^ I remember Donald Michie (1923 – 2007) « A Programmers Place by Maarten van Emden, June 12, 2009
^ Donald Michie (1976). AL1: a package for generating strategies from tables. ACM SIGART Bulletin, Issue 59
^ Gardner Hendrie (2005). Oral History of Kathe and Dan Spracklen. pdf from The Computer History Museum
^ John McCarthy (1997). AI as Sport. Science, Vol. 276, June 6, pp. 1518-1519.
^ AI as Sport by John McCarthy
^ ICGA Reference Database (pdf)
^ D. Michie publications
^ Publications of John Maynard Smith (pdf)
^ see Swap-off by Helmut Richter
^ www.arves.org - Moravec, Josef 1882-1969

What links here?

Page	Date Edited
Aaron L. Futer	Dec 23, 2014
ACM 1990	Jun 7, 2016
Advances in Computer Chess 1	Oct 22, 2015
Advances in Computer Chess 2	Dec 25, 2017
Advances in Computer Chess 3	Jul 23, 2015
Advances in Computer Chess 4	Jan 22, 2018
Alan Turing	Feb 8, 2017
Albrecht Heeffer	Sep 6, 2016
Alen Shapiro	May 3, 2015
Algorithms	May 5, 2017
Artificial Intelligence	Apr 9, 2018
Belle	Jan 18, 2018
Brute-Force	Jul 27, 2017
Chess	Jan 21, 2018
Chess Position	Sep 10, 2017
Chess Problems, Compositions and Studies	Feb 19, 2018
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Computer Chess Compendium	Dec 29, 2015
Computers, Chess, and Cognition	Dec 28, 2016
Conferences	Dec 18, 2017
Danny Kopec	Oct 1, 2016
Dart	Jan 19, 2018
Dartmouth College	Dec 16, 2016
Dartmouth CP	Jan 19, 2018
David Levy	Jan 3, 2017
Dietrich Prinz	Oct 14, 2016
Dinesh Gadwal	May 23, 2016
Donald Michie	Dec 23, 2017
Eduardo F. Morales	May 23, 2016
Edward Fredkin	Oct 27, 2013
El Ajedrecista	Feb 25, 2015
Endgame	Sep 18, 2017
Endgame Tablebases	Mar 6, 2018
Ferranti Mark 1	Jun 2, 2015
Games	Feb 20, 2018
Georgy Adelson-Velsky	Apr 9, 2018
Hal Terrie	Feb 19, 2015
Hardware	Jan 20, 2018
Helmut Richter	Nov 29, 2017
History	Jan 2, 2018
ICGA Journal	Dec 21, 2017
Iterative Deepening	Jun 23, 2017
Ivan Bratko	Aug 16, 2017
Jaap van den Herik	Sep 18, 2017
Jack Good	Dec 22, 2017
Jack Holloway	Nov 1, 2015
Jean Hayes Michie	Feb 9, 2016
Jim Doran	May 21, 2014
John J. Scott	Aug 30, 2016
John Maynard Smith	Nov 27, 2017
John Moussouris	Nov 1, 2015
Jürg Nievergelt	Dec 28, 2016
Kathe Spracklen	Dec 25, 2017
Knowledge	Jul 22, 2017
KRK	Nov 26, 2016
Lancaster	Aug 30, 2016
Languages	Nov 26, 2017
Larry Harris	Apr 3, 2013
Learning	Feb 20, 2018
Maarten van Emden	May 23, 2016
Mac Hack	Apr 20, 2018
Machiavelli	Jun 2, 2015
Martin Gardner	May 10, 2017
Mathematician	Apr 9, 2018
Michael Bain	Aug 8, 2013
Mikhail Donskoy	Dec 23, 2017
Minimax	Dec 29, 2017
Papers	Jan 11, 2017
Pattern Recognition	Sep 8, 2017
Pawn Structure	Oct 2, 2017
People	Feb 28, 2018
Periodical	Dec 22, 2017
Personal Computing	Dec 27, 2017
Reinforcement Learning	Feb 12, 2018
Retrograde Analysis	Mar 21, 2017
Richard Greenblatt	Jan 19, 2016
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
Shaun Wylie	Jun 2, 2015
SOMA	Mar 25, 2015
Static Exchange Evaluation	Dec 14, 2017
Stephen Muggleton	May 23, 2016
Strategy	Jan 18, 2018
The Computer History Museum	Aug 9, 2017
Tim Niblett	May 22, 2014
Tony Marsland	Nov 27, 2017
Trial and Error	Feb 11, 2018
Turochamp	Dec 14, 2017
University of Edinburgh	Nov 26, 2017
Vladimir Arlazarov	May 20, 2016
WCCC 1989	Dec 5, 2017
WMCCC 1984	Dec 31, 2017

Up one level

Doubled Pawn

GerdIsenberg — Mon, 27 Mar 2017 14:06:49 GMT

Types of Doubled Pawns

Crippled Majority

All About Doubled Pawns

Home * Evaluation * Pawn Structure * Doubled Pawn

A Pawn is doubled (or, sad to say, tripled) if there are more pawns of the same color on a given file. Early programs and papers advocated evaluation it as half a pawn, today the penalty uses to be less severe.

It might be argued that, given a perfect pawn structure evaluation, a term such as doubled pawns would not be needed, since they usually introduce another pawn structure weaknesses: some kind of backwardness, lack of a candidate passer that otherwise would be there etc. However, most evaluation functions do not go into such details as to justify removing this term.

Types of Doubled Pawns

Hans Berliner characterizes doubled pawns by their exchange potential against opponent pawns on adjacent files ^[1]^[2]:

		`The doubled pawns on the b-file are the best situation, the f-file pawns are next. The h-file pawns are the worst situation because two pawns are held back by one opposing pawn, so the second pawn has little value.`
8/1p6/p3pp1p/8/8/1PP2P1P/1P3P1P/8 w - -

Crippled Majority

A doubled pawn of a so called "crippled" majority devalue that majority. Hans Berliner on following position in Some Innovations Introduced by Hitech ^[3]:

		`Our pawn-structure algorithm is quite simple, detecting only isolated and multiple Pawns, and the effect of multiple Pawns on viable pawn majorities. For instance, in Diagram 1 the value of White's doubled Pawn is negligible, while Black's is almost full-valued. This distinction, an innovation, was first introduced in Patsoc ^[4], and we were able to adapt the code to make up tables to be loaded into six identical hardware units computing pawn structure in parallel.`
8/1pp2ppp/1p6/8/8/5P2/PPP2PPP/8 w - -

All About Doubled Pawns

The vast amount of detailed knowledge about doubled pawns, which rarely gets implemented, can be found in the article All About Doubled Pawns by Larry Kaufman ^[5].

Publications

Larry Kaufman (2005). All About Doubled Pawns. (first published in Chess Life, May 2005, p.22)

Forum Posts

Doubled and Backward Pawn Engine "Definitions" by Brian Richardson, CCC, September 07, 2009
passed but doubled pawns by Jon Dart, CCC, June 15, 2015 » Passed Pawn
Doubled pawns by Stefano Gemma, CCC, May 11, 2016

External Links

Doubled Pawn from Wikipedia
All About Doubled Pawns by IM Larry Kaufman
Doubled Pawns Strength and weakness by Georgi Orlov
Ástor Piazzolla - Tristezas de un Doble A, Montreux Jazz Festival, 1985 YouTube Videos

References

^ Hans Berliner (1999). The System: A World Champion's Approach to Chess, Gambit Publications, ISBN 1-901983-10-2
^ Types of doubled pawns from Wikipedia
^ Hans Berliner (1987). Some Innovations Introduced by Hitech. ICCA Journal, Vol. 10, No. 3, pp. 111-117
^ Hans Berliner (1985). Computer Chess at Carnegie Mellon University. Advances in Computer Chess 4
^ Larry Kaufman (2005). All About Doubled Pawns. (first published in Chess Life, May 2005, p.22)

What links here?

Page	Date Edited
More Links
Alarm	Jun 7, 2017
Amyan	Dec 10, 2013
Applied Concepts	Dec 25, 2017
Bismark	Apr 22, 2015
Cheese	Feb 17, 2018
Cheops (Miller)	Jan 13, 2017
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
Clarabit	Nov 3, 2011
Coiled	Mar 12, 2017
Cyrus	Jul 22, 2014
Dartmouth CP	Jan 19, 2018
Defenchess	Mar 18, 2018
Diablo	May 17, 2016
Dispersion and Distortion	Nov 11, 2017
Donna	Aug 17, 2017
Dorpsgek	Apr 2, 2018
Double and Triple (Bitboards)	May 12, 2016
Doubled Pawn	Mar 27, 2017
Eval Tuning in Deep Thought	Jun 7, 2016
Evaluation function draft	Jul 11, 2014
Evaluation Overlap	Jul 19, 2016
Exacto	Oct 3, 2015
Garbochess	Sep 23, 2017
Gk	Oct 9, 2017
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Hakkapeliitta	Apr 26, 2016
Hans Kmoch	Nov 11, 2017
ISA	Apr 2, 2018
Kaissa	Apr 9, 2018
Larry Kaufman	Jan 28, 2018
Marvin	Feb 10, 2018
Nebula	Feb 7, 2015
Neurosis	Dec 23, 2017
Passed Pawn	Oct 11, 2017
Patsoc	Jan 7, 2016
Paul	Jan 8, 2016
Pawn Center	Feb 12, 2015
Pawn Majority	Jun 8, 2012

Up one Level

ECO

GerdIsenberg — Thu, 02 Nov 2017 20:09:00 GMT

Main Classifications

Ambiguity

Sample Implementation

Home * Knowledge * Opening Book * ECO

Encyclopaedia of Chess Openings, (ECO)
a de facto standard of a classification system for chess openings, established by Chess Informant since 1966, using a coding system that has been widely-used and adopted by other chess publications, chess programs, databases and GUIs. There are five main categories, "A" to "E", which are divided into one hundred subcategories each, in total 500 from A00 to E99. ECO code is a registered trademark of Chess Informant ^[1] .

Main Classifications

A - Flank openings
B - Semi-Open Games other than the French Defence
C - Open Games and the French Defence
D - Closed Games and Semi-Closed Games
E - Indian Defences

Ambiguity

ECO codes are defined by halfmove sequences from the initial position with non-uniform length or depth of one to 28 plies ^[2] . The position reached after that move sequence associates the ECO code. Depending on the particular opening and its classification granulation and depth, the ECO assignment may change during the course of the opening from halfmove to halfmove to more specific classified ECO codes until it sticks with the final assessment. However, due to transpositions, even into color flipped positions, ambiguity manifests in different implementations of chess engines, databases and GUIs. As pointed out by Gregor Cramer, ChessBase assigns "1.f4 e5 2.d4" to A02, and "1.d4 e5 2.f4" to A40, but Scidb assigns both lines to A02 ^[3] . Since there are zillions of transpositions f.i. between Scandinavian gambit B01, Caro Kann B13, B14, Symmetrical English A35, and Queens Gambit D26, D40, ..., the following position has ambiguous ECO assignments. How should it be classified? Depending on the sequence of moves reaching it?

r1bqkb1r/pp3ppp/2n1p3/3n4/3P4/2N2N2/PP3PPP/R1BQKB1R w KQkq -

Four of many possible move sequences to reach the same position:

1.e4 d5 2.exd5 Nf6 3.c4 c6 4.d4 cxd5 5.Nc3 Nc6 6.Nf3 e6 7.cxd5 Nxd5
1.e4 c6 2.d4 d5 3.exd5 cxd5 4.c4 e6 5.Nf3 Nf6 6.cxd5 Nxd5 7.Nc3 Nc6
1.d4 d5 2.c4 e6 3.Nc3 Nf6 4.Nf3 c5 5.cxd5 Nxd5 6.e3 cxd4 7.exd4 Nc6
1.c4 c5 2.Nc3 Nf6 3.Nf3 Nc6 4.e3 e6 5.d4 cxd4 6.exd4 d5 7.cxd5 Nxd5

Sample Implementation

The book identification code of the opening book in IsiChess (commercial DOS version) had all book lines defined in a PGN-like textfile with a descriptive name and ECO code associated, much more than the 500 determinative ECO lines and full of transpositions, merged into an opening tree similar to a persistent transposition table indexed by the Zobrist key, keeping not only a list of possible moves from the current position, but also a list of different predecessor moves aka indices to the different opening lines. Its book editor has not only an opening tree view, but also a list view of opening lines where multiple lines with different last moves and possibly ECO codes may appear, leading to the current position.

Forum Posts

1998 ...

Electronic ECO by C.M.A., CCC, November 23, 1998
Mercilous Attack? What is it? What is the ECO on it? by Dann Corbit, CCC, July 07, 1999

2000 ...

ECO question by Robert Pope, CCC, March 04, 2000
implement program to identify eco code by Sylvain Eche, CCC, May 13, 2002
ECO-Browser in Scid 3.6.1 (under WinXP) by Daniel Clausen, CCC, September 23, 2004
ECO Codes as PGN 1.16 available for download by Michael Diosi, CCC, May 17, 2005

2010 ...

Scid.eco by Gregor Cramer, scid-users, April 19, 2014
code method to get ECO code/opening name by Mike Adams, CCC, April 27, 2014
Hint for ChessGUI users by Jon Dart, CCC, April 26, 2016 » ChessGUI
Tool to ECO classify EPD positions? by Dann Corbit, CCC, July 28, 2017

External Links

References

^ List of chess openings from Wikipedia
^ D69: Queen's Gambit Declined, Orthodox defence, classical, 13.en - 365Chess.com
^ Scid.eco by Gregor Cramer, scid-users, April 19, 2014

What links here?

Page	Date Edited
Buğra Fırat	Nov 2, 2017
ChessBase (Database)	Feb 26, 2018
ChessGUI	Jan 17, 2018
ChessX	Feb 26, 2015
Christopher Conkie	May 17, 2016
Databases	Mar 18, 2018
Dictionary	Aug 24, 2017
ECO	Nov 2, 2017
Extended Position Description	Dec 2, 2017
Jose	Feb 26, 2015
Kvetka	Mar 28, 2016
Neural MoveMap Heuristic	Sep 24, 2015
NIC-Key	Jul 16, 2017
Opening Book	Feb 26, 2018
Robert Pope	Jun 10, 2017
Scid	Apr 15, 2017
Scid on the Go	Jan 26, 2015
Scidb	Mar 18, 2018
TascBase	Dec 7, 2016
TCEC Season 10	Jan 3, 2018
TCEC Season 5	Jun 2, 2014
TCEC Season 6	Dec 2, 2014
TCEC Season 7	Jan 23, 2015
TCEC Season 8	Nov 30, 2015
TCEC Season 9	Nov 6, 2017

Up one level

En passant

GerdIsenberg — Tue, 16 Jan 2018 08:34:29 GMT

Home * Chess * Moves * En passant

En passant (from French: "in passing") ^[1] is a special pawn capture move, which is only possible immediately after an opposing pawn tried passing an advanced pawn on the fifth rank (or fourth for black pawns) by a double pawn push. This double pushed pawn can then be captured the same way, as it would only performed a single push - but only as an immediate reply.

This chess rule makes chess programming a bit harder. First, the target square of the en passant capture is not identical with origin of the captured pawn, opposed to all other captures. Second, the double pawn push, which triggered the immediate possibility of an en passant capture, must be part of the chess position. The information required is whether there was a previous pawn push, and if so, at least the file number of that pawn, considered as en passant target square inside the Forsyth-Edwards Notation (FEN), albeit with the redundant rank (3 or 6) as well.

Legality Test

To prove an en passant capture is actually possible, at least the en passant target square should be under attack of an opponent pawn for pseudo legality. Further, for strict legality, the ep capturing pawn should not be absolutely pinned, which additionally requires a horizontal pin test of both involved pawns, which disappear from the same rank.

8/6bb/8/8/R1pP2k1/4P3/P7/K7 b - d3 after d2-d4

The legality test should be best applied in making of the double pawn push, also considering updating Zobist keys to avoid dissimilarity of otherwise repeated positions if the first occurrence happened after a double pawn push with no en passant capture actually possible ^[2] .

En passant bugs

The implementation of the en passant rule often caused subtle bugs. Almost every chess programmer had various issues with it ^[3] , most notable Louis Kessler with his Program Brute Force. Gerd Isenberg had a special en passant experience with IsiChess at Aegon 1994 in the game versus Henk Arnoldus. IsiChess pushed its white pawn from b2 to b4 "between" the two advanced pawns a4 and c4 from Henk, allowing two possible en passant options. Unfortunately IsiChess only generated one - the "wrong" one (an assembly bug due to jc instead if jnz or that like, otherwise it would not have played it), and was immediately lost after Henk played the "right" one ^[4] ^[5] :

[Event "9th AEGON man-comp"]
[Site "The Hague NED"]
[Date "1994.05.02"]
[Round "4"]
[White "IsiChess"]
[Black "Henk Arnoldus"]
[Result "0-1"]
 
1.e4 e6 2.d4 d5 3.Nd2 Nf6 4.e5 Nfd7 5.Bd3 b6 6.Ngf3 Ba6 7.O-O Bxd3
8.cxd3 Be7 9.Nb3 O-O 10.Bd2 Na6 11.Qe2 Qc8 12.Rac1 Qb7 13.Rc2 c5
14.Rfc1 Rfc8 15.dxc5 bxc5 16.Qe3 Nb4 17.Bxb4 Qxb4 18.Nbd2 a5 19.a3 Qb7
20.Kh1 Ra6 21.d4 c4 22.Qc3 a4 23.b4 axb3 24.Nxb3 Rxa3 25.Nfd2 Rb8
26.Rb1 cxb3 27.Rcb2 Bb4 28.Qc1 Bxd2 29.Rxd2 Ra2 30.Rdb2 Rxb2
31.Qxb2 Qb4 32.f4 g6 33.h3 Qc4 34.Rc1 Qd3 35.f5 Qxf5 0-1

2r3k1/1q1nbppp/r3p3/3pP3/pPpP4/P1Q2N2/2RN1PPP/2R4K b - b3 0 23

Forum Posts

1999

en-passant move generation by Larry Griffiths, CCC, February 06, 1999
Unique nodes, en passant and perfect hashing by Andreas Stabel, CCC, November 25, 1999

2000 ...

annoying en passant x-ray by Georg von Zimmermann, CCC, November 30, 2003

2005 ...

Programmer bug hunt challenge by Ed Schröder, CCC, May 04, 2007 » Portable Game Notation

2010 ...

en passant and hash key calculation by Fred Hamilton, CCC, March 21, 2010
Komodo 3 and a minor bug by Jouni Uski, CCC, September 02, 2011
Re: Causes for inconsistent benchmark signatures by Evert Glebbeek, CCC, March 27, 2013 » Forsyth-Edwards Notation
polyglot en passant square by Marco Belli, CCC, September 12, 2013 » Polyglot
ep and castle rights hashing by Natale Galioto, CCC, September 15, 2013 » Castling rights, Repetitions, Transposition Table
Abundance of castling vs en passant rights by Kirill Kryukov, CCC, April 14, 2014 » Castling
En-passant legality test by tetra, OpenChess Forum, August 07, 2014 » Legal Move

2015 ...

En passant bonus by Lyudmil Tsvetkov, CCC, February 10, 2015 » Pawn Structure
Dynamic EP flag by thevinenator, OpenChess Forum, October 02, 2015
Triple Repitition: Is this considered a repitition or not? by Jayakiran Akurathi, CCC, May 07, 2016 » Repetitions
Enpass + Castling for Zorbist hashes by Andrew Grant, CCC, January 06, 2017 » Castling rights, Zobrist Hashing
3-fold repetition and cutechess-cli by Lars Mathiesen, CCC, January 14, 2018 » Repetitions

External Links

References

^ Earliest Occurrences of Chess Terms by Edward Winter
^ en passant and hash key calculation by Fred Hamilton, CCC, March 21, 2010
^ Chrilly Donninger (1999). Computer machen keine Fehler. CSS 2/99, pdf (German)
^ CSVN Downloads Games Aegon Tournaments
^ Aegon 1994 Round 4 (REPOST) by Dap Hartmann, rgc, May 09, 1994

What links here?

Page	Date Edited
1K ZX Chess	Oct 1, 2015
ACM 1978	Dec 23, 2017
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
AlphaZero	Feb 10, 2018
Andrew Grant	Jan 13, 2018
Atom Chess	Dec 11, 2016
Atomic Chess	Nov 26, 2016
Board Representation	Dec 11, 2017
BootChess	May 16, 2017
Brute Force (Program)	Sep 7, 2017
Butterfly Boards	Jan 27, 2015
Captures	Oct 1, 2017
Castling	May 5, 2017
Castling rights	Jan 7, 2017
Charly	Jan 10, 2013
Check	Feb 1, 2018
CHEKMO-II	Jan 3, 2018
Chess Position	Sep 10, 2017
ChessLin	May 17, 2017
Color Flipping	May 17, 2017
Copy-Make	May 23, 2017
CTG	Aug 22, 2016
Dabbaba	Oct 21, 2014
David Forthoffer	Apr 25, 2016
Deep Pink	Feb 6, 2017
Dictionary	Aug 24, 2017
DirGolem	Jun 5, 2016
Double Check	Apr 4, 2013
EGA Chess	Nov 30, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
Eval Tuning in Deep Thought	Jun 7, 2016
Evert Glebbeek	Sep 25, 2017
Extended Position Description	Dec 2, 2017
Firstchess	Nov 27, 2014
Forsyth-Edwards Notation	Sep 10, 2017
Galahad	Jan 8, 2015
Gaviota Tablebases	Apr 22, 2018
General Setwise Operations	Feb 25, 2018
Genie	Feb 7, 2016
Georg von Zimmermann	May 29, 2017
Harald Lüßen	Mar 20, 2013
Incremental Updates	Sep 6, 2017
iota	Feb 10, 2016
James Swafford	Jan 1, 2018
Jonathan Warkentin	Jun 29, 2014
Kirill Kryukov	Apr 16, 2014
Lars Rasmussen	Apr 25, 2016
Last Best Reply	Jul 6, 2013
Legal Move	Feb 16, 2017
Little Rook Chess	Sep 1, 2015
Lomonosov Tablebases	May 20, 2016
Lyudmil Tsvetkov	Mar 28, 2018
Make Move	Mar 2, 2016
Marco Belli	Jan 6, 2018
Mark Taylor	Jan 7, 2016
Mate-in-two	Oct 14, 2016
Mini Chess	Jun 7, 2013
Move Generation	Jan 29, 2018
Moves	Feb 19, 2018
MyChess	Dec 25, 2017
Nalimov Tablebases	Dec 23, 2016
Paladin	Jan 29, 2017
Pawn Push	Mar 27, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Pawn Structure	Oct 2, 2017
Perft	Sep 26, 2017
Perft Results	Feb 10, 2018
Pieces versus Directions	Oct 6, 2016
Pin	Mar 7, 2017
PolyGlot	Jan 17, 2018
Portable Game Notation	Jan 11, 2018
Pseudo-Legal Move	May 23, 2015
Quad-Bitboards	Jan 30, 2017
Quiet Moves	Mar 4, 2010
Repetitions	Jan 16, 2018
Sito Dekker	Apr 25, 2016
Sneaky Pete	Mar 18, 2016
Squares	Feb 15, 2015
Toledo	Sep 23, 2017
Transposition Table	Apr 19, 2018
Unmake Move	Jun 10, 2017
WMCCC 1996	Sep 15, 2016
Z-Chess	Dec 23, 2017
Zobrist Hashing	Jan 22, 2018

Up one Level

Encoding Moves

ecabiac — Sun, 27 Mar 2016 23:30:39 GMT

Information Required

From-To Based

Extended Move Structure

C++ Sample

Various Encodings and Decorations

Home * Chess * Moves * Encoding Moves

Encoding Moves inside a chess program refers to both game records or game notation, and search related generation, make and unmake move to incremental update the board. During generation, moves are stored inside move lists, and best moves or refutation moves failing high inside the search are stored inside the transposition table, Killer slots, PV- or refutation table, and moves, or certain aspects of a move, such as origin square and the target square are used to index butterfly boards for history- or countermove heuristic.

Move encoding in game records and game databases is usually designed to minimize size, while in search efficiency in generating is the main concern, considering board representation and other data structures like attack and defend maps. In general, move encoding either comprehend full information, that is contains involved pieces and square coordinates, or more common, omits the redundant piece information and relies on a adequate board representation to lookup the pieces by square. In Alpha-Beta like search, an important consideration is lazy move generation, to delay acquisition of certain information until it is really needed, which might be never in case of Cut-nodes.

Information Required

From-To Based

The information required to uniquely describe a move is the initial square, also called from-, origin- or departure square, and the target square, also called to- or destination square, and in case of promotions the promoted piece code. While this from-to information is also sufficient for castling in standard chess, due to the otherwise impossible double king step, it might not in Chess960. Therefore and also for efficiency reasons, castles are tagged as "special" moves. Such a move encoding conveniently fits inside a 16-bit word, 6 bits for from-to square each to index a butterfly board, still leaves a nibble for flags for move kind and promoted piece code, for instance this arbitrary flags:

code	promotion	capture	special 1	special 0	kind of move
0	0	0	0	0	quiet moves
1	0	0	0	1	double pawn push
2	0	0	1	0	king castle
3	0	0	1	1	queen castle
4	0	1	0	0	captures
5	0	1	0	1	ep-capture
8	1	0	0	0	knight-promotion
9	1	0	0	1	bishop-promotion
10	1	0	1	0	rook-promotion
11	1	0	1	1	queen-promotion
12	1	1	0	0	knight-promo capture
13	1	1	0	1	bishop-promo capture
14	1	1	1	0	rook-promo capture
15	1	1	1	1	queen-promo capture

Extended Move Structure

The information which piece performs the move and which piece is captured (if any) is implicit given by the from-to squares, with the requirement to lookup the current board before making the move, but in case of captures not after making or before unmaking the move. Some programs use a 32-bit double word as extended move structure at generation time as well for making/unmaking moves, with the upper bits used for a move score scaled by various move ordering techniques for instance dedicated piece-square tables and/or history heuristic, and perhaps two three bit codes for the moving and captured piece (if any) which also implies a kind of MVV-LVA coding. Also the extended move may apply composite indices for incremental update of Zobrist- or BCH keys.

Having the piece codes inside the move structure safes the board lookups during make, and makes storing captured pieces on a ply stack for unmake needless. Of course for space considerations to store moves inside transposition table, Killer slots, PV- or refutation table, the compact 16-bit move structure is still adequate for coordinate and move kind comparison with the lower 16 bits of the extended move structure.

C++ Sample

Rather than using bitfield move structures or classes in C and C++, most programmers rely on scalar integers, such as short and int for 16- or 32-bit words, but implement the composition and extraction while writing and reading various structure elements by explicit shifts and masks, likely encapsulated thought an interface with most likely inlined functions (or macros) to hide the internal representation. Further extended move structures might either embed or inherit this most compact base structure or class, which might already rely the native 32-bit integer type to avoid x86 16-bit optimization issues.

class CMove {
   CMove(unsigned int from, unsigned int to, unsigned int flags) {
      m_Move = ((flags & 0xf)<<12) | ((from & 0x3f)<<6) | (to & 0x3f);
   }
   void operator=(CMove a} {m_Move = a.m_Move;}
 
   unsigned int getTo() const {return m_Move & 0x3f;}
   unsigned int getFrom() const {return (m_Move >> 6) & 0x3f;}
   unsigned int getFlags() const {return (m_Move >> 12) & 0x0f;}
 
   void setTo(unsigned int to) {m_Move &= ~0x3f; m_Move |= to & 0x3f;}
   void setFrom(unsigned int from) {m_Move &= ~0xfc0; m_Move |= (from & 0x3f) << 6;}
   ...
 
   bool isCapture() const {return (m_Move & CAPTURE_FLAG) != 0;}
   ...
 
   unsigned int getButterflyIndex() const {return m_Move & 0x0fff;}
   bool operator==(CMove a) const {return (m_Move & 0xffff) == (a.m_Move & 0xffff);}
   bool operator!=(CMove a) const {return (m_Move & 0xffff) != (a.m_Move & 0xffff);}
 
   unsigned short asShort() const {return (unsigned short) m_Move;}
 
protected:
   unsigned int m_Move; // or short or template type
};

Various Encodings and Decorations

Algebraic Notation

Based on Philipp Stamma's short Algebraic chess notation, a move can be described by the moving piece code and destination square. In case of disambiguating moves if two (or more) identical pieces can move to the same square, the file of departure, or if files are identical as well, the rank or both file and rank are given. A capture move, denoted by the symbol 'x' (takes) does not explicitly specify the captured piece and requires a look to the board as well.

Chess programs usually use algebraic notations concerning the user interface and Portable Game Notation - for appropriate conversion they have to deal with disambiguating source squares, that is need to be aware of all other moves of this piece-kind to the destination square to determine whether the from square needs additional file and/or rank information despite the moving piece.

Direction-Target

Another move encoding alternative motivated by direction wise target square serialization in bitboards is not to use the from-square but target square and direction. While the information is non-ambiguous it needs some effort with ray-lookup and bitscan to determine the from-square.

Check Flag

It might be interesting to determine whether a move gives check in advance during generation time, to possibly score them higher for move ordering, i. e. to don't reduce or even extend them, and also to safe in check detection after make move. However, as mentioned, lazy move generation is required, to delay acquisition of information until it is really needed, which might be never in case of Cut-nodes. Additionally an early determined checking move, even if failing high, usually implies a huge sub-tree due to check extensions, while an early non checking moves likely makes a cheaper cutoff for most futile Cut-nodes. Therefor, determining checking moves in advance is not that recommended for most board-representations.

Move Index

If the generated moves inside a move list are deterministic, one may encode moves as relative list index. Since the maximum number of moves per positions seems 218 ^[1] ^[2] , one byte is enough to index the move. This encoding was used in early game databases.

Two Positions with 218 Moves each		A. Dickins (1968) ^[3]

R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1		3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1

Move Enumeration

Based on Influence Quantity of Pieces one may enumerate all moves, to specify a unique determined move number with respect to moving piece, from- and to squares, captured piece (if any) and promoted piece inside a 16-bit range.

Pawn Moves

Move Kind	Ranks	Files	Directions	Target Combinations	Cardinality
Pushs	5	8	1	1	40
Promotions	1	8	1	4	32
Double Pushs	1	8	1	1	8
Total Pushs	6	8	1	1+2/3	80
Captures	5	7	2	5	350
Captures & Promotions	1	7	2	4*4 ^[4]	224
En passant	1	7	2	1	14
Total Captures	6	7	2		588
Total Pawns	6		3		668

Piece Moves

Reversible and Captures, Influence Quantity of Pieces times six target combinations for empty and five possible capture targets.

Piece	Influence Quantity	Cardinality
Knight	336	2016
King	420	2520
Bishop	560	3360
Rook	896	5376
Queen	1456	8736
Total	3668	22008

All Moves

Sheet of all moves, considering Castling (but no null move):

Piece	Move Kind	From-To	None	Captures	per Side	Total
Pawn	Promotions	8	32	-	32	64
	Captures & Promotions	14	-	224	224	448
	Double Pushs	8	8	-	8	16
	Pushs	40	40	-	40	80
	Captures	70	-	350	350	700
	En passant	14	-	14	14	28
	Total		80	588	668	1336
King	Castles	2	2	-	2	4
		420	420	2100	2520	5040
	Total		422	2100	2522	5044
Knight		336	336	1680	2016	4032
Bishop		560	560	2800	3360	6720
Rook		896	896	4480	5376	10752
Queen		1456	1456	7280	8736	17472
	Total		3248	16240	19488	38976
Total			3750	18928	22678	45356

Forum Posts

Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005
max amount of moves from a position? by Srdja Matovic, CCC, June 10, 2011 » Chess Maxima
Contest: Find Position with the most moves by Charles Roberson, CCC, December 09, 2011
Move encoding by Russell Reagan, CCC, April 21, 2014
Killer and move encoding by Fabio Gobbato, CCC, August 14, 2014 » Killer Heuristic

External Links

Move Representation - Computer Architecture and Languages Laboratory, University of Maribor

References

^ Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005
^ max amount of moves from a position? by Srdja Matovic, CCC, June 10, 2011
^ Re: max amount of moves from a position? by Árpád Rusz, CCC, June 11, 2011
^ PxP not possible during promotion, therefore only four capture targets

What links here?

Page	Date Edited
Algebraic Chess Notation	Sep 25, 2017
Andrew Shapira	May 7, 2017
C	Feb 19, 2018
Chess	Jan 21, 2018
Chess Position	Sep 10, 2017
Copy-Make	May 23, 2017
Data	Nov 26, 2017
Encoding Moves	Mar 27, 2016
Fabio Gobbato	Mar 6, 2015
Game Notation	Jan 11, 2018
Incremental Updates	Sep 6, 2017
Influence Quantity of Pieces	Jul 21, 2017
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
Make Move	Mar 2, 2016
MicroChess	Jul 14, 2015
Mini Chess	Jun 7, 2013
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Moves	Feb 19, 2018
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
Origin Square	Oct 10, 2016
Othello	Jan 4, 2018
Pawn Pushes (Bitboards)	Apr 5, 2013
Pieces versus Directions	Oct 6, 2016
Promotions	Jun 6, 2017
Scid	Apr 15, 2017
Sliding Pieces	Aug 3, 2017
Target Square	Oct 26, 2017
Unmake Move	Jun 10, 2017
Vice	Mar 8, 2016
Warren D. Smith	Sep 12, 2015

Up one Level

Faker

GerdIsenberg — Sat, 11 Nov 2017 09:14:51 GMT

Home * Evaluation * Pawn Structure * Faker

		Faker, a "faked" candidate with more opponent sentries than own helpers ^[1] ^[2]. The opponent sentries control the stop square (or tele-stop) of the faker, while the helpers defend the appropriate squares. If the number of helpers becomes equal (for instance due to a pawn-capture) the faker becomes a real candidate. A faker should not receive a candidate bonus, but is not that bad as a backward pawn. Also two opponent sentries which control the same stop square, leave a hole between both sentries, which might be considered elsewhere.
Faker c4, two sentries, but only one helper

External Links

Pawn Power in Chess by Hans Kmoch - Glossary of Terms - Chess Forums - Chess.com

Fake

Fake News

References

^ Hans Kmoch (1959, 1990). Pawn Power in Chess. New York: Dover, 1990. Previous ed.: New York: McKay, 1959. ISBN 0-486-26486-6
^ Pawn Power in Chess by Hans Kmoch - Glossary of Terms - Chess Forums - Chess.com

What links here?

Page	Date Edited
Backward Pawn	May 5, 2017
Backward Pawns (Bitboards)	May 5, 2017
Candidate Passed Pawn	Nov 11, 2017
Candidates (Bitboards)	Nov 11, 2017
Coiled	Mar 12, 2017
Dictionary	Aug 24, 2017
Faker	Nov 11, 2017
Hidden Passed Pawn	Nov 11, 2017
Pawn Structure	Oct 2, 2017

Up one Level

Wikispaces : chessprogramming - items matching description

Aegon 1993

Table of Contents

Final Standing

Selected Games

Bronstein

Quadruple pawns

Reports

External Links

References

What links here?

Alexander Szabo

Table of Contents

Tech 3

TechMate

The Technology Curve

WAC 230

Selected Publications

Forum Posts

External Links

References

What links here?

Alexandre Linhares

Table of Contents

The Nature of Chunks

See also

Selected Publications

External Links

References

What links here?

Backward Pawns (Bitboards)

Table of Contents

Backward

Straggler

Telestop Weakness

Dynamic Backwardness

A further Pass

Stops with negative SEE

See also

Publications

Forum Posts

External Links

References

What links here?

Behting Study

Table of Contents

Forum Posts

External Links

What links here?

Bill Gosper

Table of Contents

Robert Q

HAKMEM

HAKMEM 70

HAKMEM 169

HAKMEM 175

Gosper's Glider Gun

See also

Selected Publications

External Links

References

What links here?

Blockage Detection

Table of Contents

Search Application

Ram Fence

Blockage with Dynamic Pawns

See also

Publications

Forum Posts

References

What links here?

Candidate Passed Pawn

Table of Contents

See also

Forum Posts

External Links

References

What links here?

CHAOS