Chess move list ordering

Recent performance profiling of iCE showed that iCE spends a significant time just sorting the moves.

In iCE moves get assigned an order value that expresses their likelihood of being best. Depending on the kind of move this value might come from the expected material win (Static Exchange Evaluation), from its attacking value (victim vs attacker) or by the history of the move in previous searches.

After a value has been assigned to the moves in the current move generation stage they have to be ordered in descending order.

An alternative to sorting would be to just always pick the next best move from the list each time a move is accessed but this is a bit more messy. I like the cleanness of processing an ordered list.

As the number of moves in each stage is usually small insertion sort is used instead of the typical used quicksort. The algorithm for insertion sort is rather simple and I have implemented it in the TMovelist class of iCE. C++ already provides a sort algorithm with std::sort but this was significantly slower than my implementation.

To speed up the ordering I thought about special sort implementations for short lists. So first I performed an analyses what move lists usually are processed. Statistics shows that 85% of the lists have 8 or less elements. 

Move list length statistics. The last column stands here for 9 and more moves

For a fixed and small number of elements exists a technique called sorting net to sort the elements by just by a fixed sequence of element compares and swaps.

To sort a list of 4 elements the following sorting network can be used

SWAP(0, 1); SWAP(2, 3); SWAP(0, 2); SWAP(1, 3); SWAP(1, 2);

SWAP(a, b) compares a with b and swaps them if they are out of order. For more elements the sequence of swaps gets longer, so for 10 elements already 32 SWAP operations are necessary.

As the statistics looked promising I implemented the sorting networks for lists up to 12 elements and used my insertion sort algorithm for the remaining longer lists. Overall I got a small overall speedup, less than I hoped for. But profiling showed that although only 15% of the lists are longer than 8 elements, sorting them takes most of the time.

I kept the change anyway as I is not really complex and actually I like the concept.

Use your time wisely

A very old part of iCE is the time management module. As soon as I had it robust enough so that my engine does not lose on time anymore I left it alone.

Its mechanism is actually pretty simple. In the usual time control with x moves in y minutes it just divides the remaining time by the number of remaining moves to come up with a desired time for a move. It allows stretch to allow the engine to finish an iteration.

Also if there is still some time left but probably not enough to finish at least one move of a new iteration it does not start it.

This mechanism dates back to iCE 0.3 and hasn't been changed since. Recently I revisited the code and tried to improve it. Surprisingly it turned out to be very difficult to come up with something better than the simple mechanism above. Also it does not make sense to test changes with my usual set of very fast games. To play enough games to get some statistical confidence here takes much much longer.

One idea that failed was to allocate more time for early moves. This is a very common scheme in other engines but it did not help in iCE. Maybe I haven't tested it enough but none of my versions passed the regression test.

A small success was a little change to the time allocation for the last moves before the next time control. Nothing to write home about. The improvement was about 6 ELO with an error margin of 8. So there is even a chance for a small regression but I keep the change as I like the code and think it makes more sense than the previous allocation.

iCE 3 UCI Options

While I was adding MultiPV to iCE I spent some time reworking the whole UCI options in iCE. For version 3 I tried to improve the naming of the options and also changed some of the functionality.

Here is an overview of the options for the next version

Clear Hash: As the name suggests clears the main hash and all other caches incl. pawn, evaluation and material cache.

Ponder: Tells iCE that the game is run in ponder mode. This has a slight influences on the time iCE allocates for a move.

Hash: The size of the main hash in MB. The whole memory footprint of iCE is bigger as it allocates a fixed amount of memory for other caches (e.g. eval or pawn)

OwnBook: Tells iCE that it should use an external book in "ibf" format. This is a special proprietary format. Books of different sizes are available on my homepage. If OwnBook is set to true Book File has to point to the book.

Fallback to Internal Book: If iCE gets no external book (OwnBook = false) or the Book File option does not point to a valid book iCE can fallback to a small internal book that contains some common main lines. It is just part of the chess knowledge of iCE but some testers complained about this behavior. So setting this option to false will remove all opening knowledge in iCE. This is however not recommended as iCE runs then in a mode it was not designed for and tested in.

Output Search Depth Info: iCE will output search progress in UCI format (e.g. info depth 2 seldepth 2 score cp 107 nodes 42 nps 41999 time 0 multipv 1 pv e2e4 g7g6 hashfull 0 tbhits 0)

Output Total Times and Nodes: iCE will summarize the previous search statistics at the end of each search (e.g. info time 93 nodes 8796 nps 94580)

Output Current Move Info: iCE will output the move it currently calculates. This causes a lot of traffic between engine and GUI and messes up the console mode. But some user like to see that info in a GUI.

MultiPV: The number of PV lines iCE will output. Makes only sense for analyzing games or positions. It should not be used in game play as it makes the engine much weaker if set to a value larger than 1.

