Fruit question: pins

[hgm]

I was making a quick hack of Fruit 2.1 to play something other than orthodox Chess, but I stumbled on a piece of code that I don't understand. In move_check.cpp there is a routine find_pins, which says:

Code: Select all

   for (ptr = &board->piece[me][1]; (from=*ptr) != SquareNone; ptr++) { // HACK: no king

      piece = board->square[from];

      delta = king - from;
      ASSERT(delta_is_ok(delta));

      if (PSEUDO_ATTACK(piece,delta)) {

         ASSERT(PIECE_IS_SLIDER(piece));

         inc = DELTA_INC_LINE(delta);
         ASSERT(inc!=IncNone);

         ASSERT(SLIDER_ATTACK(piece,inc));

         sq = from;
         do sq += inc; while ((capture=board->square[sq]) == Empty);

         ASSERT(sq!=king);

         if (COLOUR_IS(capture,me)) {
            pin = sq;
            do sq += inc; while (board->square[sq] == Empty);
            if (sq == king) *list++ = pin;
         }
      }
   }

What I don't understand is how it can guarantee that it only finds sliders. The for-loop runs through the piece list (board->piece[me]), and then it selects on PSEUDO_ATTACK(). The latter is defined in attack.h:

Code: Select all

#define DELTA_INC_LINE(delta)             (DeltaIncLine[DeltaOffset+(delta)])
#define DELTA_INC_ALL(delta)              (DeltaIncAll[DeltaOffset+(delta)])
#define DELTA_MASK(delta)                 (DeltaMask[DeltaOffset+(delta)])

#define INC_MASK(inc)                     (IncMask[IncOffset+(inc)])

#define PIECE_ATTACK(board,piece,from,to) (PSEUDO_ATTACK((piece),(to)-(from))&&line_is_empty((board),(from),(to)))
#define PSEUDO_ATTACK(piece,delta)        (((piece)&DELTA_MASK(delta))!=0)
#define SLIDER_ATTACK(piece,inc)          (((piece)&INC_MASK(inc))!=0)

and measures if the flag set in DeltaMask[] for this delta matches the piece move. But Knight jumps should match too, as the initialization of DeltaMask in attack_init (attack.cpp) also sets the KnightFlag for all Knight delta's:

Code: Select all

   // knight attacks

   for &#40;dir = 0; dir < 8; dir++) &#123;

      delta = KnightInc&#91;dir&#93;;
      ASSERT&#40;delta_is_ok&#40;delta&#41;);

      ASSERT&#40;DeltaIncAll&#91;DeltaOffset+delta&#93;==IncNone&#41;;
      DeltaIncAll&#91;DeltaOffset+delta&#93; = delta;
      DeltaMask&#91;DeltaOffset+delta&#93; |= KnightFlag;
   &#125;

From is_attacked() in the same file it is obvious that the piece list should also contain Knights:

Code: Select all

   // piece attack

   for (ptr = &board->piece[colour][0]; (from=*ptr) != SquareNone; ptr++) {

      piece = board->square[from];
      delta = to - from;

      if (PSEUDO_ATTACK(piece,delta)) {

         inc = DELTA_INC_ALL(delta);
         ASSERT(inc!=IncNone);

         sq = from;
         do {
            sq += inc;
            if (sq == to) return true;
         } while (board->square[sq] == Empty);
      }
   }

So how come the is_pinned() routine does not choke on the ASSERT(PIECE_IS_SLIDER(piece)) ???

[Michael Sherwin]

