Generating Magic Multipliers

I finally cracked the process needed to generate magic multipliers.  I didn’t find it trivial.  Here are necessary steps:

1. Create Combination Table:

When generating magic moves the first step is to logically AND the board with the relevant square’s mask.  Let’s use the rook on e5 in the diagram below as an example:

Board with pieces

The mask used is as follows (we’ll call this the AND_MASK):

RookMask

Note the edge squares are not part of the mask. The reason is simple.  For example, if the rook can move to e2 it can always attack, protect or move  to e1.  This trick also reduced the bits in the mask; an important point as we’ll see in a moment.

So the bitboard after the AND operation only has one bit set, corresponding to the black pawn on f5.  We’ll call this the AND_RESULT.  In this case it look like this:

F5

After the magic operation this will provide a look-up to the possible attacking moves of the rook.  We’ll call this the ROOK_ATTACKS.  In this case it is the following bitboard:

RookMoves

There are a couple of things to note:

  • If g5 was set in the AND_RESULT we’d still have the same ROOK_ATTACKS
  • There are (2 to the power BitCount) possible AND_RESULTs, where BitCount is the number of bits set in the AND_MASK.

So now we need to create a list of all the possible AND_RESULTs as well the corresponding ROOK_ATTACKS.  Once again this isn’t trivial.  How do you create all of the possible permutation of the AND_RESULT?  The key is a little function which take as inputs the AND_MASK and the index you’d like to create (the index being between zero and 2 ^ BitCount).  Here’s the Delphi code I used:

function TMagicGenerator.IndexTo64(AndMask: TBitboard; Index: integer): TBitboard;
var
i, n, b: integer;
a: TBitboard;
begin
result := 0;
a := AndMask;
n := PopCount(a);
for i := 0 to n − 1 do
begin
b := BSF_Reset(a);
if IsBitSet(i, index) then
SetBit(b, result);
end;
end;

This loops through all of the bits set in AndMask.  Each bit has an index (in this case “i” which runs form 0 to n-1) and a position (in this case “b” which is between 0 and 63).  If index also has the “i” bit set then the “b” bit is also set in the result.  It’s worth spending a couple of minutes getting your head around this.  As I said it’s not trivial but nevertheless core to the whole approach. 

The function BSF_Reset(a) returns the position of the first set bit and resets that bit.  The other functions are self explanatory.

Once we have this function we can create a list of all the possible AND_RESULTS and their corresponding ROOK_ATTACKS.

 procedure TMagicGenerator.CreateAllRookMasks(b: Tbitboard; square: integer);
var
n: integer;
i: integer;
AndMask, AttackMask: TBitboard;
begin
n := PopCount(b);
Setlength(AndAttackMask, Round(Power(2, n)));
for i := 0 to High(AndAttackMask) do
begin
AndAttackMask[i].AndMask := IndexTo64(b, i);
AndAttackMask[i].AttackMask := CreateRookAttacks(square, AndAttackMask[i].AndMask);
end;
end;

2. Test Candidate Magic Multipliers:

For a magic to be valid one of two condition must be met:

  • The magic must map each AND_RESULT to a unique position in a look-up table

or

  • The magic must map the AND_RESULTS to a position with the same ROOK_ATTACKS

This can be accomplished by:

  1. Creating the look-up table
  2. Setting all values to zero
  3. Looping through all AND_RESULT transforming them into a look-up table index
  4. Check to see if the look-up table already contains a ROOK_ATTACK
  5. If it does have a ROOK_ATTACK already stored then it must be the same as the one corresponding to the AND_RESULT – if it isn’t the magic is not valid
  6. The magic is valid if this sequence can be completed for all possible AND_RESULTs

The code I used for this is here:
function TMagicGenerator.MagicWorks(xMagic: uint64): boolean;
var
i: integer;
b: uint64;
begin
// Zero Test table
for i := 0 to High(MagicTable) do
MagicTable[i] := 0;
// Test each possible mask
result := true;
i := High(AndAttackMask);
repeat
b := (AndAttackMask[i].AndMask * xMagic) shr (64 - RookBitCount);
if MagicTable[b] = 0 then
MagicTable[b] := AndAttackMask[i].AttackMask
else if MagicTable[b] <> AndAttackMask[i].AttackMask then
result := false;
dec(i);
until (result = false) or (i < 0); end; procedure TMagicGenerator.FindRookMagics(Trials: integer); var i, n: Integer; Square: integer; xMagic: uint64; RookMask: TBitboard; begin SetLength(MagicTable, Round(Power(2, RookBitCount))); // Initialize for Square := 0 to 63 do begin if assigned(fOnNewSquare) then fOnNewSquare(self, square); RookMask := CreateRookMask(Square); CreateAllRookMasks(RookMask, Square); for i := 0 to Trials do begin if (i and 1023) = 0 then Application.ProcessMessages; // Find a candidate magic repeat xMagic := SparseRandom64;
until BitCount(xMagic) > 6;
// Does Candidate work
if MagicWorks(xMagic) then
begin
if assigned(fOnFoundMagic) then
fOnFoundMagic(self, Square, xMagic);
Break;
end;
end;
if i > Trials then
if assigned(fOnSquareFail) then
fOnSquareFail(self, Square);
end;
end;

Note the random magic number seems to work best with a sparse 64 bit integer.

What I’ve outlined is the simplest form of magic bitboard with a fixed shift.  One nice aspect of magic move generation is it’s a stand-alone part of the chess engine.  So any improvements to the approach (e.g. more compact look-up tables) can be added later.

A couple of resource I found helpful were Looking for Magic and Rival Chess’ Page

Automatic Tuning of a Chess Evaluation Function

I’ve taken a little detour over the past week to look at Population Based Incremental Tuning.  This was something which Thomas Petzke brought to my attention.  You can read his take here:

http://macechess.blogspot.com/2013/03/population-based-incremental-learning.html

It’s an interesting approach.  After some investigation I’ve decide to add some form of automated tuning to Maverick’s chess position evaluation function.  I think PBIL seems to hold some promise.

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!