Blocked position

[George Lyapko]

Since some time LGPGNVER has a possibility to detect blocked positions. Many people told me that it is not necessary feature because such positions will never be reached in games between programs. But finally here is an real example, where LGPGNVER helped to award a draw:

[Event "Computer chess game"]
[Site "LYAPKO"]
[Date "2004.12.15"]
[Round "2"]
[White "Leila_053h"]
[Black "Quark v2.35Paderborn"]
[Result "0-1"]
[TimeControl "1800"]

1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. f3 O-O 6. Be3 Nc6 7. Nge2 a6 8.
Nc1 e5 9. d5 Nd4 10. N1e2 Nxe2 11. Bxe2 Nh5 12. Qd2 Rb8 13. O-O-O f5 14.
Kb1 Nf4 15. Bf1 b6 16. g3 Nh5 17. Be2 Nf6 18. Bg5 Qe8 19. Bd3 fxe4 20. Nxe4
Nxe4 21. Bxe4 Bf5 22. Qe2 Bxe4+ 23. fxe4 Qf7 24. Rhf1 Qd7 25. g4 Rxf1 26.
Rxf1 Rf8 27. h3 Rxf1+ 28. Qxf1 c5 29. Be3 b5 30. Kc2 h5 31. gxh5 gxh5 32.
Kc3 Qd8 33. b3 bxc4 34. Kxc4 Qa5 35. Qg2 Qb4+ 36. Kd3 Qe1 37. Qg1 Qxg1 38.
Bxg1 Bh6 39. a4 Kf7 40. Be3 Bxe3 41. Kxe3 Ke7 42. a5 Kf6 43. h4 Ke7 44. Ke2
Kd7 45. Ke3 Ke7 46. Ke2 Kd7 47. Kf3 Kd8 48. Kf2 Kd7 49. Kf3 Kd8 50. Kg2 Kd7
51. Kf2 Kd8 52. Ke1 Kc8 53. Kd1 Kc7 54. Ke1 Kc8 55. Kf1 Kd8 56. Kf2 Kd7 57.
Ke2 Kc7 58. Kd2 Kd8 59. Kd3 Kd7 60. Kc3 Kc7 61. Kd2 Kd8 62. Kc1 Kc7 63. Kd1
Kd7 64. Ke2 Kc7 65. Kd3 Kd7 66. Kc2 Kd8 67. Kc3 Kc7 68. Kb2 Kd7 69. Kc2 Kd8
70. Kc1 Kc7 71. Kd1 Kd7 72. b4 cxb4 73. Kc1 Kd8 74. Kb2 Kd7 75. Kb3 Ke7 76.
Kxb4 Kd7 77. Kc3 Ke7 78. Kd3 Kf6 79. Ke3 Kf7 80. Ke2 Ke7 81. Ke3 Kf7 82.
Kd3 Kf6 83. Ke2 Ke7 84. Ke1 Kd7 85. Kd1 Kd8 86. Kc2 Ke7 87. Kb3 Kd8 88. Kb4
Kd7 89. Kc4 Kd8 90. Kb3 Kd7 91. Kc2 Ke7 92. Kc3 Kd7 93. Kd2 Kd8 94. Kd3 Ke8
{Black wins on time} 0-1

Draw awarded according to LGPGNVER: the position is blocked and nobody can win.

[Tim Foden]

Hi George,

I'm interested in the logic you used to identify this as a blocked position.

If I were to do it I would:

1. Note that this is a position with only kings and pawns.
2. Note that none of the pawns can move, with or without capturing.
3. Note that neither of the kings can get to a position where they can take any pawns.

Is this the kind of thing you do?

Do you consider any positions with other types of pieces on the board?

Cheers, Tim.

[George Lyapko]

The algorythm is nearly as you've described.
The difference is only that each side could have also bishops (there are blocked positions with other peaces but it is much harder to program them).

The rules of blocked position(considered by LGPGNVER) are following:
a)none of pawns can move because of another pawn;
b)none of other peaces can capture pawns of opposite colour in any sequence of moves.

Best regards,
George

[Peter Fendrich]

Be careful.
This is not a blocked position!
[diag]8/8/p1p4k/P1Pp2p1/3P2P1/7K/8/8 w - -[/diag]
8/8/p1p4k/P1Pp2p1/3P2P1/7K/8/8 w - -

Guess why...

/Peter

[Laurens Winkelhagen]

Be careful.
This is not a blocked position!
[diag]8/8/p1p4k/P1Pp2p1/3P2P1/7K/8/8 w - -[/diag]
8/8/p1p4k/P1Pp2p1/3P2P1/7K/8/8 w - -

Guess why...

/Peter

Hi Peter,

my guess was: a possible e.p. capture on d6. But in that case you have forgotten to specify the e.p. square in your FEN-string. Please tell me this is true, else I had to doubt my chess-skills even more!!

Regards, Laurens.

[Jim Ablett]

White is playing down, black is playing up?

Jim

[Peter Fendrich]