Just a guess: && line_is_empty((board)...

[hgm]

I don't see how:

Code: Select all

bool line_is_empty(const board_t * board, int from, int to) {

   int delta;
   int inc, sq;

   ASSERT(board!=NULL);
   ASSERT(SQUARE_IS_OK(from));
   ASSERT(SQUARE_IS_OK(to));

   delta = to - from;
   ASSERT(delta_is_ok(delta));

   inc = DELTA_INC_ALL(delta);
   ASSERT(inc!=IncNone);

   sq = from;
   do {
      sq += inc;
      if (sq == to) return true;
   } while (board->square[sq] == Empty);

   return false; // blocker
}

For a Knight delta the first iteration of the do-loop should find sq==to and return true immediately. Also the code from is_attacked(), which is supposed to also find Knight and King attacks, uses exactly the same PSEUDO_ATTACK() filtering.

I would be inclined to write if(PSEUDO_ATTACK(piece & QueenFlags, delta)), to only consider the Rook and Bishop moves of the piece. This would prevent Knights from causing pseudo-attacks. (And incidentally also would make the code work for Knight + slider compounds.)

[Karlo Bala]

I was making a quick hack of Fruit 2.1 to play something other than orthodox Chess, but I stumbled on a piece of code that I don't understand. In move_check.cpp there is a routine find_pins, which says:

Code: Select all

   for (ptr = &board->piece[me][1]; (from=*ptr) != SquareNone; ptr++) { // HACK: no king

      piece = board->square[from];

      delta = king - from;
      ASSERT(delta_is_ok(delta));

      if (PSEUDO_ATTACK(piece,delta)) {

         ASSERT(PIECE_IS_SLIDER(piece));

         inc = DELTA_INC_LINE(delta);
         ASSERT(inc!=IncNone);

         ASSERT(SLIDER_ATTACK(piece,inc));

         sq = from;
         do sq += inc; while ((capture=board->square[sq]) == Empty);

         ASSERT(sq!=king);

         if (COLOUR_IS(capture,me)) {
            pin = sq;
            do sq += inc; while (board->square[sq] == Empty);
            if (sq == king) *list++ = pin;
         }
      }
   }

What I don't understand is how it can guarantee that it only finds sliders. The for-loop runs through the piece list (board->piece[me]), and then it selects on PSEUDO_ATTACK(). The latter is defined in attack.h:

Code: Select all

#define DELTA_INC_LINE(delta)             (DeltaIncLine[DeltaOffset+(delta)])
#define DELTA_INC_ALL(delta)              (DeltaIncAll[DeltaOffset+(delta)])
#define DELTA_MASK(delta)                 (DeltaMask[DeltaOffset+(delta)])

#define INC_MASK(inc)                     (IncMask[IncOffset+(inc)])

#define PIECE_ATTACK(board,piece,from,to) (PSEUDO_ATTACK((piece),(to)-(from))&&line_is_empty((board),(from),(to)))
#define PSEUDO_ATTACK(piece,delta)        (((piece)&DELTA_MASK(delta))!=0)
#define SLIDER_ATTACK(piece,inc)          (((piece)&INC_MASK(inc))!=0)

and measures if the flag set in DeltaMask[] for this delta matches the piece move. But Knight jumps should match too, as the initialization of DeltaMask in attack_init (attack.cpp) also sets the KnightFlag for all Knight delta's:

Code: Select all

   // knight attacks

   for &#40;dir = 0; dir < 8; dir++) &#123;

      delta = KnightInc&#91;dir&#93;;
      ASSERT&#40;delta_is_ok&#40;delta&#41;);

      ASSERT&#40;DeltaIncAll&#91;DeltaOffset+delta&#93;==IncNone&#41;;
      DeltaIncAll&#91;DeltaOffset+delta&#93; = delta;
      DeltaMask&#91;DeltaOffset+delta&#93; |= KnightFlag;
   &#125;

From is_attacked() in the same file it is obvious that the piece list should also contain Knights:

Code: Select all

   // piece attack

   for (ptr = &board->piece[colour][0]; (from=*ptr) != SquareNone; ptr++) {

      piece = board->square[from];
      delta = to - from;

      if (PSEUDO_ATTACK(piece,delta)) {

         inc = DELTA_INC_ALL(delta);
         ASSERT(inc!=IncNone);

         sq = from;
         do {
            sq += inc;
            if (sq == to) return true;
         } while (board->square[sq] == Empty);
      }
   }

So how come the is_pinned() routine does not choke on the ASSERT(PIECE_IS_SLIDER(piece)) ???

In DeltaMask[DeltaOffset+(delta)], masks for sliders are 32, 64 or 96. White knight on board is 17, and black knight is 18. So for knights (piece)&DELTA_MASK(delta) are 0.
Am I missing something?

[hgm]

In DeltaMask[DeltaOffset+(delta)], masks for sliders are 32, 64 or 96. White knight on board is 17, and black knight is 18. So for knights (piece)&DELTA_MASK(delta) are 0.
Am I missing something?

But the mask for Knights in DeltaMask[DeltaOffset+(delta)] is 16 (KnightFlag), as (part of) the initialization code of DeltaMask below shows:

Code: Select all

   // knight attacks

   for &#40;dir = 0; dir < 8; dir++) &#123;

      delta = KnightInc&#91;dir&#93;;
      ASSERT&#40;delta_is_ok&#40;delta&#41;);

      ASSERT&#40;DeltaIncAll&#91;DeltaOffset+delta&#93;==IncNone&#41;;
      DeltaIncAll&#91;DeltaOffset+delta&#93; = delta;
      DeltaMask&#91;DeltaOffset+delta&#93; |= KnightFlag;
   &#125;

So Knights should give a match, if positioned a Knight's jump away from the King.

I guess that what I am missing is that this is not a general routine to detect pins, but only used on positions where you are not in check.

[mar]

I guess that what I am missing is that this is not a general routine to detect pins, but only used on positions where you are not in check.

From what I understand from the source this is only used in qsearch to generate checks. So I guess find_pins is used to generate discovered checks?

I also don't understand how the code can only iterate sliders. Are you sure the assert doesn't trigger?

[Karlo Bala]

In DeltaMask[DeltaOffset+(delta)], masks for sliders are 32, 64 or 96. White knight on board is 17, and black knight is 18. So for knights (piece)&DELTA_MASK(delta) are 0.
Am I missing something?

But the mask for Knights in DeltaMask[DeltaOffset+(delta)] is 16 (KnightFlag), as (part of) the initialization code of DeltaMask below shows:

Code: Select all

   // knight attacks

   for &#40;dir = 0; dir < 8; dir++) &#123;

      delta = KnightInc&#91;dir&#93;;
      ASSERT&#40;delta_is_ok&#40;delta&#41;);

      ASSERT&#40;DeltaIncAll&#91;DeltaOffset+delta&#93;==IncNone&#41;;
      DeltaIncAll&#91;DeltaOffset+delta&#93; = delta;
      DeltaMask&#91;DeltaOffset+delta&#93; |= KnightFlag;
   &#125;

So Knights should give a match, if positioned a Knight's jump away from the King.

I guess that what I am missing is that this is not a general routine to detect pins, but only used on positions where you are not in check.

You are right. Pin detection is used for generating quiet checks, and only when side on move is not in check.

[hgm]

Now this mystery was solved, I made some progress: I have hacked Fruit to play Seirawan Chess! (Also know as S-Chess, hence the name 'S-Fruit'). The capability to use the BN and RN compound already has worked for some time, and I tested it against Fairy-Max win 'Chancellor Chess' and 'Archbishop Chess' (which replace the Queen in the opening position by RN and BN, respectively), and S-Fruit won in both cases 10-0, after I fixed a bug in SEE (which valued the new pieces at 0, making Fairy-Max occasionally win).

But now I have also implemented gating, so that pieces can start in hand. The following is the first S-Chess game it ever played:

Code: Select all

[Event "Computer Chess Game"]
[Site "hgm-xboard"]
[Date "2015.01.14"]
[Round "-"]
[White "S-Fruit 2.1 (UCI2WB)"]
[Black "Fairy-Max 4.8V"]
[Result "1-0"]
[TimeControl "40/60"]
[Variant "seirawan"]
[Annotator "1. +0.16   1... +0.27"]

1. Nc3 {+0.16/10} Nc6/H {+0.27/6 0.9} 2. d4 {+0.68/10 1.8} Nf6/E
{-0.05/6 2.2} 3. d5 {+1.14/9 1.8} Ne5 {-0.15/7 2.0} 4. f4 {+1.40/10 1.9}
Neg4 {-0.22/7 2.4} 5. e4 {+1.72/10 1.5} d6 {-0.21/6 1.4} 6. h3
{+2.38/9 1.6} Nh6 {-0.40/6 1.1} 7. g4 {+2.37/9 1.6} Nhxg4 {-1.08/7 1.2} 8.
hxg4 {+3.18/6 0.5} Bxg4 {-1.36/7 2.3} 9. Nf3/E {+3.33/8 1.5} Hd7
{-1.22/5 1.2} 10. e5 {+3.55/8 1.7} dxe5 {-1.71/8 1.4} 11. fxe5
{+4.45/8 1.1} Bxf3 {-1.84/8 2.2} 12. Exf3 {+4.69/8 1.2} Ng4 {-1.96/7 1.9}
13. Exf7 {+4.75/8 1.7} Nxe5 {-2.27/7 0.8} 14. Exd8+ {+4.95/7 1.4} Rxd8
{-2.36/7 2.4} 15. Bh3 {+5.10/8 1.4} Hb8 {-2.62/7 1.2} 16. Rf1/H
{+6.30/8 1.4} g6 {-2.91/8 1.6} 17. Qe2 {+7.29/9 1.2} c5 {-4.05/7 1.0} 18.
Qb5+ {+9.08/8 1.4} Rd7 {-4.91/7 0.9} 19. Bxd7+ {+11.41/8 1.1} Hxd7
{-6.67/10 3} 20. Qxb7 {+11.58/10 1.3} Hb6 {-7.03/9 3} 21. Qb8+
{+12.22/8 1.0} Hd8 {-7.73/8 2.0} 22. Nb5 {+14.91/9 3} Bh6 {-6.91/6 0.7} 23.
He4 {+1000.09/7 3} Nf3+ {-10.53/7 0.6} 24. Rxf3 {+1000.05/13 0.7} Bf4
{-16.89/7 0.7} 25. Rxf4 {+1000.04/32 0.8} Ef6 {-79.97/9 1.0} 26. Rxf6
{+1000.03/41 1.0} exf6 {-79.98/9 1.2} 27. Hd6+ {+1000.02/34 0.3} Kd7
{-79.99/10 0.7} 28. Qc8# {+1000.01/39 1.1}
{mate} 1-0

There still is some work to do, however:
*) Gating at the Rook square during castling is not implemented yet
*) When I compile Fruit with the DEBUG option, it still triggers an ASSERT: it complains that depth>=0 when in_check in ful_quiescence(). (Because it passes an earlier assert at the top of that routine, this must mean depth=0.)
I will have to study Fruit's search to understand what that means. It could be that this is caused by checking with freshly gated pieces not being classified as checks in an earlier stage. Just ignoring that (by compiling without the DEBUG option) doesn't seem very detrimental, as it decisively crushed Fairy-Max. This is to be expected if the only problem is that it doesn't consider checks with the gated pieces as checks, as these are not supposed to play any tactical role in normal games, and can only happen in silly lines where one side exposes his King in the opening.

