Saturday, December 22, 2012

Getting used to some C++ techniques

In the new release of my engine I plan to rewrite its board evaluation (again). This is necessary because the old evaluation uses weights declared as compile time constants.

e.g. const int BISHOP_PAIR_BONUS = 50;

This is easy to maintain and also very fast because the compiler just inserts the value in the evaluation code and no memory access is later required to find out what the bonus for having two bishops is. The problem starts when you want to change that value. It requires a recompilation of the whole program. As I want to be able to change that value at run-time, maybe even while the engine is running using constant values is not an option anymore. I have to replace them with variables even if it might slowdown execution a bit, probably not much because those values are accessed so frequently that they will stay in the L1 cache of the CPU.

But it means that I have to touch everything in my board evaluation code and if I have to touch everything anyway I can just as well clean it up a bit.

One thing that bothered me a bit is code duplication. Every feature is evaluated first for white and then again for black. The implementation of the features is not identical, e.g. white pawns move up black pawns move down, white king is safe at G1, black king is safe at G8. But the source code is very similar anyway and differs only in a few parameters. It also makes the code harder to maintain because every time I change something I must remember to change it in the WHITE and in the BLACK part of the code.

Fortunately C++ offers a language construct called function template. It's main purpose is to uses the same code to work with different types of variables e.g. a sort function that sorts integers uses the same logic as a function that sorts floats, it uses just a different declaration. C++ templates allow the programmer now to write the source code only once and the compiler will create the different code for ints and floats automatically.

This is awesome and just what I need.

While rewriting the evaluation I extract those parts where templates might be helpful and clean up my code.

Instead of a function

void TEvaluator::evaluateThreats()
{
     // do something for white threats against black pieces
     ...

    // now do the same for black threats against white pieces
    ...
}

I have now a template function

template< EColor side > void TEvaluator::evaluateThreats()
{
    const EColor enemySide = (side == WHITE ? BLACK : WHITE);

    // do something for threats of "side" against the pieces of the "enemy side"
    ...
}

which is then called via

evaluateThreats< WHITE >();
evaluateThreats< BLACK >();

This works so well that I might rewrite other parts of the engine as well at some point in the future. The move generator currently duplicates code like hell and could definitely benefit from this technique a lot.

Saturday, October 6, 2012

A simultaneous over the board experience

I usually don't play over the board. I find it interesting but I don't have the time for that. I never played in clubs or tournaments. My chess efforts are rather programming related. But today I was visiting a local gaming fair and part of it was IM Cliff Wichmann playing 16 boards simultaneous chess. My wife convinced me to play one of the boards. I did and no surprise I lost but not as badly as I thought.

I played black and had a rather bad opening. White played a Queens Gambit and I actually don't know much theory of it. My chess engine plays openings from its opening database so I did not put much efforts in learning all the variations while programming it. So my little knight was chased around and White had the control of the center after 1. d4 d5 2. c4 Nf6 3. cd Nxd5 4. e4

However I survived the opening without plundering away any material and had a rather strong middle game. Our play led later to this position.

 IM Cliff Wichmann vs. Thomas Petzke

  White to Move

So I had a knight and rook vs. the bishop pair which I considered Ok. I analyzed the position at home with iCE and also stockfish. Both agree that black has a slight advantage of a bit more than a pawn here. But due to my lack of routine I wasn't able to hold that advantage. I had played already 90 minutes and my board was one of only 3 boards that were still played in the tournament. So my thinking time dropped because with only 3 boards left my opponent appeared very rapidly after his move at my board again. 

He stormed with his h and g pawn, I was later forced to trade my rook against a bishop and a pawn and he finally promoted 1 move before I could where I resigned. 

It was quite an interesting experience anyway.


Thursday, September 6, 2012

Mastering the King a Rook vs King and Pawn endgame

In iCE 0.3 I added a lot of endgame knowledge especially for drawish pawn less endgames with material in-balance (like KRNKR). However a few fundamental ones are still missing. One of them is King and Rook vs. King and Pawn which is really tricky to evaluate nevertheless very important.

Consider the following position with white to move

1. Rc8 is very tempting but only draws, after


1. ... Ra7 2. Ke8 Rxd7 3. Kxd7 we reach the following KRKP endgame, which is a draw


iCE did not know that. In fact iCE selected the move 1. Rd1+, but this is also only a draw after 1. ... Ke4. So while the endgame is not even on the board the lack of knowledge let play iCE the wrong move. I run a search for several hours, iCE was still happy with 1. Rd1+.  And of course it makes no sense to optimize towards a single position, the underlying knowledge problem must be solved.

There are a lot of winning positions for the pawn side if the pawn is already on the 6th or 7th rank. Here the rook is not able to stop the pawn from promoting and where the pawn side then wins the Queen vs Rook endgame.  But sometimes the pawn safely promotes but the rook side  is able to force a stalemate or give permanent checks. So finding out the pawn will promote is not enough for classifying it as a win.

If the pawn is not advanced the rook side might not be able to stop it without sacrificing the rook which leads to a draw.

