Creating an Opening Book for Maverick

Maverick is the first chess engine I’ve written which can use its own opening book.  I decided at an early stage Maverick would read Polyglot opening books.  It makes so much sense.  Polyglot seems to be a great tool create opening books and its format seems to be emerging as the de-facto opening book standard.

So now I need to actually create an opening book.  I did some research on the internet and it really is quite straightforward. Here are the steps I took:

  1. There are some really good free tools which you’ll need to download:
  2. You will also need a database of high quality game.  I used Ed Schroeder’s Million Base. Make sure your database is in PGN format.
  3. Open the MillionBase using SCID.
  4. We’ll be filtering the games using SCID’s excellent filtering system – select “Search / Header…” (Ctrl-Shift-H)
  5. I created a database consisting of only White wins by players over 2400 ELO with opponents over 2200 ELO (see diagram)Filter Options
  6. I then saved the white win database as “white2400.pgn” using SCID’s “Tools / Export All Filter Games” command
  7. Repeat for Black
  8. Now put both PGN files in the same folder as Polyglot.exe, PGN-Extract.exe, the batch file.
  9. The batch file contains the commands to create the  opening book

  1. The first line runs PGN-Extract and simply cleans the database, removing and games which don’t start from the normal starting position.
  2. The second line creates a opening book of white moves, where the positions have occurred at least 50 times.
  3. The third line creates a broader book which give more responses to a variety of openings.
  4. This is repeated for Black
  5. Finally all of the books are merged

The final opening book is a little over 1 Mb (it’s available on the download page)- quite small by most standards.  I’ll need to run some test to see how good it is compared to other Polyglot books.

If there are any opening book specialists out there I’d appreciate any feedback. Can the process of creating the book be improved?

Bugs Bugs Bugs!

The chess engine Fruit has many strengths; one of the main ones I believe is simply the lack of bugs. Fruit’s author Fabian Letouzey has a defensive coding style.  He litters his code with “assert” statements.  When he was actively developing Fruit he set out a challenge – he said if you find a bug in Fruit he’ll fix a bug in your code (can’t find link).  I think this highlights his emphasis on finding and fixing bugs.  This philosophy has certainly influenced my coding style.

So now Maverick 0.2 is out I’ve spent most of my chess development time finding and fixing bugs.  There is a great temptation to add knowledge, feature and improve the search. But a couple of times I’ve sat down and just focused on finding bugs. On some occasions I have a specific bug or odd behavior I have identified and which I’d like to fix.  But often I’m just hunting for bugs.  I might set myself the goal of finding ten (small) bugs in two hours.  I then go through Maverick’s code with a fine toothpick, forcing myself to challenge the logic of every line and asking myself what I’m assuming at each stage.  It’s amazing what you discover.  If you have a chess engine give it a try.  Set aside some time to focus on simply finding bugs.

Let me know how you get on!

How strong is Maverick 0.2?

Maverick 0.2 has been out a couple of days now.  I’ve run some test games and I really quite surprised at how strong it seems to be.

Fruit 1.0:

The first test was against Fruit 1.0.  I played this match using Shredder’s GUI. As I expected Fruit won.  I really was dazzles by Fruit’s silky smooth search as it carved it ways through each ply (especially in the endgame).

  • CCRL Rating = ???? (between 2300 and 2400)
  • Time = 1 minute plus 1 second per move
  • Result for Maverick: Wins = 24, Loses = 63, Draws = 13
  • Percentage = 30.5%
  • ELO Difference = -146

I was pleased with this result.  However, it would seem Fruit’s strength is not well established.  As far as I can tell it us somewhere between 2300 and 2400 ELO on the CCRL scale.  This would put Maverick 0.2 between 2150 and 2250 ELO.

Phalanx XXIII:

