Round Robins

As engine development can be a bit frustrating from time to time I jump a bit between trying to improve my engine and playing with a GUI prototype.

Lately I worked on a pairing algorithm for round robin tournaments. Here each engine plays all other engines for a given number of rounds.

The algorithm should create a pairing with a certain number of constraints like

1. Work with both an odd and even number of players
2. Let each engine play equally with White and Black (as close as possible) even if the number of rounds is 1 or odd.
3. If an engine played one game with White it should play the next game with Black (in most cases against a different opponent)
4. If the number of rounds is even, create for each other round the same engine pairings with colors reversed and assign the same opening id.
5. Create a pairing sequence where an engine does not play a lot of games in a row (e.g. avoid a sequence where first engine A plays all the N-1 opponents and then engine B plays N-2 opponents etc.)

This seems like a really difficult problem. Luckily there exists a method used in over the board tournaments that helps here. In this method 1 player is fixed and the others after each match walk clockwise around a series of tables until the original setup would appear again.

It still requires some care to match all of the above constraints but the is solves most of them naturally.

Here is an extract of a pairing of 5 players (named 0, 1, 3, 4 and 5). The number in brackets is the opening id used in this pairing.

Revisiting king safety

In order to improve the evaluation function in my engine I decided to revisit my king safety evaluation.

King safety is an important concept as when the king is going to be mated the game is over. King safety takes care of good king locations, intact pawn shelters, number of attacker and defenders around the king, material mating potential etc. Overall this is a fairly complex sub evaluation and to have it fairly accurate is important for the playing strength. A decision whether an engine should sacrifice material in order to be able to launch a mating attack against the opponents king comes mainly from this concept. And a wrong decision is usually fatal.

To get a better understanding what terms are important I first ran some statistics. I analyzed a few million positions where the king safety term kicked in and recorder the location of the kings.

Mid game probability the king is on a given square (black side is mirrored)

In the huge majority of the cases the king resides on the target square after castling short. In some positions it has not yet castled and in even less positions it has castled long. So obviously king safety evaluation around a king on G1 is the most important.

In my evaluation I increase or decrease a counter for attacking or defending pieces. Each piece type is handled individually. A defending queen gets no bonus, a defending bishop does. The valid counter range after adding all attackers and subtracting the defenders is between 0 and 50. Now I wanted to know how this counter is distributed. I expected a uniform distribution, but it looked quiet differently.

Obviously there are some values much more likely than others. Probably because some attack / defend combinations are much more likely than others but overall the range between 10 and 30 is the most interesting one. I intend later to give tuned values higher focus if they relate to a counter value that occurs frequently.

Finally I tuned the king safety evaluation where I assigned each counter value an evaluation value. If plotted as a curve the evaluation values form a somewhat exponential function.

Evaluation per Counter

The tuning resulted not in a smooth curve. I really would have like that. I thought about modelling the curve with an exponential function minimizing the error in the important data points. But so far I did not do it. I just hard coded all 50 tuned values for now. For a serious attack (counter >= 40) the evaluation goes over the value for a rook. This might encourage some nice sacrifices, I hope.

The final regression test got me a somewhat nice improvement in strength over iCE 2. So at least it was worth it.

http://www.amateurschach.de

Frank Quisinsky runs a nice engine tournament with amateur chess engines and the qualification for the next round was just finished. iCE did really well in this field and ended up being first. As each program has played 1000 games the list is already a good reflection of the relative strength of the engines. 

So far it has not happend to often that iCE ended up first, so I'm enjoying that moment a lot. 

 

          Programs                                             Score                  1-0    =     0-1                   EloS 
01. iCE 2.0 v2240 POP x64         649.5/1000  433 433 134  65.0%  2750 

02. Spark 1.0 x64                 628.5/1000  410 437 153  62.8%  2735  

03. Deuterium 14.2.33.276 x64     608.0/1000  401 414 185  60.8%  2721 

04. Gaviota 1.0 AVX x64           600.0/1000  410 380 210  60.0%  2715 

05. Tornado 5.0 SSE4 x64          596.0/1000  400 392 208  59.6%  2713  

06. Vajolet2 1.45 POP x64         578.0/1000  360 436 204  57.8%  2700

07. Nirvanachess 1.7 x64          568.0/1000  369 398 233  56.8%  2694
08. Fizbo 1.2 x64                 545.0/1000  339 412 249  54.5%  2678 

09. Arasan 17.4 POP x64           537.5/1000  326 423 251  53.8%  2673

