checks in q-search.

[sje]

And here is some code from the check evasion move generation routine. These three chunks do all the interposition moves, and it each one the pinned piece overhead is a single bitboard mask, done only once.

Code: Select all

;;
;; Interposition for a single sweep attacker by a non-pawn
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-loc-bb)))
        (reset-sq cand-bb act-king-sq)
        (bb-and2c2d cand-bb act-pawn-bb)
        (bb-and2c2d cand-bb pinned-bb)
        (loop-bb (cand-bb cand-sq)
          (let ((to-bb (bb-and2 interpose-bb (svref (pos-atk-fr-sq-bb-vec my-pos) cand-sq))))
            (loop-bb (to-bb to-sq)
             (push (mm-simp cand-sq to-sq (get-man board-vec cand-sq)) result))))))
;;
;; Interposition for a single sweep attacker by a pawn single square advance
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-pawn-bb)))
        (bb-and2c2d cand-bb pinned-bb)
        (loop-bb (cand-bb cand-sq)
          (let ((to-sq (+ cand-sq adv-delta)))
            (when (sq-set? interpose-bb to-sq)
              (if (= (map-sq-to-rank cand-sq) act-7th-rank)
                (dolist (msc msc-gen-promotion-list)
                  (push (mm-prom cand-sq to-sq act-pawn-man msc) result))
                (push (mm-simp cand-sq to-sq act-pawn-man) result)))))))
;;
;; Interposition for a single sweep attacker by a pawn double square advance
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-pawn-bb)))
        (bb-and2c2d cand-bb pinned-bb)
        (bb-and2d cand-bb (svref rank-bb-vec act-2nd-rank))
        (loop-bb (cand-bb cand-sq)
          (let ((to-sq (+ cand-sq adv-delta)))
            (when (is-man-vacant? (get-man board-vec to-sq))
              (incf to-sq adv-delta)
              (when (sq-set? interpose-bb to-sq)
                (push (mm-simp cand-sq to-sq act-pawn-man) result)))))))

[sje]

From observing the execution of the above code and similar code in the generation functions, I'd say that the pinned/frozen data actually make them run faster overall in part because no bogus moves are generated.

So the question of overhead is limited to the actual calculation of the pinned/frozen bitboards. The calculation is not trivial, but bitboards make it fairly fast.

[bob]

Here is the code in the "not-in-check" move generation function from the CIL Toolkit for generating moves by a sweeper piece:

Code: Select all

          ((is-piece-sweeper? fr-piece)
            (let ((to-bb (bb-and2 atk-fr-sq-bb target-bb)))
              (when (sq-set? rstrct-bb fr-sq)
                (bb-and2d to-bb (fetch-beamer-bb act-king-sq fr-sq)))
              (loop-bb (to-bb to-sq)
                (push (mm-capt fr-sq to-sq fr-man (get-man board-vec to-sq)) result))))

Where is the pinned calculation overhead here? It's just one bit test plus one bitboard mask, and this happens only once per slider piece:

Code: Select all

              (when (sq-set? rstrct-bb fr-sq)
                (bb-and2d to-bb (fetch-beamer-bb act-king-sq fr-sq)))

The symbol rstrct-bb has the restricted bitboard value; this is the bitboard produced only once per move execution that contains the pieces that are pinned against the king but are not frozen. (Frozen pieces are pinned pieces that are pinned along a direction in which they can't move.) The pinned and frozen bitboards themselves are also computed once per move execution.

A beamer bitboard is the set of squares that is the open ray from the first square in the first square to second square direction.

At the start of move generation, the bitboard of active color piece locations is masked by the frozen bitboard, so the from-square scanner loop doesn't even do a dispatch.

What about the data that shows what is pinned? Has to be updated frequently...

[bob]

And here is some code from the check evasion move generation routine. These three chunks do all the interposition moves, and it each one the pinned piece overhead is a single bitboard mask, done only once.

Code: Select all

;;
;; Interposition for a single sweep attacker by a non-pawn
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-loc-bb)))
        (reset-sq cand-bb act-king-sq)
        (bb-and2c2d cand-bb act-pawn-bb)
        (bb-and2c2d cand-bb pinned-bb)
        (loop-bb (cand-bb cand-sq)
          (let ((to-bb (bb-and2 interpose-bb (svref (pos-atk-fr-sq-bb-vec my-pos) cand-sq))))
            (loop-bb (to-bb to-sq)
             (push (mm-simp cand-sq to-sq (get-man board-vec cand-sq)) result))))))