[Sven]

Now this mystery was solved, I made some progress: I have hacked Fruit to play Seirawan Chess! (Also know as S-Chess, hence the name 'S-Fruit'). The capability to use the BN and RN compound already has worked for some time, and I tested it against Fairy-Max win 'Chancellor Chess' and 'Archbishop Chess' (which replace the Queen in the opening position by RN and BN, respectively), and S-Fruit won in both cases 10-0, after I fixed a bug in SEE (which valued the new pieces at 0, making Fairy-Max occasionally win).

But now I have also implemented gating, so that pieces can start in hand. The following is the first S-Chess game it ever played:

Code: Select all

[Event "Computer Chess Game"]
[Site "hgm-xboard"]
[Date "2015.01.14"]
[Round "-"]
[White "S-Fruit 2.1 (UCI2WB)"]
[Black "Fairy-Max 4.8V"]
[Result "1-0"]
[TimeControl "40/60"]
[Variant "seirawan"]
[Annotator "1. +0.16   1... +0.27"]

1. Nc3 {+0.16/10} Nc6/H {+0.27/6 0.9} 2. d4 {+0.68/10 1.8} Nf6/E
{-0.05/6 2.2} 3. d5 {+1.14/9 1.8} Ne5 {-0.15/7 2.0} 4. f4 {+1.40/10 1.9}
Neg4 {-0.22/7 2.4} 5. e4 {+1.72/10 1.5} d6 {-0.21/6 1.4} 6. h3
{+2.38/9 1.6} Nh6 {-0.40/6 1.1} 7. g4 {+2.37/9 1.6} Nhxg4 {-1.08/7 1.2} 8.
hxg4 {+3.18/6 0.5} Bxg4 {-1.36/7 2.3} 9. Nf3/E {+3.33/8 1.5} Hd7
{-1.22/5 1.2} 10. e5 {+3.55/8 1.7} dxe5 {-1.71/8 1.4} 11. fxe5
{+4.45/8 1.1} Bxf3 {-1.84/8 2.2} 12. Exf3 {+4.69/8 1.2} Ng4 {-1.96/7 1.9}
13. Exf7 {+4.75/8 1.7} Nxe5 {-2.27/7 0.8} 14. Exd8+ {+4.95/7 1.4} Rxd8
{-2.36/7 2.4} 15. Bh3 {+5.10/8 1.4} Hb8 {-2.62/7 1.2} 16. Rf1/H
{+6.30/8 1.4} g6 {-2.91/8 1.6} 17. Qe2 {+7.29/9 1.2} c5 {-4.05/7 1.0} 18.
Qb5+ {+9.08/8 1.4} Rd7 {-4.91/7 0.9} 19. Bxd7+ {+11.41/8 1.1} Hxd7
{-6.67/10 3} 20. Qxb7 {+11.58/10 1.3} Hb6 {-7.03/9 3} 21. Qb8+
{+12.22/8 1.0} Hd8 {-7.73/8 2.0} 22. Nb5 {+14.91/9 3} Bh6 {-6.91/6 0.7} 23.
He4 {+1000.09/7 3} Nf3+ {-10.53/7 0.6} 24. Rxf3 {+1000.05/13 0.7} Bf4
{-16.89/7 0.7} 25. Rxf4 {+1000.04/32 0.8} Ef6 {-79.97/9 1.0} 26. Rxf6
{+1000.03/41 1.0} exf6 {-79.98/9 1.2} 27. Hd6+ {+1000.02/34 0.3} Kd7
{-79.99/10 0.7} 28. Qc8# {+1000.01/39 1.1}
{mate} 1-0

