Wikispaces : chessprogramming - items matching description

Home * Programming * Graphics Programming * 2D Graphics Board

2D Graphics Board,
a 2D graphics image of a chessboard and the pieces of a chess position on a computer display, either fullscreen or board window of a chess GUI, or printer, similar to a chess diagram in print media. A 2D board window should be isotropic and quadratic, with all squares of same size.

Screenshots

Mac Hack

Mac Hack, DEC 340 display, 1968 ^[1] ^[2]

GNU Chess

GNU Chess on XBoard ^[3]

MChess

M-Chess Pro 3.5 (1993) ^[4]

IsiChess

IsiChess 2D board with vector graphics

Drawing Pieces

2D Vector Graphics

		The C++ code is based on the Windows Microsoft Foundation Class Library, a class extension of the Device Context of the Graphics Device Interface ^[5] , in conjunction with "handmade" polygons with coordinates in a x- and y-range of ±16 (positive values right and down), is used in IsiChess to apply vector graphics to draw the pieces in the board window or as figurine notation. For each piece an array of connected lines is declared, the first one a closed polygon, which is filled by the piece color ^[6] :

/* Piece Coordinates */
static POINT KnightPoint0[] = {
   { 10, 12},{ 11,  2},{ 10, -3},{  8, -6},
   {  6, -8},{  4, -9},{  1,-11},{  0,-12},
   { -1,-11},{ -2,-11},{ -3,-12},{ -3,-10},
   { -5, -8},{ -6, -6},{ -8,  0},{-10,  2},
   {-10,  4},{ -8,  6},{ -6,  5},{ -5,  4},
   { -4,  2},{ -2,  1},{ -1,  0},{  0, -2},
   { -1,  0},{ -1,  2},{ -2,  4},{ -6,  8},
   { -8, 12},{ 10, 12}
};
 
static POINT KnightPoint1[] = { { -3, -7},{ -4, -6} };
static POINT KnightPoint2[] = { { -8,  2},{ -9,  3} };
 
