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:
- There are some really good free tools which you’ll need to download:
- 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.
- Open the MillionBase using SCID.
- We’ll be filtering the games using SCID’s excellent filtering system – select “Search / Header…” (Ctrl-Shift-H)
- I created a database consisting of only White wins by players over 2400 ELO with opponents over 2200 ELO (see diagram)
- I then saved the white win database as “white2400.pgn” using SCID’s “Tools / Export All Filter Games” command
- Repeat for Black
- Now put both PGN files in the same folder as Polyglot.exe, PGN-Extract.exe, the batch file.
- The batch file contains the commands to create the opening book
pgn-extract -s -C -N -V -tstartpos.txt -oclean-white2400.pgn white2400.pgn
polyglot make-book -only-white -pgn clean-white2400.pgn -bin w1.bin -max-ply 16 -min-game 50
polyglot make-book -only-white -pgn clean-white2400.pgn -bin w2.bin -max-ply 60 -min-game 5
polyglot merge-book -in1 w1.bin -in2 w2.bin -out w12.bin
pgn-extract -s -C -N -V -tstartpos.txt -oclean-black2400.pgn black2400.pgn
polyglot make-book -only-black -pgn clean-black2400.pgn -bin b1.bin -max-ply 16 -min-game 50
polyglot make-book -only-black -pgn clean-black2400.pgn -bin b2.bin -max-ply 60 -min-game 5
polyglot merge-book -in1 b1.bin -in2 b2.bin -out b12.bin
polyglot merge-book -in1 w12.bin -in2 b12.bin -out Maverick.bin
- The first line runs PGN-Extract and simply cleans the database, removing and games which don’t start from the normal starting position.
- The second line creates a opening book of white moves, where the positions have occurred at least 50 times.
- The third line creates a broader book which give more responses to a variety of openings.
- This is repeated for Black
- 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?
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!
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.
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.
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.
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).
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
Since 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:
- First you need to download CuteChess-Cli
- 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.
- 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.
- The engines I selected are as follows:
- 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:
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
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.
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!
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!
When humans chess players evaluate a sequence of moves they often mentally “swap off” the pieces at the end of a variation. For example if a proficient chess player took a quick look at the following position they would see Nxd5 wins a pawn:
Black can recapture with his knight but white would recapture again to win the piece. Effectively the player has resolved the sequence of captures on one square to see if the initial capture is winning or not. This type of logic is invaluable to humans and to chess engines.
In computer chess this type of routine is the “Static Exchange Evaluation” or “SEE” for short. It’s used in many different places in a chess engine. One of the most common uses is to prune losing captures in the quiescent search.
You would think such a simple “swap-off” procedure would be relatively easy to code. In my experience it’s not as simple as it seems at first! Tricky little situations add to the complexity. Is Rxd5 winning, losing or drawing?
All those discovered attacks on d5 need to be handled correctly. You also need to be able to handle the “stand-pat” condition, where one side can take but chooses not to as they would subsequently lose material.
In my previous engine (Monarch) I was never happy with the performance of the Static Exchange Evaluation. It built a list of attacking pieces and tried to resolve a score. It seemed to work but was really quite slow and I’m not convinced it was bug free. I’m determined the SEE routine in Maverick should be more robust.
In most cases the SEE function only needs to figure out if the move loses material. This simplification can save a lot of time. I Googled previous discussion about Static Exchange Evaluation on the various forums. Some people try to resolve the to a specific value using mini-max while other have an alpha-beta routine. I decided to be somewhat different and introduce a “threshold” parameter. The routine would return true if the move was equal-to, or better-than, the threshold parameter, and false if less than the threshold.
Here’s the logic in pseudo code first. “Side-to-move” is the same side as the initial SEE move being evaluated. Opponent is the opposite side:
- Generate all of the attacks and x-ray attacks on the target square for both sides
- The “see_value” is set to the value of the initially captured piece
- The “trophy_value” is set to the value of the piece making the initial capture
- Find the least valuable opponent’s piece which is attacking the target square (and is not blocked)
- Reduce the see_value by the trophy_value i.e. see_value = see_value – trophy_value
- Set the trophy_value equal to the value of the piece found in step 4
- If see_value >= threshold then return TRUE (i.e. the side to_move can stand pat and still have a score which reaches the threshold)
- If see_value + trophy_value < threshold then return FALSE (i.e. even if the side to move captures the new piece on offer, they will not reach the threshold)
- Find the least valuable piece for the side-to-move which is attacking the target square (and is not blocked)
- Increase the see_value by the trophy_value i.e. see_value = see_value + trophy_value
- Set the trophy_value equal to the value of the piece found in step 9
- If see_value – trophy_value >= threshold then return TRUE (i.e. even of the opponent captures the new piece on offer, they will not each the threshold)
- If see_value < threshold then return FALSE (i.e. the opponent can stand-pat and the score is less than the threshold).
- While each side has potential captures go to Step 4.
There are a few other wrinkles such as what to do when one side runs out of moves but I’m sure you can figure these out. I’ve also added some simple initial tests to see if an early decision can be make (e.g. can the piece be taken by a pawn?), without the need to generate all of the attacks.
Having tested the routine it seems to be quite efficient (certainly better than the SEE routine in Monarch).