;;
;; Interposition for a single sweep attacker by a pawn single square advance
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-pawn-bb)))
        (bb-and2c2d cand-bb pinned-bb)
        (loop-bb (cand-bb cand-sq)
          (let ((to-sq (+ cand-sq adv-delta)))
            (when (sq-set? interpose-bb to-sq)
              (if (= (map-sq-to-rank cand-sq) act-7th-rank)
                (dolist (msc msc-gen-promotion-list)
                  (push (mm-prom cand-sq to-sq act-pawn-man msc) result))
                (push (mm-simp cand-sq to-sq act-pawn-man) result)))))))
;;
;; Interposition for a single sweep attacker by a pawn double square advance
;;
    (when interpose-flag
      (let ((cand-bb (clone-bb act-pawn-bb)))
        (bb-and2c2d cand-bb pinned-bb)
        (bb-and2d cand-bb (svref rank-bb-vec act-2nd-rank))
        (loop-bb (cand-bb cand-sq)
          (let ((to-sq (+ cand-sq adv-delta)))
            (when (is-man-vacant? (get-man board-vec to-sq))
              (incf to-sq adv-delta)
              (when (sq-set? interpose-bb to-sq)
                (push (mm-simp cand-sq to-sq act-pawn-man) result)))))))

I have always had a legal move generator for use when I start off in check. But that is a different animal than generating legal moves when you are not in check to start with...

[sje]

What about the data that shows what is pinned? Has to be updated frequently...

Yes, this is where the "overhead" exists. Thanks to bitboards, it doesn't cost too much:

Code: Select all

;;; Pinned/frozen bitboard calculation using a board vector as input

(defun does-pinner-exist? (my-color my-dir my-scan-sqs my-board-vec)
  "Return t if a pinning man exists according to the input parameters."
  (let ((result nil))
    (when my-scan-sqs
      (let ((cand-sq nil) (other-color (flip-color my-color)) (scan-man nil))
        (do ((scan-sq (pop my-scan-sqs))) ((not scan-sq))
          (setf scan-man (get-man my-board-vec scan-sq))
          (let ((scan-color (svref mc-man-to-color-vec scan-man)))
            (cond
              ((= scan-color color-vacant)
                (setf scan-sq (pop my-scan-sqs)))
              ((= scan-color my-color)
                (setf scan-sq nil))
              ((= scan-color other-color)
                (setf cand-sq scan-sq)
                (setf scan-sq nil))
              (t (error "cond fault: does-pinner-exist?")))))
        (when (and cand-sq (aref man-dir-sweep-vec scan-man my-dir))
          (setf result t))))
    result))


;;; Pinned/frozen bitboard calculation using a position as input

(defun calc-pinned (my-pos)
  "Calculate the bitboard vector of the pinned men for the given position."
  (let
    (
      (result              (mk-bb-vector color-rlimit))
      (loc-merge-bb        (pos-loc-merge-bb my-pos))
      (atk-by-color-bb-vec (pos-atk-by-color-bb-vec my-pos))
    )
    (docolors (color)
      (let
        (
          (other-color (flip-color color))
          (king-sq     (svref (pos-king-sq-vec my-pos) color))
          (cand-bb     (clone-bb (svref (pos-loc-color-bb-vec my-pos) color)))
          (board-vec   (pos-board-vec my-pos))
        )
        (bb-and2d cand-bb (svref sweep-attack-bb-vec king-sq))
        (bb-and2d cand-bb (svref atk-by-color-bb-vec other-color))
        (loop-bb (cand-bb cand-sq)
          (when (bb-ni2? loc-merge-bb (fetch-pathway-bb king-sq cand-sq))
            (let ((dir (fetch-dir king-sq cand-sq)))
              (when (does-pinner-exist? color dir (fetch-open-ray-sqs cand-sq dir) board-vec)
                (set-sq (svref result color) cand-sq)))))))
    result))

(defun calc-frozen-bb-vec (my-king-sq-vec my-pinned-bb-vec my-board-vec)
  "Return a new frozen bitboard vector calculated from the given board vector."
  (let ((result (mk-bb-vector color-rlimit)))
    (docolors (color)
      (let
        (
          (king-sq (svref my-king-sq-vec color))
          (cand-bb (clone-bb (svref my-pinned-bb-vec color)))
        )
        (loop-bb (cand-bb cand-sq)
          (let
            (
              (piece (svref mc-man-to-piece-vec (get-man my-board-vec cand-sq)))
              (dir (fetch-dir cand-sq king-sq))
            )
            (cond
              ((= piece piece-pawn)
                (when (aref frozen-pawn-color-dir-vec color dir)
                  (set-sq (svref result color) cand-sq)))
              ((= piece piece-knight)
                (set-sq (svref result color) cand-sq))
              ((= piece piece-bishop)
                (when (is-dir-ortho? dir)
                  (set-sq (svref result color) cand-sq)))
              ((= piece piece-rook)
                (when (is-dir-diago? dir)
                  (set-sq (svref result color) cand-sq)))
              ((= piece piece-queen)
                nil)
              ((= piece piece-king)
                nil)
              (t (error "cond fault: calc-frozen-bb-vec")))))))
    result))

