Bitboards Magic Number Research

I’ve quite happy with the global list of possible move.  Now I need to turn my attention to move generation.  For the pieces which don’t slide (i.e. pawns, knight and kings) this is trivial.  For sliding pieces I’m going to use the “new kid on the algorithmic block” – Magic Bitboards.  I’m in the process of going over Pradu Kannan’s 2007 paper.  I need to think about how I will generate my magic multipliers.  At this stage I’m not sure if I’ll do it in Delphi or C.  I also think a fixed shift seem to be sensible (from simplicity).

Are There 65,884 Legal Chess Moves?

I’ve finished creating the global move list.  This list contains all legal chess moves (e.g. one move might be white bishop on g2 captures black queen on d5).  It would seem there are 65,884 possible legal moves!  Does anyone know if this is indeed correct?

EDIT: It looks like my first attempt was off.  After more debugging I have 43,764 possible moves!

Refining the Piece Index Values

I’ve been thinking about the piece index values.  The original set had all of the pieces in a random list.  I think there is an advantage in having the following piece index values:

#define WHITE 0
#define BLACK 1

#define KNIGHT 1
#define BISHOP 2
#define ROOK 3
#define QUEEN 4
#define PAWN 5
#define KING 6

#define BLANK 0
#define WHITEKNIGHT 1
#define WHITEBISHOP 2
#define WHITEROOK 3
#define WHITEQUEEN 4
#define WHITEPAWN 5
#define WHITEKING 6

#define BLACKKNIGHT 8
#define BLACKBISHOP 9
#define BLACKROOK 10
#define BLACKQUEEN 11
#define BLACKPAWN 12
#define BLACKKING 13

With these values note the following:

You can detect the color easily with a simple (piece >>> 3).  This isn’t a big deal.

Since the king has the highest index of all piece, I can find any move in the global move table using the following code:

move = global_move_list[from][to][piece] + captured_piece

or for promoting a pawn:

move = global_move_list[from][to][piece] + captured_piece + (4 * promote_to)

That’s neat!

One of the weakness of bitboards is it is sometimes difficult to see which piece is occupying a particular square.  In a pure bitboard only structure you’d need to loop through all the piece bitboards until you find the relevant one.  This sounds cumbersome.  So I think I’ll also need to add a square[64] array to the board structure. This will simply hold the index of the piece occupying the square.

I think Maverick is going to fly!

Global Move List

In the first version of Monarch I used an Exhaustive Global List of Chess Moves.  This is a list of about (from memory), 47k moves which collectively describe all possible moves on the chess board.  So an example of one move might be white Bishop on b2 takes black Rook on e5.  This will be one of the moves in the table.  I think this approach may well work well with Magic Bitboards – so I intend to implement it in Maverick.  The main advantage is you can store move specific information in the move’s record (e.g. the changes in hash value).  Also generating moves is just a matter of storing a pointer to the move in question.  Obviously the downside is the memory used to store the table and the negative impact on the cache.

This structure was first popularized by Gnu Chess 3.  Subsequent engines which have used a similar approach are Ferret by Bruce Moreland and Diep by Vincent Diepeveen.

So my first task is to classify every possible move into “move types”.  This will be used in switch statements to make and unmake moves quickly.  Here’s my first pass:

//===========================================================//
// Types of Moves
//===========================================================//
#define MOVE_CASTLE 0
#define MOVE_PAWN_PUSH1 1
#define MOVE_PAWN_PUSH2 2
#define MOVE_PxPAWN 3
#define MOVE_PxPIECE 4
#define MOVE_PxP_EP 5
#define MOVE_PROMOTION 6
#define MOVE_CAPTUREPROMOTION 7
#define MOVE_PIECE_MOVE 8
#define MOVE_PIECExPIECE 9
#define MOVE_PIECExPAWN 10
#define MOVE_KING_MOVE 11
#define MOVE_KINGxPIECE 12
#define MOVE_KINGxPAWN 13

 Now I need to think about generating the Global Move List!

When Will Maverick be “Launched”?

I see over on CCC Pawel Koziol has launched Rodent 1.0. Big Congrats! I was intrigued by Pawel’s “launch criteria” (i.e. 1.0 status).  He says he would only go to “1.0” status when Rodent beat Fruit 2.1 in a 100 game match.  This is an interesting criteria for launching a chess engine!

It got me thinking!

So here’s what I’m going to do for Maverick.  The first version, Maverick 0.1 will be launched only when it beats Monarch 1.7 over a 100 game match.  Version 0.2 will be launched when Maverick reaches 2100 ELO, version 0.3 at 2200 ELO, version 0.4 at 2300 ELO, version 0.5 at 2400 ELO and finally 1.0 at 2500 ELO (i.e. Grandmaster level!).

Chess Board Representation

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

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

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!