generating valid moves

[flok]

Hi,

Currently my program generates valid moves by doing the following:

- getting list of moves for current player
- getting list of moves for opponent

Then it checks for each (+/-) move if after that move the king can (still) be captured.
Of course it doesn't need to do that verification for each move, only when
1 the piece moved is the king
2 the king is pinned
3 the move is en passant
4 the king can be captured

1, 3 and 4 are easy to figure out but what about 2? Currently I have that information after I've generated the list of moves of the opponent. But if I don't want to generate that opponent list, do I need then to search all paths from the king until I first reach a piece of my own and then an opponent? Or are there quicker ways?

Remarks: current version uses https://raw.githubusercontent.com/MJoer ... tsuite.epd to verify that it is correct, and it is but only slow Furthermore I do not use bitboard.

[jorose]

I can only speak for how I do it in my engine, I could imagine other engines might have a cleaner solution.

To look for pinned pieces I first calculate the legal moves of an enemy queen from the position the allied king is on. The allied pieces this theoretical queen could capture are potentially pinned pieces. You can then either just assume these are pinned or alternatively you can temporarily remove them and calculate the legal captures of an allied queen from the position the allied king is on and check whether any of these are enemy bishops, rooks or queens.

[hgm]

In Joker I look for pinned pieces before move generation, by running through the slider section of the opponent piece list (typically 5 pieces, QRRBB), performing a 0x88 test on it (if it is actually present on the board; pieces in the list can be marked as CAPTURED) to check for alignment with the King. Usually that is it, because there is no alignment. Occasionally there is alignment, and then I scan the board from the King in the direction of the piece, to look if there is only a single piece of the stm in between. (If there is nothing in between I know that I am in check as a side effect.) In that piece would be mine, I temporarily mark it as CAPTURED, to make the normal move generation ignore it, and generate all its moves along the pin ray (which is known at that time), if it has any.

If view distances are available they can be used to avoid the ray scan: you just add the view distance of the King in the direction of the enemy slider to the view distance of the enemy slider towards the King, and if they add up to their mutiual distance, there is only a single piece in between. You can then examine that piece to see if it is yours, because you know how far from the King it is.

I do this mainly because excluding the pinned pieces from move generation saves more time than the pin test typically takes. Normally I don't care if moves are legal; if they are not the daughter node will see it can capture the King, and return a +INF score. Occasionally finding that the enemy King stumbled into check, so that you have done the move generation in vain, is cheaper than always performing a complex test on the moves to almost always discover that they are OK. King moves (and e.p.) are only a small fraction of the moves. Positions in the tree tend to resemble the root, and in the root the King most of the time has only 2 moves, both of which are legal.

Joker does a similar test on its own pieces and the enemy King to test which pieces could give discovered checks.

[cdani]

With bitboards is a bit elaborated but pretty fast. For example at Discocheck engine:

Code: Select all

Bitboard Board::hidden_checkers(bool find_pins, int color) const
{
   assert(initialized && color_ok(color) && (find_pins == 0 || find_pins == 1));
   const int aside = color ^ find_pins, kside = opp_color(aside);
   Bitboard result = 0ULL, pinners;

   // Pinned pieces protect our king, dicovery checks attack the enemy king.
   const int ksq = king_pos[kside];

   // Pinners are only sliders with X-ray attacks to ksq
   pinners = (get_RQ(aside) & bb::rattacks(ksq)) | (get_BQ(aside) & bb::battacks(ksq));

   while (pinners) {
      int sq = bb::pop_lsb(&pinners);
      Bitboard skewered = (bb::between(ksq, sq) ^ (1ULL << sq)) & st().occ;

      if (!bb::several_bits(skewered) && (skewered & all[color]))
         result |= skewered;
   }
   return result;
}

Basically is counting the pieces between the possible checkers (sliders aligned with the king), and if there is one of the same color of the king, then is pinned.

I use this technique in Andscacs not one but three times in each node, to search for pinned pieces of each player, and to discover pieces tan can make discovered check. This makes easier and fast to find illegal moves also.