Unify move generation
authorMarco Costalba <mcostalba@gmail.com>
Wed, 5 Jan 2011 18:47:01 +0000 (19:47 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Fri, 7 Jan 2011 15:56:42 +0000 (16:56 +0100)
Functional change due only to moves reorder. Anyhow after
5242 games at 15"+0.1 TC verified we have no regression.

Mod vs Orig 994 - 958 - 3290 +2 ELO

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/book.cpp
src/movegen.cpp
src/movegen.h
src/movepick.cpp
src/position.cpp
src/san.cpp
src/search.cpp

index 2c11a3d507b066db136e23e916257368d6e51291..7b5be1864c667b4269a388b0e4bdf4b267c9a2d0 100644 (file)
@@ -437,7 +437,7 @@ Move Book::get_move(const Position& pos, bool findBestMove) {
 
   // Verify the book move is legal
   MoveStack mlist[MOVES_MAX];
-  MoveStack* last = generate_moves(pos, mlist);
+  MoveStack* last = generate<MV_LEGAL>(pos, mlist);
   for (MoveStack* cur = mlist; cur != last; cur++)
       if ((int(cur->move) & 07777) == bookMove)
           return cur->move;
index 349d3b71e2c940d54b4657b2019b259212ff4871..b130247bea5f151cd810ec3e73ddd8b1a1204a83 100644 (file)
@@ -45,13 +45,6 @@ namespace {
     QUEEN_SIDE
   };
 
-  enum MoveType {
-    CAPTURE,
-    NON_CAPTURE,
-    CHECK,
-    EVASION
-  };
-
   template<CastlingSide Side>
   MoveStack* generate_castle_moves(const Position&, MoveStack*);
 
@@ -108,15 +101,15 @@ namespace {
   template<>
   inline MoveStack* generate_direct_checks<PAWN>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
 
-    return (us == WHITE ? generate_pawn_moves<WHITE, CHECK>(p, m, dc, ksq)
-                        : generate_pawn_moves<BLACK, CHECK>(p, m, dc, ksq));
+    return (us == WHITE ? generate_pawn_moves<WHITE, MV_CHECK>(p, m, dc, ksq)
+                        : generate_pawn_moves<BLACK, MV_CHECK>(p, m, dc, ksq));
   }
 
   template<PieceType Piece, MoveType Type>
   inline MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us, Bitboard t) {
 
     assert(Piece == PAWN);
-    assert(Type == CAPTURE || Type == NON_CAPTURE || Type == EVASION);
+    assert(Type == MV_CAPTURE || Type == MV_NON_CAPTURE || Type == MV_EVASION);
 
     return (us == WHITE ? generate_pawn_moves<WHITE, Type>(p, m, t, SQ_NONE)
                         : generate_pawn_moves<BLACK, Type>(p, m, t, SQ_NONE));
@@ -153,84 +146,70 @@ namespace {
 
 }
 
-
 ////
 //// Functions
 ////
 
 
-/// generate_captures() generates all pseudo-legal captures and queen
+/// generate<MV_CAPTURE> generates all pseudo-legal captures and queen
 /// promotions. Returns a pointer to the end of the move list.
-template<>
-MoveStack* generate<CAPTURES>(const Position& pos, MoveStack* mlist) {
-
-  assert(pos.is_ok());
-  assert(!pos.is_check());
-
-  Color us = pos.side_to_move();
-  Bitboard target = pos.pieces_of_color(opposite_color(us));
-
-  mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
-  mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
-  mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
-  mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
-  mlist = generate_piece_moves<PAWN, CAPTURE>(pos, mlist, us, target);
-  return  generate_piece_moves<KING>(pos, mlist, us, target);
-}
-
-
-/// generate_noncaptures() generates all pseudo-legal non-captures and
+///
+/// generate<MV_NON_CAPTURE> generates all pseudo-legal non-captures and
 /// underpromotions. Returns a pointer to the end of the move list.
-template<>
-MoveStack* generate<NON_CAPTURES>(const Position& pos, MoveStack* mlist) {
-
-  assert(pos.is_ok());
-  assert(!pos.is_check());
-
-  Color us = pos.side_to_move();
-  Bitboard target = pos.empty_squares();
-
-  mlist = generate_piece_moves<PAWN, NON_CAPTURE>(pos, mlist, us, target);
-  mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
-  mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
-  mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
-  mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
-  mlist = generate_piece_moves<KING>(pos, mlist, us, target);
-  mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
-  return  generate_castle_moves<QUEEN_SIDE>(pos, mlist);
-}
-
-
-/// generate_non_evasions() generates all pseudo-legal captures and
+///
+/// generate<MV_NON_EVASION> generates all pseudo-legal captures and
 /// non-captures. Returns a pointer to the end of the move list.
-template<>
-MoveStack* generate<NON_EVASIONS>(const Position& pos, MoveStack* mlist) {
+
+template<MoveType T>
+MoveStack* generate(const Position& pos, MoveStack* mlist) {
 
   assert(pos.is_ok());
   assert(!pos.is_check());
 
   Color us = pos.side_to_move();
-  Bitboard target = pos.pieces_of_color(opposite_color(us));
+  Bitboard target;
 
-  mlist = generate_piece_moves<PAWN, CAPTURE>(pos, mlist, us, target);
-  mlist = generate_piece_moves<PAWN, NON_CAPTURE>(pos, mlist, us, pos.empty_squares());
+  if (T == MV_CAPTURE || T == MV_NON_EVASION)
+      target = pos.pieces_of_color(opposite_color(us));
+  else if (T == MV_NON_CAPTURE)
+      target = pos.empty_squares();
+  else
+      assert(false);
 
-  target |= pos.empty_squares();
+  if (T == MV_NON_EVASION)
+  {
+      mlist = generate_piece_moves<PAWN, MV_CAPTURE>(pos, mlist, us, target);
+      mlist = generate_piece_moves<PAWN, MV_NON_CAPTURE>(pos, mlist, us, pos.empty_squares());
+      target |= pos.empty_squares();
+  }
+  else
+      mlist = generate_piece_moves<PAWN, T>(pos, mlist, us, target);
 
   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
   mlist = generate_piece_moves<KING>(pos, mlist, us, target);
-  mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
-  return  generate_castle_moves<QUEEN_SIDE>(pos, mlist);
+
+  if (T != MV_CAPTURE)
+  {
+      mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
+      mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist);
+  }
+
+  return mlist;
 }
 
+// Explicit template instantiation
+template MoveStack* generate<MV_CAPTURE>(const Position& pos, MoveStack* mlist);
+template MoveStack* generate<MV_NON_CAPTURE>(const Position& pos, MoveStack* mlist);
+template MoveStack* generate<MV_NON_EVASION>(const Position& pos, MoveStack* mlist);
+
 
 /// generate_non_capture_checks() generates all pseudo-legal non-captures and knight
 /// underpromotions that give check. Returns a pointer to the end of the move list.
 template<>
-MoveStack* generate<NON_CAPTURE_CHECKS>(const Position& pos, MoveStack* mlist) {
+MoveStack* generate<MV_NON_CAPTURE_CHECK>(const Position& pos, MoveStack* mlist) {
 
   assert(pos.is_ok());
   assert(!pos.is_check());
@@ -271,7 +250,7 @@ MoveStack* generate<NON_CAPTURE_CHECKS>(const Position& pos, MoveStack* mlist) {
 /// generate_evasions() generates all pseudo-legal check evasions when
 /// the side to move is in check. Returns a pointer to the end of the move list.
 template<>
-MoveStack* generate<EVASIONS>(const Position& pos, MoveStack* mlist) {
+MoveStack* generate<MV_EVASION>(const Position& pos, MoveStack* mlist) {
 
   assert(pos.is_ok());
   assert(pos.is_check());
@@ -327,7 +306,7 @@ MoveStack* generate<EVASIONS>(const Position& pos, MoveStack* mlist) {
   // checker piece is possible.
   target = squares_between(checksq, ksq) | checkers;
 
-  mlist = generate_piece_moves<PAWN, EVASION>(pos, mlist, us, target);
+  mlist = generate_piece_moves<PAWN, MV_EVASION>(pos, mlist, us, target);
   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
@@ -335,22 +314,26 @@ MoveStack* generate<EVASIONS>(const Position& pos, MoveStack* mlist) {
 }
 
 
-/// 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 non time-critical paths.
+/// generate<MV_LEGAL / MV_PSEUDO_LEGAL> computes a complete list of legal
+/// or pseudo-legal moves in the current position.
+template<>
+inline MoveStack* generate<MV_PSEUDO_LEGAL>(const Position& pos, MoveStack* mlist) {
 
-MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLegal) {
+  assert(pos.is_ok());
+
+  return pos.is_check() ? generate<MV_EVASION>(pos, mlist)
+                        : generate<MV_NON_EVASION>(pos, mlist);
+}
+
+template<>
+MoveStack* generate<MV_LEGAL>(const Position& pos, MoveStack* mlist) {
 
   assert(pos.is_ok());
 
   MoveStack *last, *cur = mlist;
   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 
-  // Generate pseudo-legal moves
-  last = pos.is_check() ? generate<EVASIONS>(pos, mlist)
-                        : generate<NON_EVASIONS>(pos, mlist);
-  if (pseudoLegal)
-      return last;
+  last = generate<MV_PSEUDO_LEGAL>(pos, mlist);
 
   // Remove illegal moves from the list
   while (cur != last)
@@ -370,7 +353,7 @@ MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLega
 bool move_is_legal(const Position& pos, const Move m) {
 
   MoveStack mlist[MOVES_MAX];
-  MoveStack *cur, *last = generate_moves(pos, mlist, true);
+  MoveStack *cur, *last = generate<MV_PSEUDO_LEGAL>(pos, mlist);
 
    for (cur = mlist; cur != last; cur++)
       if (cur->move == m)
@@ -515,10 +498,10 @@ namespace {
     {
         to = pop_1st_bit(&b);
 
-        if (Type == CAPTURE || Type == EVASION)
+        if (Type == MV_CAPTURE || Type == MV_EVASION)
             (*mlist++).move = make_promotion_move(to - Delta, to, QUEEN);
 
-        if (Type == NON_CAPTURE || Type == EVASION)
+        if (Type == MV_NON_CAPTURE || Type == MV_EVASION)
         {
             (*mlist++).move = make_promotion_move(to - Delta, to, ROOK);
             (*mlist++).move = make_promotion_move(to - Delta, to, BISHOP);
@@ -527,7 +510,7 @@ namespace {
 
         // This is the only possible under promotion that can give a check
         // not already included in the queen-promotion.
-        if (   Type == CHECK
+        if (   Type == MV_CHECK
             && bit_is_set(pos.attacks_from<KNIGHT>(to), pos.king_square(opposite_color(Us))))
             (*mlist++).move = make_promotion_move(to - Delta, to, KNIGHT);
         else (void)pos; // Silence a warning under MSVC
@@ -551,16 +534,16 @@ namespace {
     Bitboard b1, b2, dc1, dc2, pawnPushes, emptySquares;
     Bitboard pawns = pos.pieces(PAWN, Us);
     Bitboard pawnsOn7 = pawns & TRank7BB;
-    Bitboard enemyPieces = (Type == CAPTURE ? target : pos.pieces_of_color(Them));
+    Bitboard enemyPieces = (Type == MV_CAPTURE ? target : pos.pieces_of_color(Them));
 
     // Pre-calculate pawn pushes before changing emptySquares definition
-    if (Type != CAPTURE)
+    if (Type != MV_CAPTURE)
     {
-        emptySquares = (Type == NON_CAPTURE ? target : pos.empty_squares());
+        emptySquares = (Type == MV_NON_CAPTURE ? target : pos.empty_squares());
         pawnPushes = move_pawns<TDELTA_N>(pawns & ~TRank7BB) & emptySquares;
     }
 
-    if (Type == EVASION)
+    if (Type == MV_EVASION)
     {
         emptySquares &= target; // Only blocking squares
         enemyPieces  &= target; // Capture only the checker piece
@@ -569,7 +552,7 @@ namespace {
     // Promotions and underpromotions
     if (pawnsOn7)
     {
-        if (Type == CAPTURE)
+        if (Type == MV_CAPTURE)
             emptySquares = pos.empty_squares();
 
         pawns &= ~TRank7BB;
@@ -579,19 +562,19 @@ namespace {
     }
 
     // Standard captures
-    if (Type == CAPTURE || Type == EVASION)
+    if (Type == MV_CAPTURE || Type == MV_EVASION)
     {
         mlist = generate_pawn_captures<Type, TDELTA_NE>(mlist, pawns, enemyPieces);
         mlist = generate_pawn_captures<Type, TDELTA_NW>(mlist, pawns, enemyPieces);
     }
 
     // Single and double pawn pushes
-    if (Type != CAPTURE)
+    if (Type != MV_CAPTURE)
     {
         b1 = pawnPushes & emptySquares;
         b2 = move_pawns<TDELTA_N>(pawnPushes & TRank3BB) & emptySquares;
 
-        if (Type == CHECK)
+        if (Type == MV_CHECK)
         {
             // Consider only pawn moves which give direct checks
             b1 &= pos.attacks_from<PAWN>(ksq, Them);
@@ -614,7 +597,7 @@ namespace {
     }
 
     // En passant captures
-    if ((Type == CAPTURE || Type == EVASION) && pos.ep_square() != SQ_NONE)
+    if ((Type == MV_CAPTURE || Type == MV_EVASION) && pos.ep_square() != SQ_NONE)
     {
         assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6);
         assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3);
@@ -622,7 +605,7 @@ namespace {
         // An en passant capture can be an evasion only if the checking piece
         // is the double pushed pawn and so is in the target. Otherwise this
         // is a discovery check and we are forced to do otherwise.
-        if (Type == EVASION && !bit_is_set(target, pos.ep_square() - TDELTA_N))
+        if (Type == MV_EVASION && !bit_is_set(target, pos.ep_square() - TDELTA_N))
             return mlist;
 
         b1 = pawns & pos.attacks_from<PAWN>(pos.ep_square(), Them);
index 636e439dc841f30604dbcc786c4c231afa702260..35fda92abe49350255bbd3be3d19a0ff5398908f 100644 (file)
 
 #include "position.h"
 
-enum MoveGeneration {
-  CAPTURES,
-  NON_CAPTURES,
-  NON_CAPTURE_CHECKS,
-  EVASIONS,
-  NON_EVASIONS,
-  ALL_MOVES
+enum MoveType {
+  MV_CAPTURE,
+  MV_NON_CAPTURE,
+  MV_CHECK,
+  MV_NON_CAPTURE_CHECK,
+  MV_EVASION,
+  MV_NON_EVASION,
+  MV_LEGAL,
+  MV_PSEUDO_LEGAL
 };
 
-template<MoveGeneration T>
+template<MoveType T>
 MoveStack* generate(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);
 
-
 #endif // !defined(MOVEGEN_H_INCLUDED)
index e4e45d41f87390c357b42c4d846de45a86c41598..9b274d59ff6be53d8f5948ac85189df4416ccb21 100644 (file)
@@ -132,7 +132,7 @@ void MovePicker::go_next_phase() {
       return;
 
   case PH_GOOD_CAPTURES:
-      lastMove = generate<CAPTURES>(pos, moves);
+      lastMove = generate<MV_CAPTURE>(pos, moves);
       score_captures();
       return;
 
@@ -142,7 +142,7 @@ void MovePicker::go_next_phase() {
       return;
 
   case PH_NONCAPTURES:
-      lastMove = generate<NON_CAPTURES>(pos, moves);
+      lastMove = generate<MV_NON_CAPTURE>(pos, moves);
       score_noncaptures();
       sort_moves(moves, lastMove, &lastGoodNonCapture);
       return;
@@ -156,17 +156,17 @@ void MovePicker::go_next_phase() {
 
   case PH_EVASIONS:
       assert(pos.is_check());
-      lastMove = generate<EVASIONS>(pos, moves);
+      lastMove = generate<MV_EVASION>(pos, moves);
       score_evasions();
       return;
 
   case PH_QCAPTURES:
-      lastMove = generate<CAPTURES>(pos, moves);
+      lastMove = generate<MV_CAPTURE>(pos, moves);
       score_captures();
       return;
 
   case PH_QCHECKS:
-      lastMove = generate<NON_CAPTURE_CHECKS>(pos, moves);
+      lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
       return;
 
   case PH_STOP:
index 44a1a404b580da478671a4b765ccffe839b23ffb..9c61cc88181e89411427d9158b92108d35285344 100644 (file)
@@ -1709,7 +1709,7 @@ bool Position::is_draw() const {
 bool Position::is_mate() const {
 
   MoveStack moves[MOVES_MAX];
-  return is_check() && generate_moves(*this, moves) == moves;
+  return is_check() && generate<MV_LEGAL>(*this, moves) == moves;
 }
 
 
@@ -1730,8 +1730,8 @@ bool Position::has_mate_threat() {
   do_null_move(st1);
 
   // Then generate pseudo-legal moves that could give check
-  last = generate<NON_CAPTURE_CHECKS>(*this, mlist);
-  last = generate<CAPTURES>(*this, last);
+  last = generate<MV_NON_CAPTURE_CHECK>(*this, mlist);
+  last = generate<MV_CAPTURE>(*this, last);
 
   // Loop through the moves, and see if one of them gives mate
   Bitboard pinned = pinned_pieces(sideToMove);
index d8e7da15a7f8b7b83931956f7a8d9beb6d432f13..1eb59c32fb17bca173466a764d7e090710ab6ed5 100644 (file)
@@ -149,7 +149,7 @@ Move move_from_san(const Position& pos, const string& movestr) {
   int matches, state = START;
 
   // Generate all legal moves for the given position
-  last = generate_moves(pos, mlist);
+  last = generate<MV_LEGAL>(pos, mlist);
 
   // Castling moves
   if (movestr == "O-O-O" || movestr == "O-O-O+")
@@ -377,7 +377,7 @@ namespace {
         return AMBIGUITY_NONE;
 
     // Collect all legal moves of piece 'pc' with destination 'to'
-    last = generate_moves(pos, mlist);
+    last = generate<MV_LEGAL>(pos, mlist);
     for (MoveStack* cur = mlist; cur != last; cur++)
         if (move_to(cur->move) == to && pos.piece_on(move_from(cur->move)) == pc)
             candidates[matches++] = cur->move;
index 88160ef2529df13179ce9cb8839090ec2aa9fa2d..cdd38407c6dff60b23c166e812d20d2da80f1659 100644 (file)
@@ -378,7 +378,7 @@ int64_t perft(Position& pos, Depth depth)
     int64_t sum = 0;
 
     // Generate all legal moves
-    MoveStack* last = generate_moves(pos, mlist);
+    MoveStack* last = generate<MV_LEGAL>(pos, mlist);
 
     // If we are at the last ply we don't need to do and undo
     // the moves, just to count them.
@@ -2671,7 +2671,7 @@ split_point_start: // At split points actual search starts from here
     ss[0].eval = ss[0].evalMargin = VALUE_NONE;
 
     // Generate all legal moves
-    MoveStack* last = generate_moves(pos, mlist);
+    MoveStack* last = generate<MV_LEGAL>(pos, mlist);
 
     // Add each move to the RootMoveList's vector
     for (MoveStack* cur = mlist; cur != last; cur++)