In general one can state for this endgame
  • Usually the rook side is able to stop the pawn
  • If the attacker king is in front of the pawn the attacker will win
  • If the pawn gets support from its own king and the attacker king is away and behind the pawn the pawn side might be able to draw.
  • If the pawn is already on the 7th and sometimes on the 6th (with the pawn side to move) it might be able to promote and win 
  • There are hard to spot exceptions for both sides.
Those exceptions make it very hard to assemble a rule set to classify a position correctly. After several tries I decided on the following implementation for my KRKP module.

First I implemented a method to detect the wins for the pawn side. This method detects the trivial cases where the rook is immediately captured and the resulting KPK endgame is won, but also the non trivial ones where the pawn is able to promote and the queen survives (without stalemating the other king). The detector must handle the 3 non trivial cases
  • the pawn is on the 7th and the pawn side moves
  • the pawn is on the 7th and the rook side moves
  • the pawn is on the 6th and the pawn side moves
In all other non trivial positions the pawn side will not win. Most won positions obviously are found in the first case. I came up with a very complex rule that detects 99% of the wins in that situation. To detect the remaining 1% (about 1300 positions) I decided to just store them explicitly.

Only about 6000 positions make up the 2nd case. I tried hard to assemble some rules for that but at the end I gave up and also store them explicitly. The 3rd case is easy then. To win the pawn must move and we can look whether we have stored the resulting position for case number 2.

So this method detects 100% the pawn wins with a small internal database and a few complex rules.

Next I require a 2nd method that detects the drawn positions which is called only if we see that the position is not a win for the pawn obviously.

Theory states to count the tempi for the pawn side to promote with king support and the rook side to control the promotion square with both rook and king. If the pawn side requires less tempi than the rook side it is a draw. This is maybe a good rule of thumb for a human but it is not a correct rule for a computer. It will announce a lot of false draws. So I tried another approach.

Whether a position is drawn depends mainly on the pawn and king positions and less on the position of the rook. I assembled a small internal database of about 2600 records (each 2 byte) that contain those king and pawn positions that are drawn no matter where the rook stands or whose side to move it is. With those 2600 records I'm able to detect 700k out of 1.2M drawn positions.

I decided to stop here, this is good enough.

So after all that efforts I wanted to see whether it helped iCE to find a better move in the above position and voila it actually did. It sticks to the winning move realizing that the alternatives will draw. It is even able to announce the correct distance to mate.


depth move score  nodes
move score  nodes
1 d8=Q 379 56
d8=Q 277 72
2 d8=Q 379 275
d8=Q 277 234
3 d8=Q 379 386
d8=Q 267 336
4 d8=Q 367 1648
d8=Q 267 1220
5 d8=Q 344 2367
d8=Q 277 1993
6 d8=Q 356 6264
d8=Q 307 11897
7 Rc2 356 22k
d8=Q 317 20k
8 Ra1 341 123k
d8=Q 327 50k
9 Ra1 341 142k
d8=Q 327 57k
10 Rc8 356 5948k
d8=Q 327 285k
11 Rd1+ 341 2337k
d8=Q 367 363k
12 Rd1+ 341 805k
d8=Q 317 9M
13 Rd1+ 341 20M
d8=Q 317 14M
14 Rd1+ 336 8M d8=Q 367 3M
15 Rd1+ 341 13M d8=Q 417 8M
16 Rd1+ 338 54M d8=Q Mate 25 34M
17 Rd1+ 341 94M d8=Q Mate 24 73M

