src/moves.cpp

   1 /* Copyright (C) 2007-2011 Vincent Ollivier
   2  *
   3  * Purple Haze is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * Purple Haze is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  15  */
  16
  17 #include <assert.h>
  18
  19 #include "moves.h"
  20 #include "board.h"
  21 #include "position.h"
  22
  23 /*
  24  * Use lazy move generation to get the next move.
  25  *
  26  * Best and killers moves are added first to the moves array and we start
  27  * with the best move. We then generate the captures but only if there have
  28  * been no cut-off with the best move.
  29  *
  30  * MVV/LVA is used to pickup the best captures first by selection sort and
  31  * next we try the killer moves (stored near the beginning of the moves array)
  32  * before the bad captures. Which are none by the way with MVV/LVA but in
  33  * the future SEE will be used for that.
  34  *
  35  * Finally when there is no captures left and no cut-off occurred we generate
  36  * the remaining quiets moves and try them with no particular order.
  37  */
  38 ExtendedMove Moves::next()
  39 {
  40     if (!use_lazy_generation) {
  41         if (i == 0) generate(); // generate() will change the value of 'n'
  42
  43         if (i == n) return ExtendedMove();
  44         return moves[i++];
  45     }
  46
  47     switch (generation_state) {
  48         case BEST:
  49             if (i < size[BEST]) return moves[i++];
  50             generation_state = GOOD_CAPTURES;
  51             generate(CAPTURE);
  52             i = size[BEST] + size[KILLERS]; // Jump to the first good capture
  53         case GOOD_CAPTURES:
  54             if (i < (size[BEST] + size[KILLERS] + size[GOOD_CAPTURES])) break;
  55             generation_state = KILLERS;
  56             i = size[BEST]; // Jump to the first killer
  57         case KILLERS:
  58             if (i < (size[BEST] + size[KILLERS])) return moves[i++];
  59             generation_state = BAD_CAPTURES;
  60             i = size[BEST] + size[KILLERS] + size[GOOD_CAPTURES];
  61         case BAD_CAPTURES:
  62             if (i < n) break;
  63             generation_state = QUIET_MOVES;
  64             generate(QUIET_MOVE);
  65         case QUIET_MOVES:
  66             if (i < n) return moves[i++];
  67         default:
  68             return ExtendedMove();
  69     }
  70
  71     // If we are here, next() should return a capture
  72     // FIXME: Review this assert
  73     assert(generation_state == GOOD_CAPTURES);
  74
  75     // Find the best remaining capture by selection sort
  76     auto max = i;
  77     for (auto j = i + 1; j < n; ++j) {
  78         if (moves[j].value() > moves[max].value()) {
  79             max = j;
  80         }
  81     }
  82
  83     // Swap it with the current one
  84     if (max != i) {
  85         ExtendedMove tmp = std::move(moves[i]);
  86         moves[i] = std::move(moves[max]);
  87         moves[max] = std::move(tmp);
  88     }
  89
  90     // Return it
  91     return moves[i++];
  92 }
  93
  94 void Moves::add(Move move, MovesState mt)
  95 {
  96     if (!use_lazy_generation) {
  97         moves[n++] = ExtendedMove(move, 0);
  98         return;
  99     }
 100
 101     if (move.is_null()) return;
 102
 103     // Don't add again best and killer moves
 104     auto end = size[BEST] + size[KILLERS];
 105     for (auto j = 0; j < end; ++j) if (moves[j] == move) return;
 106
 107     // Calculate the move's score
 108     Score score = 0;
 109     switch (mt) {
 110         case BEST:
 111             score = BEST_SCORE;
 112             size[mt]++;
 113             break;
 114         case KILLERS:
 115             score = KILLERS_SCORE - size[KILLERS];
 116             size[mt]++;
 117             break;
 118         default:
 119             //assert(generation_state > KILLERS);
 120             //size[generation_state]++; // If move is a capture or a quiet move
 121             break;
 122     }
 123     switch (generation_state) {
 124         case GOOD_CAPTURES:
 125         case BAD_CAPTURES:
 126             score = mvv_lva_score(move);
 127             size[generation_state]++;
 128             break;
 129         case QUIET_MOVES:
 130             score = -BEST_SCORE;
 131             size[generation_state]++;
 132             break;
 133         default:
 134             //assert(mt < GOOD_CAPTURES);
 135             //size[mt]++; // If move is a best or killer move
 136             break;
 137     }
 138
 139     // Add the move and its score to moves list
 140     moves[n++] = ExtendedMove(move, score);
 141 }
 142
 143 Score Moves::mvv_lva_scores[][NB_PIECE_TYPES] = { { 0 } };
 144
 145 /*
 146  * PxK = 94,  NxK = 92,  BxK = 90,  RxK = 88,  QxK = 86,  KxK = 84,  PxQ = 78,
 147  * NxQ = 76,  BxQ = 74,  RxQ = 72,  QxQ = 70,  KxQ = 68,  PxR = 62,  NxR = 60,
 148  * BxR = 58,  RxR = 56,  QxR = 54,  KxR = 52,  PxB = 46,  NxB = 44,  BxB = 42,
 149  * RxB = 40,  QxB = 38,  KxB = 36,  PxN = 30,  NxN = 28,  BxN = 26,  RxN = 24,
 150  * QxN = 22,  KxN = 20,  PxP = 14,  NxP = 12,  BxP = 10,  RxP =  8,  QxP =  6,
 151  * KxP =  4
 152  */
 153 void Moves::init_mvv_lva_scores()
 154 {
 155     for (const PieceType& v : PIECE_TYPES) {
 156         for (const PieceType& a : PIECE_TYPES) {
 157             mvv_lva_scores[v][a] = (16 * v) - (2 * a);
 158         }
 159     }
 160 }
 161
 162 Score Moves::mvv_lva_score(Move move)
 163 {
 164     assert(move.is_capture());
 165     PieceType a = board[move.orig()].type();
 166     PieceType v = board[move.dest()].type();
 167     if (move.is_en_passant()) return mvv_lva_scores[PAWN][a];
 168     return mvv_lva_scores[v][a];
 169 }