The second opponent was Phalanx XXIII.  Another classic engine.  As I watched them play it is clear Phalanx has much more knowledge than Maverick.  Yet Maverick did well to win some game based on its speed.

  • CCRL Rating = 2387
  • Results for Maverick: Wins = 36, Loses = 49, Draws = 15,
  • Percentage = 43.5%
  • ELO Difference = -45

Once again I was pleased.  Based on this result Maverick is over 2300 ELO, which is probably too high but let’s see.

And remember, at this stage Maverick is lacking some standard features:

  • No mobility in the evaluation
  • No passed pawn code
  • No king safety
  • No pawn structure code
  • No late move reduction
  • No Internal Iterative Deepening
  • Lots of endgame evaluation missing

So I’m encouraged by Maverick’s strength.  If you run any sort of ratings test I’d be interested in the results.

I will not release another version until it has gained 100 ELO.  This may be some time.

New Mavericks version 0.2

It’s only been a few days since I launched Maverick 0.11.  However,  yesterday was unusual.  I spent most of the day at Sort Hills Mall in New Jersey (don’t ask!).  I set myself the task of finding 10 bugs.  In the end I found three.  As it turns out these three severely impacted Maverick’s playing ability.  So the latest version seems to play at around 2150 ELO on the CCRL scale i.e. about 100 ELO better than version 0.11).

The download links are here and the source code is here.

New Version of Maverick

It’s been just under two weeks since I released Maverick into the wild.   Over that period there have been over 200 downloads – quite amazing.

I’ve also been busy.  After setting up the testing framework I had some time to add some standard chess engine components:

  • Checks in the first ply of the quiescent search
  • Standard endgame knowledge (KQ vs. K, KR vs. K, KBB vs. K, KBN vs. K)
  • Null move heuristic
  • Hash tables
  • Bug fixes (including a nasty time management bug)

To my surprise the null move heuristic didn’t add much value until I added the hash tables.  Once the hash tables were added the increase in strength was noticeable.  By my test this version of Maverick is now better than Monarch 1.7 and approximately +200 ELO better than the previous version.  In a 300 game match it convincingly beat Monarch in a lighting chess match (60 moves in 20 secs) with 140 wins, 104 loses and 56 draws, which is 56%  – yippee!!  The win was replicated at slightly slower time controls of 60 moves in 5 mins when Maverick scored 38 wins, 30 loses and 32 draws (54%).  If these results scale to other opponents it would give Maverick 0.1 a rating of about 2050 ELO on the CCRL rating list.  You can download Maverick 0.11 here.

EDIT: Version 0.11 replaces Version 0.10 which had a time management bug

Adding Endgame Knowledge

If you test the first version of Maverick (v 0.05) you’ll soon find out it cannot mate at fast time controls with rook and king vs. a lone king. Quite shocking!  Despite gnawing its way through 9 million positions per second, the mate is too deep for an engine without hash tables.  So it just pushes its king and rook around the board aimlessly.  Obviously it needs help.  

I could add a few “if-then” statements to handle these cases.  This would work well if there are only a few standard endgame.  But I’d like to create a scalable solution where I can add all sorts of knowledge.  I posted a questions on the Computer Chess Club and Steven Edwards pointed me in the rights direction – material hash tables.  

Material hash work like this.  Each position has a material hash value which is calculated based on the number of each type of pieces on the board.  So when a piece us added or taken away the material hash value is updated.  Unlike a normal zobrist hash value the location of the piece is not relevant.

When the evaluation routine is called, one of the first tasks is to check to see if the material hash of the position matches the signature of a known endgame.  If there is a match the endgame specific routine is used to evaluate the position.  Here’s the code to evaluate white rook and king vs. long black king:

void known_endgame_RKvk(struct t_board *board, struct t_chess_eval *eval)
{
eval->static_score = lone_king[board->king_square[BLACK]] + 800 - 10 * square_distance(board->king_square[WHITE], board->king_square[BLACK]);
eval->static_score *= (1 - board->to_move * 2);
}