static POINT BishopPoint0[] = {
...
 
struct PIECEPOLY {
   unsigned int nPoints;
   const POINT *Points;
};
 
static PIECEPOLY KnightPoly[] = {
   {sizeof (KnightPoint0) / sizeof (KnightPoint0[0]), KnightPoint0},
   {sizeof (KnightPoint1) / sizeof (KnightPoint1[0]), KnightPoint1},
   {sizeof (KnightPoint2) / sizeof (KnightPoint2[0]), KnightPoint2}
};
...
 
struct PIECEIMAGE {
   int nPolys;
   PIECEPOLY *Poly;
};
 
static PIECEIMAGE PieceImage[] = {
   {0,  NULL},
   {sizeof (PawnPoly)   / sizeof (PawnPoly  [0]),  PawnPoly},
   {sizeof (BishopPoly) / sizeof (BishopPoly[0]),  BishopPoly},
   {sizeof (KnightPoly) / sizeof (KnightPoly[0]),  KnightPoly},
   {sizeof (RookPoly)   / sizeof (RookPoly  [0]),  RookPoly},
   {sizeof (KingPoly)   / sizeof (KingPoly  [0]),  KingPoly},
   {sizeof (QueenPoly)  / sizeof (QueenPoly [0]),  QueenPoly},
   {0,  NULL},
};
 
/* Drawing implemented as extension of Windows MFC Device Context Class CDC */
void CIsiDC::drawPiece(const CRect &r, int piece) {
   drawPiece(r, piece, m_sPieceColor[piece&1], m_sPieceBorderColor[piece&1]);
}
 
void CIsiDC::drawPiece(const CRect &r, int piece, COLORREF piececolor, COLORREF pencolor) {
   CPen pen(PS_SOLID, 1, pencolor);
   CBrush brush(piececolor);
   CPen* pOldPen = SelectObject(&pen);
   CBrush* pOldBrush = SelectObject(&brush);
 
   PIECEIMAGE *pim = PieceImage + (piece >> 1);
   int i; PIECEPOLY  *p;
   for (i=0, p = pim->Poly; i < pim->nPolys; ++i, ++p) {
      POINT points[64];
      transformPoints (points, p->Points, p->nPoints, r);
      if (i == 0) { /* closed polygon */
         BeginPath();
         Polyline(points, p->nPoints);
         EndPath();
         FillPath();
      }
      Polyline(points, p->nPoints);
   }
   SelectObject(pOldBrush);
   SelectObject(pOldPen);
}
 
void CIsiDC::transformPoints (POINT* target, const POINT* source, int nPoints, const CRect &r) {
   int width = r.Width();
   int height = r.Height();
   CPoint center = r.CenterPoint();
   while (nPoints--)
      *target++ = transfrom (*source++, width, height, 32, center);
}
 
POINT CIsiDC::transfrom (const POINT &c, int scalx, int scaly, int qxy, const POINT &trans) {
   return CPoint((c.x*scalx)/qxy, (c.y*scaly)/qxy) + trans;
}

Bitmaps

A more common way is to display pieces in form of bitmaps or pixmaps, small images of pieces, painted with an external program such as GIMP, Paint etc., stored as Raster graphics in an external file or resource format, such as Portable Network Graphics ^[7] or Windows BMP file format, which may be used in conjunction with Bit blit for scaling.

Unicode

An alternative technique for piece drawing is the use of Chess symbols in Unicode as scalable TrueType fonts ^[8] ^[9] ^[10]:

Publications

Oliver Vornberger (2006). Computergrafik. pdf (German)
Leen Ammeraal and Kang Zhang (2007). Computer Graphics for Java Programmers, 2nd Edition, ISBN-13: 978-0-470-03160-5 / ISBN-10: 0-470-03160-3 by John Wiley

Forum Posts

Unicode values for chessmen by Steven Edwards, CCC, March 07, 2011
Piece graphics by Harm Geert Muller, CCC, October 19, 2015 » XBoard
MinGW AlphaBlend by Harm Geert Muller, CCC, November 29, 2016 » WinBoard, Windows ^[11] ^[12]

External Links

Coordinates

Geometric primitives

Toolkits, Libraries and APIs

References

^ I resign by Lawrence J. Krakauer
^ Chess stories by Lawrence J. Krakauer
^ XBoard from Wikipedia
^ Studie: Schachspielen mit ein 286er 12 MHz Laptop - Schachcomputer.info Community by Spacious Mind, May 22, 2010 (German)
^ CDC Class - Device Context, Microsoft Foundation Class Library, MSDN
^ Code by Gerd Isenberg, written in about 2000
^ File:Chess bdl40.png - Wikimedia Commons
^ Unicode values for chessmen by Steven Edwards, CCC, March 07, 2011
^ Miscellaneous Symbols – Test for Unicode support in Web browsers
^ Unicode representations of Chess symbols in two fonts (Arial Unicode MS and Tahoma) by Monedula, Wikimedia Commons
^ Alpha compositing from Wikipedia
^ MinGW from Wikipedia

What links here?

Page	Date Edited
2D Graphics Board	Sep 23, 2017
3D Graphics Board	Sep 23, 2017
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
Arts	Nov 5, 2017
Bookbuilder	Feb 4, 2018
Brainless (Forth)	Jun 24, 2017
Chess 2013	Nov 6, 2013
Chess Academy	Jan 15, 2014
Chessboard	May 10, 2017
Chessmaster	Jan 21, 2018
David Hendricks	Aug 20, 2017
Delfi	Jan 7, 2016
Dreamer	Aug 5, 2015
EGA Chess	Nov 30, 2017
Grandmaster Chess	Dec 7, 2016
Graphics Programming	Dec 22, 2017
GUI	Mar 16, 2018
Intelligent Chess	Apr 14, 2013
JavaScript	Dec 11, 2017
John T. Bell	Aug 20, 2017
Jose	Feb 26, 2015
Lawrence J. Krakauer	Oct 9, 2013
Majestic Chess	Jan 20, 2018
Maurizio Monge	Nov 27, 2015
Millennium Chess System	Jul 12, 2017
Pieces	Feb 19, 2018
Psi Chess	Aug 1, 2016
TechMate	Aug 23, 2014
The Final Chesscard	Apr 7, 2013
The Sniper	Jun 3, 2016
Vektor3	Feb 17, 2015
WinBoard	Mar 4, 2018
Windows	Nov 2, 2017
XBoard	Jan 21, 2018

Up one Level

3D Graphics Board

GerdIsenberg — Sat, 23 Sep 2017 11:20:49 GMT

Home * Programming * Graphics Programming * 3D Graphics Board

		3D Graphics Board, a 3D graphics projection of a 3D model of a chessboard and the pieces of a chess position to the two dimensional surface of a computer display, either as fullscreen or board window of a chess GUI, or printer. For simplicity, some programs or 3D capable GUIs combine vector graphics for drawing the board with raster graphics for drawing the pieces. A perspective center projection applies for the board, where farther square trapezoids are scaled smaller, while a orthographic projection applies for the pieces, i.e. drawing fixed sized piece-bitmaps with 3D-effect. More sophisticated implementations use 3D vector graphics in the wire-frame model for the projection, and 2D raster graphics in the rendered display, and feature a variable camera's position, angle of view, field of view, may rotate the object around various axis, apply ray tracing with one or more light sources for photorealistic shading with shadow and reflection effects, and perform more or less sophisticated animations of piece movements. A full perspective projected 3D board requires additional hardware and software resources, such as sophisticated graphic cards with GPUs and 3D graphic libraries or frameworks like OpenGL or Direct3D as subset of the DirectX collection.
A rendered 3D animation ^[1]

Ergonomics

Despite the more challenging task for the GUI or graphics programmer and progress to simulate the view on a real chessboard, the 3D Board is usually harder to grasp for a human chess player than good 2D Boards. Pieces and specially pawns are often partly covered by pieces in front, and movement of head and eyes of the chess player lack the same visual feedback as looking on a real chess board. Therefor 3D Boards are often featured in mass market products and some programs where authors are interested in 3D graphics programming. The really sophisticated 3D boards of Chessmaster and Fritz are eye catchers and rich of features, but rarely used for serious playing.

Screenshots & Images

Early 3D Boards


Colossus Chess 4.0 3D chessboard ^[2]		Cyrus II 3D screen ^[3]

Chessmaster

Chessmaster XI - House of Staunton chess sets ^[4]

ChessPartner

ChessPartner 6, 3D pieces ^[5]

KnightCap

KnightCap's 3D Board ^[6] ^[7]

Nemeton

Nemeton3D 1.51 with its 3D Graphics Board ^[8]

Uragano 3D

Uragano 3D board ^[9]

Publications

Nina Amenta, Yong Joo Kil (2005). Defining Point-Set Surfaces. pdf ^[10]
Oliver Vornberger (2006). Computergrafik. pdf (German)
Leen Ammeraal and Kang Zhang (2007). Computer Graphics for Java Programmers, 2nd Edition, ISBN-13: 978-0-470-03160-5 / ISBN-10: 0-470-03160-3 by John Wiley
Eric Lengye (2011). Mathematics for 3D Game Programming and Computer Graphics, Third Edition. ISBN-13: 978-1435458864, amazon.com

Forum Posts

Re: Going commercial, maybe by Andrew Tridgell, rgcc, March 9, 1997 » KnightCap

External Links

Basics

Projection

3D Graphics API and Frameworks

3D-Editors

Ardor3D from Wikipedia
Autodesk 3ds Max
MeshLab from Wikipedia
MeshLab
Blender (software) from Wikipedia
Blender 3D: MemoBook - Wikibooks
Code archives/3D Graphics - Mesh/3D chessboard Rotational solids editor using example by Matt Merkulov, March 15, 2007 » Blitz BASIC
Pointshop3D developed at the Computer Graphics Lab at ETH Zurich
ShiVa from Wikipedia

Tutorials

3D Chess

Chessmaster

Chessmaster 10th Edition - PC Review at IGN by Steve Butts, August 26, 2004

Fritz GUI

Kasparov takes on X3D Fritz in November!, ChessBase News, July 14, 2003 » Kasparov versus X3D Fritz 2003
Kasparov vs X3D Fritz match finishes 2-2 after game four draw, ChessBase News, November 19, 2003
Fritz 9 3D boards – part 1 by Steve Lopez, ChessBase News, January 10, 2006
Fritz 9 3D boards – part 2 by Steve Lopez, ChessBase News, January 17, 2006
Fritz 9 3D boards – part 3 by Steve Lopez, ChessBase News, January 25, 2006
Spider-Man, Aliens and Fritz chess sets, ChessBase News, June 23, 2006
Fritz 3D Board, Chess.com

References

^ Image selfmade with Blender, Author: J.A. Freyre, January 22 2006, CC BY-SA 2.5, Wikimedia Commons
^ Colossus Chess from Wikipedia
^ Cyrus II - World of Spectrum
^ PC-Screenshots | Chessmaster XI: The Art of Learning | Ubisoft
^ ChessPartner Screen shots | ChessPartner - Lokasoft - Home of ChessPartner
^ Welcome to the KnightCap home page
^ Re: Going commercial, maybe by Andrew Tridgell, rgcc, March 9, 1997
^ Nemeton3D 1.51 by Stan Arts, CCC, June 04, 2017
^ Home page Uragano 3D
^ Pointshop3D developed at the Computer Graphics Lab at ETH Zurich

What links here?

Page	Date Edited
2D Graphics Board	Sep 23, 2017
3D Graphics Board	Sep 23, 2017
Andrew Tridgell	Aug 3, 2015
Battle Chess	Dec 12, 2016
Chess Academy	Jan 15, 2014
Chessboard	May 10, 2017
Chessmaster	Jan 21, 2018
ChessPartner	Nov 13, 2017
Colossus Chess	Dec 10, 2017
Corel Chess	Dec 7, 2016
Cyrus	Jul 22, 2014
Disney's Aladdin Chess Adventures	May 15, 2014
Dreamer	Aug 5, 2015
Forsyth-Edwards Notation	Sep 10, 2017
glChess	Aug 18, 2017
Grandmaster Chess	Dec 7, 2016
Graphics Programming	Dec 22, 2017
GUI	Mar 16, 2018
JavaScript	Dec 11, 2017
Jose	Feb 26, 2015
Kasparov versus X3D Fritz 2003	Aug 17, 2016
KnightCap	Nov 6, 2016
Majestic Chess	Jan 20, 2018
Millennium Chess System	Jul 12, 2017
Nemeton	Dec 23, 2017
Neurosis	Dec 23, 2017
Pandix	Feb 4, 2017
Psi Chess	Aug 1, 2016
Psion	Mar 20, 2017
PT 51	Oct 5, 2017
Stan Arts	Nov 21, 2014
The Sniper	Jun 3, 2016
Treebeard	Mar 25, 2015
Uragano	Oct 2, 2017
Virtual Chess	Mar 25, 2017
Virtual Kasparov	May 20, 2012
XChess	Sep 9, 2015

Up one Level

Algol

GerdIsenberg — Sat, 01 Feb 2014 10:56:18 GMT

Home * Programming * Languages * Algol

		Algol (short for ALGOrithmic Language) is a family of imperative computer programming languages developed jointly by a committee of European and American computer scientists in a meeting in 1958 at ETH Zurich (Algol 58). Algol 58 introduced code blocks and the begin and end pairs for delimiting them. Two years later, Algol 60 was specified, as the result of a meeting in Paris in January 1960 by 13 European and American scientists, Peter Naur, John Backus, John McCarthy, Friedrich L. Bauer, Adriaan van Wijngaarden, et al. Algol 60 became the standard for the publication of algorithms and had a profound effect on future language development, it was the first language implementing nested function definitions with lexical scope. Algol 68 was designed by IFIP, while Niklaus Wirth based his own Algol W ^[1] on Algol 60 before moving to develop Pascal.
Algol rotation ^[2]

Algol W

Selected Publications

External Links

References

What links here?

Algol W

A boolean procedure in Algol W from the chess program Awit by Tony Marsland ^[3] :

11662 LOGICAL PROCEDURE CLEAR(INTEGER VALUE SQA, SQF, SQT);
11663 BEGIN
11664   INTEGER DIR;
11665   LOGICAL FREE;
11666   FREE := FALSE;
11667   DIR := BOTV(EDGE, OFFSET(SQF)−OFFSET(SQT));
11668   IF DIR ~= 0 THEN BEGIN
11669     FREE := TRUE;
11670     IF SQA ~= SQF AND
11671        DIR = BOTV(EDGE, OFFSET(SQA)−OFFSET(SQT))
11672     THEN FREE := FALSE;
11673     FOR SQ := SQF+DIR STEP DIR UNTIL SQT−DIR
11674     DO IF FREE AND BRD(SQ) ~= 0
11675       THEN FREE := FALSE;
11676   END;
11677   FREE
11678 END CLEAR;

Selected Publications

Christopher Strachey, Maurice Wilkes (1961). Some Proposals for Improving the Efficiency of ALGOL 60. Communications of the ACM, Vol. 4, No. 11
V. I. Sobel'man, Mikhail R. Shura-Bura (1962). Realization of recursive procedures in the language of AlGOL-60. (Реализация Рекурсивных Процедур В Языке Алгол-60) Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, Vol. 2, No. 2

External Links

ALGOL from Wikipedia
ALGOL 58 from Wikipedia
ALGOL 60 from Wikipedia
ALGOL 68 from Wikipedia
History of ALGOL — Software Preservation Group from The Computer History Museum
Revised Report on the Algorithmic Language ALGOL 68
ALGOL W from Wikipedia
Трансляторы с Алгола-60 - № 45, 1999 Computerworld Россия (Russian)
aw2c Algol W Compiler - aw2c correctly compiles Tony Marsland's computer chess player Awit
A Case against the GO TO Statement by Edsger W. Dijkstra, transcribed by Guy Haworth
Algol (β Per, Beta Persei) from Wikipedia

References

^ Algol W Language Description (pdf)
^ Algol (β Per, Beta Persei) from Wikipedia
^ Awit Source code in Algol W by Tony Marsland (pdf)

What links here?

Page	Date Edited
ACM 1970	Jun 13, 2015
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
Alex Bell	Mar 1, 2017
Algol	Feb 1, 2014
Atlas	Nov 5, 2017
Awit	Dec 22, 2017
Chess 0.5	Nov 20, 2016
CMU Chess Program	Oct 6, 2014
Coen Zuidema	Mar 25, 2016
Computerworld	Sep 9, 2017
IFIP	Aug 20, 2014
Jerusalem CC Tournament 1978	Jan 3, 2018
John Birmingham	Jan 7, 2016
Languages	Nov 26, 2017
M-20	Oct 9, 2013
Master	Dec 28, 2017
Matthias Engelbach	Jan 7, 2016
Mikhail R. Shura-Bura	Oct 30, 2013
Nova	Jan 20, 2016
Orwell	Dec 31, 2017
Pascal	Nov 28, 2016
Peter Kent	Jan 7, 2016
PL 1	Jan 20, 2016
Schach	Jan 7, 2016
Schach (US)	Jul 21, 2016
Shy	Jul 19, 2016
Stack	Nov 18, 2016
Thomas Kreitmair	Feb 12, 2016
Tony Marsland	Nov 27, 2017
TR-4	Aug 27, 2014
Victor Vikhrev	Jan 7, 2016
WCCC 1974	Jan 19, 2018
WCCC 1977	Dec 22, 2017
WCCC 1983	Jan 20, 2018
WCCC 1986	Jul 27, 2017

Up one Level

Algorithms

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

Home * Programming * Algorithms

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

General Concepts

Sorting and Searching

Enumeration and Backtracking

Mathematical Optimization

Combinatorial

Publications

1960 ...

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

1970 ...

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

1980 ...

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

1990 ...

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

2000 ...

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

2010 ...

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

External Links

Algorithms

Algebra and Calculus

Graphics

Linear Programming

Sorting and Searching

Complexity

Misc

References

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

What links here?

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

Up one Level

Avoiding Branches

GerdIsenberg — Fri, 16 Dec 2016 19:27:41 GMT

Abs, Max, Min

Absolute value of an Integer

Maximum of two Integers

By CRT

By Sign-Mask

Minimum of two Integers

By CRT

By Sign-Mask

Conditional Expressions

Conditional Assignment

Conditional Increment

Home * Programming * Optimization * Avoiding Branches

Miss-predicted branches causes huge penalties on todays super pipelined processors. While processors become smarter to predict branches with several heuristics, branches on random data should be avoided.

The techniques shown here often use arithmetical shift right (by bit-width - 1, that is 31 for 32-bit double words as integers) to determine a mask of sign-bits, either all bits set (-1) or all bits clear 0. x86 compiler may emit an cdq (Convert Double to Quad) instruction, which sign extends a 32 bit register to two 32 bit registers. Since arithmetical shift right is not strictly specified in C, it might be not portable through all compilers and architectures. Note that in C, a comparison or a boolean expression with the result {false, true} might be treated as numerical value {0, 1}.

Abs, Max, Min

It is recommend to use functions provided by the programming language. In C or C++ one should use appropriate compiler intrinsics and/or template functions provided by the C Runtime Library or Standard Template Library.

The tricks shown here, might be useful if compiler don't support those functions or don't generate the intended branchless assembly and the input is quite random, so that the branch prediction heuristics will fail often.

Absolute value of an Integer

Abs as C intrinsic ^[1] is likely implemented based on following code snippet ...

int abs(int a) {
   int s = a >> 31; // cdq, signed shift, -1 if negative, else 0
   a ^= s;  // ones' complement if negative
   a -= s;  // plus one if negative -> two's complement if negative
   return a;
}

... by compilers, on x86 a sequence three instructions: {cdq, xor, sub} or {cdq, add, xor}.

Maximum of two Integers

By CRT

Microsoft Visual C Run-Time Library provides a _max macro ^[2].

By Sign-Mask

Following trick only works for a reduced integer range of effectively one bit less, which is most often no problem for 32-bit integers in chess programs, like scores and that like: INT_MIN <= a - b <= INT_MAX:
If a is greater b, a - 0 is returned, otherwise a - (a - b) == +b

int max(int a, int b) {
  int diff = a - b;
  int dsgn = diff >> 31;
  return a - (diff & dsgn);
}

Minimum of two Integers

By CRT

Microsoft Visual C Run-Time Library provides a _min macro ^[3].

By Sign-Mask

int min(int a, int b) {
  int diff = a - b;
  int dsgn = diff >> 31;
  return b + (diff & dsgn);
}

Conditional Expressions

Conditional Assignment

A conditional assignment in C or C++ may be implemented by compilers as x86 conditional move (cmovCC) instruction.

x = ( a > b ) ? C : D;

otherwise it might be reformulated with conditional increment:

x = D;
if ( a > b ) x += C - D;

Conditional Increment

If a > b is hard to predict,

if ( a > b ) x += C;

it might be reformulated branch-less in C, which likely emits a x86 setCC instruction:

x += -( a > b ) & C; // with any boolean expression

With a reduced value range and INT_MIN <= b - a <= INT_MAX, greater and less relations might be implemented using a sign mask:

x += (( b - a ) >> 31) & C;

Conditional Write

During list generation, while conditionally writing data to an array with post-incrementing a pointer or index, one may try to avoid the conditional branch by storing always and to increment the pointer by the condition, which is either 0 or 1 ^[4] ^[5].

if (a > b)
  *ptr++ = value;

might be rewritten by

  *ptr = value;
  ptr += (a > b);

Indirect Branch

Robert Hyatt on x86 Branch predictor, Branch target predictor, and Indirect branch in CCC ^[6]:

There are two parts to predicting a branch on x86. 1. Is the branch taken (for a call it is always "yes")? 2. Where is the branch going? (2) is more interesting because when you fetch and then predict the branch, you don't have a clue where it is going since the register being used might not yet be ready for access. The solution is a "branch target buffer" which simply predicts the branch AND where it is going, based on the last time it was encountered. You can do a conditional jump to an indirect address and predict the jump correctly and miss the address (entire thing is then predicted wrong) or you can predict the address correctly and miss the jump (again, entire thing is wrong), or you can miss both. Only when you get both right do you have any success. Your code always jumps to the same place, whether you use the explicit jump address, or the indirect address through a register. When you get into a call where the address changes, performance will drop. Your code really is not testing that at all...

Forum Posts

branch misprediction by Eric Oldre, CCC, July 14, 2004
Re: Fruit 2.0 Toga : Recapture extension by Gerd Isenberg, CCC, March 19, 2005
Re: Function pointers hurt performance? by Robert Hyatt, CCC, September 22, 2011
Branch-poor looping by Harm Geert Muller, CCC, September 02, 2015
Mispredicted branch VS cache miss by Natale Galioto, CCC, September 09, 2015
Tipical cache and branch misses for a chess engine by Nicu Ionita, CCC, September 14, 2016 » Memory, Profiling

External Links

Compute the integer absolute value (abs) without branching by Sean Eron Anderson
Compute the minimum (min) or maximum (max) of two integers without branching by Sean Eron Anderson
Programming Optimization by Paul Hsieh
Avoiding the Cost of Branch Misprediction - Intel® Software Network by Rajiv Kapoor, February 20, 2009
Branch (computer science) from Wikipedia
Branch table
Indirect branch
Conditional (programming)
Branch predictor
Branch target predictor
Defunkt - Avoid The Funk, Live at Drom, April 14, 2010, YouTube Video
lineup: Joe Bowie, Ronny Drayton, Bill Bickford, Kim Clarke, John Mulkerin, Kenny Martin

References

^ abs, _abs64 Visual C++ Developer Center - Run-Time Library Reference
^ _max Visual C++ Developer Center - Run-Time Library Reference
^ _min Visual C++ Developer Center - Run-Time Library Reference
^ Software Optimization Guide for AMD Family 10h and 12h Processors (pdf) see pp. 102 on Conditional Write
^ Write-combining from Wikipedia
^ Re: Function pointers hurt performance? by Robert Hyatt, CCC, September 22, 2011

What links here?

Page	Date Edited
ARM2	Dec 16, 2016
Avoiding Branches	Dec 16, 2016
Bitboard Board-Definition	Jun 23, 2014
Center Manhattan-Distance	Nov 26, 2016
Classical Approach	Jan 28, 2018
DirGolem	Jun 5, 2016
Distance	Sep 25, 2015
Dumb7Fill	May 27, 2016
Files	Nov 22, 2015
KBNK Endgame	Nov 26, 2016
Knight-Distance	Oct 20, 2013
Manhattan-Distance	May 19, 2014
Max	Dec 23, 2017
MAX (Gillogly)	Sep 1, 2013
Memory	Dec 8, 2017
Nicu Ionita	May 3, 2017
Optimization	Feb 28, 2018
Profiling	Sep 15, 2016
Programming	Dec 16, 2017
Ranks	Dec 15, 2008
Square Attacked By	Jan 20, 2018
SSE2	Feb 27, 2018
Static Exchange Evaluation	Dec 14, 2017
Table-driven Move Generation	Feb 19, 2017

Up one Level

Backtracking

GerdIsenberg — Sat, 16 Dec 2017 08:48:38 GMT

Home * Programming * Algorithms * Backtracking

		Backtracking is a general search algorithm for finding solutions of certain computational problems. It incrementally builds candidates to a solution, and "backtracks" a partial candidate as soon as it determines it cannot become member of the solution. Therefor backtracking algorithms, most often implemented as recursive depth-first algorithm, are not considered brute-force, and have the advantage of potentially requiring a search tree with less nodes.
Eight queens puzzle ^[1]

History

Bitner and Reingold ^[2] credit Derrick H. Lehmer with first using the term 'backtrack' in the 1950s, but it has been discovered and rediscovered many times. Robert J. Walker ^[3] was the first who called using a well-known depth-first procedure Backtracking in 1960.

Applications

Classic examples of using backtracking algorithms are solving Exact cover problems and Tour puzzles, like the Eight queens puzzle, the Knight's tour puzzle and other Maze or Labyrinth puzzles. Knuth's Algorithm X along with Dancing Links finds all solutions to an exact cover problem. Backtracking is further applied to solving Constraint satisfaction problems, such as Crossword puzzles, Sudoku, Pentomino tiling, boolean satisfiability problems and other NP-complete problems. Logic programming languages such as Prolog internally use backtracking to generate answers.

De Bruijn sequences

A further sample is to find De Bruijn sequences, as demonstrated by the recursive De Bruijn Sequence Generator. Here early partial candidates may be discarded if the lock indicates a new six-bit number already occured before.

Looking for Magics

Unfortunately, looking for magics to find factors for the application of Magic Bitboards, seems not to fit into a class of these kind of problems. Here trial and error with spare populated, but otherwise randomly chosen numbers is used.

8Q in Bitboards

"Thinking" Bitboards, Gerd Isenberg made following Eight queens ^[4] ^[5] proposal, to traverse ranks as disjoint candidate sets for one queen each, with premature elimination of redundant tests ^[6] of squares already attacked by queens put on the board . Therefor, while serializing the set of not attacked candidate squares from one rank to put a queen on it, it maintains a "taboo" union set for consequent queens on upper ranks by "oring" queen attacks in north directions. It performs some optimization to keep the processed rank always the first, to only use a lookup array of queen attacks of that first rank, and to shift the taboo-set consecutively one rank down. A little space-time tradeoff saves the bitscan at the cost of some more memory to index the eight attacks from an sparse array of 129 bitboards with the single isolated bit inside one byte (the first rank).

Code

The sample C code demonstrates an iterative solution using arrays as explicit stacks on the stack:

typedef unsigned char U8;
 
/**
 * eightQueen Bitboard implementation
 * @author Gerd Isenberg
 * @date April 29, 2011
 */
void eightQueenBitboard( /*U64 taboo */ ) {
   U64 t[8];             /* stack of taboo bitboards */
   U8  q[8], c[8];       /* stack of queens and candidate squares */
   unsigned int p = 0;   /* ply, queen index 0..7 as "stack pointer" */
   t[0] = 0;             /* no square attacked so far (taboo) */
 
C: c[p] = ~(U8)t[p];     /* 1. rank squares not attacked */
   while ( c[p] ) {      /* while candidate squares */
      q[p] = c[p]&-c[p]; /* LS1B -> 1,2,4,8,16,32,64,128 */
      if ( p == 7 ) {
         print8Q( q );   /* solution found */
      } else {           /* "or" attacks to taboo, shift it  */
         t[p+1] = (t[p] | nAtt[q[p]]) >> 8; /* one rank down */
         ++p; goto C;    /* make "recursive call" iterative  */
R:       p--;
      }
      c[p] ^= q[p];      /* reset candidate square */
   }
   if ( p ) goto R;      /* return from iterative "call" */
}

Node Counts

The algorithm backtracks all 92 distinct Eight queen solutions. Using an if do-while else construct instead of while control structure allows counting "pruned" nodes, where the candidate set is initially empty in the else case, leaving following node statistics differentiated by ply (excluding the root):

Ply	Nodes	Pruned	Sum
0	8	0	8
1	42	0	42
2	140	0	140
3	344	0	344
4	568	18	586
5	550	150	700
6	312	256	568
7	92	220	312
Sum	2056	644	2700

Data and Print

The declaration of the north attack array to save a byte-wise bitscan, and for convenience the print routine used:

/**
 * north | nw | ne attacks of a queen on the 1. rank
 *
 * indexed by a first rank - bitboard
 * with one bit set, representing the file
 * 1,2,4,8,16,32,64,128
 */
static const U64 nAtt[130] = {
   0,
   C64(0x8141211109050300), /*   1 */
   C64(0x02824222120A0700), /*   2 */
   0,
   C64(0x0404844424150E00), /*   4 */
   0,0,0,
   C64(0x08080888492A1C00), /*   8 */
   0,0,0,0,0,0,0,
   C64(0x1010101192543800), /*  16 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x2020212224A87000), /*  32 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x404142444850E000), /*  64 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x8182848890A0C000), /* 128 */
   0
};
 
/**
 * printing 8q boards
 */
void print8Q( unsigned char q8[] ) {
   static int count=1;
   int r, f, b;
   printf("NQ %d\n", count++ );
   for (r=7; r >= 0; --r) { /* 8th rank top */
      for ( f=0, b=1; f < 8; ++f, b <<= 1) {
         printf("%c ", (q8[r] & b) ? 'Q' : '.');
      }
      printf("\n");
   }
   printf("\n");
}

N Queens

By Marcel van Kervinck

A very short and therefor slightly obfuscated, but elegant and tricky general backtracker in enumerating N Queen solutions is given by Marcel van Kervinck in two lines of C code, Version 2, 1996 ^[7], Bit-Twiddling as its best:

t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;e-=d,d=e&-e;f+=t(a-d,(b+d)*2,(
c+d)/2));return f;}main(q){scanf("%d",&q);printf("%d\n",t(~(~0<<q),0,0));}

By Tony Lezard

As mentioned by Marcel van Kervinck, a similar 8 Queen program was introduced by Tony Lezard in 1991 ^[8]:

static int count = 0;
 
void try(int row, int left, int right) {
   int poss, place;
   if (row == 0xFF) ++count;
   else {
      poss = ~(row|left|right) & 0xFF;
      while (poss != 0) {
         place = poss & -poss;
         try(row|place, (left|place)<<1, (right|place)>>1);
         poss &= ~place;
      }
   }
}
 
