Saturday, November 30, 2013

Drawish pawn structures

Many moves later the games ends 1/2 : 1/2
One of the things I had on my todo list was related to pawn structures. I thought that some pawn structures have a more drawish character than others.

Especially blocked or symmetrical positions tend to be more drawish than open ones. 

My idea was to build up a statistics over a lot of games and calculate the probability that a game ends as draw depending on the pawn structure that's on the board. If my engine later encounters a pawn structure with a high probability for a draw the score is pulled towards 0.

So if my engine is ahead it tries to avoid such structures (e.g. not lock its pawns) and if behind it tries to play towards them.

The first step was to collect a lot of positions from games and categorize them depending on the game outcome of the game they were taken from. I assembled a collection of games that lasted at least 60 moves as a base.
  • I saved the position at move number 50 into either a WIN or DRAW file.
  • I then processed the positions from the WIN and DRAW files. 
  • In all positions I only considered the specific pawn structure for the files B - G
Index: 111101 111011 = 3.963
  • For a white pawn at the file I recorded a 1 in the lower 6 bits and for a black pawn a 1 in the higher 6 bits. This number served as a index where I stored the number of games that ended as DRAW or as WIN when this structure was present.
Example: In my statistics the above pawn structure was found in 2.286 games. 857 were drawn and 1.429 were won. This resulted in a draw probability of 37% pct. The overall draw probability over all games and structures was 36%. So this pawn structure is a tiny bit more drawish than the average.

I did this for every possible combination. If there is no white and black pawn present on the B - G files the structure is very drawish (62%), symmetrical combinations had values of about 45%.

Finally I modified my evaluation function to scale the score up or down depending on the pawn structure. It used a lookup table where it stored all the 4096 possible scaling values.

Unfortunately it did not work. The tests showed the modified engine as equal or even slightly weaker then the original engine. I used also different indexing schemes like only counting files with blocked pawns etc... Nothing worked. So the patch was removed from the code again.

It was worth a try.

Hopefully I have more luck with the next idea.


Sunday, November 10, 2013

Is it a draw ?

While working on my knowledge module for the king and two pawns vs. king and knight endgame I had to deal with a lot of questions like this.

Given the following position.

Black to move offers a DRAW. Should White accept it ?
White has two passed pawns including a rook pawn where the knight has often trouble with. He also controls the promotion square of the pawn.
But the pawns have still a long way to go and the black king and knight are also placed not so bad.

Black is convinced he can stop the pawns and offers a Draw.

Should White accept it ?

PS: Don't cheat be looking it up in a table base like most of the engines do ...

Friday, November 1, 2013

Knight vs two pawns endgame

In a recent chess tournament where the best Italian engines played against an international selection my iCE engine managed to get into the quarter finals. It was paired against Booot, a very strong chess program rated more than 200 ELO higher than iCE in the rating lists.

It was a 6 round match and iCE scored 2 out of 5 points in the first 5 games. It needed a win in the last round playing White to get into the tie break. It looked promising but at the end it only got a Draw and was out.

In this last game iCE exchanged into an endgame where it plays with two pawns against a lonely knight. iCE wasn't able to see that its pawns won't be able to queen until it was to late.

iCE played 1. Kxf2 Ne4+ 2. Ke3 Nxd6 with a very good score

It had to search 29 half moves (plies) deep to understand the position.

info depth 29 seldepth 53 nodes 1388226533 pv g1f2 f6e4 f2e3 e4d6 e3d4 d6b7 d4e5 h7g6 e5e6 g6g5 e6d7 b7a5 score cp 0

Most humans will see the draw without problems. One pawn is stopped by the knight and the other be the king. So not realizing this is a clear defect.

So I decided to put some effort in coding a few rules for a KPPKN endgame just for fun.

In a KPPKN endgame there are 855.071.008 legal positions and 439.033.368 can be won (usually but not always for the side with the pawns of course). This means almost half of the possible positions are draws. Nevertheless it is really difficult to find some patterns that spot the draws.

I was able to find rules that detect 30.371.460 draws, so less than 10%. This is not to impressive, luckily combined with search it already helps a lot.

The new iCE performs much better in the above position

position fen 8/7k/1P1R1n2/8/6P1/8/5r2/6K1 w - - 2 68
go depth 10
info depth 1 seldepth 0 time 0 nodes 23 pv g1f2 f6g4 f2f3 nps 22999 score cp 1086 

info depth 2 seldepth 3 time 16 nodes 142 pv g1f2 f6e4 f2e3 e4d6 nps 8874 score cp 521 
info depth 3 seldepth 4 time 0 nodes 200 pv g1f2 f6e4 f2e3 e4d6 nps 199999 score cp 521
info depth 4 seldepth 5 time 0 nodes 181 pv g1f2 f6e4 f2e3 e4d6 nps 180999 score cp 521
info depth 5 seldepth 7 time 0 nodes 281 pv g1f2 f6e4 f2e3 e4d6 e3d4 nps 280999 score cp 567 
info depth 6 seldepth 11 time 15 nodes 12448 pv d6e6 f6g4 b6b7 f2b2 e6e7 h7g6 g1f1 nps 829866 score cp 251
info depth 7 seldepth 11 time 15 nodes 17080 pv g4g5 f6e4 g5g6 h7g7 d6d7 g7g6 b6b7 f2b2 nps 1138666 score cp 218 
info depth 8 seldepth 14 time 0 nodes 12371 pv g4g5 f6e4 d6h6 h7g7 h6h2 f2f7 h2b2 f7b7 nps 12370999 score cp 153 
info depth 9 seldepth 16 time 16 nodes 26088 pv g4g5 f6g4 b6b7 f2b2 g5g6 h7g7 d6d7 g7g6 nps 1630499 score cp 53 
info depth 10 seldepth 18 time 31 nodes 55953 pv g4g5 f6e4 d6e6 f2b2 g5g6 h7g7 e6e4 nps 1804935 score cp 0 
bestmove g4g5 ponder f6e4
info time 172 nodes 124767 nps 725389

Already at depth 6 iCE realizes that Kxf2 will only draw and at depth 10 it realizes that the alternatives are no better.