CommandFile: Setting this option will cause iCE to read a series of commands from an external file and execute them. This is more an internal option that I use for tuning and most likely not relevant for other users.

Console Mode: If set to true iCE will switch the output format of search depth info into something more readable if iCE runs in console mode. If connected to a GUI it should be set to false as the GUI otherwise will probably not understand the output of iCE anymore

Console mode = false:
go depth 8
info depth 1 seldepth 0 score cp 116 nodes 20 nps 20000 time 0 multipv 1 pv e2e4
 hashfull 0 tbhits 0
info depth 2 seldepth 2 score cp 107 nodes 42 nps 41999 time 0 multipv 1 pv e2e4
 g7g6 hashfull 0 tbhits 0
info depth 3 seldepth 3 score cp 73 nodes 133 nps 133000 time 0 multipv 1 pv e2e
4 d7d5 d1h5 hashfull 0 tbhits 0

Console mode = true:
setoption name console mode value true
go depth 8
 1/ 0 0:00   1.16  1. e4  (20)
 2/ 2 0:00   1.07  1. e4 g6  (42)
 3/ 3 0:00   0.73  1. e4 d5 2. Qh5  (133)
 4/ 4 0:00   0.31  1. e3 d5 2. d4 e6  (348)
 5/ 6 0:00   0.40  1. e3 e5 2. d4 Qf6 3. Nc3  (768)
 6/ 7 0:00   0.31  1. e3 d5 2. d4 e6 3. Bd2 Bd7  (1.760)

So when version 3 is released (later this year probably) then the uci options of iCE are hopefully more meaning and useful.

City Championship - Lipsiade 2015

My two boys, who use my little Chess GUI to do some tactics training participated here in the local city chess championship for kids called Lipsiade. Julian (7), my younger son, played in the U8 league, and Jonas (9) played in the U9.

Both did fairly well. Julian finished 2nd place with 4.5/5 pts and Jonas finished 4th place with 3.5/5. So it seems the training pays off a bit.

Julian Petzke

 

 

Jonas Petzke

  
Boys, I'm proud of you.

Nullmove Blindness