There still is some work to do, however:
*) Gating at the Rook square during castling is not implemented yet
*) When I compile Fruit with the DEBUG option, it still triggers an ASSERT: it complains that depth>=0 when in_check in ful_quiescence(). (Because it passes an earlier assert at the top of that routine, this must mean depth=0.)
I will have to study Fruit's search to understand what that means. It could be that this is caused by checking with freshly gated pieces not being classified as checks in an earlier stage. Just ignoring that (by compiling without the DEBUG option) doesn't seem very detrimental, as it decisively crushed Fairy-Max. This is to be expected if the only problem is that it doesn't consider checks with the gated pieces as checks, as these are not supposed to play any tactical role in normal games, and can only happen in silly lines where one side exposes his King in the opening.

If a program asserts some particular condition at a given point in the code this often implies that the algorithm relies on this condition being true, so ignoring it is not desired.

In your case I'd say it is possible that full_search() calls full_quiescence() with depth=0 even though the moving side is currently in check, but this was not detected in full_search somehow.

[hgm]

True, I am not completely at ease about this. Fruit is extremely generous in ASSERTs, however, and when I started to test my hacked version with DEBUG on, for the first few ASSERTs that triggered I simply could adapt the test in the assert. (E.g. on the total number of pieces; the piece-list are actually large enough to hold 31 non-Pawns for each side, plus 15 Pawns, but the ASSERTs limit it to how many you could acquire by playing from the standard opening position. Which, in case of S-Chess, is of coursetwo more than for regular Chess.)

It doesn't seem to crash because of this failing assert, and actually plays a pretty strong game, beating all other publicly available engines by 10-0. But against stronger opposition it could of course matter.