I like it when something works !

    Sunday, August 12, 2012

    mACE GUI Update

    I decided to publish a small update to the mACE GUI that can be used to play against my iCE engine. Unlike iCE it is written in Free Pascal, so I had a bit of a hard time to switch back to Pascal coding syntax ( := instead of =, = instead of ==, no ; before an else statement and this kind of stuff).

    The mACE GUI allowed 3 strength settings (low, medium and high) which allowed the engine 3, 5 and 10 minutes thinking time for 40 moves. It turned out that this is to strong, even in low it was unbeatable for an average amateur player. I decided to weaken it further by putting search limits to its search. I call that skill level and I implemented the skill level 0 - 10.

    The skill level specifies the max main search depth for the engine, so in skill level 5 the engine searches 5 ply deep. The engine performs still a quiescence search (it plays out all winning captures when the max search depth is reached, so it does not hang a piece there) and uses some extensions (like the check extension).

    I was surprised that even in skill level 0, the engine plays quiet reasonable and it takes some effort to beat it. So to have some real weak levels I also introduced some randomness. In skill level 0 and 1 there is a 10% - 20% chance that the GUI discards the move sent from the engine and picks a random move from the legal move list. This now gives me a real good chance to beat it and hopefully increases the fun for others as well.



    Monday, July 30, 2012

    iCE 0.2 last and final fight

    As I published now the new iCE in version 0.3 there will probably no more matches where iCE 0.2 participates in. Very likely the Division 5 of WBEC Ridderkerk 19 was it's final fight. Here almost 100 engines played, first in 4 groups and the best 5 in each group went into a playoff. The best 7 in the playoff qualify for Division 4 then.

    Little iCE did excellent and finished the playoff at number 2. So it would have earned iCE a spot in Division 4, which is not played anymore. Leo Dijksman has unfortunately decided to stop its tournaments as he lost his interest because of the many engine clones that appear. Very sad!

    Here is the final cross table

    WBEC Ridderkerk, 5th division FINAL.

    AMD-PHENOM-3100, 2012.07.04 - 2012.07.21
                                   Score     Di iC At If Be TJ Me Sj Ev Ay 
    -----------------------------------------------------------------------
     1: DiscoCheck 3.61-x64      29.5 / 36   XX 01 10 11 11 10 10 01 01 11 
     2: iCE 0.2-b1092            26.5 / 36   10 XX =0 0= 10 10 11 =1 01 =1 
     3: Atlas 3.20-x64           25.5 / 36   01 =1 XX 10 01 01 =1 11 =1 11 
     4: Ifrit m1.8-x64-JA        25.0 / 36   00 1= 01 XX 00 == 1= =1 1= 11 
     5: Bearded Neural 44.5-x64  24.5 / 36   00 01 10 11 XX 0= 10 00 11 11 
     6: TJchess 1.1-x64          23.5 / 36   01 01 10 == 1= XX 01 =0 =1 01 
     7: Mediocre 0.4-JA          22.0 / 36   01 00 =0 0= 01 10 XX =0 0= 10 
     8: Sjakk 1.1.9              21.5 / 36   10 =0 00 =0 11 =1 =1 XX 01 00 
     9: EveAnn 1.67-b11          20.5 / 36   10 10 =0 0= 00 =0 1= 10 XX 01 
    10: Ayito 0.2.994            17.5 / 36   00 =0 00 00 00 10 01 11 10 XX 

    Thursday, July 12, 2012

    My Chess Engine iCE 0.3 is out

    Quite some time has passed since I released the last version of my little chess engine project. So I'm happy to announce that finally iCE 0.3 is seeing the light of the day. It's available from my homepage.

    In the development of iCE 0.3 a lot of ideas have been tried, most of them failed, some worked. I introduced new functionality and added tons of endgame chess knowledge. My initial tests indicate some ELO gain compared with iCE 0.2. But it is to early to tell how big it is. I'll know when it has played its first official 200 tournament games.

    Major changes in iCE 0.3
    • some new evaluation terms (e.g. pawns islands)
    • Understands the draw by fifty move rule and tries to avoid it when leading
    • Improved endgame knowledge. Better understanding of drawn positions especially if one side is ahead in material like king and 2 minors vs king and 1 minor or king and rook vs king and 2 minors.
    • Implements a small internal opening book if no external book is supplied.
    • Support for external opening books in a proprietary format.
    • Changed node counting rule (horizon nodes not counted twice anymore)
    • Algorithm improvements to speed up the code.
    • Draw by Repetition detection bug fix (was not really working)
    • New smarter time management, varies time for move depending on position and search progress. Leaves a safety buffer on the last move before time control to avoid time losses. Engine is now able to play very fast games with less than 100 ms per move without losing on time anymore. 
    • Implements a special move generator for "getting out of check" moves. Got some speedup.
    The engine is still only available as 32 bit version, as I don't own a 64 bit system yet. Most of its evaluation weights are not tuned at all, because I don't have the computing resources available to tune them. I used my intuition to pick a hopefully not so bad number. So tuning is definitely on the todo list for version 0.4 but this will required also some significant changes to the engine to make it tunable.

    Friday, June 29, 2012

    The fifty-move rule

    Most of my recent attempts to improve my engine failed, any possible improvement stayed within the error bar, so no breakthrough yet.

    As I'm running out of ideas for the moment to improve iCE without any major effort (e.g. major changes to eval and tuning the evaluation weights) I think I will release the current version of the code soon. It has at least functional enhancements compared with iCE 0.2 like using an opening book or better endgame knowledge.

    One of the missing functional features so far was the implementation of the DRAW by the 50 move rule. It is no big deal to implement but as I did not see any major benefit for playing strength in it I just thought I will implement it later when the time is right.

    It is right now and iCE does now know it.

    To demonstrate it consider the following position: 8/5k2/8/8/1R6/R6K/7P/8 w - - 96 200

    48 moves have been played without pawn move or capture. The old version of iCE here announces a Mate in 3, trying to mate with the rooks right away. This would fail because the game would be adjudicated as draw by the 50 move rule before Black is Mated.


    The new version of iCE is now seeing the way out.

    info depth 14 seldepth 24 time 13797 nodes 38389600 pv h3g2 f7e6 h2h3 e6e5 a3a5 e5d6 b4b6 d6c7 b6h6 c7b7 a5g5 b7c7 g5g7 c7d8 h6h8 nps 2782459 score mate 8

    So it is first moving the king and the pawn and mating with the rooks later.

    So one more source of possible embarrassment removed.