checks in q-search.

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20929
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search. some data...

Post by bob » Fri Sep 05, 2008 12:30 am

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...

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Even simpler pinned piece detection code

Post by sje » Fri Sep 05, 2008 2:19 am

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

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Even simpler pinned piece detection code

Post by sje » Fri Sep 05, 2008 3:38 am

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
Posts: 887
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: checks in q-search. some data...

Post by Aleks Peshkov » Fri Sep 05, 2008 7:44 am

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
Posts: 20929
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search. some data...

Post by bob » Fri Sep 05, 2008 3:02 pm

Aleks Peshkov wrote: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...

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: checks in q-search. some data...

Post by Zach Wegner » Fri Sep 05, 2008 3:21 pm

You don't verify moves for legality in qsearch?

bob
Posts: 20929
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: checks in q-search. some data...

Post by bob » Fri Sep 05, 2008 9:01 pm

Zach Wegner wrote: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
Posts: 46
Joined: Thu Jun 15, 2006 9:21 am

Re: checks in q-search.

Post by kongsian » Fri Sep 05, 2008 10:44 pm

Tord Romstad wrote:
Zach Wegner wrote: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? :wink:

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
Posts: 691
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: checks in q-search.

Post by OliverBr » Mon Sep 29, 2008 8:26 am

kongsian wrote:
Tord Romstad wrote:
Zach Wegner wrote: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? :wink:

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 ;)

Post Reply