10. Cheng4 0.36c x64              507.5/1000  295 425 280  50.7%  2653

11. Crafty 24.1 SSE42 x64         493.0/1000  314 358 328  49.3%  2644

12. EXchess 7.31b x64             477.0/1000  277 400 323  47.7%  2633

13. Glaurung 2.2 JA x64           471.5/1000  267 409 324  47.1%  2629

14. Rodent 1.4 POP Build 2 x64    466.0/1000  264 404 332  46.6%  2626

 --- first 14 places are qualified (without Glaurung and with Andscacs 0.70)
15. Atlas 3.70em x64              465.0/1000  264 402 334  46.5%  2625

16. OctoChess r5190 SSE4 x64      458.5/1000  231 455 314  45.9%  2621

17. Andscacs 0.64 POP x64         419.0/1000  220 398 382  41.9%  2594

18. Rhetoric 1.4.1 x64            413.0/1000  205 416 379  41.3%  2590

19. Godel 3.4.9 x64               403.5/1000  207 393 400  40.4%  2584

20. Djinn 1.021 POP x64           312.0/1000  129 366 505  31.2%  2518

21. ProDeo 1.87 w32               303.5/1000  147 313 540  30.3%  2511

iCE 2 and the chess engine rating lists

CCRL 40/40

iCE 2 has now played enough games and is strong enough to be listed in the major chess engine rating lists. My main reference source is the CCRL as here it was listed since it very first prototype version. With some 400 games played it is now listed at number #39 in the "games at long time control" section. Its ELO will probably improve a bit over time with more games played. I've seen this with iCE 1.0 too that ended up after 1000 played games even above the error bar from the early games. In the short time control list iCE 2 is listed at  #28 with 2921 ELO (after far more games were played) and I don't expect a 30 ELO difference just coming from a different time control.
 

CEGT 40/20

CEGT lists iCE 2 at #26. iCE was also tested for a "ponder ON" list, where the engine keeps thinking when it's the opponents turn. This revealed an ugly bug in iCE that went so far undetected and has been fixed by now.

So when I reflect on my goals to pass the 2800 ELO mark and to enter the top 40 of the CCRL I think I'm done. I also passed the best single CPU version of crafty. Just passing the latest version of DiscoCheck is still open. Currently they are to close together to be able to tell which engine is stronger.

I also might fall out of the Top40 again, so I keep my goals open for the next version of iCE.
   

Some more GUI fun

Shaker GUI Proto Type

To relax a bit from the engine programming madness I worked a bit further on my GUI project. Here the challenges are completely different.

So far I have

• a somewhat working PGN parser. I have not tested it with a large collection of pgns so there might be some he cannot process (especially illegal ones)
• A game recorder that creates a pgn from manually played moves on the board including annotations.
• A simple tournament manager that is able to run some engine vs engine matches. It still needs a lot of configuration options. Everything is currently still hard coded.
• An interface to play an engine as a human.
• A working time control
• A simple analyses interface that analyzes a given position

Especially keeping track of the GUI / Engine status is mind boggling. Certain commands only work when GUI and loaded engine are in a certain state so the menus must be enabled or disabled depending on those states.

So I think this will keep me entertained for a while and then I will probably very welcome a bit of simple engine programming again.

iCE 2 first ratings are being established

After an official release one is always curious whether one was able to improve the engine and if so by how much. I was pretty sure that the new iCE is better, my test against the old version at very short time controls showed a real improvement. But I was unsure how this scales to other opponents and much longer time controls.

As with iCE 1 Lars Hallerström performed an initial rating test and the results look encouraging. In his private rating list iCE 2 gained 200 ELO and climbed 66 spots. Considering the fact that it now already is faced with some 4 core engines while iCE is running only on 1 this is nice progress. 


 53 Ice 2.0 (64) : 2954   19  19  1000    57.2 %   2904   26.2 %
119 Ice 1.0 (64) : 2754   19  19   900    52.3 %   2738   26.7 %

53 Ice 2.0 (64)              : 2954  1000 (+441,=262,-297), 57.2 %