White moves and Mates in 3 (1. Rh5 h6 2. h4 Kh2 3. Rh3#)

From time to time I challenge iCE with some Mate in X problems. Usually iCE has no problems solving them, at least if the Mate is not to far away. But lately I encountered a position (above) where iCE surprisingly struggled.

It is a Mate in 3 but iCE solves it as a Mate in 5.

iCE 3.0 v386 x64/popcnt [2015.6.1]
position fen 8/7p/8/8/3p4/3P2RR/6PP/5K1k w - - 0 1
analyze depth 20
Analysing 14 moves up to depth 20

g3g7  mate 5    1. Rg7 h6 2. Rg8 h5 3. Rg7 h4 4. g4 hg 5. hg
g3g5  mate 5    1. Rg5 h6 2. Rg8
g3g8  mate 5    1. Rg8 h6 2. Rg6 h5 3. Rg7
h3h5  mate 5    1. Rh5 h6 2. Rh3 h5 3. Rg7 h4 4. g4 hg 5. hg
..

Mate is Mate in in game play it will not really matter if it takes 2 moves longer. But it is kind of embarrassing for a 2900 ELO engine to not be able to solve a Mate in 3.

I looked into the problem and it turned out to be a combination of 2 things.

1. iCE is doing a Mate distance pruning in the root node. This means if it finds a Mate in 5 it will stop search at ply 10 because searching more plies should not find shorter Mates. This was true for early versions of iCE but as it is now having such an aggressive reduction and pruning scheme more plies will reveal shorter mates (when formerly reduced or pruned moves turn out to be good).
2. The null move reduction was to high if a forced Mate was found, pruning away possible better candidates.

So I turned off Mate distance pruning in the root position and also reduced the null move reduction to not exceed a certain threshold. This seems to fix the problem at least for this position.

iCE 3.0 v392 x64/popcnt [2015.6.4]
position fen 8/7p/8/8/3p4/3P2RR/6PP/5K1k w - - 0 1
analyze depth 18
Analysing 14 moves up to depth 18
 
h3h5  mate 3    1. Rh5 h6 2. h4 Kh2 3. Rh3
f1f2  mate 4    1. Kf2 h6 2. Rg7 h5 3. Rc7 h4 4. Rc1
..

A final regression test with 16000 games showed that the patched version is very likely not weaker than the previous one. It scored (W/L/D) 4300-4181-7515.

Rank Name                      Elo    +    - games score oppo. draws
   1 iCE 3.0 v392 x64/popcnt     1    4    4 16000   50%    -1   47%
   2 iCE 3.0 v386 x64/popcnt    -1    4    4 16000   50%     1   47%

Patch committed.

Chess is 99% tactics

Tactics for School Chess Volume 6 (Problem #8 - Mate in 2)

I'm currently in the process of building a database of not to hard chess tactics for my kids to get some practice. After searching the net for a while I followed the recommendation to use the collection of Paul Gaffron of about 3000 problems especially designed for younger kids to improved their tactical vision.

They are only available as hardcover so I ordered them in a local chess store. In total they consist of 12 volumes of increasing difficulty with about 250 problems each. I decided to start with volume 4 as this seems to fit the current strength of my boys best.

In my new GUI there is a tactics training module that reads in a set of problems in PGN format, presents them on the board, checks the user input for correctness, sums up and saves the scores and even has the option to repeat the problems one initially failed. To use it all I had to do was transferring the problems from the books into PGN format.

I came up with the following approach.

1. Setup the position from the book in my chess GUI (takes about 30s in average per position)
2. Copy the FEN of that position in a FEN collection file 
3. If all FENs are collected run a chess engine over the positions and use their best move (or move sequence) suggestion as solution
4. Store each problem with its solution in a PGN file

Input: 

3r4/p4rPk/1b1q1P2/2p1p3/8/5NR1/5P1P/6RK w - - 0 1

Output:

[Event "Tactics for School Chess Volume VI"]
[Site "Mate in 2"]
[Date "2015.05.04"]
[Round "8"]
[White "Winner"]
[Black "Loser"]
[Result "1-0"]
[Termination "normal"]
[FEN "3r4/p4rPk/1b1q1P2/2p1p3/8/5NR1/5P1P/6RK w - - 0 1"]
[PlyCount "3"]
[Setup "1"]

 1. g8=Q+ ( 1. Rh3+ Kg8 2. Rh8#) 1... Rxg8 2. Rh3# 1-0

In general that works really great but I encountered some unexpected challenges

• The problems are from a pre-computer area so their author obviously wasn't able to check them with an engine. This means in some problems the author misses a possible refutation for the defending side. Some problems announced as Mate in 2 are in fact Mate in 3, some problems don't have a solution at all or the given master solution is wrong.
• Some problems have more than 1 correct solution. In some of those cases the author gives 2 solutions but I encountered problems with up to 11 correct choices for the first move.
• In some problems the author looks for a best move to maybe win a piece but the engine might see another tactic leading to mate. So instead of going for the piece the engine selects another move leading to a distant forced mate. 

Intended solution Bb6 (winning the bishop) fails to Bh3+

Intended solution Qh6 (with idea Qg7#) fails to Re1#

11 moves lead to Mate in 2 (incl. all white king moves)

Especially the problems with multiple solutions are frustrating for kids if they find a correct move that is not in the list of correct solutions. They are really not relaxed about this. I'm talking from experience.

So I modified my tactics builder to run Stockfish in MultiPV mode with 12 lines. It will then include all lines with an evaluation equal to the best evaluation as alternative solutions. I originally inteded to use iCE as solving engine but iCE has no MultiPV mode yet. So I can't use iCE.

But overall I would say only 5% of the problems are somehow problematic. Overall its a good training set. By now I have a nice couple from the early volumes digitized. I hope it will help my boys a bit.

Chess Tactics for Kids

My two sons love chess and to let them have a chance in some kids tournaments I encourage them to do some chess problems from time to time. I started with the Manual of Chess Combinations 1a by Sergey Ivashchenko which is really a nice collection for kids, but unfortunately the problems get harder fast. So volume 1a is doable for a kid of about 900 - 1000 ELO (DWZ in Germany) but volume 1b is already very tough (three and four move combinations). 

So I'm looking for alternatives. There are a lot of problem sets in the internet but most of them are not in the range I'm looking for. Polgars 5334 problems start with 300+ Mates in 1. Those were nice and solved in No Time, but after that already tricky Mate in 2 problems start.

Polgar's Problem #325, Mate in 2

They are mostly not about recognizing common patterns. They are about calculation and board control. If a kid enters a endgame with a king and a queen it should know how to mate at all and what a stalemate is and it should not start to look for possible mates in the middle of the board. 

So those problems surely teach nice skills but are not actually what I'm looking for.

One often recommended problem set especially for kids is one that a local coach (Paul Gaffron) assembled over the years. It is a collection called Tactics for School Chess. I started to look a volume 4 out of 12 and here it seems the difficulty is about right for my kids (especially for training of fast pattern recognition). 

Now I'm faced with a different challenge. I have those books as hard cover only. To load them into my training GUI I need them in PGN format.

I have an idea how to do it at least semi-automated. Unfortunately the first step, namely turning a printed diagram into a FEN that the computer understands, is a manual step. But if I have a collection of FEN I hope I can enable my computer to do the rest of the work. 

I'll give it a try.