(defun calc-frozen (my-pos)
  "Calculate the bitboard vector of the frozen men for the given position."
  (calc-frozen-bb-vec
    (pos-king-sq-vec   my-pos)
    (pos-pinned-bb-vec my-pos)
    (pos-board-vec     my-pos)))

At move execution time, this runs:

Code: Select all

    (when not-null-flag
      (setf (pos-pinned-bb-vec my-pos) (calc-pinned my-pos))
      (setf (pos-frozen-bb-vec my-pos) (calc-frozen my-pos))))

[Zach Wegner]

Zack

Did you read this post by HG?

[snip]

Grant

I might have seen that a while ago, I'm not sure.

Looking at it though, I don't like the idea. I don't want a separate attack table just for pins, which would even be 4x bigger than my current ones. I'm not even sure if it works--you can't determine the type of situation (discovered checks, double checks, etc.) without the piece type and color of every piece between the king and the attacker. And you would need to separate it from either direction. This approach would need to differentiate between these situations in order to be useful to me:

Code: Select all

r.B.K... ->  abs. pinned on left
.rb.K... ->  double check on left
rb..K.Rq ->  discovered check on left, half pin on right
...and myriad other possibilities...

...which it clearly can't, unless I'm mistaken. I don't know if this approach would even be faster than my current (mental) approach, and it is far less flexible.

[grant]

Well, I have it working. And now I'm re-writing my move generators to handle the information to produce only legal moves.

To get it working I have to handle the rank, file and two diagonals separately.

Example, the rank:-

If the king is checked along the rank on the left, a pin on the right can be ignored (and vice-versa), the index no. tells me the file no. of the checker and whether it's a contact check or distance check. The lookup gives me the defendable squares.
If there is a pin or two pins, (there are only 16 combinations) the index tells me that there is a pin and which combination. I create a bitboard of pinned/discovered_check pieces from the lookup.

If the king is also checked along the diagonal or by a knight I set the index to a certain number to trigger the king_moves_only move generator.

If there are other pins along the file and diagonals I just OR these in to the pinned/discovered_check bitboard to be filtered in the move generator.
The total of all tables added together is about 50K (good magics required).

The rank, file and two diagonals, each give an index if there is a check or pin. The information is combined and passed to the relevant move generator.

Grant

[jwes]

Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.

I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...

I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.

I'm not so sure. Generating legal moves has a relatively small constant cost, while you have to verify every move for legality.

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

Are you sure of that ? I ran some tests on crafty a while ago which said that crafty called incheck() more than once per move generated and that the number of nodes searched was not much smaller than the number of moves generated. I could have made a mistake, but you might want to run the tests yourself.

[Tord Romstad]

Ha, I knew there would be someone to correct me. I suppose I should've said "bitboard-based legal generators in C", but even then I'm not sure.

Hi Zach,

I hope you don't mind being corrected again?

It may very well be true that the majority of current open source bitboard chess engines only do pseudo-legal move generation, but the best, most instructive and elegant program of them all does true legal move generation: Olithink.

Tord

[bob]

Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.

I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...

I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.

I'm not so sure. Generating legal moves has a relatively small constant cost, while you have to verify every move for legality.

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

Are you sure of that ? I ran some tests on crafty a while ago which said that crafty called incheck() more than once per move generated and that the number of nodes searched was not much smaller than the number of moves generated. I could have made a mistake, but you might want to run the tests yourself.

It had better not do that. After a move is made, a call to InCheck() is made, unless we are in check when we start that ply, then we trust the legal move generator to get us out without the test. There are no InCheck() calls in the q-search where most of the moves are actually produced and searched. So I can't imagine how that could happen. Even if you only count move generated and InCheck() calls in the normal Search() function, I don't see how InCheck() could be called more than the number of moves actually searched, which is _far_ less than the total number of moves generated. I might try to verify this to be sure there is no bug anywhere, but this would usually show up on profile runs anyway...