Making a Move

Now we have our board representation we need a way to make and unmake moves. As before, this is going to be a very naive implementation that is more about readability than efficiency.

We’ll start with the interface. We need two functions. One for making a move and one for undoing the last move.

So, what do we store in the move structure?

Not a lot! We just need to keep track for the cell a piece is moving from and where it is going to along with the piece a pawn that reaches the end should be promoted to. One important thing to note here is that the move/unmove code assumes that all moves are valid; it performs no validity checking whatsoever.

So let’s start to implement the move function. The most obvious thing we have to do is to move the piece. Recall from the last post that we created a global variable holding the board state – the move function will directly update this state.

If only it was that simple! We have a number of other things to consider when moving pieces:

  • Capturing en-passant
  • Castling
  • Promotion

Let’s deal with these in order.

En-Passant

The move function needs to perform three functions related to en-passant:

  1. For any other move the current en-passant cell needs to be cleared.
  2. If a pawn is advanced two places then the board structure needs to be updated to keep track of the en-passant cell
  3. If a pawn moves to the current en-passant cell then the enemy pawn needs to be removed from it’s cell

Here are 1 and 2.

And 3.

Castling

Castling is another special case with two functions.

  1. If the board indicates castling is available and the king is moved to a castling destination then the rook needs to also be moved
  2. Moving the king or either rook removes castling ability

This gets a bit messy (and could easily be improved – remember this is not the final code…)

Yuck! Magic numbers. I’ll fix them later. This is a lot of code but it’s fairly straightforward. If the king is being moved from it’s home position to a castling location then move the rook as well. We don’t need to check for castling availability because we assume that the move being passed to us is valid.

Removing castling availability is straightforward.

More magic numbers… We don’t need to check whether the piece we are moving is the king or a rook as if it is not then the castling availability will have already been removed so we will not be changing any state.

Pawn Promotion

Finally we have pawn promotion. This one is easy.

That completes the move function. So how do we undo a move? In the interests of keeping this simple we are going to add a new field to the CHESS_MOVE structure.

We’ve added the ‘board’ member. Before we make a move we will copy the entire board state into this member then we can just copy it back when we undo the move. So, at the start of the move function we add this:

This leaves us with the simple task of implementing the unmove function:

Well, that’s it for this instalment. Next we’ll start taking a look at the code required to generate all the legal moves from a starting position.

0x88 Board

In this post we’ll start looking at my reference chess board implementation. Remember, I want to keep this simple and maybe not spend too much time thinking about optimisation or even optimisable code. This is just a learning experience that will ease the future development of a much more efficient version.

The simplest implementation would seem to be just to define a structure that describes the contents of a square (I call them ‘cells’ in my code) and then define an array of 8×8 of these or simply:

These could be arrange any way you please but it makes sense that cells[0] is A1, cells [1] is A2, cells[8] is B1, etc.

However, a slightly larger, more complicated board array actually makes a lot of the chess rules engine code much easier. Therefore for this implementation I’m going to be using the common 0x88 board format. Much has been written about this format so I’m not going to duplicate it in my words here but basically the board is laid out as in the diagram below:

88board

What you’ll notices is that the indices for the cells follow a simple pattern; all indices for a particular file share the same low nibble and all indices for a particular rank share the same high nibble. Further, the top bit of each nibble is clear for all valid cells so we can easily check whether an index is valid using the following C code:

So now we can declare some structures that represent the data in a cell and create the board array.

 

Now we have our board structure we can start writing some functions.

Starting with a simple one just to clear all pieces from the board:

And here’s a useful function for debugging that prints an ASCII representation of the board:

Notice that the function above uses a macro ‘CELL_INDEX’ to convert from file and rank to an index. I’ve generated a number of useful macros like this:

And finally for now, a very scrappy, partial implementation of a FEN string parser just so I’m able to populate the board.

Putting all this together with a simple main() function containing the following code results in an 0x88 board that can be printed to the screen.

board_output

The Plan

I think we’re ready to start putting some chess into the Ircos project :) .  I have a plan…

I’m going to try to make this chess engine project an exercise of optimisation. I’m going to try not to rush into getting a fully working chess engine as soon as possible and instead I’m going to concentrate on each stage trying to make it as fast as possible. With that said, I’m going to start with the rules of chess and the chess board implementation.

As I’ve never written a chess engine before, I can assume that I’m going to make design mistakes :) . Therefore I’m going to write a reference chess board implementation first of all which will serve a few purposes:

  1. I can make all the mistakes in this implementation and learn how and how not to write a board implementation
  2. I can throw-away the code at the end and use my newly acquired knowledge to write a better, more efficient version
  3. I can use the reference implementation to verify the validity of any subsequent (likely more complicated) board implementation
  4. The reference implementation can be used as a benchmark to show how well the optimisation is progressing

So, for the reference implementation I want to keep it as simple as possible so it can be developed quickly and will minimise the chance of bugs creeping in.

In the next instalment we will take a look at this reference implementation.

Building Ircos

It’s time to build the Ircos. I know it doesn’t do anything at the moment but we’ve got to start somewhere :)

One think I like about CMake is that you can easily target multiple build platforms. I’m currently using both Linux and Windows and will detail the build process for both.

Windows

