Chess Board Representation

/0 Comments/in /by

When anyone writes a chess program, one of the first things to decide is how you’re going to represent the layout of the chess board.  Chess Programming Wiki has a good section on the various approaches to Board Representation.  When considering the different structures you need to consider the ease and speed of several factors:

  • Generating Moves
  • Making Moves
  • Undoing Moves
  • Evaluating the Position

I find rookies chess programmers tend to focus too much on Move Generation but in reality all four factors are important.

As I outlined in the Design Philosophy section, I am keen to create a Magic Bitboard engine.  Bitboards are not new.  They use a 64 bit number to represent the locations of each type of chess piece.  In the binary format an occupied square is “1” and an unoccupied square in a “0”.  Generating king, knight and pawn moves is trivial.  The “magic” comes in when generating moves for sliding pieces (which was always the awkward part of bitboard programming).  Sliding piece move generation is now a “multiplication, a shift and a table look-up”.  The result is extremely efficient manipulation of chess boards.  Not only is the good for move generation, it comes in handy when evaluating a chess position, where attack tables can be quickly generated on the fly.

So let’s create a bitboard board structure:

//===========================================================//
// Chess Board Structure
//===========================================================//
typedef struct t_board
{
t_bitboard piece[2][6];
t_chess_color to_move;
t_hash hash;
t_hash pawn_hash;
uchar castling;
uchar ep_square;
uchar king_square[2];
uchar ply;
uchar in_check;
t_chess_square check_attacker;
uchar fifty_move_count;
int static_value;
};

The  “piece” variable has two dimensions, one for the color (i.e. black or white) and the other for the 6 types of chess pieces.  The structure also contains all of the board “state”  information (e.g. castling rights etc.).  I may add to the structure with variable such as the kings’ location.  This may be helpful when detecting check.  But at this stage I’d like to keep the structure as small as possible and only add more terms when absolutely necessary.

I can then declare the board as:

// ----------------------------------------------------------//
// Chess Board
// ----------------------------------------------------------//
struct t_board position[1];

I’m planning to pass this “position” variable to most of the board manipulation routines.  This will make it easier to implement a multi-core engine at a later stage.

UCI Protocol – Capturing User Input

/3 Comments/in , /by

I found the Monarch’s source code in a corner of my hard disk.  One of the strong points of Monarch was its stability.  Users reported running thousands and thousand of games without it crashing.  I put this down to defensive programming (hat tip Fabian!) and a solid implementation of the UCI protocol. So since Monarch was so stable I’ll reuse as much of the UCI code as possible.  This is not intended as a lesson on the UCI protocol, so if you want ot find out more I suggest you read Shredder’s Page or UCI Chess Engine:

Listening for the Input:

There are basically two ways to listen for input in console mode.  One way is to check for the data in the standard pipes (Fruit uses this approach).  The other is to use a separate Thread for the engine and use the main thread to get the user input.  Monarch used the second approach.  It seemed to work well.

So here’s the main loop.  This sets the buffer to zero (highly recommended to avoid any timing delays) and initializes the engine:

int main(int argc, char *argv[])
{
setbuf(stdout, NULL);
setbuf(stdin, NULL);
setvbuf(stdout, NULL, _IONBF, 0);
setvbuf(stdin, NULL, _IONBF, 0);

//uci.engine_initialized = FALSE;
//uci.mode = UCI_STARTING;

create_uci_engine_thread();

uci_set_author();
listen_for_uci_input();
//destroy_hash();

return TRUE;
}

Creating the engine thread is relatively straightforward:

void create_uci_engine_thread()
{
thread_handle = (HANDLE)_beginthreadex( NULL, 0, &engine_loop, NULL, 0, &threadID );
SetThreadPriority(thread_handle, THREAD_PRIORITY_NORMAL); // needed for Fritz GUI! :-))
}

Now the engine just needs to respond to changes in the UCI mode.

unsigned __stdcall engine_loop(void* pArguments)
{
uci.mode = UCI_WAITING;
while(TRUE){
if (uci.mode == UCI_START_THINKING){
//root_search(position);
if (uci.mode != UCI_QUIT)
uci.mode = UCI_WAITING;
}
if (uci.mode == UCI_QUIT){
_endthreadex(0);
return 0;
}
else{
Sleep(1);
}
}
}

Now I have a working console application I can start to write the basic building blocks of the engine and test them with the “test” command.

Tomorrow, I’ll work on the chess board data structure.

New Computer Chess Programming Blog

/3 Comments/in , /by

It’s been six years since I’ve done any serious chess development. During that time family life has been full-on, with two high energy daughters and one demanding wife. The pace of work has also picked up the pace. While I haven’t had time for chess computer coding I certainly haven’t been far from the computer chess scene (it’s so addictive!). There have been few days when I haven’t checked CCC.

During those seven years I’ve also observed many changes in the world of computer chess, some of which have piqued my desire to code another engine. From my perspective here are the notable developments:

  • Magic Bitboards: These provide the ability to quickly generate attack tables for sliding pieces. The tables can be used for move generation or to create sophisticated evaluation functions. Back in 2006 the jury was still as to whether or not bitboards are any better than other board structures; Magic Bitboards seem to tip scales heavily in favor of a bitboard architecture. I’d really like to develop a magic bitboard engine.
  • Ubiquitous 64 Operating Systems: 64 bit is now the norm. This wasn’t the case back in 2006. This makes bitboard engines even more attractive.
  • Late Move Reduction: This seems to be one of the main developments in computer chess over the last few years. It was starting to be discussed back in 2006 but now it seems to be the norm. I think there are many possibilities for enhancing the basic LMR techniques and making a highly selective engine.
  • New Testing Tools & Methods: Fabian Letouzey managed to improve Fruit at an amazing pace. One of his secrets was his obsession with testing. It would seem that playing thousand of super fast games (e.g. 1 second per game) is the best way to prove, or disprove, potential improvements. I find this interesting. One of my other passions is marketing. I suspect computer chess testing methods may provide a philosophical framework for improving businesses in general. Anyway I’d like to set up such a rapid-fire testing environment.

As a result of all of this I’ve downloaded Visual Studio Express, set up this website and rummaged around to find my old Monarch code. I thought about carrying on with Monarch chess but it doesn’t seem quite right. The new project will be a new code base (apart from basic i/o code), so I think it’s right I start a new engine. This new engine will be called “Maverick“, which conveys, in one word, my overall design philosophy and aims.

If you want to follow along you can access my live code base here. I’ve also set out what I’m striving to achieve on the development philosophy page.

I’d be interested to hear your comments and suggestions!