void main() {   
   try(0,0,0);
   printf("There are %d solutions.\n", count);
}

Publications

1960 ...

Robert J. Walker (1960). An Enumerative Technique for a Class of Combinatorial Problems. Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis, Richard E. Bellman and Marshall Hall, Jr., eds., American Mathematical Society, Providence, Rhode Island, pp. 91-94
Solomon W. Golomb, Leonard D. Baumert (1965). Backtrack Programming. Journal of the ACM, Vol. 12, No. 4
Martin Gardner (1969, 1991). The Unexpected Hanging and Other Mathematical Diversions. Simon & Schuster, University Of Chicago Press.
Chapter 16: The Eight Queens and Other Chessboard Diversions.

1970 ...

Mark B. Wells (1971). Elements of Combinatorial Computing. Pergamon Press, amazon.com
James R. Bitner, Edward M. Reingold (1975). Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11 ^[9]
Donald Knuth (1974). Estimating efficiency of backtrack programs. STAN-CS-74-442, CS-Department, Stanford University ^[10]
Donald Knuth (1975). Estimating the Efficiency of Backtrack Programs. Mathemathics of Computation, Vol. 29
Nissim Francez, Boris Klebansky, Amir Pnueli (1977). Backtracking in Recursive Computations. Acta Informatica Vol. 8, No. 2
John Gaschnig (1977). A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977
Hirosi Hitotumatua, Kohei Noshita (1979). A technique for implementing backtrack algorithms and its application. Information Processing Letters Vol. 8, No. 4
Gary Lindstrom (1979). Backtracking in a Generalized Control Setting. ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1

1980 ...

Paul Walton Purdom, Jr., Cynthia A. Brown, Edward L. Robertson (1981). Backtracking with Multi-Level Dynamic Search Rearrangement. Acta Informatica Vol. 15, No. 2
Oliver Vornberger, Burkhard Monien, Ewald Speckenmeyer (1986). Superlinear Speedup for Parallel Backtracking. Technical Report 30, University of Paderborn
Andrew Appel, Guy Jacobson (1988). The World’s Fastest Scrabble Program. Communications of the ACM, Vol. 31, No. 5, pdf » Scrabble

1990 ...

