Monday, August 29, 2011

iCE 0.2 is about to be released

I think it is now time to release the 2nd version of my chess engine. All the changes I did in the last 6 month should summarize into a nice improvement compared with iCE 0.1

last thing I activated is the permanent brain feature. I designed the engine from the beginning for it but did not enable it because of the more difficult protocol handshake and it makes testing more difficult. But as most other engines use a permanent brain (means they think also when its the opponents turn) I like to level the ground.

A final private tournament should give me the confidence that the engine is stable and it is really an improvement. I paired it against the same set of opponents that I paired its first version with and it did pretty good. Only Ruffian is still giving it a hard time.

RankEngineCountryScoreRuIce 0.2
1Ruffian 1.0.5Sweden44,0/48· ·· ·· ··=11101=1
2Ice 0.2 Germany39,5/48=00010=0· ·· ·· ··
3Resp019 Germany27,5/480000000000000000
4GERBIL USA16,5/48001000000000=000
5Bestia_090 Ukraine14,5/48000000000000=010
6Ice 0.1 Germany 14,5/480=00000=00000000
7BigLion Cameroon11,5/4800000000000000=0

 168 games played / Tournament is finished

Tournament start: 2011.08.27, 14:42:18
Latest update: 2011.08.29, 09:00:06
Site/ Country: Germany
Level: Tournament 40/5, Ponder ON
Hardware: Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHzDual 2394 MHz with 1.992 MB Memory
Operating system: Microsoft Windows XP Professional Service Pack 3 (Build 2600)

Friday, August 12, 2011

Chess Engine Move Ordering Statistics

As stated in my previous post move ordering in alpha beta searches is very important to cut down the size of the search tree. I lately spend a lot of time and effort to improve the move ordering and wasn't that successful to shrink the search tree no matter what I tried.

I wondered whether the reason that I did not improve was the fact that the remaining room left for improvement was so small. So I started to measure the quality of the move order in my engine (should have done that earlier, I know).

I ran a 10 second search over 250 random test positions to get an idea at which position in the list a move causes a cutoff. The earlier the better. Here are my results from those 250 positions.

Total recorded cut offs:         251,607,401
CutOff with 1st move:                 95.368%
CutOff with 2nd move:                  2.519%
Avg. move no that causes cut off:      1.174
CutOff in remaining moves*:        8,643,777   (3.43%)
CutOff move no in remaining moves:     3.022
Cutoff with a losing capture:      1,558,615   (0.62%)

*after hash, captures and killers

This analyses shows that in more than 95% the cutoff happens with the first move that is searched, which is an excellent number. Killer moves and captures also lead to early cutoffs, so in only a bit more 3% of all nodes where a cutoff is possible the quiet moves have to be generated and searched at all.

And here without doing history heuristics or piece square stuff in average the 3rd move in the list gets us a cutoff. I do however look at the killer moves from 2 plys above and 2 plys below the current node and order those moves first in the list if they are legal in thsi position. This seems to help a little bit to improve the order and I have this data anyway available.

After seeing those numbers I don't think I will put more efforts in this area in the near future because the order quality seems quite good already and the slow down in execution to get a better ordering in 3% of cut nodes will probably not pay off.

Thursday, August 11, 2011

Improve Move Ordering for Alpha Beta

The ice engine uses an alpha beta based search, that means if we search possible moves and find one that gives us a position so good, that our opponent will not play the moves that lead to it (because he can reach one that is better for him), we can stop searching further. This is called a cut off (sometimes also called beta cutoff or fail high)

This reduces the search tree. The effective reduction depends on the move order. The earlier I find a move that leads to a "to good to be true" position the more moves I can skip searching. So a simple rule can be formulated that says

Always search the best move first.

This rule is very simple but not 100% accurate, because we don't want to search the best move first, but we want to search a move that gives us a cut off with the least required effort. If the 2nd best move or even the worst move gives us also a cutoff but we only have to search half of the nodes compared to the best move, then we should search this move first obviously.

Always search the move that gives you a cutoff with the least required effort first.