[quote="Laurens Winkelhagen
Hi Peter,

my guess was: a possible e.p. capture on d6. But in that case you have forgotten to specify the e.p. square in your FEN-string. Please tell me this is true, else I had to doubt my chess-skills even more!!

Regards, Laurens.[/quote]

Right - you can collect the first prize next time you're here in Sweden!
Of course I had to exclude the e.p for obvious reasons but if you are stating rules for a blocking position, that George Lyapko did, it's easy to forget the e.p.
/Peter

[George Lyapko]

You know, this is exactly what I did...

Game 1: ---

1. b4 b5 2. Nc3 Nc6 3. Nd5 Nd4 4. Nxc7+ Qxc7 5. e3 Nxc2+ 6. Qxc2 Ba6 7.
Ba3 Qxc2 8. Rc1 Rc8 9. Bd3 Qxd3 10. Rxc8+ Bxc8 11. Ne2 Qxa3 12. O-O Qxa2
13. Ra1 Ba6 14. Rxa2 e5 15. f3 e4 16. f4 d5 17. g4 Bd6 18. Rxa6 f5 19. g5
g6 20. h4 Nf6 21. Nd4 O-O 22. Rxa7 Bc5 23. Ne6 Bxa7 24. Nxf8 Nd7 25. Nxd7
Kf7 26. h5 Bc5 27. Nxc5 Ke7 28. Ne6 Kxe6 29. hxg6 hxg6 30. d4 *

Result :*
Warning level :4
Final position: 8/8/4k1p1/1p1p1pP1/1P1PpP2/4P3/8/6K1 b - d3 0 31
Analyze result:1/2-1/2 {blocked position}

So you must wait for a new release of LGPGNVER(it's very easy to fix)

[Peter Fendrich]

White is playing down, black is playing up?

Jim

A good try!
But I'm not sure if such position can arise?
/Peter

[Anonymous]

George, would you like to share how you exactly are detecting, that there is now way for either king to find a way into foreign territory? Would it be fast enough, to be used in eval? My idea: All pawns must be blocked. Create attack maps of all pawns for both sides. Pawn positions belong to both attack maps. Now do an area filling algorithm on the board, starting from one king, and using the opponent attack map as border.

Would your program detect, when for example one doubled pawn hs one move left until totally blocked, but it won't make a difference in principle and the pos is draw (say white pawns *b2* b4 e4 g4, black pawns b5, e5, g5).

Even more basic question: How to efficiently find out, that the king is "behind" all his pawns?

Cheers,
Dieter


Cheers,
Dieter

[Tim Foden]

George, would you like to share how you exactly are detecting, that there is now way for either king to find a way into foreign territory? Would it be fast enough, to be used in eval? My idea: All pawns must be blocked. Create attack maps of all pawns for both sides. Pawn positions belong to both attack maps. Now do an area filling algorithm on the board, starting from one king, and using the opponent attack map as border.

I have a similar algorithm that I was already experimenting with some time ago, but for different reasons. I did a flood fill from each of the kings, to find how many steps they would take to attack pawns of the other side. With this in place it is possible to know that neither king can attack any pawns.

Even more basic question: How to efficiently find out, that the king is "behind" all his pawns?

You don't need to know this, just that the king can't capture any pawns.

Cheers,
Tim[/quote]

[George Lyapko]

George, would you like to share how you exactly are detecting, that there is now way for either king to find a way into foreign territory? Would it be fast enough, to be used in eval? My idea: All pawns must be blocked. Create attack maps of all pawns for both sides. Pawn positions belong to both attack maps. Now do an area filling algorithm on the board, starting from one king, and using the opponent attack map as border.

Would your program detect, when for example one doubled pawn hs one move left until totally blocked, but it won't make a difference in principle and the pos is draw (say white pawns *b2* b4 e4 g4, black pawns b5, e5, g5).

Even more basic question: How to efficiently find out, that the king is "behind" all his pawns?

My algorythm is not the fastest one(it is no problem for LGPGNVER to think longer on final position of a game). I don't think it could be used in eval as it is, but here it is in short:

There is an array piece_pos[0..31] for position of pieces.
0-white king
1..15-white pieces(pawns can be only 8..15)
16-black king
17..31-black pieces(pawns can be only 24..31)

I use an array squares[0..99] to represent a board for blocked position detection.
There are three possible values (0=empty, 1=not accessible, 2=enemy pawn).

The rest is done 2 times(for both kings).
Array is filled with values from position of pieces(example is for white king):

Code: Select all

FirstFill;(*fills the borders with 1*);
for i:=8 to 15 do if piece_pos[i]<>M1 (*no piece*) then begin
   j:=piece_pos[i];
   if board[j]=PAWN then squares[i]:=1;
end;
for i:=24 to 31 do if piece_pos[i]<>M1 then begin
   j:=piece_pos[i];
   if board[j]=B_PAWN then begin
      if squares[i]<>1 then squares[i]:=2;
      squares[i+9]:=1;
      squares[i+11]:=1;
   end;
end;


then I use recursive function to check if a king could capture enemy pawns:

Code: Select all

const K_dist:array [0..7] of integer=(-11,-9,9,11,-10,-1,1,10);

function Reachable(source:integer):boolean;
var i,j:integer;
begin
   Reachable:=False;
   if squares[source]=2 then begin Reachable:=True; Exit; end;
   if squares[source]=1 then Exit;
   squares[source]:=1;
   for i:=0 to 7 do begin
      if Reachable(source+K_dist[i]) then begin
         Reachable:=True;Exit;
      end;
   end;
end;

BlockedPosition:=False;
for j:=0 to 7 do begin
   if Reachable(piece_pos[0]+K_dist[j],True) then Exit;
end;
...
BlockedPosition:=True;
...


that's all.

Best regards,
George