Ilan Vardi (1991). Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, ISBN 0201529890, amazon.com
Paul Walton Purdom, Jr. (1993). Backtracking and Probing. zipped ps
Matthew L. Ginsberg (1993). Dynamic Backtracking. JAIR Vol. 1
Patrick Prosser (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence, Vol. 9, No. 3, pdf
Richard Karp, Yanjun Zhang (1993). Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, Vol. 40, No. 3 ^[11]
Matthew L. Ginsberg, David McAllester (1994). GSAT and Dynamic Backtracking. KR 1994 ^[12]
Peter Sanders (1995). Better Algorithms for Parallel Backtracking. IRREGULAR 1995

2000 ...

Carla P. Gomes, Cèsar Fernández, Bart Selman, Christian Bessière (2004). Statistical Regimes Across Constrainedness Regions. CP 2004, pdf
Lukas Kroc, Ashish Sabharwal, Bart Selman (2008, 2011). Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. CPAIOR 2008, Annals of Operations Research, Vol. 184

2010 ...

Pablo San Segundo (2011). New decision rules for exact search in N-Queens. Journal of Global Optimization, Vol. 51, No. 3
Martin Gardner (2014). Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpected Hanging. The Mathematical Association of America / Cambridge University Press
Chapter 16: The Eight Queens and Other Chessboard Diversions.

Forum Posts

N-Queens number for large boards by Truman Collins, rgcm, January 30, 1997
N Queens Puzzle Algorithm by Aaron Alfer, CCC, December 15, 2017

External Links

References

^ Visual Example of the Eight Queens backtrack Algorithm, Wikimedia Commons, Eight queens puzzle from Wikipedia
^ James R. Bitner, Edward M. Reingold (1975). Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11
^ Robert J. Walker (1960). An Enumerative Technique for a Class of Combinatorial Problems. Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis, Richard E. Bellman and Marshall Hall, Jr., eds., American Mathematical Society, Providence, Rhode Island, pp. 91-94
^ Onur Demirörs, N. Rafraf, M.M. Tanik (1992). Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions. Journal of Recreational Mathematics, Vol. 24
^ Magic square from Wikipedia
^ John Gaschnig (1977). A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977
^ Queens ~ /etc/marcelk
^ 8 Queens (NO *SPOILER*) by Tony Lezard, rec.puzzles, November 18, 1991
^ The 70*70 Square Puzzle by Thomas Wolf
^ Re: Perft(15) estimate after averaging 800 MC samples by Daniel Shawul, CCC, November 21, 2013 » Perft
^ Branch and bound - Wikipedia
^ WalkSAT from WIkipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
Andrew Shapira	May 7, 2017
Backtracking	Dec 16, 2017
Bitboards	Nov 14, 2017
Brute-Force	Jul 27, 2017
David McAllester	May 23, 2016
De Bruijn Sequence Generator	Dec 1, 2016
Depth-First	Jun 25, 2016
Donald Knuth	Aug 29, 2016
Iteration	May 5, 2017
Iterative Search	Oct 20, 2016
John Gaschnig	Sep 5, 2012
José Antônio Fabiano Mendes	Feb 25, 2014
Kohei Noshita	Aug 21, 2014
Mathematician	Apr 9, 2018
Matthew L. Ginsberg	May 23, 2016
Pattern Recognition	Sep 8, 2017
Recursion	Nov 18, 2017
Search	Feb 1, 2018
Trial and Error	Feb 11, 2018
Zillions of Games	May 29, 2017

Up one Level

Butterfly Boards

GerdIsenberg — Tue, 27 Jan 2015 19:02:19 GMT

Home * Programming * Data * Butterfly Boards

		Butterfly Boards are two-dimensional arrays (typically of various history counters for each color), indexed by the from- and to-square coordinates of (valid and likely quiet) moves, which appear inside the search. Those counters can then be used for move ordering as mentioned in the history heuristic, or to decide about late move reductions and history leaf pruning. Another application is a kind of killer- or refutation table, to store a refutation of a specific move ^[1], also base of the countermove heuristic ^[2] ^[3].
M. C. Escher, Symmetry ^[4]

Layout

The size of the array is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most from- and to-square combinations are illegal moves by the rules of chess. Thus, most entries inside the Butterfly boards are not used. Also, as an additional drawback, from-to coordinates, specially those with distance one, are ambiguous and may be legal for several pieces. For instance e2-e3 might be a rook-, queen-, king- or white pawn-move. However, knight-, rook- and bishop moves are disjoint, queen moves are the superset from rook- and bishop-moves, king-moves the one-distance subset of queen moves, and pawn pushes are subset of rook-moves, while pawn captures and en passant (if stored at all) are subset of bishop-moves.

Therefor some programmers omit the origin from-square, but use piece-type instead for denser 12 x 64 tables with only 3/4K entries - or exclude not only captures, but also pawn pushes and/or king moves. Other programmers have abandoned hashing moves for History Heuristic and LMR, and say that given enough search depth, History counters produce just some random noise ^[5] .

This is how butterfly boards may be declared in C or C++:

counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K

counterType arrButterfly[2][64][64]; // color, from, to -> 8K

Valid Entries

As mentioned in Influence Quantity of Pieces, there are only 1792 (7/16 of 4K) possible valid moves coordinates, 9/16 of the space in the Butterfly boards is "wasted".

Piece	covers other pieces	#	div 112 (7*16)
Rook	queen, king and pawn pushes	896	8
Bishop	queen, king and pawn captures	560	5
Knight	-	336	3
possible from-to move coordinates		1792	16

The Eponym

The name Butterfly Boards was proposed by Dap Hartmann in 1988, when he introduced the Butterfly Heuristic in the ICCA Journal ^[6], and the application of a Butterfly refutation table at the Advances in Computer Chess 6 conference in 1990 ^[7]. Plotting the illegal move coordinates as black cells # inside a 64*64 sheet, seven butterfly shaped pattern appear along the impossible move diagonal (where squares are equal).

The Butterfly

Single Shape

The thorax of the Butterfly is centered by the wraps from one rank (or dependent on the Square Mapping Considerations, one file) to the next one. With 'a1' as square null mapping, and 'd1' as square 3, 'e2' is square 12, the shape indexed by square coordinates looks as follows, covering two wrapped rank "halfs" including their center files, e.g. d1 - e2:

d e f g h a b c d e        d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2        1 1 1 1 1 2 2 2 2 2
#         #           d1   # - - - - # ~ \ | /
  #       # #         e1   - # - - - # # ~ \ |
    #     # # #       f1   - - # - - # # # ~ \
      #   # # # #     g1   - - - # - # # # # ~
        # # # # # #   h1   - - - - # # # # # #
# # # # # #           a2   # # # # # # - - - -
  # # # #   #         b2   ~ # # # # - # - - -
    # # #     #       c2   \ ~ # # # - - # - -
      # #       #     d2   | \ ~ # # - - - # -
        #         #   e2   / | \ ~ # - - - - #

That is why Dap Hartmann called it Butterfly Boards.

Connected Shapes

one butterfly spans a 10 square range
n butterflies span an 8*n + 2 square range
seven butterflies span 58 square range, from 3 (d1) to 60 (e8)

d e f g h a b c d e f g h a b c d e       d e f g h a b c d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3       1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3
#         #                          d1   # - - - - # ~ \ | / ~ # # # \ ~ | ~
  #       # #                        e1   - # - - - # # ~ \ | / ~ # # # \ ~ |
    #     # # #                      f1   - - # - - # # # ~ \ | / ~ # # # \ ~
      #   # # # #                    g1   - - - # - # # # # ~ \ | / # # # # \
        # # # # # #                  h1   - - - - # # # # # # ~ \ | # # # # #
# # # # # #                          a2   # # # # # # - - - - - - - | / ~ # #
  # # # #   #                        b2   ~ # # # # - # - - - - - - \ | / ~ #
    # # #     #                      c2   \ ~ # # # - - # - - - - - ~ \ | / ~
      # #       #         #          d2   | \ ~ # # - - - # - - - - # ~ \ | /
        #         #       # #        e2   / | \ ~ # - - - - # - - - # # ~ \ |
                    #     # # #      f2   ~ / | \ ~ - - - - - # - - # # # ~ \
                      #   # # # #    g2   # ~ / | \ - - - - - - # - # # # # ~
                        # # # # # #  h2   # # ~ / | - - - - - - - # # # # # #
                # # # # # #          a3   # # # # # | \ ~ # # # # # # - - - -
                  # # # #   #        b3   \ # # # # / | \ ~ # # # # - # - - -
                    # # #     #      c3   ~ \ # # # ~ / | \ ~ # # # - - # - -
                      # #       #    d3   | ~ \ # # # ~ / | \ ~ # # - - - # -
                        #         #  e3   ~ | ~ \ # # # ~ / | \ ~ # - - - - #

C-Code

Some arbitrary C-code, to produce the plot:

#include "stdafx.h"
#include <math.h>
 
void butterflyBoard(int from, int to) {
   int sq1, sq2, f1, f2, r1, r2, df, dr;
   int nr = 0, nb = 0, nn = 0;
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%c", (sq2 % 10) ? ' ' : '0' + (sq2/10) );
   printf("\n");
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%1d", sq2 % 10 );
   printf("\n");
   for (sq1 = from; sq1 <= to; sq1++) {
      for (sq2 = from; sq2 <= to; sq2++) {
         if ( sq1 != sq2 ) {
            r1 = sq1 >> 3;
            r2 = sq2 >> 3;
            if (r1 == r2) { // same rank
               nr++;
               printf("-");
               continue;
            }
            f1 = sq1 & 7;
            f2 = sq2 & 7;
            if ( f1 == f2 ) { // same file
               nr++;
               printf("|");
               continue;
            }
            if  (f1 - r1 == f2 - r2) { // same diagonal
               nb++;
               printf("/");
               continue;
            }
            if  (f1 + r1 == f2 + r2) { // same anti-diagonal
               nb++;
               printf("\\");
               continue;
            }
            df = abs (f2 - f1);
            dr = abs (r2 - r1);
            if ( df + dr == 3 )    { // knight distance
               nn++;
               printf("~");
               continue;
            }
         }
         printf("#"); // invalid
      }
      printf(" %2d\n", sq1);
   }
   printf("rook   moves %4d\n", nr);
   printf("bishop moves %4d\n", nb);
   printf("knight moves %4d\n", nn);
   printf("total  moves %4d\n", nr + nb + nn);
}
 
int main(int argc, char* argv[])
{
   butterflyBoard(3, 20); // 0, 63
   return 0;
}

Analogy in Astronomy

Dap Hartmann found a nice analogy in astronomy. Edward Maunders was the first astronomer (1904) to plot the distribution in heliographic latitude of the centers of sunspot groups as a functions of time:

A modern version of the Mauders' sunspot "butterfly diagram" ^[8] .

Publications

Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1

External links

AVR Butterfly Board from Asuro Wiki (German)

Wikipedia

Butterflies from Wikipedia ^[9]

Butterfly insect of the order Lepidoptera
Butterfly Game a two-player abstract strategy game from Mozambique
BBN Butterfly a massively parallel computer from the 1980s
Butterfly diagram in the context of fast Fourier transform ^[10] algorithms
Butterfly or Zassenhaus lemma
Schmetterlingsgraph (German)
Butterfly knot
Butterfly theorem in elementary geometry
Butterfly curve (algebraic)
Butterfly curve (transcendental)
Butterfly catastrophe Catastrophe theory
Butterfly options a combination option trade strategy
Iron Butterfly spread
Iron Butterfly (band)
Butterfly ballot
Butterfly effect in the context of Chaos theory
The Butterfly Effect (Film)
The Butterfly Effect (band)

Musicvideo

Herbie Hancock & The Headhunters, Butterfly, 1974, YouTube Video

References

^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
^ Picture gallery "Symmetry" from The Official M.C. Escher Website
^ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Edward Walter Maunder, Solar observations A modern version of the Mauders' sunspot "butterfly diagram". (This version from the solar group at NASA Marshall Space Flight Center.)
^ Butterfly (disambiguation) from Wikipedia
^ Fast Fourier Transform (FFT) from Reliable Software

What links here?

Page	Date Edited
Array	Dec 1, 2016
Bobby	Jan 7, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Countermove Heuristic	Oct 1, 2017
Dap Hartmann	Jun 10, 2017
Dappet	Dec 12, 2016
Data	Nov 26, 2017
Dictionary	Aug 24, 2017
Direction	Oct 6, 2016
Encoding Moves	Mar 27, 2016
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
ICGA Journal	Dec 21, 2017
Influence Quantity of Pieces	Jul 21, 2017
Last Best Reply	Jul 6, 2013
Mathematician	Apr 9, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Relative History Heuristic	Jun 8, 2015
Squares	Feb 15, 2015
Table-driven Move Generation	Feb 19, 2017
Vector Attacks	Dec 15, 2017

Up one Level

C

GerdIsenberg — Mon, 19 Feb 2018 16:13:27 GMT

Home * Programming * Languages * C

C is a pragmatical, general purpose, block structured, procedural, imperative programming language. C was developed in 1972 by Dennis Ritchie at the Bell Laboratories. It was first intended as a system programming language for the Unix operating system, but has spread to many other platforms and application programming as well. C and its derivations are likely the most often used languages so far for computer chess programming.

Due to explicit pointers (address of a variable or function), C can be considered as a high level assembly language, but has some weak spots in its initial design and implementation, which are addressed in

Data

Data Types

Primitive Data Types

To be aware of the scalar 64-bit origin of bitboards in computer chess, we use so far a type defined unsigned integer U64 in our C and C++ source snippets. The macro C64 will append a suffix to 64-bit constants as required by some compilers:

typedef unsigned __int64 U64;    // for the old microsoft compilers
typedef unsigned long long  U64; // supported by MSC 13.00+ and C99
#define C64(constantU64) constantU64##ULL

Pointer

Array

Struct

A structure in C refers to Object composition to encapsulate related scalar datatypes inside one structured item. The size of the structure is the sum of its element sizes. To access the structure elements the dot-operator separates the element from the variable or reference. Pointers require arrow operator.

struct MOVE
{
   char from;
   char to;
};
 
...
MOVE m, a, *b;
m.from = square;
...
if ( a.from == b->to )

Bitfield

So called Bitfields might be implemented as structure where integer members are declared with explicit bit length specifier from 1 .. 31. However due to portability issues of various C-compilers and platforms concerning bit ordering, padding and eventually the sign, most programmer rely on explicit bitfields to composite and extract sub-items by shift and masks, i.e. in encoding moves.

Union

Variables

Variables are either stored in various memory areas or kept inside processor registers.

Globals

On the Stack

On the Heap

Register

Instructions

Operations

Arithmetical

Bitwise boolean

Relational

Logical

Functions

C mathematical functions from Wikipedia

Expressions

Control Flow

Control flow from Wikipedia

Do while

Preprocessor

C preprocessor from Wikipedia

Portabilty

Twos' Complement

sizeof

shift

Endianness

Main article Endianness

Libraries

C standard library (libc)

C and C++ Compiler

A C-Compiler is used to translate the source program, usually ascii-text files with the extension .C, to so called object files, containing machine instructions. A linker binds all the object files together with libraries containing external functions (and data) to build an executable program.

Books

Brian W. Kernighan, Dennis M. Ritchie (1978, 1988). The C Programming Language. First Edition ISBN 0-13-110163-3, Second Edition ISBN 0-13-110362-8
Andrew Koenig (1989). C Traps and Pitfalls. Addison-Wesley, ISBN 0-201-17928-8, pdf preprint
Patrick Winston (1994). On To C. ISBN-13: 978-0201580426
Andrew Appel, Maia Ginsburg (1998). Modern Compiler Implementation in C. Cambridge University Press

Publications

Robert C. Seacord (2010). Dangerous Optimizations and the Loss of Causality. CS 15-392 © 2010 Carnegie Mellon University, slides as pdf
Xi Wang, Haogang Chen, Alvin Cheung, Zhihao Jia, Nickolai Zeldovich, M. Frans Kaashoek (2012). Undefined Behavior: What Happened to My Code? pdf
Will Dietz, Peng Li, John Regehr, Vikram Adve (2012). Understanding Integer Overflow in C/C++. pdf

Forum Posts

1999

C or C++ for chess programming: speed by Marc-Philippe Huget, CCC, October 20, 1999

2000 ...

One (silly) question about "C" by Antonio Senatore, CCC, February 05, 2002

2005 ...

Re: chess engines writen in C by Dann Corbit, CCC, January 13, 2005
ansi-C question by Vincent Diepeveen, CCC, June 08, 2008
setjmp() - another one by Chris Whittington, CCC, August 27, 2008
kbhit() taking huge CPU?? by John Merlino, CCC, April 01, 2009 » Thread
Critter: Pascal vs C by Richard Vida, CCC, August 27, 2009 » Pascal

2010 ...

MSVC calloc question by Harm Geert Muller, CCC, March 17, 2011
My experience with Linux/GCC by Richard Vida, CCC, March 23, 2011 » Linux
a cautionary tale about simple-looking macros by Wylie Garvin, CCC, July 03, 2011
c or c++ ? by ethan ara, CCC, July 10, 2011
VisualStudio - __fastcall instead of __cdecl? by Martin Sedlak, CCC, June 18, 2012
C vs ASM by Ed Schröder, CCC, March 05, 2013 » Assembly
Re: goto thread (split) by Steven Edwards, CCC, August 01, 2013 » Iterative Search, Symbolic
A note for C programmers by Robert Hyatt, CCC, November 23, 2013
Re: A note for C programmers by Rein Halbersma, CCC, November 28, 2013
A note on strcpy by User923005, OpenChess Forum, November 26, 2013
strcpy() revisited by Robert Hyatt, CCC, December 08, 2013

2015 ...

Using more than 1 thread in C beginner question by Uri Blass, CCC, January 11, 2016 » Thread
C programming style question by Michael Sherwin, CCC, January 19, 2016
Crafty c questions by J. Wesley Cleveland, CCC, March 10, 2016 » Crafty
I'm not very happy with the do {} while() statement in C by Michael Sherwin, CCC, February 18, 2018

External Links

C from Wikipedia
The C Book - Table of Contents, an online version of the popular introduction and reference on the ANSI Standard C programming language
C utilities by Gijsbert Wiesenekker
Programming Bits by Paul Hsieh
comp.lang.c Discussion about C
comp.lang.c Frequently Asked Questions
Chess Engine In C - YouTube Videos by BlueFeverSoft » Vice
How to C in 2016

References

^ LLVM from Wikipedia
^ Edsger Dijkstra (1968). Go To Statement Considered Harmful. Communications of the ACM, Vol. 11, No. 3, pdf
^ William A. Wulf (1971). Programming Without the GOTO. IFIP, Ljubljana, Yugoslavia, August 1971
^ William A. Wulf (1972). A Case Against the GOTO. Proceedings of the ACM National Conference, Boston, August 197
^ Donald Knuth (1974). Structured Programming with go to Statements. ACM Computing Surveys, Vol. 6, No. 4, pdf
^ Ward Douglas Maurer (1996). Attitudes toward the go-to statement (or, hydrogen considered harmful). Computers & Education, Vol. 26, No. 4
^ Coding Horror: I'd Consider That Harmful, Too by Jeff Atwood, October 25, 2007
^ Steve McConnell (1993). Code Complete: A Practical Handbook of Software Construction. Microsoft Press

Up one Level

C sharp

GerdIsenberg — Sun, 26 Nov 2017 11:45:02 GMT

Home * Programming * Languages * C#

C# has been developed by Microsoft as part of the .NET Framework. It is a Multi-paradigm programming language, being functional, imperative, generic, object-oriented, and component-oriented. C# Chief Architect is Anders Hejlsberg, the creator of Turbo Pascal and Delphi ^[1].

Chess Programs

Chess Program in C# by Jacques Fournier, from the Code Project, Last Updated: June 08, 2009
How to Develop a Chess Program for Dummies based on Huo Chess by Spiros (Spyridon) Kakos ^[2]

Dynamic List

Engines, written in C#. To expand this list, create a new engine page with the tag "csharpengines".

1. Alfil
2. ChessBin.com
3. ChessMaps
4. ChessV
5. Counter
6. Dolphin
7. Excelsior
8. FUSCsharp
9. Jabba
10. MadChess
11. NoraGrace
12. Portfish
13. RumbleMinze
14. Sharp Chess
15. SharpChess
16. The Turk (TR)

Neural Networks

John Wakefield's Dynamic Notions, a Blog about the evolution of neural networks with C# samples:

Publications

Liwu Li, Wenjiang Wang (2004). Object-oriented programming with dynamic classification in C#. IASTED Conference on Software Engineering and Applications 2004

Forum Posts

c# for chess engine by Sergei Markoff, CCC, September 13, 2011
C# Performance by Richard Allbert, CCC, January 27, 2012
[.Net only] - fast bit operations by Balint Pfliegel, CCC, June 18, 2012
Question About CPP-C#, Performance, and Square Represenation by Cheney Nattress, CCC, September 29, 2012
Re: Question About CPP-C#, Performance, and Square Represenation by Erik Madsen, CCC, October 03, 2012 ^[3]
C# compiler for Windows XP SP3 by Norbert Raimund Leisner, CCC, January 15, 2014

External Links

C#

Yield

SYSK 149: Performance Analysis of the ‘yield return’ Statement - AppDev: Something You Should Know by Irena Kennedy - MSDN Blogs, July 05, 2006
Give way to the yield keyword! - IronShay, June 2008
Behind the scenes of the C# yield keyword by Lars Corneliussen, June 9, 2008
Demystifying the C# Yield-Return Mechanism -- Visual Studio Magazine by James McCaffrey, February 02, 2012

Frameworks

References

^ Behind the Code with Anders Hejlsberg, YouTube Video
^ Huo Chess from MSDN Code Gallery
^ Behind the scenes of the C# yield keyword by Lars Corneliussen, June 9, 2008

What links here?

Page	Date Edited
Adam Berent	Jul 6, 2010
Albert Bertilsson	Jun 6, 2017
Alfil	Sep 3, 2015
Balint Pfliegel	Aug 30, 2015
C sharp	Nov 26, 2017
ChessBin.com	Jan 6, 2012
ChessMaps	Dec 7, 2017
Chessmaps Heuristic	Aug 27, 2015
ChessV	Jan 21, 2018
Colossus Chess	Dec 10, 2017
Counter	Nov 13, 2017
Dolphin	Nov 28, 2014
Engines	Mar 10, 2018
Eric Oldre	Jul 3, 2014
Erik Madsen	Apr 13, 2014
Excelsior	Apr 16, 2014
Fafis	May 17, 2016
FUSCsharp	Jun 7, 2013
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Gary Linscott	Jan 16, 2018
Generic Programming	Jul 7, 2012
Jabba	Sep 10, 2016
Kieran Greer	Nov 7, 2014
Languages	Nov 26, 2017
Learning	Feb 20, 2018
Linked List	Oct 11, 2016
MadChess	Jul 4, 2017
Marco Belli	Jan 6, 2018
Marco Block-Berlitz	May 26, 2013
Marek Kłonowski	Apr 16, 2014
Neural Networks	Mar 12, 2018
NoraGrace	Nov 23, 2014
Norbert Raimund Leisner	Jul 28, 2016
Oliver Uwira	Apr 5, 2013
Philippe Fabiani	Sep 15, 2016
Portfish	Sep 8, 2016
Pseudorandom number generator	May 11, 2017
Richard Allbert	Feb 7, 2016
RumbleMinze	Apr 13, 2014
Sergei Markoff	Mar 12, 2018
Sharp Chess	Jun 6, 2017
SharpChess	Jun 6, 2017
Sharper	Jun 6, 2017
Sinobyl	Jul 3, 2014
The Turk (TR)	Apr 1, 2017
Vajolet	Jan 25, 2018
Windows	Nov 2, 2017
Woodpusher	Dec 12, 2016
Yakup Ipek	Sep 6, 2015

Up one Level

Chess Query Language

GerdIsenberg — Mon, 08 Jan 2018 09:06:09 GMT

Home * Chess * Chess Query Language

The Chess Query Language (CQL) is a structured query language to search for games, problems, and studies that match specific themes from a collection in Portable Game Notation. CQL was developed by Gady Costeff and Lewis Stiller. It is Copyright (c) 2003-2018 and is free. The CQL Manual is hosted by the Internet Archive ^[1] ^[2] .

The current version is 5.1 and the documentation and download of the executable can be found on the website of Gady Costeff ^[3].

Sample query

^[4] ^[5]

;; look for positions where a rook circles in a 4x3 rectangle
;; we use the rectangle g2, d2, d6, g6 together with shift and flip
;;
(match :pgn input.pgn
       :output output.pgn
       :forany piece [Rr]
       (position
        $piece[g2]
        :and (
              (position :gappedsequence ((position :movefrom $piece[g6,d2] :moveto ?g2)))
              (position :gappedsequence ((position :movefrom $piece[d6,g2] :moveto ?d2)))
              (position :gappedsequence ((position :movefrom $piece[d6,g2] :moveto ?g6)))
              (position :gappedsequence ((position :movefrom $piece[g6,d2] :moveto ?d6)))
             )
        :shift
        :flip
       )
)

Publications

Gady Costeff (2004). The Chess Query Language: CQL. ICGA Journal, Vol. 27, No. 4, pdf

Forum Posts

CQL Users? by Guy Haworth, CCC, August 11, 2004
CQL - Stalemate with 2 pieces pinned by James Constance, CCC, July 17, 2005
Chess Query Language by David Dahlem, CCC, August 13, 2011
Chess Query Language by Giovanni Lavorgna, CCC, May 07, 2016
Scid vs PC with CQL , build issue by Steven Atkinson, CCC, November 25, 2017 » Scid vs. PC

External Links

CQL Introduction by Gady Costeff
CQL Manual hosted by the Internet Archive
Chess Query Language from Tim Krabbé's Chess Site
Chess Query Language from Wikipedia
CQL VisualCQL by Emil Vlasák

References

^ Chess Query Language by Giovanni Lavorgna, CCC, May 07, 2016
^ CQL Manual hosted by the Internet Archive
^ CQL Introduction by Gady Costeff
^ Sample CQL files (Internet Archive)
^ An html version of rookrectangle.cql (Internet Archive)

What links here?

Page	Date Edited
Chess	Jan 21, 2018
Chess Assistant	Jul 16, 2017
Chess Query Language	Jan 8, 2018
ChessBase (Database)	Feb 26, 2018
ChessX	Feb 26, 2015
Databases	Mar 18, 2018
Dictionary	Aug 24, 2017
Gady Costeff	May 30, 2014
ICGA Journal	Dec 21, 2017
Jose	Feb 26, 2015
Languages	Nov 26, 2017
Lewis Stiller	Oct 11, 2016
Portable Game Notation	Jan 11, 2018
Scid	Apr 15, 2017
Scid vs. PC	Jan 21, 2018
Scidb	Mar 18, 2018

Up one Level

Cilk

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

Parallel Chess

Cilk-5 Linguistic Extensions

Home * Programming * Languages * Cilk

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

Parallel Chess

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

Cilk-5 Linguistic Extensions

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

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

Parallel Alpha-Beta

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

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

Quote

by Vincent Diepeveen after WCCC 1999 ^[4]:

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

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

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

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

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

Cilk++

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

Intel Cilk Plus

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

Publications

^[8]

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

Manuals

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

Forum Posts

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

External Links

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

References

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

What links here?

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

Up one Level

Copy-Make

GerdIsenberg — Tue, 23 May 2017 13:48:35 GMT

Home * Chess * Position * Copy-Make

While traversing a Search Tree, the Copy-Make approach keeps and updates local copies of certain aspects of a chess position inside an array indexed by ply, which could also be interpreted as explicit, random accessible search stack. It usually refers the irreversible aspects of the position, like ep state, castling rights and the halfmove clock, which can not incrementally updated during unmake move. Some programs even keep reversible stuff inside an array, to avoid incremental update during unmake. Copy-Make is required, if aspects need to be accessed randomly in the current branch from the root (or even starting game position) to the current one.

Copy-Make

// make
memcpy (&position[ply+1].irrvrsAspects, 
        &position[ply  ].irrvrsAspects, 
        sizeof(irrvrsAspects));
ply++;
update (position[ply], move)
...
// unmake
ply--;
// position[ply] is still valid

Stack

The alternative, to maintain those irreversible aspects inside a global structure, would require a stack (LIFO), with push and global update during make, and pop from stack to global structure during unmake, and therefor higher memory bandwidth for copying back and forth.

// make
push (position.irreversibleAspects);
ply++;
update (position, move)
...
// unmake
ply--;
pop (position.irreversibleAspects);
// position is restored from stack

Forum Posts

1995 ...

cheaper search ? by James F. Long, rgcc, April 27, 1997 » Tristram
Re: cheaper search ? by Shaun Press, rgcc, April 28, 1997 » Vanilla Chess, KnightCap
Unmake move v copy the board by Hugh Cumper, CCC, January 24, 1999

2000 ...

The need to unmake move by Mathieu Pagé, CCC, August 19, 2003 » Unmake Move
undo move vs. Position Cloning by BoldReceiver, CCC, September 16, 2009
Re: undo move vs. Position Cloning by Marco Costalba, CCC, September 16, 2009 » Stockfish
Re: undo move vs. Position Cloning by Don Dailey, CCC, September 16, 2009 » Doch
copy/make vs make/unmake test results by Robert Hyatt, CCC, September 19, 2009 » Crafty

2010 ...

Copy Board vs Unmake Move by ChrisJ, OpenChess Forum, September 29, 2010
performance of copy-make by Rein Halbersma, CCC, August 02, 2011
How costly is taking moves back ? by Piotr Lopusiewicz, CCC, April 30, 2013
Saving info before making a move by CDaley11, OpenChess Forum, December 30, 2013
copy/make vs make/unmake by Robert Hyatt, CCC, January 07, 2014
Memory usage in make/unmake vs logic complexity by Matthew Lai, CCC, August 30, 2014

2015 ...

Unifying make/undo and copy-make by Rein Halbersma, CCC, December 21, 2015
Copy-make vs Make/Unmake ? by Mahmoud Uthman, CCC, November 12, 2016

What links here?

Page	Date Edited
Aaron Becker	Jul 22, 2015
Board Representation	Dec 11, 2017
Chess Position	Sep 10, 2017
Copy-Make	May 23, 2017
DayDreamer	Aug 22, 2016
Doch	May 23, 2017
Gromit	Apr 5, 2017
Incremental Updates	Sep 6, 2017
James Swafford	Jan 1, 2018
KnightCap	Nov 6, 2016
LTChess	Mar 30, 2017
Make Move	Mar 2, 2016
Mate-in-two	Oct 14, 2016
Matthew Lai	Dec 6, 2017
Moves	Feb 19, 2018
Nemorino	Dec 21, 2017
Occam	Jan 21, 2016
Paladin	Jan 29, 2017
Pedone	Jan 16, 2018
Rein Halbersma	Dec 22, 2015
Robert Hyatt	Dec 25, 2017
Senpai	Nov 10, 2017
Shaun Press	Sep 24, 2014
Stan Arts	Nov 21, 2014
Tristram	Jan 29, 2014
Unmake Move	Jun 10, 2017
Vadim Demichev	Jul 26, 2013
Vanilla Chess	Jan 13, 2013

Up one Level

Cpp

GerdIsenberg — Tue, 24 Oct 2017 17:26:33 GMT

Home * Programming * Languages * C++

C++ is a pragmatical, object oriented general-purpose programming language, initially an extension of C and designed and implemented in 1979 by Bjarne Stroustrup from the Bell Laboratories. C++ is pragmatical because one may write in "usual" C-style, using the C standard library (printf, strcpy, ...), except perhaps using C++ comments and references up and then (instead of pointer). On the other hand C++ allows to design classes and interfaces (pure virtual classes) in a more object oriented manner. There are lots of free and commercial class libraries for arithmetics, database related stuff, portable and proprietary window management and whatever else.

C Extensions

References

Reference (C++) from Wikipedia

Exception Handling

Classes

Classes as declaration for objects are more or less C-Structures. None static functions may be declared inside the scope of a class. Those functions, called Member function have an implicit parameter called "this", a pointer to this structure, allocated either inside the data segment as static or global, via "new" (malloc) on the heap or as automatic object (variable) on the stack.

C++ classes from Wikipedia

Data Definition

Basic declaration and member variables from Wikipedia

Member Functions

Member functions from Wikipedia

Modifiers

Public

Protected

Private

Static

Pointer to member-functions

For instance an array of member-function pointers of a class CNode, which is indexed by arbitrary pieces code - as switch-case replacement via indirect call/jump. The special atomic C++ operator '->*' is used to call the indexed member-functions:

class CNode {
  U64 AssertAttack (EnumSquare sq) const;
  U64 wPawnAttacks (EnumSquare sq) const;
  U64 bPawnAttacks (EnumSquare sq) const;
  U64 knightAttacks(EnumSquare sq) const;
  U64 kingAttacks  (EnumSquare sq) const;
  U64 bishopAttacks(EnumSquare sq) const;
  U64 rookAttacks  (EnumSquare sq) const;
  U64 queenAttacks (EnumSquare sq) const;
  ...
  typedef U64 (CNode::*AttackPtrType)(EnumSquare sq) const;
  static AttackPtrType m_scPieceAtta[14];
  ...
 
  U64 getAttack(EnumSquare sq, EnumPiece piece) const {return (this->*m_scPieceAtta[piece])(sq);}
};
 
CNode::AttackPtrType CNode::m_scPieceAtta[14] =
{
  AssertAttack,
  AssertAttack,
  wPawnAttacks,
  bPawnAttacks ,
  bishopAttacks,
  bishopAttacks,
  knightAttacks,
  knightAttacks,
  rookAttacks,
  rookAttacks,
  kingAttacks,
  kingAttacks,
  queenAttacks,
  queenAttacks
};

Inheritance

Function overloading

Function overloading from Wikipedia

Operator overloading

Operator Overloading from Wikibooks

Late binding

Abstract Classes

Abstract Classes from Wikibooks

Pure Abstract Classes

Pure Abstract Classes from Wikibooks

Multiple Inheritance

Multiple inheritance from Wikipedia

Templates

Class Design of a Chess Engine

main article Class Design of a Chess Engine

C++ Compiler

Libraries

C++ Publications

1985 ...

Bjarne Stroustrup (1985, 1991, 1997, 2000). The C++ Programming Language. Addison-Wesley ^[2]
Keith E. Gorlen (1987). An Object-Oriented Class Library for C++ Programs. C++ Workshop 1987, pp. 181-208
Bjarne Stroustrup, Andrew Koenig (1989). C++: as close as possible to C -- but no closer. C++ Report, Vol. 1, no. 7

1990 ...

Andrew Koenig, Bjarne Stroustrup (1990). Exception Handling for C++. Proc USENIX C++ Conference 1990, Also, Journal of Object Oriented Programming, Vol. 3 No. 2
Keith E. Gorlen, Sanford M. Orlow, Perry S. Plexico (1990). Data abstraction and object-oriented programming in C++. Wiley ^[3]
Andrew Koenig, Thomas A. Cargill, Keith E. Gorlen, Robert B. Murray, Michael Vilot (1991). How Useful is Multiple Inheritance in C++? C++ Conference 1991
Andrew Koenig (1992). Space-Efficient Trees in C++. C++ Conference 1992
Scott Meyers (1992,2005). Effective C++: 50 Specific Ways to Improve Your Programs and Designs. Addison-Wesley
Andrew Koenig (1994). Templates and Generic Algorithms. JOOP 7 No. 3
Andrew Koenig (1994). Generic Iterators. JOOP 7, No. 5
Bjarne Stroustrup, Andrew Koenig, Barbara Moo (1994). The C++ Programming Language. Encyclopedia of Software Engineering, Wiley, ISBN 0-471-54004-8.

1995 ...

Andrew Koenig, Bjarne Stroustrup (1995). Foundations for Native C++ Styles. Software Practice and Experience, Vol 25, special issue S4
Patrick Winston (1995). On To C++
Greg Wilson and Paul Lu (eds.) (1996). Parallel Programming Using C++. MIT Press.
Leen Ammeraal (1996). Algorithms and Data Structures in C++. ISBN 0-471-96355-0, Chichester: John Wiley
Andrew Koenig, Barbara Moo (1997). Ruminations on C++. Addison-Wesley, ISBN 0-201-42339-1
Leen Ammeraal (1997). STL for C++ Programmers. ISBN 0-471-97181-2, Chichester: John Wiley

2000 ...

Andrew Koenig, Barbara Moo (2000). Accelerated C++. Addison-Wesley, ISBN 0-201-70353-X
Leen Ammeraal (2000). C++ for Programmers. ISBN 0-471-60697-9, Chichester: John Wiley
Bjarne Stroustrup, Andrew Koenig, Barbara Moo (2001). The C++ Programming Language. Encyclopedia of Software Engineering. Wiley
Andrei Alexandrescu (2001). Modern C++ Design: Generic Programming and Design Patterns Applied.
Robert L. Akers, Ira Baxter, Michael Mehlich (2004). Invited application paper: re-engineering C++ components via automatic program transformation. PEPM 2004, pdf

2005 ...

Robert L. Akers, Ira Baxter, Michael Mehlich, Brian J. Ellis, Kenn R. Luecke (2005). Reengineering C++ Component Models via Automatic Program Transformation. WCRE 2005
Robert L. Akers, Ira Baxter, Michael Mehlich, Brian J. Ellis, Kenn R. Luecke (2007). Case study: Re-engineering C++ component models via automatic program transformation. Information & Software Technology, Vol. 49, No. 3
Bjarne Stroustrup (2008). Programming -- Principles and Practice Using C++. Addison-Wesley, ISBN 978-0321543721

2010 ...

Robert C. Seacord (2010). Dangerous Optimizations and the Loss of Causality. CS 15-392 © 2010 Carnegie Mellon University, slides as pdf
Anthony Williams (2012). C++ Concurrency in Action: Practical Multithreading. ^[4]
Xi Wang, Haogang Chen, Alvin Cheung, Zhihao Jia, Nickolai Zeldovich, M. Frans Kaashoek (2012). Undefined Behavior: What Happened to My Code? pdf ^[5]
Will Dietz, Peng Li, John Regehr, Vikram Adve (2012). Understanding Integer Overflow in C/C++. pdf

Andrew Koenig at Dr Dobbs

Andrew Koenig's C++ Blog at Dr. Dobb's

Introducing C++ Order Relations, January 18, 2013
If C++ Objects Are Unrelated, Are They Equal?, January 24, 2013
A Strategy for Defining Order Relations, February 01, 2013
How Dictionaries Work, February 06, 2013
Concrete Examples of Orderings, February 15, 2013
Comparison and Inheritance, February 22, 2013
It's Hard To Compare Floating-Point Numbers, March 01, 2013
Comparing an Integer With a Floating-Point Number, Part 1: Strategy, March 08, 2013
Comparing an Integer with a Floating-Point Number, Part 2: Tactics, March 15, 2013
If Order Relations are Such a Pain, Why Bother?, March 22, 2013
Is Optimization Immoral?, March 28, 2013
Optimization Versus Flexibility — An Example, April 04, 2013
Optimizing a Program Means Making It Run Faster, Right?, April 10, 2013
Sometimes Optimizations Cancel Each Other, April 17, 2013
Some Optimizations Are No-Brainers, April 26, 2013
Sometimes, Making a Program Clearer Makes It Faster, May 02, 2013
Some Subtleties of Aliasing, May 09, 2013
Aliasing Is Particularly Troublesome With Vector Elements, May 17, 2013
The Hazards of Remembering Positions in Vectors, May 24, 2013
Copying Container Elements From The C++ Library: It's Trickier Than It Looks, May 30, 2013
Moving Is Not Copying, June 06, 2013
When Is It Safe to Move an Object Instead of Copying It?, June 12, 2013
More Thoughts About Moving Objects Safely, June 21, 2013
Moving and Rvalue References, June 27, 2013
Moving an Object Does Not Destroy The Original, July 04, 2013
How the C++ Compiler Decides to Move Objects, July 10, 2013
Sometimes You Must Violate an Abstraction to Maintain It, July 17, 2013
Is Moving Objects Worth the Hassle?, July 26, 2013
Why Would You Ever Pass a Container By Value?, July 31, 2013
Some Optimizations Are More Important Than Others, August 08, 2013
An Important Move Optimization Is Nearly Invisible, August 15, 2013
Moving Data and Address Arithmetic, August 21, 2013
Addresses and Nodes: Two Ways To Get Around, August 29, 2013
Theory Versus Practice: The Great Divide in Programming Languages, September 06, 2013
Programming Without Variables, September 12, 2013
Containers That Never Change, September 19, 2013
What Does It Mean To Change An Object?, September 26, 2013
A Simple, Immutable, Node-Based Data Structure, October 02, 2013
Introduction to Programming with Lists, October 09, 2013
Reversing an Immutable List, October 17, 2013
How Do You Decide On Intermediate States?, October 23, 2013
Sorting An Immutable List, October 31, 2013
Practical Advantages of Immutable Values, November 07, 2013
When Is An Optimization More Than Just An Optimization?, November 14, 2013
Abstraction and Performance Bugs, November 21, 2013
Performance Bugs Can Be Hard to Detect, November 27, 2013
Performance Bugs: Not Just Hard To Detect, But Hard To Define, December 05, 2013
How Can One Test a Program's Average Performance? December 12, 2013
Testing Behavior, Not Just Results, December 19, 2013
Not All Bugs Are Random, December 27, 2013
Testing Is Not Verification and Vice Versa, January 02, 2014
Social Processes and the Design of Programming Languages, January 08, 2014
Why Language Designers Tolerate Undefined Behavior, January 16, 2014
Even Simple Floating-Point Output Is Complicated, January 23, 2014
Why Is Exact Floating-Point Output So Hard? January 30, 2014
Floating-Point Input and Output Are Not Symmetric, February 06, 2014

Forum Posts

1997 ...

Search Degredation w/ C++ by Chris Jason Richards, rgcc, June 12, 1997
Re: Search Degredation w/ C++ by Amir Ban, rgcc, June 17, 1997
Question to Amir Ban by Bas Hamstra, CCC, November 05, 1997 ^[6]
object oriented chess programming by James Long, rgcc, December 31, 1997
Re: object oriented chess programming by Dave Fotland, rgcc, January 06, 1998
C or C++ for chess programming: speed by Marc-Philippe Huget, CCC, October 20, 1999

2000 ...

C++ Programming Q: are const and define efficiency the same by Federico Corigliano, CCC, January 16, 2004
Kiwi for Win98 and input-reading stuff by Alessandro Scotti, CCC, September 29, 2004 » Kiwi, Windows, Thread

2005 ...

Find The Bug - C / C++ by David Rasmussen, bytes.com, July 22, 2005 » Chezzz
forcing compilers to inline (or to not inline) by Wylie Garvin, CCC, May 04, 2008

2010 ...

c or c++ ? by ethan ara, CCC, July 10, 2011

2012

C++ templates question by José C. Martínez Galán, CCC, January 18, 2012
C++11 for chess engines by Marco Costalba, CCC, September 03, 2012
Has GCC caught up with Intel with respect to performance? by Don Dailey, CCC, October 07, 2012

2013

Need Help Getting GCC Working?!? by Steve Maughan, CCC, April 23, 2013
[ub] Objectives and tasks for SG12 by Gabriel Dos Reis, Open Standards, The ub Archives, May 29, 2013
C++ Question by Ted Wong, CCC, July 30, 2013 » Thread

2014

C++11 threads seem to get shafted for cycles by User923005, OpenChess Forum, March 18, 2014 » Parallel Search, Senpai, Thread
c++11 std::atomic and memory_order_relaxed by Kevin Hearn, CCC, April 01, 2014 » Memory
C++ puzzle by Marco Costalba, CCC, April 12, 2014
std::vector<> considered harmful by Folkert van Heusden, CCC, September 25, 2014 » Move List, Array

2015 ...

Polling standard input from C++ by Steven Edwards, CCC, May 10, 2015
BMI2 intrinsics in gcc by Álvaro Begué, CCC, May 14, 2017 » BMI2
Advantages of C++11 for Chess? by Steve Maughan, CCC, October 23, 2017

External Links

C++ from Wikipedia
C++11 from Wikipedia
C++ Programming from Wikibooks
cplusplus.com - The C++ Resources Network
Google C++ Style Guide
C++ Notes by Fred Swartz
C++ Historical Sources Archive — Software Preservation Group, The Computer History Museum
Agner Fog's manuals
Calling conventions for different C++ compilers and operating systems (pdf) by Agner Fog
C++ Optimization Strategies and Techniques by Pete Isensee
Threads and memory model for C++ by Hans J. Boehm
C++ Frequently Questioned Answers by Yossi Kreinin
comp.lang.c++ The object-oriented C++ language.
GoingNative 2012 | Channel 9, Redmond, WA, February 2 - 3, 2012, with Bjarne Stroustrup, Herb Sutter, Andrei Alexandrescu, Stephan T. Lavavej, Chandler Carruth, Hans Boehm, and Andrew Sutton ^[7]

References

^ Keith E. Gorlen, Sanford M. Orlow, Perry S. Plexico (1990). Data abstraction and object-oriented programming in C++. Wiley
^ Books by Bjarne Stroustrup
^ NIH Class Library — Software Preservation Group, The Computer History Museum
^ Information on the C++11 Memory Model by Scott Meyers, April 24, 2012
^ Re: A note for C programmers by Rein Halbersma, CCC, November 28, 2013
^ Search Degredation w/ C++ by Chris Jason Richards, rgcc, June 12, 1997, post 4 and 6 by Amir Ban
^ Nice talk by Bjarne Stroustrup on C++ 11 programming style by Rémi Coulom, CCC, September 09, 2012

Up one Level

Data

GerdIsenberg — Sun, 26 Nov 2017 19:00:32 GMT

Home * Programming * Data

		Data is anything in a form suitable for use with a computer to represent information or knowledge. Bits, bytes, characters, strings, numbers, codes, sets, sequences and structures, as well as references (pointers, addresses) to related data, retrievable stored in memory of any kind of hardware. A variable in the context of programming languages, associates a symbolic name with a memory address.
Data mining ^[1]

Processor's View

From processor's point of view, an atomic fixed sized data item with a unique memory address is a primitive data item, today usually with a size of one, two, four, or up to eight bytes, sometimes even 16 or 32 bytes. One of these data items may represent numbers in various formats and value ranges, finite sets, codes like a character of a text or a piece on the chessboard, or even instruction codes and memory addresses. It fits into one processor register and is subject of arithmetical or logical operations, or, if interpreted as (part of an) address, to perform random memory access, that is to store and retrieve primitive data items. Program code is decoded and interpreted as instruction to control the combinatorial and sequential logic while executing a program within its processor, usually distinct from application specific data, if the application is not an assembler, compiler or debugger or anything related to self-modifying code or self-replication ^[2] .

A collection of primitive data types, located consecutively in memory may be accessed relative to the address of its first element via another data item, an index, or - specially if the primitive data items have different sizes, via constant offsets. From machine perspective, this covers array (vector) and structure, while the latter may be interpreted as concrete implementation of abstract objects.

Lifetime of Data

Data may resist in persistent non-volatile memory or volatile random-access memory. The lifetime of volatile data depends on the data declaration of various programming languages, in C related to storage class specifiers ^[3] .

Static Data

Global or static data as determined and may be initialized at compile time requires static memory allocation. Static data resides in an object file or in segmentated memory in a data- or bss-segment, dependent on their initialization. For instance, some chess programs keep material- and other lookup tables initialized in their object file and data segment, for huge tables likely by generated source code with appropriate data declarations and static initialization. Assuming the initialization code is (much) shorter than the generated data, others prefer to reduce the size of the object file to initialize stuff located in the bss-segment or elsewhere after program startup.

Dynamic Data

Dynamic data is created during the runtime of a process, it might be allocated from a memory pool (heap), and freed if no longer needed, depending on the framework or programming languages, either explicitly, or implicitly by garbage collection.

Automatic Data

Automatic data and variables like local variables and actual parameters have a limited lifetime inside the scope of a subroutine or block. Automatic variables either reside on the processor stack, or inside a processor register.

Algorithms + Data

Data structures are inherently related to algorithms and their efficiency, as for instance elaborated by Niklaus Wirth in Algorithms + Data Structures = Programs ^[4] .

Primitive Types

General Purpose

Chess Specific

Scalar integers as numbers, enumerations or simple structures related to Chess and Search basics.

Structured Data

General Purpose

Chess Specific

Persitant Data

Endianness

Publications

1960 ...

Georgy Adelson-Velsky, Evgenii Landis (1962). An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences, 146: 263–266. (Russian) English translation by Myron J. Ricci in Soviet Mathematics Doklady, No. 3 ^[5]

1970 ...

Burton H. Bloom (1970). Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, Vol. 13, No. 7, pdf ^[6]
Niklaus Wirth (1976). Algorithms + Data Structures = Programs

1980 ...

Guy Jacobson (1989). Succint Static Data Structures. Ph.D. thesis, Carnegie Mellon University, CMU-CS-89-112, pdf
Guy Jacobson (1989). Space-efficient Static Trees and Graphs. SFCS'89, pdf

1990 ...

Keith E. Gorlen, Sanford M. Orlow, Perry S. Plexico (1990). Data abstraction and object-oriented programming in C++. Wiley ^[7] ^[8] » C++
Bernhard Balkenhol (1994). Data Compression in Encoding Chess Positions. ICCA Journal, Vol. 17, No. 3, zipped ps » Chess Position
Robert Levinson (1994). UDS: A Universal Data Structure. UCSC CRL-94-15
Leen Ammeraal (1996). Algorithms and Data Structures in C++. ISBN 0-471-96355-0, Chichester: John Wiley
Liwu Li (1998). Java - Data Structures and Programming. Springer

2000 ...

Julio César Hernández-Castro, Ignacio Blasco-López, L.Javier Garcéa-Villalba (2004). Hiding Data in Games. ICGA Journal, Vol. 27, No. 2
Julio César Hernández-Castro, Ignacio Blasco-López, Juan M. Estevez-Tapiador, Arturo Ribagorda-Garnacho (2006). Steganography in games: A general methodology and its application to the game of Go. Computers & Security, Vol. 25, pdf ^[9]
Carl Burch, Data & Procedure. On-line Book
Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer, ISBN 978-3540779773
Denis Xavier Charles, Kumar Chellapilla (2008). Bloomier Filters: A Second Look. ESA 2008 ^[10]
Anthony Cozzie, Frank Stratton, Hui Xue, Samuel T. King (2008). Digging for Data Structures. OSDI 2008, pdf
Felix Putze, Peter Sanders, Johannes Singler (2009). Cache-, hash-, and space-efficient bloom filters. ACM Journal of Experimental Algorithmics Vol. 14

External Links

References

What links here?

Page	Date Edited
68030	Jun 7, 2016
Algorithms	May 5, 2017
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
Barbara Liskov	Oct 30, 2014
Big-endian	Jan 25, 2015
Bit	Oct 29, 2012
Butterfly Boards	Jan 27, 2015
Byte	Apr 5, 2013
Chafitz	Dec 25, 2017
Data	Nov 26, 2017
David Eppstein	Oct 10, 2013
De Bruijn sequence	Feb 20, 2018
Deep Learning	Feb 12, 2018
Donna	Aug 17, 2017
Double	May 30, 2016
Double Word	Jan 25, 2015
Endianness	Jan 25, 2015
Ferranti Mark 1	Jun 2, 2015
Float	Nov 11, 2016
Fredrik Niemelä	Dec 29, 2016
Generic Programming	Jul 7, 2012
Gerard Zielinski	Sep 25, 2014
Hash Table	Jan 1, 2018
Joe Culberson	Dec 13, 2016
Kazunori Yamaguchi	Jun 20, 2016
Keith Gorlen	May 23, 2016
Linked List	Oct 11, 2016
Little-endian	Jan 25, 2015
Memory	Dec 8, 2017
Move List	Jul 19, 2017
MVC to include	May 7, 2011
Nibble	Jan 25, 2015
Node	Jul 20, 2015
NoonianChess	Jan 7, 2016
Oliver Vornberger	Oct 23, 2015
Process	Jul 31, 2017
Programming	Dec 16, 2017
Protocols	Jan 20, 2018
Quad Word	Jan 25, 2015
Queue	Apr 4, 2017
Shared Hash Table	Sep 11, 2017
Shy	Jul 19, 2016
Sinclair ZX81	Sep 14, 2015
Sloppy	Sep 17, 2016
Space-Time Tradeoff	Jun 17, 2015
Stack	Nov 18, 2016
Steven Walczak	May 23, 2016
Triangular PV-Table	Jun 12, 2017
Wee Chong Oon	Jul 16, 2015
Wojciech Wieczorek	Mar 17, 2015
Word	Jan 25, 2015

Up one Level

De Bruijn sequence

GerdIsenberg — Tue, 20 Feb 2018 10:21:34 GMT

Home * Programming * Data * De Bruijn sequence

		In combinatorial mathematics, a k-ary De Bruijn sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once ^[1] . In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in hashing sets like Piece-Sets or Square-sets, also called Bitboards, most notably in Bit scanning ^[2] .
Escher's ants on Moebius Strip ^[3]

Binary alphabet

According to De Bruijn himself ^[4] , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest ^[5] and himself.

Binary digits or bits inside a computer word are B(2, n) de Bruijn sequences, with 2n bits length and equal number of ones and zeros, with 2n overlapping unique n-bit subsequences. Since the sequences are cyclic and n-1 subsequences need to wrap, we restrict them to at least n-1 leading zeros, to make them overlap the hidden trailing "zeros".

Odd sequences have n leading zeros. The even ones with n-1 leading zeros are rotated (shifted) left by one. Due to n leading zeros of these odd sequences we further consider, the first subsequence[0] is zero. Due to the overlapping, each subsequence[i+1] is dependent from subsequence[i]. The doubled value incremented by either zero or one. Since subsequence[0] is zero, a second zero subsequence with six consecutive binary zeros is further prohibited, and subsequence[1] must be one. Subsequence index i is counted from most significant bit left to right, and therefor reversed from usual bit-index. A modulo 2n restricts all subsequences to n bits:

$s[i+1] = (2s[i] + (0|1)) \mod (2^n)$

The Cardinality of all distinct B(2, n) de Bruijn sequences is:

$|B(2, n)| = 2 ^ {({2 ^ {n-1}} - n)}$

$n$	${({2 ^ {n-1}} - n)}$	$\|B(2, n)\|$
1	0	1
2	0	1
3	1	2
4	4	16
5	11	2,048
6	26	67,108,864
7	57	144,115,188,075,855,872
8	120	~1.329e+36

B(2, 1)

The two one-bit subsequences obviously do not overlap:

i  01  s[i]
0  0    0
1   1   1

B(2, 2)

B(2, 2) implies 2^2 or 4-bit sequences. There is one odd four-bit de Bruijn sequence with four overlapping unique two-bit subsequences, 0x3.

i  0011|0  s[i]
0  00 . . . 0
1   01      1
2  . 11 . . 3
3     1|0   2

B(2, 3)

B(2, 3) implies 2^3 or 8-bit sequences. There are two odd eight-bit sequences with eight overlapping unique three-bit subsequences, 0x17 and 0x1d. Note that the five relevant bits are reversed.

i  00010111|00 s[i]    i  00011101|00 s[i]
0  000 . . . .  0      0  000 . . . .  0
1   001         1      1   001         1
2  . 010 . . .  2      2  . 011 . . .  3
3     101       5      3     111       7
4  . . 011 . .  3      4  . . 110 . .  6
5       111     7      5       101     5
6  . . . 11|0   6      6  . . . 01|0   2
7         1|00  4      7         1|00  4

B(2, 4)

B(2, 4) implies 2^4 or 16 bit sequences. There are 16 odd 16-bit sequences with 16 overlapping unique four-bit subsequences:

0x09af  0000100110101111
0x09eb  0000100111101011
0x0a6f  0000101001101111
0x0a7b  0000101001111011
0x0b3d  0000101100111101
0x0b4f  0000101101001111
0x0bcd  0000101111001101
0x0bd3  0000101111010011
0x0cbd  0000110010111101
0x0d2f  0000110100101111
0x0d79  0000110101111001
0x0de5  0000110111100101
0x0f2d  0000111100101101
0x0f4b  0000111101001011
0x0f59  0000111101011001
0x0f65  0000111101100101

for instance 0x0d2f:

i  0000110100101111|000 s[i]
 0  0000 . . . . . . . .  0
 1   0001                 1
 2  . 0011 . . . . . . .  3
 3     0110               6
 4  . . 1101 . . . . . . 13
 5       1010            10
 6  . . . 0100 . . . . .  4
 7         1001           9
 8  . . . . 0010 . . . .  2
 9           0101         5
10  . . . . . 1011 . . . 11
11             0111       7
12  . . . . . . 1111 . . 15
13               111|0   14
14  . . . . . . . 11|00  12
15                 1|000  8

B(2, 5)

B(2, 5) implies 2^5 or 32 bit sequences. There are 2^11 or 2,048 odd 32-bit sequences with 32 overlapping unique five-bit subsequences, for instance 0x076be629

 i  00000111011010111110011000101001|0000 s[i]
 0  00000 . . . . . . . . . . . . . . . .  0
 1   00001                                 1
 2  . 00011 . . . . . . . . . . . . . . .  3
 3     00111                               7
 4  . . 01110 . . . . . . . . . . . . . . 14
 5       11101                            29
 6  . . . 11011 . . . . . . . . . . . . . 27
 7         10110                          22
 8  . . . . 01101 . . . . . . . . . . . . 13
 9           11010                        26
10  . . . . . 10101 . . . . . . . . . . . 21
11             01011                      11
12  . . . . . . 10111 . . . . . . . . . . 23
13               01111                    15
14  . . . . . . . 11111 . . . . . . . . . 31
15                 11110                  30
16  . . . . . . . . 11100 . . . . . . . . 28
17                   11001                25
18  . . . . . . . . . 10011 . . . . . . . 19
19                     00110               6
20  . . . . . . . . . . 01100 . . . . . . 12
21                       11000            24
22  . . . . . . . . . . . 10001 . . . . . 17
23                         00010           2
24  . . . . . . . . . . . . 00101 . . . .  5
25                           01010        10
26  . . . . . . . . . . . . . 10100 . . . 20
27                             01001       9
28  . . . . . . . . . . . . . . 1001|0. . 18
29                               001|00    4
30  . . . . . . . . . . . . . . . 01|000   8
31                                 1|0000 16

B(2, 6)

B(2, 6) implies 2^6 or 64 bit sequences. There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit subsequences, for instance 0x022fdd63cc95386d

 i  0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
 0  000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  0
 1   000001                                                                 1
 2  . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
 3     000100                                                               4
 4  . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8
 5       010001                                                            17
 6  . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
 7         000101                                                           5
 8  . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
 9           010111                                                        23
10  . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11             011111                                                      31
12  . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13               111110                                                    62
14  . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15                 111011                                                  59
16  . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17                   101110                                                46
18  . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19                     111010                                              58
20  . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21                       101011                                            43
22  . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23                         101100                                          44
24  . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25                           110001                                        49
26  . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27                             000111                                       7
28  . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29                               011110                                    30
30  . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31                                 111001                                  57
32  . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33                                   100110                                38
34  . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35                                     011001                              25
36  . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37                                       100100                            36
38  . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . .  9
39                                         010010                          18
40  . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41                                           001010                        10
42  . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43                                             101010                      42
44  . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45                                               101001                    41
46  . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47                                                 100111                  39
48  . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49                                                   011100                28
50  . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51                                                     110000              48
52  . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53                                                       000011             3
54  . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . .  6
55                                                         001101          13
56  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57                                                           110110        54
58  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59                                                             01101|0     26
60  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00  . 52
61                                                               101|000   40
62  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000  16
63                                                                 1|00000 32

De Bruijn Graphs

A De Bruijn graph is a directed graph representing overlaps between sequences of symbols ^[6] .

Each vertex has exactly m incoming and m outgoing edges
Each n-dimensional de Bruijn graph is the line digraph of the (n-1)-dimensional de Bruijn graph
Each de Bruijn graph is Eulerian and Hamiltonian. The Euler cycles and Hamiltonian cycles of these graphs are de Bruijn sequences.

The graph construction of the three smallest binary de Bruijn graphs

B(2, 4) Graph

A De Bruijn graph. Every four-digit sequence occurs exactly once if one traverses every edge exactly once and returns to one's starting point.

De Bruijn Graph on a Chess Board

A directed De Bruijn Graph of B(2, 6) sequences with Little-Endian Rank-File Mapping board coordinates (a1 = 0, b1 = 1, h8 = 63). For topology reasons, almost each node (except a1 and h8) of the graph is deconcentrated and appears twice in the form of two reversed binary trees. The leaf outputs join the respective reversed tree. Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares exactly once.

+----------------->---------------a1--------------<-----------------+
|                                 |                                 |
|                                 b1                                |
|                 +--------------/  \-------------+                 |
|                c1                               d1                |
^         +-----/  \-----+                 +-----/  \-----+         |
|        e1              f1               g1              h1        |
|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     |
|    a2      b2      c2      d2       e2      f2      g2      h2    |
|  a3  b3  c3  d3  e3 |f3| g3  h3   a4  b4  c4  d4  e4  f4  g4  h4  |
+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8  |  |
     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^  |  |
                                                                 |  |
+----------------->---------------h8--------------<--------------+  ^
|                                  |                                |
|                                 g8                                |
|                 +--------------/  \-------------+                 |
|                f8                               e8                |
^         +-----/  \-----+                 +-----/  \-----+         |
|        d8              c8               b8              a8        |
|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     |
|    h7      g7      f7      e7       d7      c7      b7      a7    |
|  h6  g6  f6  e6  d6 |c6| b6  a6   h5  g5  f5  e5  d5  c5  b5  a5--+
+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1
     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

De Bruijn Networks

So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by Feldmann et al. to connect Transputer networks ^[7] ^[8] .

Selected Publications

1894

Camille Flye Sainte-Marie (1894). Solution to question nr. 48, L'Intermédiaire des Mathématiciens 1, reproduced in Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf

1946

Nicolaas de Bruijn (1946). A Combinatorial Problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764.
Jack Good (1946). Normal Recurring Decimals. Journal of the London Mathematical Society ^[9]

1950 ...

Lester Randolph Ford, Jr. (1957). A Cyclic Arrangement of M-Tuples. Report No. P-1071. Rand Corporation
Solomon W. Golomb (1967, 1982). Shift Register Sequences. Holden-Day Inc., revised 2nd edition, Aegean Park Press
Harold M. Fredricksen (1968). Disjoint Cycles from the de Bruijn Graph. Ph.D. thesis, University of Southern California, advisor Solomon Wolf Golomb

1970 ...

Harold M. Fredricksen (1970). The lexicographically least de Bruijn cycle. Journal of Combinatorial Theory, Vol. 9, No. 1
Abraham Lempel (1970). On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers. IEEE Transactions on Computers, Vol. 19, No. 12
Harold M. Fredricksen (1972). Generation of the Ford Sequence of Length 2n, n Large. JPL Technical Report 32-1526, Vol. IV, pdf

1990 ...

Yuejiang Huang (1990). A new algorithm for the generation of binary de Bruijn sequences. Journal of Algorithms, Vol. 11, No. 1
Chris J. Mitchell, Tuvi Etzion, Kenneth G. Paterson (1996). A method for constructing decodable de Bruijn Sequences. pdf via CiteSeerX
Fred S. Annexstein (1997). Generating De Bruijn Sequences: An Efficient Implementation. IEEE Transactions on Computers, Vol. 46, No. 2, pdf, Supplement: C-code implementation
Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf

2000 ...

Vladimir Raphael Rosenfeld (2002). Enumerating De Bruijn Sequences. Institute of Evolution, University of Haifa, pdf
Vladimir Raphael Rosenfeld (2002). Enumerating Kautz Sequences. Institute of Evolution, University of Haifa, pdf
Anwitaman Datta, Sarunas Girdzijauskas, Karl Aberer (2004). On de Bruijn routing in distributed hash tables: There and back again. P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, pdf
Pierre Fraigniaud, Philippe Gauron (2005). D2B: a de Bruijn Based Content-Addressable Network. pdf
Drew Armstrong (2006). De Bruijn Sequences. pdf
Jean Berstel, Dominique Perrin (2007). The origins of combinatorics on words. European Journal of Combinatorics 28, pdf

2010 ...

Yaw-Ling Lin, Charles B. Ward, Bharat Jain, Steven Skiena (2011). Constructing Orthogonal de Bruijn Sequences. LNCS 6844, WADS 2011
Zuling Chang, Martianus Frederic Ezerman, San Ling, Huaxiong Wang (2016). On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials. arXiv:1611.10088 ^[10]
Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, San Ling, Huaxiong Wang (2017). Large Order Binary de Bruijn Sequences via Zech's Logarithms. arXiv:1705.03150 ^[11]
Joe Sawada, Aaron Williams (2017). Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences. Journal of Discrete Algorithms, Vol. 43, No. C, pdf

External Links

De Bruijn sequence from Wikipedia
De Bruijn graph from Wikipedia
Kautz graph from Wikipedia
Koorde from Wikipedia
A166315 - OEIS
Lyndon word from Wikipedia
If - Forgotten Roads, Beat-Club #71, September 25, 1971, YouTube Video

References

^ De Bruijn sequence from Wikipedia
^ Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf
^ Escher's Moebius Strip - Ants, from Escher for Real (C) Copyright 2002-2011 Gershon Elber, Computer Science Department, Technion, based on Moebius Strip II, 1963
^ Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf
^ Nicolaas de Bruijn (1985). In Memoriam T. van Ardenne-Ehrenfest. pdf
^ De Bruijn graph from Wikipedia
^ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6, pdf
^ Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems Phd-Thesis, pdf
^ Recurring decimal from Wikipedia
^ LFSR from Wikipedia
^ Zech's logarithm from Wikipedia

What links here?

Page	Date Edited
Backtracking	Dec 16, 2017
BitScan	Sep 10, 2017
Charles Leiserson	Oct 12, 2016
Data	Nov 26, 2017
De Bruijn sequence	Feb 20, 2018
De Bruijn Sequence Generator	Dec 1, 2016
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Harald Prokop	Nov 29, 2017
Hash Table	Jan 1, 2018
Keith H. Randall	Jun 16, 2015
Kim Walisch	Aug 10, 2017
Kurt	Apr 20, 2014
Linked List	Oct 11, 2016
Magic Bitboards	Apr 13, 2018
Mathematician	Apr 9, 2018
Nicolaas de Bruijn	Feb 3, 2015
Shared Hash Table	Sep 11, 2017
Tim Mann	Nov 5, 2016
Transputer	Apr 30, 2015
Tunguska	Sep 16, 2017

Up one Level

Debugging

GerdIsenberg — Sat, 20 Jan 2018 22:20:29 GMT

Home * Programming * Debugging

		Debugging is a process of finding and reducing bugs in a computer program. A debugger, usually in software, allows to execute the program (debugee) under its control, to set breakpoints, let the user step to single lines of his source or machine code, to inspect variables, memory and processor registers. Processors often provide special instructions for the purpose of debugging.
Hin und her und rundherum Kriecht es, fliegt es mit Gebrumm ^[1]

x86 Breakpoints

8086, x86 and x86-64 have the int 3 one byte software interrupt instruction with opcode 0xCC, which might be explicitly used, or implicitly in assertions. This instruction is also used, when setting a breakpoint from a debugger, where current opcode is (temporarily) replaced by the int 3 opcode (0xCC), which when executed calls a special interrupt routine of the debugger or runtime system.

Breakpoint opcode may be inserted inside the code at compile time, for instance with x86 inline assembly or compiler intrinsic like DebugBreak ^[2] :

  __asm int 3

Compiler Support

Various compiler allow a special Debug build, which disables optimizations, default initialization of otherwise not initialized variables or memory, and/or enable runtime checking, like bounds checking of array access. Various integrated development environments (IDE) provide an integrated debugger.

Debugging the Search

A recursive search is quite hard to debug. Therefor chess programs may provide debug routines to use a sequence of certain moves or a zobrist key as a precondition to break the search if they occur. Here are Tord Romstad's suggestions in a reply to Patrice Duhamel ^[3]:

Extend the UCI/XBoard command set with a few commands of your own for use in debugging. In particular, it is useful to have a command for looking up the current position in the hash table and printing the information (score, score type, best move , etc). to the standard output. You can use this to browse the search tree after a search is finished. When you want to know why the program discarded some move, you can make the move and inspect the hash table entry for the corresponding position to find the score and refutation. I've found this to be a very valuable debugging technique, and even have a simple GUI app for browsing the tree (the GUI app communicates with the engine through pipes connected to the standard input and output).
The technique above can be further enhanced by including lots of additional information in the hash table when debugging the program. I sometimes store complete move lists with information about extension, reduction and pruning decisions for each move in every transposition table entry. Of course this makes each entry huge and greatly slows down the search, but it can be useful when chasing bugs or looking for ways to make the search more efficient.
Implement an MTD(f) search, even if you intend to use PVS. MTD(f) is great for debugging the hash table; all sorts of obscure bugs which are very tricky to find in PVS or other conventional searches suddenly become easy to spot.
Whenever you add some non-trivial new function to your program, try to write two versions: One which is very slow and stupid, but almost certainly correct, and one which is highly optimized. Verify on a huge number of positions that they give the same results. Remove the slow version only when you feel 100% sure that the fast version is correct.
Always make symmetry tests when you add a new term to your evaluation function .
Run through a simple tactical test like WAC at 5 seconds/move every time you change something important in your search. Don't try to optimize the results, but just make sure that the score doesn't suddenly drop dramatically.
Check the quality of your move ordering by measuring how often a beta cutoff occurs on the first move, and the frequencies with which the 1st, 2nd, 3rd, ... move turns out to be best at PV nodes.

Publications

Zhonghua Yang, Tony Marsland (1992). Global Snapshots for Distributed Debugging. ICCI 1992, pp. 436-440
Zhonghua Yang, Tony Marsland (1993). Distributed Debugging in the Large. pdf
Chrilly Donninger (1999). Computer machen keine Fehler. CSS 2/99, pdf (German)
Yngvi Björnsson and Jónheiður Ísleifsdóttir (2006). Tools for debugging large game trees. 11th Game Programming Workshop, Hakone, Japan » Search Tree
Jónheiður Ísleifsdóttir (2007). GTQL: A Query Language for Game Trees. M.Sc. thesis, Reykjavík University, pdf
Jónheiður Ísleifsdóttir, Yngvi Björnsson. (2008). GTQ: A Language and Tool for Game-Tree Analysis. CG 2008, pdf

Forum Posts

2000 ...

Debug Help by Georg von Zimmermann, CCC, September 16, 2000
Winboard.debug by David Rasmussen, CCC, December 07, 2002 » WinBoard
bugs, Bugs and BUGS! by milix, CCC, May 27, 2004
Q. Why might node count differ between DEBUG and RELEASE by David B. Weller, CCC, December 13, 2004

2005 ...

General Tips and Tricks for debugging a search by Eric Oldre, CCC, June 15, 2005
Testing and debugging chess engines by Patrice Duhamel, Winboard Forum, December 03, 2006
Re: Testing and debugging chess engines by Tord Romstad, Winboard Forum, December 05, 2006

2010 ...

Debugging regression tests by Onno Garms, CCC, June 16, 2011 ^[4]
DrMemory: memory debugger tool for Windows (and Linux) by Martin Sedlak, CCC, January 22, 2013 » Memory

2015 ...

OT: Finding the Line of the Assert Fail? by Steve Maughan, CCC, March 07, 2015 » Maverick
Best way to debug perft? by Meni Rosenfeld, CCC, January 25, 2016 » Perft
Help with Debugging My Chess Engine by Pranav Deshpande, CCC, September 28, 2016
Help with Debugging My Chess Engine - 2 by Pranav Deshpande, CCC, September 30, 2016
How to go about chasing a bug like this? by Colin Jenkins, CCC, February 09, 2017
How to find SMP bugs ? by Lucas Braesch, CCC, March 15, 2017 » Lazy SMP
assert by Folkert van Heusden, CCC, November 13, 2017 ^[5]
How do I debug cutechess-cli engine input/output? by Daniel Dugovic, CCC, December 25, 2017 » Cutechess-cli
Debugging UCI engine by Cadel Watson, CCC, January 19, 2018 » InBetween, UCI Engines

External Links

Debugging from Wikipedia
Debugger from Wikipedia
Assertion (software development) from Wikipedia
Regression testing from Wikipedia
GDB: The GNU Project Debugger
gdb + eclipse - SWiK
IDA Pro Disassembler - multi-processor, windows hosted disassembler and debugger
SoftICE from Wikipedia
CHESS - Microsoft Research a tool for finding and reproducing Heisenbugs in concurrent programs.
From Chapter 5, Debugging excerpt from Chapter 5 of
Brian W. Kernighan, Rob Pike (1999). The Practice of Programming. Addison-Wesley, ISBN: ISBN 0-201-61586-X
Electric Fence (Memory Debugger) from Wikipedia » Memory

References

^ Wilhelm-Busch, Max und Moritz - Fünfter Streich from Wilhelm-Busch Seiten von Jochen Schöpflin (German)
^ DebugBreak Function (Windows) from Develop for Windows 7 and Windows Vista | MSDN
^ Re: Testing and debugging chess engines by Tord Romstad, Winboard Forum, December 05, 2006
^ Regression testing from Wikipedia
^ Assertion (software development) from Wikipedia

What links here?

Page	Date Edited
Bibob	Jul 5, 2014
Cheese	Feb 17, 2018
Color Flipping	May 17, 2017
Cutechess-cli	Jan 6, 2018
Debugging	Jan 20, 2018
Engine Testing	Feb 1, 2018
Fencer	Jan 20, 2013
Fidelity Electronics	Dec 1, 2017
Fruit	Sep 27, 2016
Graphics Programming	Dec 22, 2017
InBetween	Jan 21, 2018
Incremental Updates	Sep 6, 2017
Iteration	May 5, 2017
Jónheiður Ísleifsdóttir	Jun 22, 2015
Logging	Jan 20, 2018
Martin Sedlak	Dec 25, 2017
Maverick	Jan 7, 2016
Memory	Dec 8, 2017
Norman Schmidt	Oct 12, 2017
Parallel Search	Dec 30, 2017
Perft	Sep 26, 2017
Perft Results	Feb 10, 2018
Principal variation	Dec 4, 2017
Profiling	Sep 15, 2016
Programming	Dec 16, 2017
Search Tree	Dec 23, 2016
Steve Maughan	Jan 31, 2018
Vice	Mar 8, 2016
WinBoard	Mar 4, 2018
Zhonghua Yang	May 23, 2016

Up one Level

Delphi

GerdIsenberg — Fri, 16 Dec 2016 20:07:56 GMT

Home * Programming * Languages * Delphi

		Delphi, a programming language dialect of the Object Pascal programming language, a branch of object-oriented derivatives of Pascal, mostly known as the primary programming language of Embarcadero Delphi, formerly CodeGear Delphi, Inprise Delphi and Borland Delphi , designed and implemented by Anders Hejlsberg, the creator of Turbo Pascal. As a chief architect at Borland , Hejlsberg secretly turned Turbo Pascal into an object-oriented application development language, complete with a truly visual environment and superb database-access features. Developer Danny Thorpe chose the name Delphi, in reference to the Oracle at Delphi. Delphi provides an Integrated development environment for Microsoft Windows applications. Delphi pioneered in rapid application development by introducing an application framework and visual window layout designer that drastically reduced application prototyping times of GUI and Database applications. Delphi XE ^[1] is now part of Embarcadero RAD Studio ^[2], including C++Builder and UML modeling ^[3], still supporting x86 inline assembly ^[4]. A former Linux version of Borland Delphi, called Kylix discontinued. In 2009, Embarcadero announced 64-bit, Linux and Mac OS support ^[5] ^[6] .
John Collier - Priestess of Delphi ^[7]

Delphi Engines

Dynamic list with tag 'delphi'. Engines (at least some versions) written in Delphi or parts in Pascal.

1. Anatoli
2. Anechka
3. Argonaut
4. Atomystica
5. BBchess
6. Bestia
7. BlackBishop
8. Blikskottel
9. Booot
10. Celes
11. Critter
12. Crux
13. Delfi
14. Delphil
15. DelphiMax
16. Eveann
17. Excelsior
18. Gustav
19. Holmes
20. Ikarus
21. KChess
22. Nexus
23. RDChess
24. SpiderChess
25. Ufim
26. XiniX
27. Zzzzzz

Publications

Martin Harvey (2000). Multithreading - The Delphi Way. » Thread

Forum Posts

Delphi / Winboard by Tony Werten, CCC, July 13, 2000 » WinBoard
Delphi version of TSCP by Steve Maughan, CCC, December 18, 2000
Delphi/Kylix Compiler by Olaf Jenkner, CCC, March 14, 2001
Which is the strongest Delphi chess program? by Andreas Herrmann, CCC, March 14, 2002
Delphi and the UCI Protokoll by Martin Bauer, CCC, April 18, 2002 » UCI
One more time Delphi and UCI by Martin Bauer, CCC, April 21, 2002
Winboard problem (maybe Delphi only ) by Tony Werten, CCC, August 22, 2003
Question for Delphi programmers by Ed Seid, Winboard Forum, April 23, 2004
A Delphi - WinBoard problem by Martin Giepmans, CCC, September 24, 2004
What can .Net do for me? by Linda Scherzer, DerKeiler.com, June 3, 2005
Ikarus, FastMM4 and Delphi 2005? by Steve Maughan, CCC, November 22, 2005 » Ikarus ^[8]
Critter: Pascal vs C by Richard Vida, CCC, August 27, 2009
for Pascal fans: Critter by Richard Vida, CCC, September 16, 2011 » Critter

External Links

References

What links here?

Page	Date Edited
Anatoli	Oct 22, 2014
Andrea Lanza	Feb 27, 2014
Andreas Herrmann	Nov 7, 2014
Anechka	Mar 20, 2014
Argonaut	Apr 15, 2013
Assembly	Sep 3, 2017
Atomystica	Oct 2, 2014
BBchess	Oct 30, 2011
Bestia	Jan 5, 2013
Bitboards	Nov 14, 2017
BlackBishop	Nov 7, 2014
Blikskottel	Feb 15, 2014
Booot	Jan 22, 2018
C sharp	Nov 26, 2017
Celes	May 23, 2014
Chest	Mar 3, 2015
Critter	Jan 25, 2014
Crux	Jan 30, 2017
Delfi	Jan 7, 2016
Delphi	Dec 16, 2016
Delphil	Sep 17, 2016
DelphiMax	Apr 3, 2013
Engines	Mar 10, 2018
Eveann	Apr 3, 2017
Excelsior	Apr 16, 2014
Generic Programming	Jul 7, 2012
Gustav	May 14, 2016
Hector for Chess	Jan 7, 2016
Holmes	Apr 24, 2014
Ikarus	Jul 5, 2016
KChess	Jan 2, 2018
Languages	Nov 26, 2017
Maciej Szmit	May 5, 2017
Marek Kłonowski	Apr 16, 2014
Martin Bauer	Apr 3, 2013
Martin Blume	May 17, 2012
Martin Giepmans	Jan 7, 2016
Minimax (program)	Dec 27, 2013
Mitja Luštrek	Jan 23, 2016
Nexus	Jan 7, 2016
Pascal	Nov 28, 2016
Pawel Koziol	Dec 17, 2017
Philippe Fabiani	Sep 15, 2016
Protej	Jul 27, 2014
RDChess	May 3, 2013
Richard Vida	Aug 11, 2013
Rudolf Posch	Apr 5, 2015
SpiderChess	Oct 4, 2017
Thread	Apr 22, 2018
Tony van Roon-Werten	Jan 14, 2017
UCI	Mar 4, 2018
Ufim	Mar 22, 2014
x86	Jan 4, 2018
XiniX	Jan 7, 2016
Zzzzzz	May 14, 2016

Up one Level

Dynamic Programming

GerdIsenberg — Sun, 11 Feb 2018 08:50:11 GMT

DP in Computer Chess

See also

Selected Publications

Home * Programming * Algorithms * Dynamic Programming

Dynamic Programming, (DP)
a mathematical, algorithmic optimization method of recursively nesting overlapping sub problems of optimal substructure inside larger decision problems. The term DP was coined by Richard E. Bellman in the 50s not as programming in the sense of producing computer code, but mathematical programming, planning or optimization similar to linear programming, devoted to the study of multistage processes. These processes are composed of sequences of operations in which the outcome of those preceding may be used to guide the course of future ones ^[1].

DP in Computer Chess

In computer chess, dynamic programming is applied in depth-first search with memoization aka using a transposition table and/or other hash tables while traversing a tree of overlapping sub problems aka child positions after making a move by one side in top-down manner, gaining from stored positions of sibling subtrees due to transpositions and/or common aspects of positions, in particular effective inside an iterative deepening framework. Another approach of dynamic programming in computer chess or computer games is the application of retrograde analysis, to solve a problem by solving subproblems in bottom-up manner starting from terminal nodes ^[2].

Selected Publications

1953 ...

Richard E. Bellman (1953). An Introduction to the Theory of Dynamic Programming. R-245, RAND Corporation
Richard E. Bellman (1954). The Theory of Dynamic Programming. P-550, RAND Corporation, pdf
Richard E. Bellman (1954). On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, U. S. Air Force Project RAND
Samuel Karlin (1955). The Stucture of Dynamic Programming Models. Naval Research Logistics, Vol. 2
Richard E. Bellman (1957). Dynamic Programming. Princeton University Press
Richard E. Bellman (1958). Dynamic Programming and Stochastic Control Processes. RAND Corporation, Santa Monica, CA, Information and Control 1

1960 ...

Richard E. Bellman (1960). Sequential Machines, Ambiguity, and Dynamic Programming. Journal of the ACM, Vol. 7, No. 1
Ronald A. Howard (1960). Dynamic Programming and Markov Processes. MIT Press, amazon ^[3]
Richard E. Bellman, Stuart E. Dreyfus (1962). Applied Dynamic Programming. RAND Corporation, Princeton University Press, pdf
Richard E. Bellman (1962). Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM, Vol. 9, No. 1, 1961 pdf preprint
David Blackwell (1962). Discrete Dynamic Programming. Annals of Mathematical Statistics, Vol. 33, No. 2
Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
David Blackwell (1965). Discounted Dynamic Programming. Annals of Mathematical Statistics, Vol. 36, No. 1 ^[4]
David Blackwell (1967). Positive Dynamic Programming. Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability

1970 ...

David Blackwell (1976). The Stochastic Processes of Borel Gambling and Dynamic Programming. Annals of Statistics, Vol. 4, No. 2
Stuart E. Dreyfus, Averill M. Law (1977). Art and Theory of Dynamic Programming. Academic Press
Steven E. Shreve, Dimitri Bertsekas (1979). Universally Measurable Policies in Dynamic Programming. Mathematics of Operations Research, Vol. 4, No. 1

1990 ...

Dimitri Bertsekas (1996, 2017). Dynamic Programming and Optimal Control. Athena Scientific

2000 ...

Dimitri Bertsekas (2001). Neuro-Dynamic Programming: An Overview. Encyclopedia of Optimization, pdf, slides as pdf
Stuart E. Dreyfus (2002). Richard Bellman on the Birth of Dynamic Programming. Operations Research, Vol. 50, No. 1, pdf
Richard E. Bellman (2003). Dynamic Programming. Dover Publications
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (2006). Algorithms. McGraw-Hill, Chapter 6 Dynamic programming (pdf)
Sylvain Gelly, Jérémie Mary, Olivier Teytaud (2006). Learning for stochastic dynamic programming. pdf, pdf
Sylvain Gelly, Olivier Teytaud, Jérémie Mary (2007). Active learning in regression, with application to stochastic dynamic programming. ICINCO and CAP, 2007, pdf
Warren B. Powell (2007). Approximate Dynamic Programming - Solving the Curses of Dimensionality. Wiley

2010 ...

Richard E. Bellman (2010). Dynamic Programming. With a new introduction by Stuart E. Dreyfus, Princeton University Press
Rémi Munos (2010). Approximate dynamic programming. In Olivier Sigaud and Olivier Buffet, editors, Markov Decision Processes in Artificial Intelligence, chapter 3, ISTE Ltd and John Wiley & Sons Inc., pdf
Warren B. Powell (2011). Approximate Dynamic Programming - Solving the Curses of Dimensionality. 2nd edition, Wiley
Dimitri Bertsekas (2013). Abstract Dynamic Programming. Athena Scientific
Richard E. Bellman, Stuart E. Dreyfus (2015). Applied Dynamic Programming. Princeton University Press

External Links

References

^ Richard E. Bellman (1953). An Introduction to the Theory of Dynamic Programming. R-245, RAND Corporation
^ Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
^ Markov chain from Wikipedia
^ David Blackwell and Dynamic Programming (pdf) by William Sudderth

What links here?

Page	Date Edited
Algorithms	May 5, 2017
Automated Tuning	Feb 27, 2018
Dynamic Programming	Feb 11, 2018
Genetic Programming	Dec 26, 2017
Jérémie Mary	May 11, 2013
Learning	Feb 20, 2018
Mathematician	Apr 9, 2018
Neural Networks	Mar 12, 2018
Olivier Teytaud	Jan 7, 2017
Programming	Dec 16, 2017
Reinforcement Learning	Feb 12, 2018
Rémi Munos	Dec 8, 2017
Retrograde Analysis	Mar 21, 2017
Richard E. Bellman	Mar 15, 2017
Robert A. Wagner	Oct 28, 2013
Sylvain Gelly	Dec 31, 2016
Temporal Difference Learning	Feb 20, 2018
Transposition Table	Apr 19, 2018

Up one Level

Forth

GerdIsenberg — Sat, 15 Jun 2013 08:34:44 GMT

Home * Programming * Languages * Forth

Forth,
a structured, imperative, reflective, stack-based computer programming language and environment. It performs arithmetical and logical operations on a stack in reverse Polish notation. Forth evolved from Charles H. (Chuck) Moore's programming system from 1958. With Elizabeth Rather, Chuck Moore founded the FORTH, Inc. ^[1] in 1973. Chuck Moore now develops extremely fast, low-power, multi-core chips which use a subset of Forth for their instruction set. They might be an interesting target for a high-powered yet economical dedicated chess computer.

Publications

James Bowman (2010). J1: a small Forth CPU Core for FPGAs. EuroForth 2010, pdf ^[2]

External Links

Forth (programming language) from Wikipedia
Forth Language
Stack machine from Wikipedia
Green Arrays 40- and 144-core Forth microcontrollers
ANS Forth - generate and use a directed acyclic word graph (DAWG) by Ian Osgood
Forth application benchmark suite (ZIP) contains both FCP by Ian Osgood and Brainless by David Kühling ^[3]

References

What links here?

Page	Date Edited
Brainless (Forth)	Jun 24, 2017
FCP	Jun 15, 2013
Forth	Jun 15, 2013
FPGA	Jul 9, 2016
Ian Osgood	Jun 14, 2013
Languages	Nov 26, 2017
Nova	Jan 20, 2016
Open Source Engines	Jul 14, 2015
Stack	Nov 18, 2016

Up one Level

Fortran

GerdIsenberg — Wed, 26 Jul 2017 18:57:23 GMT

Home * Programming * Languages * Fortran

Fortran is a general purpose, procedural and imperative programming language. Fortran was proposed and designed by John W. Backus as alternative for the IBM 704 assembly language. A draft specification for the IBM mathematical Formula Translating System was completed by mid 1954. The first Fortran compiler appeared in 1957 and was the first widely used high-level programming language. Successive versions have added varios features over the years, such as recursive routines and dynamic memory allocation in Fortran 90. Many early chess programs were written in Fortran.

Punched card

Punched card from a Fortran program: Z(1) = Y + W(1) ^[1]

Sample Chess Code

A recursive Fortran 90 Alpha-Beta search routine ^[2]:

RECURSIVE FUNCTION EVALUATE (ID, PRUNE) RESULT (RES) 
  USE GLOBALS 
  IMPLICIT INTEGER(A-Z) 
  DIMENSION XX(0:26), YY(0:26), CC(0:26) 
  LEVEL=LEVEL+1 
  BESTSCORE=10000*ID 
  DO B=7,0, -1 
     DO A=7,0, -1 
        ! generate the moves for all the pieces 
        ! and iterate through them 
        IF (SGN(BOARD(B,A))/=ID) CYCLE 
        CALL MOVELIST (A, B, XX, YY, CC, NDX) 
        DO I=0,NDX,1 
           X=XX(I); Y=YY(I); C=CC(I) 
           OLDSCORE=SCORE; MOVER=BOARD(B,A); TARG=BOARD(Y,X) 
           ! make the move and evaluate the new position 
           ! recursively. Targ holds the relative value of the piece 
           ! allowing use to calculate material gain/loss 
           CALL MAKEMOVE (A, B, X, Y, C) 
           IF (LEVEL<MAXLEVEL) THEN 
              SCORE=SCORE+EVALUATE(-ID, & 
                    BESTSCORE-TARG+ID*(8-ABS(4-X)-ABS(4-Y))) 
           END IF 
           SCORE=SCORE+TARG-ID*(8-ABS(4-X)-ABS(4-Y)) 
           ! we want to minimize the maximum possible loss 
           ! for black 
           IF ((ID<0 .AND. SCORE>BESTSCORE) .OR. & 
              (ID>0 .AND. SCORE<BESTSCORE)) THEN 
              BESTA(LEVEL)=A; BESTB(LEVEL)=B 
              BESTX(LEVEL)=X; BESTY(LEVEL)=Y 
              BESTSCORE=SCORE 
              IF ((ID<0 .AND. BESTSCORE>=PRUNE) .OR. & 
                 (ID>0 .AND. BESTSCORE<=PRUNE)) THEN 
                 BOARD(B,A)=MOVER; BOARD(Y,X)=TARG; SCORE=OLDSCORE 
                 LEVEL=LEVEL-1 
                 RES = BESTSCORE 
                 RETURN 
              END IF 
           END IF 
           BOARD(B,A)=MOVER; BOARD(Y,X)=TARG; SCORE=OLDSCORE 
        END DO 
     END DO 
  END DO 
  LEVEL=LEVEL-1 
  RES=BESTSCORE 
  RETURN 
END FUNCTION EVALUATE

Publications

P E Bryant and M J Baylis (1968). FORTRAN - A Comparative Study. Literature: Reports hosted by Atlas Computer Laboratory
James Gillogly (1970). MAX : A FORTRAN Chess Player. RAND paper
John Backus (1978) The history of Fortran I, II, and III. in Richard L. Wexelblat (ed) History of programming languages I
Alfio Marazz, Johann Joss, Alex Randriamiharisoa (1993). Algorithms, routines, and S functions for robust statistics: the FORTRAN library ROBETH with an interface to S-PLUS. Wadsworth And Brooks/Cole Statistics/Probability Series, amazon

External Links

Fortran from Wikipedia
Cray Blitz FTP Page crayblitz.tar.gz Source Code, by Robert Hyatt
Microsoft® FORTRAN Version Features
Intel Fortran Compiler
History of FORTRAN and FORTRAN II — Software Preservation Group from The Computer History Museum
Fortran FAQ
comp.lang.fortran Discussion about Fortran

References

^ Punched card from Wikipedia, Image from the Wikimedia Commons
^ chessf90.zip, Source and 64 bit Windows executable of A Fortran 90 chess program from cap.connx.com by Dann Corbit

What links here?

Page	Date Edited
ACM 1970	Jun 13, 2015
ACM 1971	Jul 19, 2016
ACM 1972	Dec 22, 2017
ACM 1973	Jan 19, 2018
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
ACM 1986	Dec 5, 2017
ACM 1987	Dec 5, 2017
ACM 1988	Dec 5, 2017
ACM 1989	Jun 7, 2016
ACM 1991	Nov 25, 2017
ACM 1993	Oct 30, 2017
ACM 1994	May 5, 2017
Alan Kotok	Sep 21, 2014
Black Knight	Dec 25, 2017
Blitz	Dec 23, 2017
Bs6676	Jul 21, 2016
CHAOS	Dec 28, 2017
Charly	Jan 10, 2013
Chess (Program)	Dec 22, 2017
Chest	Mar 3, 2015
Chris Peters	Oct 13, 2014
Clash	May 19, 2016
Coko	Jul 13, 2015
Cray Blitz	Dec 25, 2017
Cube	Apr 23, 2017
Dan Spracklen	Jan 17, 2017
Dark Horse	Jul 19, 2016
DOCCC 1981	Nov 14, 2015
DOCCC 1982	Nov 14, 2015
DOCCC 1983	Nov 13, 2015
DOCCC 1984	May 22, 2016
DOCCC 1985	Dec 9, 2016
DOCCC 1992	Dec 12, 2016
Donald Miller	Jan 21, 2012
Dynamic Tree Splitting	Apr 10, 2017
Fortran	Jul 26, 2017
GVNA	Nov 4, 2013
Heiner Marxen	Apr 19, 2014
Helmut Richter	Nov 29, 2017
IBM 704	Jan 2, 2016
Intel	Aug 29, 2015
James Gillogly	Jan 7, 2016
James Mundstock	Apr 10, 2013
Jerusalem CC Tournament 1978	Jan 3, 2018
John Stanback	Dec 7, 2016
Jonathan Schaeffer	Jan 29, 2018
Kai Himstedt	Jun 28, 2016
Kotok-McCarthy-Program	Jul 14, 2015
Lachex	Jan 7, 2016
Languages	Nov 26, 2017
M-20	Oct 9, 2013
Mater	Apr 26, 2016
MAX (Gillogly)	Sep 1, 2013
Merlin (GB)	Mar 25, 2015
Mikhail R. Shura-Bura	Oct 30, 2013
Mr. Turk	Feb 21, 2015
Nova	Jan 20, 2016
Nuchess	Apr 3, 2017
Orwell	Dec 31, 2017
Parwell	Sep 9, 2017
Paul W. Abrahams	Oct 9, 2013
Peasant	May 21, 2015
PK	Jan 8, 2016
PL 1	Jan 20, 2016
Planner	Sep 24, 2012
Pseudorandom number generator	May 11, 2017
Ribbit	Jan 19, 2018
Ron Hansen	Jan 7, 2016
Schach	Jan 7, 2016
Schach (US)	Jul 21, 2016
Schach MV 5,6	Nov 29, 2017
Shess	Jan 7, 2016
Tech	Apr 20, 2018
TechMate	Aug 23, 2014
Tony Marsland	Nov 27, 2017
TR-4	Aug 27, 2014
Treefrog	Jan 19, 2018
Ulf Rathsman	Jan 7, 2016
WCCC 1974	Jan 19, 2018
WCCC 1977	Dec 22, 2017
WCCC 1983	Jan 20, 2018
WCCC 1986	Jul 27, 2017
WCCC 1989	Dec 5, 2017
WCCC 1992	Feb 26, 2018
Xenarbor	Sep 6, 2014
Yaoqing Gao	May 23, 2016
CWtejP1 : 1954 Fortran	Sep 24, 2015

Up one Level

Wikispaces : chessprogramming - items matching description

2D Graphics Board

Table of Contents

Screenshots

Drawing Pieces

2D Vector Graphics

Bitmaps

Unicode

See also

Publications

Forum Posts

External Links

References

What links here?

3D Graphics Board

Table of Contents

Ergonomics

Screenshots & Images

Early 3D Boards

See also

Publications

Forum Posts

External Links

Basics

Projection

3D Graphics API and Frameworks

3D-Editors

Tutorials

3D Chess

References

What links here?

Algol

Table of Contents

Algol W

Selected Publications

External Links

References

What links here?

Algorithms

Table of Contents

General Concepts

Sorting and Searching

Enumeration and Backtracking

Mathematical Optimization

Combinatorial

See also

Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

External Links

Algorithms

Algebra and Calculus

Sorting and Searching

Misc

References

What links here?

Avoiding Branches

Table of Contents

Abs, Max, Min

Absolute value of an Integer

Maximum of two Integers

By CRT

By Sign-Mask

Minimum of two Integers

By CRT

By Sign-Mask

Conditional Expressions

Conditional Assignment

Conditional Increment

Conditional Write

Indirect Branch

See also

Forum Posts

External Links

References

What links here?