checks in q-search.

[bob]

I ran some tests, here is one sample, although all show close to the same ratio of nodes searched to moves generated:

time=50.87 mat=0 n=70223748 fh=90% nps=1.4M
ext-> check=502K qcheck=853K 1rep=72K mate=27K reduce=28.7M/5.2M
predicted=0 evals=60.8M 50move=0 EGTBprobes=0 hits=0
SMP-> splits=0 aborts=0 data=0/128 elap=50.87
ngen=117933631

It generated a total of 118M moves, and searched a total of 70M. At first this seemed low, but after looking a bit, I noticed the following: (1) the hash move is often good enough to produce a cutoff, if it is available. If so, no moves are generated at all. If that fails, a capture is most often the best move in a full-width search and there are usually not very many in any given position. if that fails, the killers are the next choice and I try those before generating anything else, so if I get a cutoff, no moves generated there either. So, most of the time if I generate them all, I end up searching them all, something I had not really considered. But the idea of putting off generation until the last instant actually does pay off quite well.

So, it appears that I search about 3/4 of what I generate. I did check the Check() calls and they were around 55% of nodes searched but I only tested a couple of positions for that...

[sje]

The following pinned piece detection code could be easily translated and then transplanted into a C/C++chess program that uses bitboards. In the specific case of Crafty, the values for the sweep pieces bitboard and the attack-to-square bitboard vector would either have to be maintained from move to move or be generated as needed.

This code seems to run quite fast, even in Lisp.

Code: Select all

(defun calc-pinned (my-pos)
  "Calculate the bitboard vector of the pinned men for the given position."
  (let
    (
      (result              (mk-bb-vector color-rlimit))      ; A vector of two empty bitboards; one per color
      (loc-merge-bb        (pos-loc-merge-bb my-pos))        ; All pieces merged bitboard
      (loc-sweep-bb        (pos-loc-sweep-bb my-pos))        ; All sweeper pieces bitboard
      (loc-color-bb-vec    (pos-loc-color-bb-vec my-pos))    ; Pieces by color bitboard vector
      (atk-by-color-bb-vec (pos-atk-by-color-bb-vec my-pos)) ; Attacks by color bitboard vector
      (atk-to-sq-bb-vec    (pos-atk-to-sq-bb-vec my-pos))    ; Attacks to square bitboard vector
      (king-sq-vec         (pos-king-sq-vec my-pos))         ; King location square vector
    )
    (docolors (color) ; Produce two pinned piece bitboards, one per color
      (let*
        (
          (other-color    (flip-color color))                        ; The other color
          (other-loc-bb   (svref loc-color-bb-vec other-color))      ; The other color pieces bitboard
          (other-sweep-bb (bb-and2 loc-sweep-bb other-loc-bb))       ; The other color sweep pieces bitboard
          (king-sq        (svref king-sq-vec color))                 ; The king square
          (cand-bb        (clone-bb (svref loc-color-bb-vec color))) ; Pinned pieces candidate bitboard
        )
        (bb-and2d cand-bb (svref sweep-attack-bb-vec king-sq))     ; Remove not in line candidates
        (bb-and2d cand-bb (svref atk-by-color-bb-vec other-color)) ; Remove unattacked candidates
        (loop-bb (cand-bb cand-sq)                         ; For each candidate square in the candidate bitboard
          (when (clear-path? king-sq cand-sq loc-merge-bb) ; A clear path from the king to the candidate?
            (unless
              (bb-ni3?                                     ; Test for the null intersection of 3 bitboards
                other-sweep-bb                             ; Other color sweepers
                (svref atk-to-sq-bb-vec cand-sq)           ; Attackers to the candidate square
                (fetch-beyond-bb king-sq cand-sq))         ; The squares beyond the candidate in line with king
              (set-sq (svref result color) cand-sq))))))   ; Set candidate square in the result bitboard
    result)) ; Function return value is a bitboard vector indexed by color

[sje]

The frozen pieces bitboard vector calculation routine is a bit simpler; it runs using the pinned pieces bitboard vector as an input.

Code: Select all

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

[Aleks Peshkov]

Bob, IMO you have to call in_check() twice in each visited node (for both sides to move), that is why the number of check-test calls can be greater then the number of generated moves.

[bob]

Bob, IMO you have to call in_check() twice in each visited node (for both sides to move), that is why the number of check-test calls can be greater then the number of generated moves.

It isn't quite done like that.

In the normal search, you are correct, and this covers 50% of total nodes searched (or usually less). I have to use Check() to verify that a move is legal, and then use Check() to determine if a move checks the opponent to determine whether to extend or not. But in the q-search, Check() is not used at all, except for the leaf nodes (where I need to determine if a move checks the opponent to determine whether to do a normal capture search in reply or use the special evasion qsearch that is full width. But these are currently only done at the first ply of the qsearch (to deliver checks). I believe this is why my test had Check() being called less than once (and remember we were discussing moves generated, not nodes searched) per move. Only 70% of the moves generated are actually searched so that cuts out a lot of checks with respect to total moves generated...

[Zach Wegner]

You don't verify moves for legality in qsearch?

[bob]

You don't verify moves for legality in qsearch?

No. If I capture a king at the next ply, I just back up and consider that move illegal and continue as if it were never tried...

[kongsian]

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

I would also like to state that my perft engine which is bitboard based generates legal moves. I've designed it to be very compact. It even has a routine to generate quiet checks for use in the QS.

http://www.geocities.com/kongsian/

Once I have figured out how to generate legal moves, I have never looked back. My own testing indicates that it is faster than using pseudo-legal move. And it makes bulk counting possible in perft giving good numbers

PS. Is Glaurung a legal move generator as well?

[OliverBr]

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

I would also like to state that my perft engine which is bitboard based generates legal moves. I've designed it to be very compact. It even has a routine to generate quiet checks for use in the QS.

http://www.geocities.com/kongsian/

Once I have figured out how to generate legal moves, I have never looked back. My own testing indicates that it is faster than using pseudo-legal move. And it makes bulk counting possible in perft giving good numbers

PS. Is Glaurung a legal move generator as well?

Yes, Glaurung has a legal move generator. And for me it's the best open source chess program. I know there is still strelka, but Glaurung has most structure in its code.

Anyway, when I was beginning with chess programming, I used pseudo legal moves, too. They have the big advantage the the code is easier to understand and mantain, but once switching to real legal moves you never go back