Unfortunately it is not trivial to know it advance what moves give you a cutoff and what is their related effort without searching them. But it is not that bad. In a chess engine various mechanisms exist to help the engine to decide which moves should be searched first.

  1. There is the hash move. When a position was searched earlier (with a lower depth) the 1st move that gives you a cutoff was recorded. When this position is searched again with a higher depth, this move is tried first, often it still gives you a cutoff.
  2. If you don't have a hash move (you see the position for the first time or last time no move produced a cutoff) or the hash move fails this time, then you look for winning captures. Often they are good.
  3. Next you look for equal captures, maybe you get a cutoff here.
  4. Then you look for moves that caused a cutoff in similar positions (so called killers). First you have to look whether those killers are legal on the current board and if they are you search them. Good chance for a cutoff with them.
  5. Then I try losing captures, most engines search losing captures last and claim that is best for them. I search them before the quiet moves for three reasons. Sometimes a losing capture is not really losing but gives you enough counter play. If it is is really bad than the efforts searching it are small. And last I already have the losing captures generated while generating all captures. When they produce a cutoff I save the generation of all the quiet moves. In average it pays out for me.
Up to this point most engines behave similar (except where they order the losing captures). In 90% of the positions where you get a cutoff, you have got the cutoff with one of the moves above. So when you get here chances are none of the remaining moves will get you a cutoff, nevertheless you can't rely on that. You have to search them and sometimes they surprise you.

So you look for a mechanism to order all the remaining quiet (boring) moves or you decide to search them randomly the way they were generated. Here a lot is tried in different engines but is a bit of black art.

Commonly used is
  • Generate the moves in a meaningful order (like casteling moves first, than knight moves, bishop moves, rook moves, queen moves, king moves, pawn moves) and maybe also moves that advance before moves that retreat and just search them in that order
  • Use a table for every piece and square (called a piece - square - table) to mark good and bad squares for each piece (like knights get a bad score at the edge and a good score in the center). Search moves first where pieces go from bad squares to good squares. This sounds logic and really helps to order the moves in positions you expect to see on a chess board. Unfortunately in a search tree most of the positions are very strange resulting from a strange sequence of moves and applying a common sense move order must not necessarily help (some state it does, other say it does not)
  • Use a technique called history heuristics. Every time in search a move produces a cut off increment a counter for that move (moves searched with higher depth increase the counter more than moves from lower depth searches). Order then your moves according to the value of their counter. This certainly helped when hardware was slow and engines did not search so deeply because the positions in the tree had still some properties in common. Today engines search very deeply and positions after 8 moves of white and a 8 moves of black don't have much in common anymore. So using information from one position in another totally different position must not necessarily be a good thing to do.   
History heuristic is still very commonly used and programmers state it makes their engine stronger. To come up with such a conclusion you must run a lot of games (several 100 at least) against other engines with and without that feature used. Often those games use very short time controls so the testing does not take weeks. Short time controls lead to shallower searches and here history heuristic might help (as it did on slow hardware). So maybe it is still around because the testing framework (with short time controls) of the engine programmers favors it. I tried it at longer time controls and it did not help my engine so I don't use it.

I recently tried the piece square approach. To generate the tables I run longer searches against a lot of positions (more than 1000) and recorded which moves where generated how often, which produced a cut off, which did not and what was the effort required to search them. I also collected information about the pieces that were attacked after that move (if the king was attacked it was a checking move) and about the pieces that were defended by that move. So I generated a database with move heuristics.

The idea was to use the data in that database to generate a rule set or tables to help in the decision process of what move should be tried next.

The data allowed to say something like

A white queen that moves to e7 and attacks a black knight produces a cutoff in 10% of the cases and requires in average 500 nodes to be searched.
A white rook that moves to b5 and gives check produces a cutoff in 90% of the cases and requires in average 5000 nodes to be searched.

So if you encounter a move list that contains only those two moves, the queen move should be search first. (queen move first gives you 5000 nodes in total, rook move first gives you 5050 nodes in total).
but usually the moves lists are longer than 2 moves and it is really difficult to determine a least cost order for the moves even if you have all the data available.

I spent a lot of time with it and I did not find a schema that finally made the engine stronger. It solved some test positions faster but in real play I did not notice a difference.

So for the moment I give up on that idea and go back to a simple ordering schema for the remaining moves. This is maybe not better but as long as it is not worse it helps because it is definitely faster than anything else.