In order to build for Windows you need to install the following tools:

  • Visual Studio (I am using Visual Studio Ultimate 2013 but I think the Express edition should work fine)
  • CMake
  • If you want to support unit testing then you will need CxxTest. I downloaded version 3.10.1. It’s really old but seems to be compatible with CMake.
  • CxxTest requires Python  so you need to install that too

Building is very simple and requires following a few steps:

  1. Unzip the project files (see previous post) into an empty directory
  2. Open a command prompt and change directory to the root of where you unzipped the source
  3. Make a new directory for the build (I use the very original name of “build”)
  4. Extract the CxxTest source somewhere
  5. Change to your newly created build directory
  6. Run the following cmake command:

  1. The CMake command should have generated a Visual Studio solution in the build directory. Open this in Visual Studio
  2. Build!

You only need to do the above process once and thereafter use the Visual Studio solution. If you make any changes to CMakeLists.txt this will automatically be picked up on the next build of the Visual Studio solution.

Linux

I base this on Debian based Linux  systems as I’m using Linux Mint.

  1. Install some pre-requisites

  1.  Unzip the source into a new empty directory
  2. Open a terminal and change to the root of the source directory
  3. Create a new directory to contain the build files
  4. Change to the build directory
  5. Run the following CMake command:

  1.  Run “make” to build the project

Let’s get started

I’m going to be writing my engine in my favourite language, C. This seems to be a natural choice for a chess engine as it lends itself to performance analysis and optimisation and can easily live alongside assembly language for those performance critical routines.

For a build system I’m going to be using CMake. This will provide cross-platform build capability as well as providing support for a number of toolchains and IDEs including Visual Studio and Eclipse.

So let’s start with some placeholder C files, starting with main.c the entry point for Ircos.

As you can see this file currently just calls “reset_board” which will ultimately set the initial configuration of the chess board.

Let’s follow that up with the header and implementation files for our chess board.

 

As you can see, these are just empty but compilable files at present so we can get the build environment working.

For CMake we need to provide a CMakeLists.txt that configures the build.

This maybe needs a short explanation.

Line #9 – defines the include directories for the project. The CMakeLists.txt lives in the root folder and the .c and .h files live in a subdirectory named “src”.

Line #15 – we build the engine source files into a static library. This allows us two link it into two modules; the main Ircos engine executable and a unit test executable (more on this later).

Line #20 – the main.c module is compiled and linked with the static library to generate the engine executable.

You’ll also notice that I’m looking for a package named “CxxTest”. This is a unit test framework that I’ll be using to test various parts of the engine. In order to achieve this we need to add a few more lines to CMakeLists.txt.

I’ve made the unit testing optional based on whether the CxxTest framework was found or not. This allows the engine to still be built on platforms that do not support CxxTest.

Line #4 – The CxxTest framework is found so we enable testing.

Line #7 – We will add a single test module at present. The tests are defined in “test_board.h”. CxxTest will auto-generate a source file from this named “test_board.cpp” (we do not need to provide this file) and the test module will be added to the target “test_ircos”

Line #9 – We can see now why I built the engine source into a static library. It can be added as a dependency of the unit test application “test_ircos” rather than having to rebuild the source files all over again.

Line #20 – Finally, we make the unit tests run as part of the build process after the build is complete.

The final piece of the puzzle is the unit test module, “test_board.h”. Again I provide a placeholder to be filled-in later.

In here we provide a single example test on line #12 that calls the (empty) reset_board() function before asserting ‘true’ (which will obviously never fail).

All that is left to do now is to build the engine and see if works! I’ll do this in the next post.

Ircos – What’s in a name

I thought long and hard about what to call my chess engine. “Chess Engine” just didn’t seem right :)

I’m writing this engine just for the fun of it. You could say I’m writing just “because” I want to. My youngest daughter is 3 and instead of saying “because”, she says “er-cos” so I thought this would be a fitting name after jiggling the spelling a bit.

Well, there you have it. From now on and forever more my little engine will be known as ‘Ircos’!

Introduction

I suppose I’d better introduce myself. My name is Roy Hopkins and that’s me in the photo along with my three little ones.

2014-12-22 15.18.47

I live in Worthing in the South of England.

I’m a Software Engineer with 21 years of experience. I currently work for Intel Security (McAfee) working on encryption products. I work on all aspects of product development but am most at home working on low-level software such as device drivers, OS preboot, reverse engineering and that sort of stuff.

I’m the drummer in Random Man – a rock band formed with a few mates just for fun. We haven’t been playing that long and only had one real gig but we’re getting there.

Hello!

Hello and welcome to my chess programming blog where I plan to document the development of my very own chess engine.

So, why do I want to write a chess engine? It all began when my son started learning chess. At first, when he was just playing in his school club I could use my rudimentary chess skills to provide a reasonable opponent. But over the next couple of years he started competing in Sussex Junior Chess events and got stronger and stronger. Now he is 9 and has just been selected for the Sussex team. This all means that when I play him I quite often “let him win” – in other words I lose.

I started trying to improve my game and have had some success by reading, playing online and solving chess puzzles but progress is slow. Being a software engineer I wondered if knowing and understanding how a computer plays chess would help me in my game.

This project documents my progress in researching computer chess and implementing my very own chess engine. I’m not sure now far I’m going to go with this engine but I plan to at least make it be able to beat me – not a hard challenge!