Saturday, June 28, 2014

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.

Sunday, June 22, 2014

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.




Tuesday, June 10, 2014

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.