Pawn structure evaluation

Lately I spent some efforts trying to improve the evaluation of pawn structures. A pawn structure is a rather long lasting feature of a position. A good understanding of strength and weaknesses of those structures helps the engine to better understand the position.

I'm not so happy with the current evaluation of iCE in that area so I tried to improve it. I studied some of the theory e.g. Pawn Power in Chess by Hans Kmoch and tried to deduct meaningful patters like different kinds of double pawns (the closely shielded central double pawn which is not necessarily a weakness), isolated and backward pawns, levers etc.

I modified my evaluation with those patterns but unfortunately none of the regression tests succeeded. The best version was still a minor regression of about -4 ELO although I noticed that the playing style of the engine changed a lot. Usually if I test a new version against the old one I have a draw ratio of more than 50%. Here I only experienced a draw ratio of only about 30% which is the usual draw ratio of unrelated engines. So the changed pawn structure code had a significant impact. To bad it was not stronger.

So I went back to my old evaluation.

Nevertheless it was not a complete waste of time. Not my engine but I did learn something along the way about pawn structures and I got an impression what terms to target next. But overall of course I hoped for a better outcome.

Not being lazy anymore

Lazy evaluation describes a technique where an engine does not do a full evaluation of a certain position but does only a rough estimate.

Lets say the engine knows already it has a line where it will even with best play of the opponent end with a pawn up (+1.00). Now it considers a different line where already the basic material evaluation shows that it is a rook down (-5.00). Now the engine can save time, because it does not really need to know what the influence of other factors in that position like mobility, space, open file coverage, weak pawns etc. is. All those will not compensate the loss of a rook so the engine will not play that line anyway.

This sounds like a simple and smart concept and some well known engines use it. It really speeds up the evaluation, so nps (evaluated nodes per seconds) goes up. But there is no free lunch. The problem is to pick the right safety margin. In the above example the safety margin was more than a rook, this is pretty safe. But with such a big margin you have only few cases where you can apply lazy eval. If you shrink the margin you have more and more cases for lazy eval, but so also increases the danger that you will miss stuff. 

My experiences where that while lazy eval increases the raw speed of the engine it also increases the amount of work the engine has to do to reach the same quality. In terms of time it was about even.

So far in iCE I had a very limited form of lazy eval. The safety margin was between a rook and a queen. This seemed to help overall a little but I always disliked it.

So I recently tested the complete removal again. And after 16.000 games both versions were equal. Considering the error margin removing the feature can still lose about 5 ELO in the worst case but I'm willing to take that risk.

Safety first.

Next Generation chess players

My success in chess relates rather to improving my little engine. Although I enjoy playing over the board I'm not really doing great in that area. Maybe the next generation is here more sucessful.

Last Saturday my elder son (8 years) played its first chess tournament and he did surprisingly well. He managed to win its first 4 games and only lost the last one for the tournament victory. So he got a remarkable 2nd place in its group.

Congratulations, Jonas.

Razoring

In chess programming Razoring describes a forward pruning algorithm. In order to process the huge search tree some "uninteresting" branches are not searched as deep as others. This simulates a bit the human behavior where obviously bad lines are not considered as carefully as promising lines.

When thinking ahead and the engine finds itself in a position that is worse than a position it already knows it can get to it will stop searching the moves into that direction and consider other moves.

Of course this means the engine can also miss some good moves that it would have found if it searched just a bit more into that direction. So this is a bit gambling. If the engine gains more from skipping bad moves than it loses from missing some good ones overall it is a gain.

In the past iCE did not use razoring, I tried it and it did not work. I also read hat Bob Hyatt tried it extensively and it did not work for him either.

Anyway from time to time I retest some features. Recently I got history heuristics working that also failed in the past. So now I retested razoring and it also seems that it now works. Even without tuning the razor conditions iCE got another small improvement.

It seems the time for the big jumps is gone, so progress means piling up small gains. But in total a lot of small steps gets you as far as a big jump. It is just more work.

iCE 1.0 breaks through the 2700 ELO barrier

It's about 9 month since I released iCE 1.0 and it has played now well over 800 games for the CCRL. Its ratings is stabilizing with more games played and it has now reached the 2700 ELO mark.

I thought I make a screenshot. Just in case it does not last for long. Currently iCE is playing in the already very strong division 3 of the CCRL where it is one of the weakest engine of that division. Probably it will score some bad losses and lose some points again.

But for now time for a little celebration.

Older versions of iCE

A fellow programmer asked me about older weaker versions of iCE to measure progress against. I think this is a nice idea. I remember when I started most of the programs I found were so strong iCE did lose almost every game. I measured progress by the moves until checkmate was delivered.

So I looked up my old files. I did not have an ice01 executable anymore but I still had a collection of the sources and they still compiled, yeah !

So here is a link to a fresh compile of old ice01. This version is from 2011. It is not able to use a book already.

http://www.fam-petzke.de/downloads/ice01.exe

I have no package of ice02 anymore. This was before I was using git. The sources were modified to become ice03 and I don't have the ones that compile to ice02 anymore.

But I still have a iCE 0.3 available. You find it here

http://www.fam-petzke.de/downloads/iCE_v03_2750.zip

Both ice01 and ice03 are only available as 32 bit versions. They don't compile as native x64 applications due to some inline assembler that I used. They run however fine on a x64 system, just a bit slower.

iCE 1.0 is the first iCE that is available as native x64 application.

Have fun with them. I hope they help.

Move ordering

The way the chess engine search demand a very good ordering of moves. To be able the handle the huge search space it is important to search the best move in a certain position first. Often it turns out that this move is so good, the opponent won't play moves leading into that position and then you don't have to look at the remaining moves at all.

There are several techniques available to deal with that and iCE uses most of them. Last time I measured it did search the best move first in more than 90% of the positions.

For that I tried to use some knowledge in the function that orders moves, e.g. order moves with an attacked piece early and moves to squares attacked by opponents pawns late in the list so the function got a bit complex.

One technique I do not use (I tried once but it failed) is history heuristics. This is a simple statistics. Moves that were in other earlier searched positions good are tried before moves that have no or a bad history. I wondered whether I can maybe now replace a bit of my complex knowledge with such a statistics to simplify the engine a bit.

And it turned out I can.

I striped all my move ordering functions that handle quiet moves from knowledge and replaced it by history. The now simpler engine even seems to play a bit better, not by a huge margin but statically significant.

After a lot of failed attempts I'm happy I encountered now a change that works and even makes things simpler. However the idea is well known and widely applied. So nothing to get to excited about.