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
  21 /*
  22  * Use lazy move generation to get the next move.
  23  *
  24  * Best and killers moves are added first to the moves array and we start
  25  * with the best move. We then generate the captures but only if there have
  26  * been no cut-off with the best move.
  27  *
  28  * MVV/LVA is used to pickup the best captures first by selection sort and
  29  * next we try the killer moves (stored near the beginning of the moves array)
  30  * before the bad captures. Which are none by the way with MVV/LVA but in
  31  * the future SEE will be used for that.
  32  *
  33  * Finally when there is no captures left and no cut-off occurred we generate
  34  * the remaining quiets moves and try them with no particular order.
  35  */
  36 ExtendedMove Moves::next()
  37 {
  38     if (!use_lazy_generation) {
  39         if (i == 0) generate(); // generate() will change the value of 'n'
  40
  41         if (i == n) return ExtendedMove();
  42         return moves[i++];
  43     }
  44
  45     switch (state) {
  46         case BEST:
  47             if (i < size[BEST]) return moves[i++];
  48             state = GOOD_CAPTURES;
  49             generate(CAPTURE);
  50             i = size[BEST] + size[KILLERS]; // Jump to the first good capture
  51         case GOOD_CAPTURES:
  52             if (i < (size[BEST] + size[KILLERS] + size[GOOD_CAPTURES])) break;
  53             state = KILLERS;
  54             i = size[BEST]; // Jump to the first killer
  55         case KILLERS:
  56             if (i < (size[BEST] + size[KILLERS])) return moves[i++];
  57             state = BAD_CAPTURES;
  58             i = size[BEST] + size[KILLERS] + size[GOOD_CAPTURES];
  59         case BAD_CAPTURES:
  60             if (i < n) break;
  61             state = QUIET_MOVES;
  62             generate(QUIET_MOVE);
  63         case QUIET_MOVES:
  64             if (i < n) return moves[i++];
  65         default:
  66             return ExtendedMove();
  67     }
  68
  69     // If we are here, next() should return a capture
  70     // FIXME: the two conditions are identical
  71     assert(state == GOOD_CAPTURES || state == GOOD_CAPTURES);
  72
  73     // Find the best remaining capture by selection sort
  74     auto max = i;
  75     for (auto j = i + 1; j < n; ++j) {
  76         if (moves[j].get_score() > moves[max].get_score()) {
  77             max = j;
  78         }
  79     }
  80
  81     // Swap it with the current one
  82     if (max != i) {
  83         ExtendedMove tmp = std::move(moves[i]);
  84         moves[i] = std::move(moves[max]);
  85         moves[max] = std::move(tmp);
  86     }
  87
  88     // Return it
  89     return moves[i++];
  90 }
  91
  92 void Moves::add(Move move, MovesState mt)
  93 {
  94     if (!use_lazy_generation) {
  95         moves[n++] = ExtendedMove(move, 0);
  96         return;
  97     }
  98
  99     if (move.is_null()) return;
 100
 101     // Don't add again best and killer moves
 102     auto end = size[BEST] + size[KILLERS];
 103     for (auto j = 0; j < end; ++j) if (moves[j] == move) return;
 104
 105     // Calculate the move's score
 106     Score score = 0;
 107     switch (mt) {
 108         case BEST:
 109             score = BEST_SCORE;
 110             size[mt]++;
 111             break;
 112         case KILLERS:
 113             score = KILLERS_SCORE - size[KILLERS];
 114             size[mt]++;
 115             break;
 116         default:
 117             //assert(state > KILLERS);
 118             //size[state]++; // If move is a capture or a quiet move
 119             break;
 120     }
 121     switch (state) {
 122         case GOOD_CAPTURES:
 123         case BAD_CAPTURES:
 124             score = get_mvv_lva_score(move);
 125             size[state]++;
 126             break;
 127         case QUIET_MOVES:
 128             score = -BEST_SCORE;
 129             size[state]++;
 130             break;
 131         default:
 132             //assert(mt < GOOD_CAPTURES);
 133             //size[mt]++; // If move is a best or killer move
 134             break;
 135     }
 136
 137     // Add the move and its score to moves list
 138     moves[n++] = ExtendedMove(move, score);
 139 }
 140
 141 Score Moves::mvv_lva_scores[][NB_PIECE_TYPES] = { { 0 } };
 142
 143 /*
 144  * PxK = 94,  NxK = 92,  BxK = 90,  RxK = 88,  QxK = 86,  KxK = 84,  PxQ = 78,
 145  * NxQ = 76,  BxQ = 74,  RxQ = 72,  QxQ = 70,  KxQ = 68,  PxR = 62,  NxR = 60,
 146  * BxR = 58,  RxR = 56,  QxR = 54,  KxR = 52,  PxB = 46,  NxB = 44,  BxB = 42,
 147  * RxB = 40,  QxB = 38,  KxB = 36,  PxN = 30,  NxN = 28,  BxN = 26,  RxN = 24,
 148  * QxN = 22,  KxN = 20,  PxP = 14,  NxP = 12,  BxP = 10,  RxP =  8,  QxP =  6,
 149  * KxP =  4
 150  */
 151 void Moves::init_mvv_lva_scores()
 152 {
 153     for (const PieceType& v : PIECE_TYPES) {
 154         for (const PieceType& a : PIECE_TYPES) {
 155             mvv_lva_scores[v][a] = (16 * v) - (2 * a);
 156         }
 157     }
 158 }
 159
 160 Score Moves::get_mvv_lva_score(Move move)
 161 {
 162     assert(move.is_capture());
 163     PieceType a = board.get_piece(move.get_orig()).get_type();
 164     PieceType v = board.get_piece(move.get_dest()).get_type();
 165     if (move.is_en_passant()) return mvv_lva_scores[PAWN][a];
 166     return mvv_lva_scores[v][a];
 167 }