Winglet forum
Winboard forum
Talkchess forum
OpenChess forum
References

A chess program that beats most human players

 

01 Introduction
02 Anatomy of a chess program
03 Choices
	- What if your system is different?
04 Preparations
	- Setting up Microsoft Visual C++ 2010 Express
	- Setting up Winboard
05 First steps with C++
	001 your new friend
	- My C++ header philosophy
	- Targeting for 64-bit platforms
06 Reading user commands
	002 wingletx.cpp
	003 defines.h
	004 protos.h
	005 command.cpp
	006 globals.h
	007 extglobals.h
07 Internal representation of the chess board - bitboards
	- Bitwise setting and testing
	008 board.h
08 Displaying the position
	009 globals.h
	010 extglobals.h
	011 defines.h
	012 bitops.cpp
	013 protos.h
	014 wingletx.cpp
	015 command.cpp
	016 data.cpp
	017 board.cpp
09 Reading a FEN string
	018 readfen.cpp
	019 protos.h
	020 command.cpp
10 Setting up the board manually
	021 setup.cpp
	022 command.cpp
	023 protos.h
11 The move generator
	- The move structure
	024 move.h
	025 move.cpp
	- Move generation for Knights
	- Move generation for sliding pieces
	- 6 bits only
	- Calculation of a 6-bit occupancy state index
	- Rank occupancy
	- File occupancy - magic multipliers
	- A8H1 diagonal occupancy - magic multipliers
	- A1H8 diagonal occupancy - magic multipliers
	- Generalized sliding attack
	026 board.h
	027 data.cpp
	028 movegen.cpp
	- isAttacked
	029 command.cpp
	- Display the list of generated moves
	030 displaymove.cpp
	031 protos.h
	032 globals.h
	033 extglobals.h
	034 defines.h
12 Making the moves
	- How moves are stored
	035 gameline.h
	036 board.h
	- Adding timers
	037 timer.h
	038 timer.cpp
	- Perft - measuring speed and verify correctness
	039 perft.cpp
	040 makemove.cpp
	041 command.cpp
	042 defines.h
	043 protos.h
13 The evaluation function
	044 eval.cpp
	045 board.h
	046 board.cpp
	047 defines.h
	048 wingletx.cpp
	049 perft.cpp
	050 command.cpp
	051 data.cpp
	052 globals.h
	053 extglobals.h
14 Search
	- Minimax
	- Alpha-beta
	- Principal variation search
	- Collecting the principal variation
	054 globals.h
	055 extglobals.h
	056 board.h
	057 search.cpp
	058 command.h
15 Mate and draw detection
	- Move disambiguation
	059 globals.h
	060 extglobals.h
	061 protos.h
	062 board.h
	063 command.cpp
	064 data.cpp
	065 displaymove.h
	066 search.cpp
16 Repetition detection - Zobrist keys
	- Zobrist keys
	067 hash.h
	068 hash.cpp
	069 globals.h
	070 extglobals.h
	071 data.cpp
	072 board.h
	073 board.cpp
	074 makemove.cpp
	075 command.cpp
	076 search.cpp
17 Iterative deepening and move ordering
	077 board.h
	078 sortmoves.cpp
	079 search.cpp
18 Quiescence search and SEE
	- SEE
	080 board.h
	081 search.cpp
	082 qsearch.cpp
	083 see.cpp
	084 movegen.cpp
	085 globals.h
	086 extglobals.h
	087 data.cpp
	088 command.cpp
	089 defines.h
	090 wingletx.cpp
19 Null move pruning
	091 globals.h
	092 extglobals.h
	093 board.h
	094 search.cpp
20 Time control and running test suites
	- Running test suites
	095 protos.h
	096 board.h
	097 globals.h
	098 extglobals.h
	099 command.cpp
	100 peek.cpp
	101 data.cpp
	102 test.cpp
	103 search.cpp
	104 qsearch.cpp
21 Connecting to Winboard
	- Specifying and reading an initialization file as command line option
	- Think, analyze, ponder
	- Peeking for input during search
	- Time control in matches
	- Setting up Winboard
	105 globals.h
	106 extglobals.h
	107 winglet.cpp
	108 defines.h
	109 data.cpp
	110 commands.cpp
	111 search.cpp
	112 peek.cpp