Fruit 2.3.1                   :  40 (+ 26,= 10,-  4), 77.5 %
Ktulu 9                       :  40 (+ 28,=  7,-  5), 78.8 %
Spike 1.4                     :  40 (+ 14,= 12,- 14), 50.0 %
Komodo CCT (64)               :  40 (+  3,=  9,- 28), 18.8 %
Junior 12.5.0.3 (4cores)      :  40 (+ 14,=  9,- 17), 46.2 %
Deuterium 14.01 (64)          :  40 (+ 14,= 11,- 15), 48.8 %
Gaviota 0.86 (64)             :  40 (+ 21,= 13,-  6), 68.8 %
Dirty Feb 26 2014 (64)        :  40 (+ 27,=  7,-  6), 76.2 %
Sjeng WC2008 (64)             :  40 (+ 21,=  8,- 11), 62.5 %
Crafty-23.8 (64)              :  40 (+ 16,= 13,- 11), 56.2 %
Texel 1.03 (64)               :  40 (+ 14,= 18,-  8), 57.5 %
Bug2 1.9 (64)                 :  40 (+ 27,=  8,-  5), 77.5 %
Scorpio 2.7.6 JA (64)         :  40 (+ 10,= 14,- 16), 42.5 %
EX 7.11b (64)                 :  40 (+ 25,= 12,-  3), 77.5 %
Djinn 1.010 (64)              :  60 (+ 39,= 19,-  2), 80.8 %
Cheng 4.36 (64-4cores)        :  40 (+ 14,= 15,- 11), 53.8 %
Rybka 4.1 SSE42 (64-4cores)   :  40 (+  3,= 13,- 24), 23.8 %
Hannibal 1.4a (64-4cores)     :  40 (+  5,=  9,- 26), 23.8 %
Chiron 2 (64-4cores)          :  40 (+  3,= 10,- 27), 20.0 %
Senpai 1.0 sse42 (64-4cores)  :  40 (+  1,= 12,- 27), 17.5 %
BobCat 3.25 (64)              :  40 (+ 20,= 11,-  9), 63.7 %
Brutus 8.05 JA (64)           :  40 (+ 34,=  6,-  0), 92.5 %
GreKo 12.0 JV (64)            :  60 (+ 55,=  4,-  1), 95.0 %
Spark 1.0 (64-4cores)         :  40 (+  7,= 12,- 21), 32.5 %

Thanks Lars for providing the data

iCE 2 has been released

Yesterday I uploaded the new release of iCE to my website and released it into the wild. Again more than 1 year development and tuning went into this release. The last release was dominated by changes to the evaluation and weight tuning. Most of the committed changes in this release are now related to the search framework. 

Download iCE 2

Of course it has no established rating yet but I'm confident that it is stronger than iCE 1. I have not really an idea by how much. I tried to pair it with some free engines but I got contradicting results. Against some engines iCE ended up only as crushed iCE while it was able to really freeze some other engines despite the fact that all those engines are close together in their CCRL rating. Probably the time control I test with or my test setup is just bad so I leave the actual testing to the experts.

Here a summary of the changes for this release.   

Changes:

Bugfixes: Bugs related to recognizing a trapped rook and to the 50 move rule were fixed

Pawn Hash Handling: King position is now stored into the pawn hash which allows the hashing of additional eval terms while the hit rate goes down a bit.

Endgame Knowledge: Some special code to handle certain 5 piece endgames was added. iCE now uses the material hash to recognize the endgame types. The ugly list of if ... then ... statements that checks for piece combinations is now gone.

Evaluation: Some changes to the evaluation to understand certain positions better. An example are positions with an isolated queens pawn. Tests showed only limited impact on the strength. I kept them because I hope the overall playing style of iCE looks more natural now in those positions. Some minor terms have been dropped or have been replaced by others. My pawn structure evaluation is still clumsy, all attempts to improved it failed.

Table Bases: iCE is not using external table bases during play. iCE 1 had the DTM data for all the 3-men TB built into the executable. Those tables were removed in iCE 2. They are calculated on the fly when the engine starts. The calculation is fairly optimized and takes less than 100 ms on a decent 1 core system.

Search Changes: Added History Heuristics, Late Move Pruning, Razoring and Counter Move Heuristics. Change LMR to be less aggressive. Lazy eval removed. Added LMR at the root node. And tuning, tuning, tuning ...

Code Cleanup: A lot of code was refactored and simplified. Especially similar code for WHITE and BLACK was merged using C++ templates. Overall from iCE 1 to iCE 2 5600 lines of code were removed while 3800 lines were added.

Unchanged iCE is still a CLOP free zone and does not access endgame tablebases in play. However the new endgame knowledge was verified against Gaviota table bases. Tribut and thanks for providing them goes to Miguel Ballicora. Also everything related to opening books is unchanged and still works the same with iCE 2.

I recorded my work on iCE over the last years in this Blog. It contains all the dirty details. So someone interested to learn about my approach to automated parameter tuning using an GA might find something interesting here