Legal move generator

[hgm]

Indeed, it is non-bitboard. I test after making to avoid the problem of the King trying to hide in it own 'shadow' when he is in check.

It sounds wose than it is, as I sort King moves last. So in cut nodes, I almost never get to the King moves. Plus that this has to be done only in the first IID iteration: if a King move turns out illegal, it is removed from the move stack, so that later iterations won't suffer from it.

I guess that now that I have SEE, it would be a bit more efficient to run a SEE for the King move rather than actually performing it. On the other hand, most King moves in the tree are legal, and then you want to make the move anyway So making it speculatively to simplify the attack test might be a winning deal.

It seems the algorithm you decribe also suffers from the problem of the King hiding in its own shadow. Or do you treat it differently when in check? If I had all opponent moves, life would indeed be simpler. But to make a fair comparison, you should of course add the cost of generating the opponent moves. So far I was not able to make that pay off.

I did consider combining the legality test of all 8 King moves, by using a table indexed by the difference between King square and potential attacker square (0x88 style) which would not indicate by a single bit if a move between the two could be possible, but would list 8 bits, one for every neighbor square. But I could not come up with something really fast there either: the different neighborhood squares might be reached through different elementary steps (e.g. Kf1, Qg4), which would make it difficult to find the correct vector to do the ray scan in case of a hit. I am still brooding on similar trick for testing castling legality in FRC, where you would like to know if a number of quares is not attacked. This is in principle easier, as you are not interested which square is attacked, just if there is one.

[grant]

I XOR the king out of the occupied bitboard so that it cannot hide in it's own shadow.

I generate opponent moves just once, and the kings attack board that is left must be legal moves. Would you not generate opponent moves for each square the king could move to (potentially 8 times) when you do your inCheck test? Even if most king moves are legal you still have to test each move.

I also thought about a combined legality test but could not come up with anything.

Grant

[sje]

I XOR the king out of the occupied bitboard so that it cannot hide in it's own shadow.

Remember that a checked king may have two shadow squares if it's double checked.

Actually, it could have more than two shadows if the input FEN isn't tested for more than two attacks to the active color king.

Code: Select all

;;
;; King moves including captures
;;
    (let
      (
        (satk-bb (bb-and2 atkr-bb loc-sweep-bb))
        (flee-bb (bb-and2c2 (svref king-attack-bb-vec act-king-sq) act-loc-bb))
      )
      (bb-and2c2d flee-bb (svref (pos-atk-by-color-bb-vec my-pos) pas-color))
      (loop-bb (satk-bb satk-sq)
        (let ((shdw-sq (aref shadow-sq-vec satk-sq act-king-sq)))
          (when shdw-sq
            (reset-sq flee-bb shdw-sq))))
      (loop-bb (flee-bb to-sq)
        (push (mm-capt act-king-sq to-sq act-king-man (get-man board to-sq)) result)))

[Zach Wegner]

Remember that a checked king may have two shadow squares if it's double checked.

And how will XORing the king out of the occupied set _not_ detect this?

[sje]

Remember that a checked king may have two shadow squares if it's double checked.

And how will XORing the king out of the occupied set _not_ detect this?