Writing a chess program in 99 steps

A step-by-step guide for writing a bitboard chess engine, winglet
copyright
full source code

01  Introduction

This is a systematic guide to write a chess engine (connected to the Winboard chess interface). The targeted audience are chess programming enthusiasts.

You will only need a PC with Windows installed, because everything else is free. I do assume however that you know how to navigate in Windows, install programs, how to play chess, and how to program (but not necessarily in C++).

The program that will be developed is called winglet (because it is loosely derived from wing, my private engine). Winglet is free and open source. You can redistribute it and/or modify it under the terms of the GNU General Public License. 

All code is going to be built from scratch. You will see code snippets that list complete (but simple) functions. Followed later by code snippets to improve, or enhance, existing functions. In the left side of this page you will see an overview of all code snippets. The functionality of the code will grow 'organically', allowing you to follow my thinking, coding and testing (and hopefully without the bugs). In 99 steps? well, it's going to be slightly more than that, I just thought 99 would be a nice goal.

The reason why this is a step-by-step guide is to allow you to go through, and think through, all phases and concepts involved when writing a chess engine from scratch, in a more or less natural and logical order. You will be able to build, run, test and experiment with the program as its functionality increases.  Alternatively, you may just want to copy & paste the snippets, ending up with a complete chess program, and skip reading the explanations. That's fine, but you will not learn anything from that.  At the other end of the creativity scale, you can treat this as a rough guideline, program your own engine, use some of the idea's, copy code parts, or use nothing at all because you can do it better!

Another reason is that, for beginning chess programmers, it's not easy to decide where to start. There is a lot of information on the internet on specific chess programming topics, but not a lot of guidance on where and how to start, what comes next, when to start worrying about the interface (at the end!).

As Robert Hyatt has put it (and I fully agree): the evaluation and search functions are the heart & soul of a chess engine, it is mainly from these two components that an engine gets its 'personality', and mainly these two components make one engine stronger than another.  Some components of the engine may not be very engine specific, or they may not affect playing strength at all.  For instance, you will find fast and similarly looking bitboard move generators in many programs.  Winglet will provide you with a basis for experimenting and improving evaluation, search and move sorting in particular.  They are the three most underdeveloped functions in winglet, and this is done intentionally, to invite you to improve and develop an engine with its own personality / strength, without having to go through the hassle of writing the backbone from scratch. Once you start adding your own thoughts into the evaluation and search code, it will become your engine, with its own 'personality', and then you should give it it's own name too!

Some of you will find my programming style odd, or just plain wrong. I am OK with that. I like to keep things simple, understandable, readable, straightforward. So that ten years from now you will still be able to read and understand the code. If you are looking for compact or advanced C++ programming techniques, you will not find them here (unless required for speed, and then I would just copy whatever is available from the internet, after testing). This engine is going to be sufficiently fast, but relatively simple, providing you a backbone that you can expand upon, change and tweak.  The implementation of bitboards should be comprehensible to all.

This website will get you to the point that you have written a basic bitboard chess engine, playing reasonable chess, as a console program, or using the Winboard interface.
If you want to discuss this project, found a bug, or have an idea for improvement, you can send me a mail, or post in one of the chess programming forums listed above.

I learned chess programming from reading internet articles and open source code. Mostly internet articles from Robert Hyatt (author of Crafty) and Bruce Moreland, and of course studying the code of other open source programs.  Others invented everything I write in this guide, not me, and in some cases I even do not know who to give credit. Thanks to others, who made their thoughts, research and inventions available through publications, discussion forums, websites, and open source code, I was able to start programming my private chess engine, wing.  Check out the list of references if you want to read the same stuff I did.

02  Anatomy of a chess program

Chess programs determine the best move by traversing down a tree of possible moves and opponent moves, up to a certain depth, and then evaluate the resulting positions at the tree tips (leafs, at the end of the search branches) to see which move will lead to the best result, assuming that the opponent will also play the best moves. Note that this tree of variations is usually shown 'upside-down', i.e. with the root at the top and branches at the bottom:

