Simplify move legality check for uncommon cases

Remove a bunch of difficult and tricky code to test
legality of castle and ep moves and instead use a slower
but simpler check against the list of generated legal moves.

Because these moves are very rare the performance impact
is small but code semplification is ver big: almost 100 lines
of difficult code removed !

No functionality change. No performance change (strangely enough
there is no even minimal performance regression in pgo builds but
instead a slightly and unexpected increase).

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/book.cpp b/src/book.cpp
index 0c72d8e80d862d35b9f17aafc5d3f14cf7321a4c..d825477f6ab9bbb82d909f4568ba9272fc430e90 100644 (file)
--- a/src/book.cpp
+++ b/src/book.cpp
@@ -430,7 +430,7 @@ Move Book::get_move(const Position& pos) {
       return MOVE_NONE;
 
   MoveStack mlist[256];
       return MOVE_NONE;
 
   MoveStack mlist[256];

-  MoveStack* last = generate_legal_moves(pos, mlist);
+  MoveStack* last = generate_moves(pos, mlist);

   for (MoveStack* cur = mlist; cur != last; cur++)
       if ((int(cur->move) & 07777) == bookMove)
           return cur->move;
   for (MoveStack* cur = mlist; cur != last; cur++)
       if ((int(cur->move) & 07777) == bookMove)
           return cur->move;

diff --git a/src/movegen.cpp b/src/movegen.cpp
index 8ec7124b1095c5517fd0252dcbb40723c65a522f..9cb588a385e6534b0a5db52a5fad5b19230ca768 100644 (file)
--- a/src/movegen.cpp
+++ b/src/movegen.cpp
@@ -345,13 +345,11 @@ MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pin
 }
 
 
 }
 
 

-/// generate_legal_moves() computes a complete list of legal moves in the
-/// current position. This function is not very fast, and should be used
-/// only in situations where performance is unimportant. It wouldn't be
-/// very hard to write an efficient legal move generator, but for the moment
-/// we don't need it.
+/// generate_moves() computes a complete list of legal or pseudo legal moves in
+/// the current position. This function is not very fast, and should be used
+/// only in situations where performance is unimportant.

 
 

-MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) {
+MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLegal) {

 
   assert(pos.is_ok());
 
 
   assert(pos.is_ok());
 


@@ -363,6 +361,8 @@ MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) {
   // Generate pseudo-legal moves
   MoveStack* last = generate_captures(pos, mlist);
   last = generate_noncaptures(pos, last);
   // Generate pseudo-legal moves
   MoveStack* last = generate_captures(pos, mlist);
   last = generate_noncaptures(pos, last);

+  if (pseudoLegal)
+      return last;

 
   // Remove illegal moves from the list
   for (MoveStack* cur = mlist; cur != last; cur++)
 
   // Remove illegal moves from the list
   for (MoveStack* cur = mlist; cur != last; cur++)


@@ -376,10 +376,24 @@ MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) {
 
 
 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)
 
 
 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)

-/// move and a pinned pieces bitboard as input, and tests whether
-/// the move is legal.  If the move is legal, the move itself is
-/// returned. If not, the function returns false.  This function must
-/// only be used when the side to move is not in check.
+/// move and tests whether the move is legal. This version is not very fast
+/// and should be used only for non time-critical paths.
+
+bool move_is_legal(const Position& pos, const Move m) {
+
+  MoveStack mlist[256];
+  MoveStack* last = generate_moves(pos, mlist, true);
+  for (MoveStack* cur = mlist; cur != last; cur++)
+      if (cur->move == m)
+          return pos.pl_move_is_legal(m);
+
+  return false;
+}
+
+
+/// Fast version of move_is_legal() that takes a position a move and
+/// a pinned pieces bitboard as input, and tests whether the move is legal.
+/// This version must only be used when the side to move is not in check.

 
 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 
 
 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 


@@ -388,6 +402,10 @@ bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
   assert(move_is_ok(m));
   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 
   assert(move_is_ok(m));
   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 

+  // Use a slower but simpler function for uncommon cases
+  if (move_is_ep(m) || move_is_castle(m))
+      return move_is_legal(pos, m);
+

   Color us = pos.side_to_move();
   Square from = move_from(m);
   Piece pc = pos.piece_on(from);
   Color us = pos.side_to_move();
   Square from = move_from(m);
   Piece pc = pos.piece_on(from);


@@ -400,92 +418,6 @@ bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
   Color them = opposite_color(us);
   Square to = move_to(m);
 
   Color them = opposite_color(us);
   Square to = move_to(m);
 