Of course the multiple shadows will be detected, as long as the scan (if it's counting shadows) doesn't stop after the first shadow.

[hgm]

I XOR the king out of the occupied bitboard so that it cannot hide in it's own shadow.

OK. But then it involves more than just the single NEG + AND. But I agree that it is not much. Moving the King on a mailbox board (the logical eqivalent of you clearing it out of the bitboard) isn't much work either, though.

I generate opponent moves just once, and the kings attack board that is left must be legal moves. Would you not generate opponent moves for each square the king could move to (potentially 8 times) when you do your inCheck test?

No, I only check for all (maximally 8) Pieces if they can reach the square, which is a lot less work than generating all moves for each piece. But I agree it could be speeded up by doing the test 'in bulk' for all King-neighborhood squares together. As in normal Chess positions most pieces cannot reach any of their opponent's King-neighborhood squares. So compiling a list of pieces that potentially can, and then using that list for the attack test on every individual square, might ready be very helpful: the list might only contain 1 or 2 pieces, rather than 8.

Perhaps an idea is this:

Make a table of 32-bit bitmaps a a function of attacker square minus King square. 3x8 bits represent contact attacks by the three different types of leaper moves (orthogonal, diagonal, hippogonal) to each of the 8 neighborhood squares. 8 other bits represent slider rays which intersect the King neighborhood. Each piece type has a mask associated with it that specifies which bits are relevant for that piece (e.g. Knight only the hippogonal contact bits, Rooks the 8 orthogonal contact bits and the 4 orthogonal ray bits. This mask is AND-ed with the table entry. Each remaining set contact bit means the corresponding square is unconditionally attacked, and they should be OR-ed into a bitmap that accumulates which squares are under attack. (In an SIMD way this treats the 3 types of leaper moves in parallel.)

If one or more ray bits remain set after masking out the directons non-relevant for the piece type, it means the piece as one or more rays that intersectthe neighborhood. Each bit corrsponds to a known elementary direction. The bits can be extracted one by one through the usual bit manipulation tricks, and DeBruin lookup can directly give the step vector of the ray. (Perhaps the DeBruin stuff is not even needed, as there are only 8 bits, and we could use them directly in a 256-entry table.) That vector can be used in a board scan starting from the piece, to see if it can reach the King neighborhood unobstructed. If it can (and we are now already discussing rarely executed code), we translate the square number to a 1-of-8 bit code representing the squre, and OR it into the accumulation bitmap.

After having gone through the list of all non-Pawn pieces this way, the 3 bitmaps for the different contact directions (bytes of the same word) have to be OR-ed together. Any zero bits in the remaining 8-bit bitmap now corresponds to a square not attacked by an enemy pieces, which the King can reach. They are extracted the usual way to obtain the King steps, which are then added to the from square. For each such move, two boad squares are examined to see if they contain enemy Pawns. (I guess the Pawns could be included in the contact atacks, by separating forward and backward diagonals and have 4 sets of 8 contact bits. On a 32-bit machine the slider bits would then have to reside in a separate byte, which is not so bad (although you would have to mask them separately with a piece-type-dependent mask), as you want to do other stuff with those bits anyway.)

This might actually work. I can try it out in qperft, to see if it gives any speed advantage.

Even if most king moves are legal you still have to test each move.

I also thought about a combined legality test but could not come up with anything.

Grant

[Dann Corbit]

Before comparing the efficiency of bitboards vs non-bitboards, there has to be a definition of exactly what a bitboard program is. And there is no exact definition as different bitboard programs will employ bitboards differently.

Let's define a bitboard database as the set of those bitboards that describe the current position and that are updated or recalculated from poisoner to position as moves are executed or retracted.

Now, some bitboard programs might have only a single bitboard: the bitboard that represents occupied squares. A different bitboard program might also have bitboards for each color and each piece kind. A more advanced bitboard database as seen in a program like Crafty will have bitboard for all attacks from each square and bitboards for all attacks by each color. A program like Chess 4.x will also have bitboards for all attacks to each square. Some programs like Symbolic and the new CIL Toolkit have bitboards for merged sweep pieces, pinned pieces by color, and frozen pieces by color. And I've heard of programs that have bitboard databases that include data on x-rays and batteries.

Some truisms:

1) The more extensive the contents of a bitboard database, the more time will be used to update and the more storage will be needed for allocation. This is the "update slowdown" and the "data cache slowdown".

2) The more extensive the contents of a bitboard database, the more it can be used in various parts of the rest of the program. For example, having pinned piece bitboards helps significantly with supporting legal-only move generation. Having pinned piece bitboards along with a set of attacks-to-square bitboards is very useful for static exchange analysis and also for positional factor evaluation.

3) Having pervasive bitboards speeds up the rest of the program in the sense that quite often only one or two bitboard operations can replace a full board scan loop in a non bitboard program. This is the time savings, and it can be more than enough to justify the extra time used for bitboard database updates.

4) Being able to think in terms of sets can help with higher level code design issues, as it's a (slightly) higher level of abstraction than thinking in terms of squares.

My experience is that bitboards are the way to go, at least if the target machine is a 32 or 64 bit architecture. Maybe for some 16 bitters as well.

On 32 bit programs, I don't think bitboard programs have any big advantage. There are array type representations that clearly perform as well as bitboard representations in terms of NPS, etc. (examples of fast 32 bit non-bitboard programs would include Fruit and Chess Tiger).

However, on 64 bit platforms with a 64 bit compiler there is a clear edge for bitboards. Typically we see that array type programs get little or no speedup from the jump while bitboard programs get a modest to huge jump in speed.

[grant]

HG

I can see no way of bulk testing the king's neighbourhood squares for attacks. You simply have to generate the attacks of opponent pieces that can potentially reach the king's neighbourhood. A simple piece-type mask from the king's square removes most attackers, so not all moves for all opponent pieces are generated, only those that are in the mask. Queens are combined with bishops and rooks.

To test for castling legality, I just use magic multiplication and a table lookup combining the two critical squares between the king and rook. One for diagonal attacks and one for orthogonal attacks.

Grant

[hgm]

Well, that already sounds like 'bulk testing' to me: you generate the relevant moves of the potentially attacking pieces only once, and then use them on the entire King neighborhood. With magic bitboards there might of course be no difference in effort between generating 'relevant moves' compared to generating all moves. (Although for Queen it still might.)

For my 0x88 representation, each direction a slider can move in requires a separate ray scan, so I have to subdivide the orthogonal and diagonal move each into 4 sub-groups to avoid unnecassary work. For magic bitboards such a subdivision would not be helpful, while for rotated bitboards you might want to divide in two sub-groups (horizontal and vertical, or diagonal and anti-diagonal).

I think the most important for efficiency is a quick test to rule out pieces that cannot possibly attack te King neighborhood. For me that requires looping through the piece lists, for bitboards it requires looping through the piece types.

[grant]

Maybe this is stating the obvious but it has only just dawned on me.

If I know that my bishop or rook is pinned and I know the pinner, I need to find out if my piece can move along the pin ray

Code: Select all

rankDiff = (pinner >> 3) ^ (pinned >> 3);
	fileDiff = (pinner & 7) ^ (pinned & 7);
	if (rankDiff == 0 || fileDiff == 0)
		//bishop cannot move
		//rook can move
	else
		//bishop can move
		//rook cannot move

Grant