The chess search tree is very wide (on average there are 35 legal moves for a chess position), and very deep (the average chess game is 40 moves, or 80 half moves or plies).  Not all possible variations can be evaluated (note that 35⁸⁰ is approximately 10¹²³ ;  by comparison, the estimated number of atoms in the universe is 10⁸⁰).  The search function is implemented as a recursive function (a function that makes a call to itself); at every chess position (node), the move generator returns a list of moves to make (and unmake, when the search traverses back up to the root of the tree to pass the result of the search to the calling function).

The evaluation of chess positions is done by considering many static aspects, starting of course with the material balance, and considering pawn structure, king safety, piece mobility, and many other aspects of the position.  The score is usually expressed in centipawns (a pawn equals 100).  

Speed is important, and there are many techniques to improve the search speed of a chess program (including using bitboards and hash tables).  Some chess engines will display their search speed in knods/s (1000 nodes per second).  

Another important area of optimization is the search algorithm. The main objective here is to minimize the number of moves to search, by skipping moves that are proven to be, or seem to be, 'unattractive'. Techniques to improve and speed up the search include the alpha-beta algorithm, pvs (principal variation search), move ordering, null-move, search extensions, and aspiration windows.  There is of course an intrinsic danger in omitting moves that seem unattractive (at small search depths), because some of them could lead to a decisive advantage as the game progresses (at greater search depths).  Alpha-beta, pvs and move ordering increase the search speed without affecting accuracy. Other techniques can severely deteriorate accuracy, if not implemented correctly, or when using too aggressive pruning parameters.

By far the best investment you can make to produce a strong program is to improve the evaluation function.  Speed is still important in the evaluation function.  However, if you can improve the evaluation function, at the cost of adding more code lines and hence making your program somewhat slower, go for it! Same is valid for the search algorithm, adding more code lines will make the code slower, but can make the search faster (by visiting less nodes).  

As a rule of thumb, the strongest chess programs have fast move generators, use data structures that allow them to implement fast makemove and unmakemove algorithms, they search a relatively small number of moves only (using aggressive forward pruning rules, allowing them to search deeper), and have extensive evaluation functions that capture a significant amount of chess knowledge.

03  Choices

Winglet is written on a platform running Windows 7 Home Premium, SP1 (64-bit), and coding is done with Microsoft Visual C++ 2010 Express,  version 4.

What if your system is different?

If your operating system or software development environment (SDE) is different, that does not automatically mean that you cannot follow this guide. It only means that some steps or implementations might be somewhat different, depending on how your particular system is set up.

I suppose you can also follow this guide in case you want to write a UCI engine under Linux (skipping the parts for Winboard and coding the UCI parts yourself). Some coding might be machine and/or OS dependent, I will gladly leave that as a complimentary challenge for you to figure out.  I choose to focus on the chess programming part.

04  Preparations

Setting up Microsoft Visual C++ 2010 Express

Download and install Microsoft Visual C++ 2010 Express (it is free, but you will need to register to use it).  It can be found here, or use a search engine to locate it.  There might be additional Service Packs available for installation, or Windows updates related to Visual Studio.  Some are required for Microsoft Visual C++ 2010 Express to function properly.  

After installation of VC++, check your Windows Updater – it will tell you which other updates and/or service packs you might need.

Setting up Winboard

Note that you do not need Winboard right away, winglet will initially be developed as a console program, with user input from the keyboard.   Winboard support and details on setting up Winboard is discussed in section 21.

You can download and install the latest Winboard version, from here (version 4.5.2) or use a search engine to locate it. 

05  First steps with Visual Studio C++

Start Visual studio C++, select New Project..., select Win32, select Win32 Console Application…,
enter wingletx as the project name, choose a suitable location, and click OK:

Now, navigate through the Win32 Application Wizard, select Win32 console application, make sure to uncheck precompiled header.   
You will end up with an empty template for a C++ program.

Note that, in Visual studio C++, you have complete control over the layout of the working space and position of windows.  You might want to spend some time to get familiar with the interface, my working space usually looks like this:

