Maverick 1.0 To Do List…

It’s been two months since I did any significant chess coding – life got in the way! I did tinker here and there but nothing special.  However, Christmas is around the corner. I’m hoping to have some time to relax with a IPA beer and do some coding.

I thought it would be worthwhile spending some time to think about what I need to do to create version 1.0 of Maverick. I’ve said from the start, version 1.0 will have a playing strength of 2500 ELO (i.e. Grandmaster level) on the CCRL scale. So I’ll release Maverick 1.0 when I can beat all of the following opponents in a 100 game match at 5 mins per move:

  • Tao 5.6 – I’ve admired Bas Hamstra’s engine for a long time – I hope one day he continues the development
  • YACE  – another classic
  • Anmon 5.6
  • Hermann 2.8 64 bit 

I tested Maverick 0.51 at fast time controls. One minute per game was the slowest time control I used. In my test this gave Maverick a rating of about 2370 ELO. However, in the CCRL Division 6 tournament Maverick struggled. I thought it would be in the top half of the table. But it finished one off the bottom! I suspect this is due to the time controls. Maverick is quite a fast searcher but I intentionally haven’t put any real selectivity into the search apart from null move. This probably results in a higher branching factor than other engines with Late-Move-Reduction. At super fast time control Maverick may do well due to its raw speed, but its higher branching factor holds it back at the slower time control. When version 0.51 is tested by CCRL I suspect it will be 100 ELO lower than my tests i.e. about 2270 ELO. This mean I have a long way to go to reach 2500 ELO.

Before I set out my to-do list for version 1.0 it might be helpful to go over what Maverick already contains i.e. the current state-of-the-engine. Here’s a reasonably comprehensive list:

  • Magic bitboard engine
  • Move dictionary architecture
  • Hash tables (4 slots structure)
  • Killer Moves
  • Evaluation function with the following terms:
    • Middle-game to Endgame interpolation
    • Piece square tables
    • All basic endgames (e.g. B + N +K vs. K)
    • Mobility
    • Passed pawns (a major impact on strength)
    • Basic pawn weaknesses (extremely rudimentary)
  • Null Move (R = 3)
  • Static-Exchange-Evaluation for move ordering and quiescent move pruning
  • Checks in the first ply of of the quiescent search
  • Extend on one-reply-to-check on the first ply of quiescent search
  • Internal Iterative Deepening
  • Enhanced Transposition cutoffs
  • Opening book
  • Pondering (really easy using the UCI protocol)

So I’d say Maverick isn’t too complex and doesn’t contain anything different.

Here’s the list of to-do’s for version 1.0:

  • CLOP tuning
  • Revisit some parameters for tuning:
    • Piece-Square-Tables
    • Mobility
    • Passed pawns
  • Add king safety
  • Add potential passed pawn terms to the evaluation
  • Add pawn storm code when castling on opposite sides
  • Add bad exchange terms to the evaluation (and tune)
  • Change the maximum depth measure to exclude the quiescent search (I think?)
  • Use magic multipliers to calculate mobility and center control
  • Improve knight placement and isolation code
  • Add pawn and king endgame code (this could be a big strength gain)
  • Add special endgame code for K + R vs. K + N (inspired by Thomas Pestzke)
  • Tweak move ordering:
    • Evade check move history
    • Null Move capture-evade
  • Multiple PV
  • Support for Chess960
  • Possibly MAC and Linux support (need to get a development environment up and running for both)

I’m hoping this list will be enough to push 2500 ELO – let’s see!

Have I missed anything?

More Work on Magic Move Data Structures

I spent a couple of hours translating some of my Delphi code into “C”.  Everything seems to be working well.  Hopefully I should be able to start generating moves soon.  Based on my past experience, once you get to the stage where you can make and unmake moves the pace of development picks up; it starts to get interesting and the addictive nature of computer chess programming sucks you in.

I’m certainly enjoying the Microsoft Visual C++ Express IDE.  It’s a well put together system – and it seems super stable.

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

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).