-  // En passant moves
-  if (move_is_ep(m))
-  {
-      // The piece must be a pawn and destination square must be the
-      // en passant square.
-      if (   type_of_piece(pc) != PAWN
-          || to != pos.ep_square())
-          return false;
-
-      assert(pos.square_is_empty(to));
-      assert(pos.piece_on(to - pawn_push(us)) == piece_of_color_and_type(them, PAWN));
-
-      // The move is pseudo-legal, check if it is also legal
-      return pos.pl_move_is_legal(m, pinned);
-  }
-
-  // Castling moves
-  if (move_is_short_castle(m))
-  {
-      // The piece must be a king and side to move must still have
-      // the right to castle kingside.
-      if (   type_of_piece(pc) != KING
-          ||!pos.can_castle_kingside(us))
-          return false;
-
-      assert(from == pos.king_square(us));
-      assert(to == pos.initial_kr_square(us));
-      assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
-
-      Square g1 = relative_square(us, SQ_G1);
-      Square f1 = relative_square(us, SQ_F1);
-      Square s;
-      bool illegal = false;
-
-      // Check if any of the squares between king and rook
-      // is occupied or under attack.
-      for (s = Min(from, g1); s <= Max(from, g1); s++)
-          if (  (s != from && s != to && !pos.square_is_empty(s))
-              ||(pos.attackers_to(s) & pos.pieces_of_color(them)))
-              illegal = true;
-
-      // Check if any of the squares between king and rook
-      // is occupied.
-      for (s = Min(to, f1); s <= Max(to, f1); s++)
-          if (s != from && s != to && !pos.square_is_empty(s))
-              illegal = true;
-
-      return !illegal;
-  }
-
-  if (move_is_long_castle(m))
-  {
-      // The piece must be a king and side to move must still have
-      // the right to castle kingside.
-      if (   type_of_piece(pc) != KING
-          ||!pos.can_castle_queenside(us))
-          return false;
-
-      assert(from == pos.king_square(us));
-      assert(to == pos.initial_qr_square(us));
-      assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
-
-      Square c1 = relative_square(us, SQ_C1);
-      Square d1 = relative_square(us, SQ_D1);
-      Square s;
-      bool illegal = false;
-
-      for (s = Min(from, c1); s <= Max(from, c1); s++)
-          if(  (s != from && s != to && !pos.square_is_empty(s))
-             ||(pos.attackers_to(s) & pos.pieces_of_color(them)))
-              illegal = true;
-
-      for (s = Min(to, d1); s <= Max(to, d1); s++)
-          if(s != from && s != to && !pos.square_is_empty(s))
-              illegal = true;
-
-      if (   square_file(to) == FILE_B
-          && (   pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, ROOK)
-              || pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, QUEEN)))
-          illegal = true;
-
-      return !illegal;
-  }
-
-  // Normal moves
-

   // The destination square cannot be occupied by a friendly piece
   if (pos.color_of_piece_on(to) == us)
       return false;
   // The destination square cannot be occupied by a friendly piece
   if (pos.color_of_piece_on(to) == us)
       return false;


@@ -560,30 +492,6 @@ bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 }
 
 
 }
 
 

-/// Another version of move_is_legal(), which takes only a position and a move
-/// as input. This function does not require that the side to move is not in
-/// check. It is not optimized for speed, and is only used for verifying move
-/// legality when building a PV from the transposition table.
-
-bool move_is_legal(const Position& pos, const Move m) {
-
-  Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
-  if (!pos.is_check())
-      return move_is_legal(pos, m, pinned);
-  else
-  {
-      Position p(pos);
-      MoveStack mlist[64];
-      MoveStack* last = generate_evasions(p, mlist, pinned);
-      for (MoveStack* cur = mlist; cur != last; cur++)
-          if (cur->move == m)
-              return true;
-
-      return false;
-  }
-}
-
-

 namespace {
 
   template<PieceType Piece>
 namespace {
 
   template<PieceType Piece>

diff --git a/src/movegen.h b/src/movegen.h
index 7b7c4e91bb4857094e7a21cb667452e72ad3cb8d..fdc90139850c8db8ec360da408ac8312846d46a5 100644 (file)
--- a/src/movegen.h
+++ b/src/movegen.h
@@ -36,7 +36,7 @@ extern MoveStack* generate_captures(const Position& pos, MoveStack* mlist);
 extern MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist);
 extern MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc);
 extern MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned);
 extern MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist);
 extern MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc);
 extern MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned);

-extern MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist);
+extern MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLegal = false);

 extern bool move_is_legal(const Position& pos, const Move m, Bitboard pinned);
 extern bool move_is_legal(const Position& pos, const Move m);
 
 extern bool move_is_legal(const Position& pos, const Move m, Bitboard pinned);
 extern bool move_is_legal(const Position& pos, const Move m);
 

diff --git a/src/search.cpp b/src/search.cpp
index 93a582035df07f4ada4a20cd82e17003720f34de..24230ee7fd6b4ebe4b38369d9fd0ad3d4e5252e5 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1966,7 +1966,7 @@ namespace {
     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
 
     // Generate all legal moves
     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
 
     // Generate all legal moves

-    MoveStack* last = generate_legal_moves(pos, mlist);
+    MoveStack* last = generate_moves(pos, mlist);

 
     // Add each move to the moves[] array
     for (MoveStack* cur = mlist; cur != last; cur++)
 
     // Add each move to the moves[] array
     for (MoveStack* cur = mlist; cur != last; cur++)