Check if you can copy this into your code:

step 1: your new friend

---

int _tmain(int argc, _TCHAR* argv[])

 {

    printf("hello, I am your new friend!\n");

    return 0;

 }

---

Build the executabe (hit F7).  
Run the executable (hit Ctrl-F5).  
This should open a console window and display the message:

You are ready to go if you've gotten this far.  I am not going to explain a lot more than this on working with Visual C++.  That is not the intention of this guide; Again, I choose to focus on the chess programming part.

My C++ header philosophy

C++ programs are usually split up into multiple smaller source code files (suffix .cpp).  Splitting up chunks of code into separate files allows programmers to separate certain elements of a program's source code into manageable and reusable files.  C++ header files (suffix .h) normally contain declarations of structures, functions, variables, and other identifiers.  Identifiers that are declared in a header file can be included in other source files. 

In my programs, the order of header file inclusion is important (which is considered bad coding practice). 
Some structure definitions, or global variables, might be using non-standard types that were defined in defines.h
So “defines.h” needs to be included first, before any structure definition headers. I find this approach quite practical for limited sized programs that are not intended to be sharing any code with other programs.

The winglet C++ header files are set up to contain the following definitions (and you always should #include them in this particular order to prevent compilation problems):
1) defines.h:  contains compiler directives (#define), type definitions (typedef), and any machine dependent definitions.  This header can be included by any source file that needs it.
2) protos.h:  contains the prototypes of all functions of the winglet program,  sorted alphabetically.  This header can be included by any source file that needs it.
3) globals.h:  contains all global variable declarations.  This header is included ONLY in wingletx.cpp (the file that contains main())
4) extglobals.h:  the same list of global variables as in globals.h, and in the same order, but now declared as external variables.   This header can be included by any source file that needs it, EXCEPT in wingletx.cpp.

Then there are a number of dedicated header files that are used by one, or a limited number, of source files.  Usually, the prefix of the header file name will indicate its intention and to which source file that header belongs.  Examples are structure definitions. 

Targeting for 64-Bit Platforms

Visual Studio C++ Express does not come with 64-bit compilers.  If you want to build your executable for a 64-bit platform, then I suggest searching the internet for "how to configure Visual C++ Projects to Target 64-Bit Platforms". This will lead you to Microsoft's site with more information. 

You will have to download and install Microsoft Windows SDK and .NET Framework 4 (which is also free software), define your 64-bit platform in Visual C++, and select Windows7.1SDK as Platform Toolset.

In case Microsoft Windows SDK cannot install the X64 or IA64 compilers, then you might have to uninstall Visual Studio 2010 Service Pack 1, and reinstall (not repair) Microsoft Windows SDK. See this link for more info on this known bug.

If you're not sure how many CPU's your system has, then you can use following program to find out (this will work in Windows-based systems only):

#include <Windows.h>

#include <iostream>

 

int main(int argc, char *argv[])

{

       SYSTEM_INFO sysinfo;

       GetSystemInfo(&sysinfo);

       std::cout << "Number of processors: " << sysinfo.dwNumberOfProcessors << std::endl;

       if (sysinfo.wProcessorArchitecture == PROCESSOR_ARCHITECTURE_INTEL)

              std::cout << "Architecture: INTEL - x86" << std::endl;

       else if (sysinfo.wProcessorArchitecture == PROCESSOR_ARCHITECTURE_IA64)

              std::cout << "Architecture: IA64 - Intel Itanium-based" << std::endl;

       else if (sysinfo.wProcessorArchitecture == PROCESSOR_ARCHITECTURE_AMD64)

              std::cout << "Architecture: AMD64 - x64 (AMD or Intel)" << std::endl;

       else std::cout << "Architecture: Unknown architecture." << std::endl;

       return 0;

}

This will probably get you the right number of processors, but I noticed that my machine thinks it's an Architecture: INTEL - x86 if I compile it for 32-bit, and it thinks it's an Architecture: AMD64 - x64 (AMD or Intel) if I compile it for 64-bit (!)... inscrutable Microsoft logic.

last update: Friday 09 September 2011