Legal move generator

[Samuele Giraudo]

Hello,

I am writing my second engine based on bitboards in C language.
I am not sure about legal move generation.
My generation schema is :

Code: Select all

legals := EmptyStack()
stack := GeneratePseudoLegalMoves(pos)
FOR ALL move IN Stack 
    PlayMove(pos, move)
    IF NOT IsAttackedSquare(pos, pos.king_square[opponent(pos.side_to_move)])
        add(legals, move)
    END IF
    UndoMove(pos, move)
END FOR

This compute exactly legals move, but is very slow because with a perft benchmark I obtain only about 2 500 000 NpS.

Can you tell me if exists a legal move generation schema more efficient?

Regards,
Samuele Giraudo

[Aleks Peshkov]

Perft benchmark favours legal move generation because it can avoid last ply make-unmake. In real chess program the performance gains of legal move generation are not observable, if any.

[WinPooh]

I'd recommend to implement legal moves generator step-by-step:

1) write pseudo-legal move generator + check each move for legality in MakeMove()
2) write "incremental" check detector - after each move find which pieces (if any) attack opponents King
3) verify "incremental" check detector with straightforward attack detector
4) write GenMovesInCheck function
5) in Perft function with pseudo-legal generator, implement counter for illegal moves. Since now you aim will be to decrease it to 0 in "perft 6" task (or in "perft 5" in some complex position)
6) implement pinning detector, use pin information in all your move generator functions
7) pay _special_ attention to en-passant - there are some non-trivial issues with horizontal pins there

You can make a look at full legal moves generator in GreKo, http://greko.chess.googlepages.com
It is implemented with bitboard masks for pins and check information (however, there still exists a bug in en-passant, to be fixed in the next version!!!)

[WinPooh]

In GreKo, switching from pseudo-legal to full-legal moves generator gives +5...10% speed in perft (and +100...200% when skipping MakeMove for depth=0 in perft).

[WinPooh]

Perft benchmark favours legal move generation because it can avoid last ply make-unmake. In real chess program the performance gains of legal move generation are not observable, if any.

But it makes more easy to implement single-reply extensions, for example. It is a matter of trade, as usual...

[sje]

Code: Select all

;;; 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-vec color-rlimit))
      (loc-merge-bb        (pos-loc-merge-bb        my-pos))
      (loc-sweep-bb        (pos-loc-sweep-bb        my-pos))
      (loc-color-bb-vec    (pos-loc-color-bb-vec    my-pos))
      (atk-by-color-bb-vec (pos-atk-by-color-bb-vec my-pos))
      (atk-to-sq-bb-vec    (pos-atk-to-sq-bb-vec    my-pos))
      (king-sq-vec         (pos-king-sq-vec         my-pos))
    )
    (docolors (color)
      (let*
        (
          (other-color    (flip-color color))
          (other-loc-bb   (svref loc-color-bb-vec other-color))
          (other-sweep-bb (bb-and2 loc-sweep-bb other-loc-bb))
          (king-sq        (svref king-sq-vec color))
          (cand-bb        (clone-bb (svref loc-color-bb-vec color)))
        )
        (bb-and3d
          cand-bb
          (svref sweep-attack-bb-vec king-sq)
          (svref atk-by-color-bb-vec other-color))
        (loop-bb (cand-bb cand-sq)
          (when (clear-path? king-sq cand-sq loc-merge-bb)
            (unless
              (bb-ni3?
                other-sweep-bb
                (svref atk-to-sq-bb-vec cand-sq)
                (fetch-beyond-bb king-sq cand-sq))
              (set-sq (svref result color) cand-sq))))))
    result))

(defun calc-frozen (my-pos)
  "Calculate the bitboard vector of the frozen men for the given position."
  (let
    (
      (result        (mk-bb-vec color-rlimit))
      (king-sq-vec   (pos-king-sq-vec   my-pos))
      (pinned-bb-vec (pos-pinned-bb-vec my-pos))
      (board         (pos-board         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 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 "calc-frozen: cond fault")))))))
    result))

[bob]

Hello,

I am writing my second engine based on bitboards in C language.
I am not sure about legal move generation.
My generation schema is :

Code: Select all

legals := EmptyStack()
stack := GeneratePseudoLegalMoves(pos)
FOR ALL move IN Stack 
    PlayMove(pos, move)
    IF NOT IsAttackedSquare(pos, pos.king_square[opponent(pos.side_to_move)])
        add(legals, move)
    END IF
    UndoMove(pos, move)
END FOR

This compute exactly legals move, but is very slow because with a perft benchmark I obtain only about 2 500 000 NpS.

Can you tell me if exists a legal move generation schema more efficient?

Regards,
Samuele Giraudo

Crafty has had a legal-move-generator for years. It is bitboard-based and it only generates legal moves without the unnecessary testing you do above...

[Samuele Giraudo]

Thanks.

I will study your programs.

[Roman Hartmann]

Hi,
you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

best regards
Roman

[sje]

you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

This works only for direct attacks, not discovered attacks.