Adding knowledge is also really easy.  Here’s the routine to add KBN vs. K:

//-- R + K vs. k
clear_array(material);
material[WHITEROOK] = 1;
key = get_material_hash(material);
index = key & material_hash_mask;
if (material_hash[index].key != 0)
return FALSE;
material_hash[index].key = key;
material_hash[index].eval_endgame = &known_endgame_RKvk;

Cool stuff!

Chess Engine Testing Framework

Chess-Engine-TestingSince Maverick is now playing chess I really need a testing framework.  Testing has always been important but I think Fabian Letouzey really “turned some heads” when he started making rapid progress with Fruit back in 2004.  His secret turned out to be making decisions about engine parameters and potential improvements based on cold hard facts i.e. testing.  Since then we’ve seen much more discussion about testing.  Then came Rybka and Houdini who championed, what I’d call, turbo-testing.  This is where the games are super short – something like 60 moves in 20 seconds.  Ten years ago I think this would have been frowned upon as too fast and the results will likely not scale to longer time controls.  As it turns out this fear seems to be incorrect.  Turbo-testing seems to be the best way to quickly test potential improvements.

When developing Monarch my testing really wasn’t systematic.  I’d run games of varying lengths.  Maybe 50 games or at most 100 games.  In hindsight Monarch really wasn’t tested well.  I’m determined not to do that with Maverick.  Thankfully there are also some great tools to help with the testing.  The tool which seems to be regarded as the best is CuteChess-Cli.  Another one is LittleBlitzer.  Both enable you to run multiple games in parallel and with minimal screen updates.  I decided to plump for CuteChess-Cli as my tool of choice.  Here’s how I went about setting up the testing framework:

  1. First you need to download CuteChess-Cli
  2. I decided to create a folder for the testing framework as a sub-folder of my root directory.  This way any paths will be quite short.
  3. I then selected a number of engines which will be Maverick’s sparing partners.  The criteria I set for selecting the engine is as follows:
    • Stable – each engine must be rock solid stable
    • A playing strength of between 1800 ELO and 2200 ELO.  This will provide a range of opponents, all of whom will initially be better players.
  4. The engines I selected are as follows:
    • Monarch 
    • Clueless
    • MadChess
    • Predateur
  5. I created a few “good-old-fashioned” batch files to execute the actual tests.  Here’s an example of one of the test batch files:

@ECHO OFF

SET varYYYY=%DATE:~10,4%
SET varMM=%DATE:~4,2%
SET varDD=%DATE:~7,2%
SET varTodaysDate=%varYYYY%%varMM%%varDD%

SET PGN_DATABASE=Games%varTodaysDate%.pgn

c:CuteChesscutechess-cli -engine name="Maverick 0.10 Beta" cmd=Maverick dir=c:CuteChessMaverickNew1 -engine name="Predateur 2.2.1 x32" cmd=Predateur dir=C:CuteChessPredateur -each proto=uci tc=60/180 book=c:CuteChessobook.bin -pgnout c:CuteChessGames%PGN_DATABASE% -games 500 -concurrency 4 -wait 5

pause 10

As you can see this, runs one match of 500 games between Maverick and Predateur.  Four games are played concurrently on the same machine.  All the games are stored in a PGN which contains today’s date (you may need to adjust the code at the top of the bat file for different date formats – mine is US).   For editing these types of files I’d suggest NotePad++.  When installed you simply right click on a .bat file and you have the option to edit it using NotePad++.  It also color code the formatting – very useful.

Since it may be useful to some of you, here’s my whole testing framework zipped up and ready for download.

Maverick is Available for Download!

You can download the first release of Maverick on the Download page.

I decided to make this release as Maverick seems to be stable.  But don’t expect anything special.  I’d estimate the strength to be about 1700 ELO on the CCRL scale (which us about 300 ELO weaker than Monarch, my previous engine).  I wouldn’t be surprised if it’s even weaker than 1700 ELO.  If you’re interested in a fast but dumb engine, then Maverick will be perfect.

Here’s what it does:

  • Magic bitboard structure which would seem to be quite fast (the 64 bit version runs at about 8 million nps in the middle game on my Core-i7 4900QM at 2.8 GHz)
  • Fully UCI compatible (tested in Shredder and Fritz)
  • Basic PVS search
  • Move ordering – captures (mvv/lva ordered), killers and history move count
  • Basic Quiescent – all SEE positive moves played
  • Basic evaluation function which is little more than piece-square tables
  • Draw by 50 move rule
  • Draw by 3 times repetition (Maverick is quite “smart” and requires 3 time in appropriate positions – see here for discussion)
  • Ponders in opponent’s time
  • Polyglot compatible opening book (selectable from Maverick’s options menu!)

And that’s it!  Maverick doesn’t even have null move pruning or hash tables (so room for improvement!).

At this point Maverick seems to be stable; having played a few hundred games against Monarch.  Please let me know if you encounter any problems.

P.S. I started writing Maverick five months ago to the day!

UCI Chess Engine Protocol

I really like the UCI protocol.  I know there are diehard fans of Winboard out there, but for me I like the cleanness of UCI.  One of the aim I have for Maverick is to support as much of the protocol as possible.  In Monarch the UCI code was stable but it was a bit messy.  So I put some thought into how I could simplify the implementation.  Here’s what I came up with for Maverick:

There are two threads.  The first thread just listens for user / GUI input.  We’ll call this the listening thread. The second thread runs the engine’s search and reports back with it’s findings.  We’ll call this the thinking thread.  Most, if not all, problems with this type of implementation crop up when one thread gets out of sync with the other thread’s state. This usually results in the thinking thread being sent unexpected commands which are either ignored or processed incorrectly.

The insight I had was by using the UCI protocol there are only two commands which change the state of the thinking thread.  These are “go” and “stop”, (there is also “quit”, which I handle as a special form of “stop”).  So the “go” command needs to change the state of the thinking thread from “waiting” to “thinking”.  And the stop command needs to change the state back from “thinking” to “waiting”.  In Maverick’s implementation I’ve also added “Start_Thinking” as another state for the thinking thread.  This is needed when there is rapid fire changes and the GUI is blasting commands at the engine.  Under the rapid fire scenario the engine can receive a stop command before the engine starts to think.  By having the “Start_Thinking” state the engine can wait for the search to start before taking any more input from the GUI.

Here’s the code:

void uci_stop()
{
uci.stop = TRUE;
while (uci.engine_state != UCI_ENGINE_WAITING)
Sleep(1);
}

void uci_go(char *s)
{
search_start_time = time_now();
last_display_update = search_start_time;
set_uci_level(s, position->to_move);
uci.engine_state = UCI_ENGINE_START_THINKING;
while (uci.engine_state == UCI_ENGINE_START_THINKING)
Sleep(1);
}

It seems to work well and be rock-solid stable!

Maverick is almost ready to start playing chess.  A few more clean-ups needed!

US Citizenship & x5 Speed-up!

It’s been a while since I last posted.  I’ve been busy getting all of the UCI plumbing in place.  Maverick is almost at the stage it can play a game of chess.  I’ve created the basic search routines – complete with alpha-beta, quiescent search and root search. 

Some early tests show quite a speed-up compared to my old Monarch letterbox framework.  On my 2.8 GHz i7 4900MQ the old Monarch 1.7 engine is doing about 1.7 million nodes per second.  On the same positions Maverick is doing about 8.6 million.  I expect this will come down once I add hash tables and beef up the evaluation but this is better than I expected.  It’s about a five times speed-up.  I think quite a bit is due to the 64 bit GCC 4.8 compiler but I’m happy with the result.

I’m hoping Maverick will play its first game this weekend.

On another note – I became a US citizen today!