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 (cur == 0) generate(); // generate() will change the value of 'n'
  42
  43         if (cur == end) return ExtendedMove();
  44         return moves[cur++];
  45     }
  46
  47     switch (generation_state) {
  48         case BEST:
  49             if (cur < size[BEST]) {
  50                 return moves[cur++];
  51             }
  52             generation_state = GOOD_CAPTURES;
  53             generate(CAPTURE);
  54             cur = size[BEST] + size[KILLERS]; // Jump to first good capture
  55         case GOOD_CAPTURES:
  56             if (cur < (size[BEST] + size[KILLERS] + size[GOOD_CAPTURES])) {
  57                 break;
  58             }
  59             generation_state = KILLERS;
  60             cur = size[BEST]; // Jump to the first killer
  61         case KILLERS:
  62             if (cur < (size[BEST] + size[KILLERS])) {
  63                 return moves[cur++];
  64             }
  65             generation_state = BAD_CAPTURES;
  66             cur = size[BEST] + size[KILLERS] + size[GOOD_CAPTURES];
  67         case BAD_CAPTURES:
  68             if (cur < end) {
  69                 break;
  70             }
  71             generation_state = QUIET_MOVES;
  72             generate(QUIET_MOVE);
  73         case QUIET_MOVES:
  74             if (cur < end) {
  75                 return moves[cur++];
  76             }
  77         default:
  78             return ExtendedMove();
  79     }
  80
  81     // If we are here, next() should return a capture
  82     assert(state() == GOOD_CAPTURES || state() == BAD_CAPTURES);
  83
  84     // Find the best remaining capture by selection sort
  85     int max = cur;
  86     for (int i = cur + 1; i < end; ++i) {
  87         if (moves[i].value() > moves[max].value()) {
  88             max = i;
  89         }
  90     }
  91
  92     // Swap it with the current one
  93     if (max != cur) {
  94         ExtendedMove tmp = std::move(moves[cur]);
  95         moves[cur] = std::move(moves[max]);
  96         moves[max] = std::move(tmp);
  97     }
  98
  99     // Return it
 100     return moves[cur++];
 101 }
 102
 103 void Moves::add(Move move, MovesState mt)
 104 {
 105     if (!use_lazy_generation) {
 106         moves[end++] = ExtendedMove(move, 0);
 107         return;
 108     }
 109
 110     if (move.is_null()) return;
 111
 112     // Don't add again best and killer moves
 113     const int n = size[BEST] + size[KILLERS];
 114     for (int i = 0; i < n; ++i) if (moves[i] == move) return;
 115
 116     // Calculate the move's score
 117     Score score = 0;
 118     switch (mt) {
 119         case BEST:
 120             score = BEST_SCORE;
 121             size[mt]++;
 122             break;
 123         case KILLERS:
 124             score = KILLERS_SCORE - size[KILLERS];
 125             size[mt]++;
 126             break;
 127         default:
 128             //assert(generation_state > KILLERS);
 129             //size[generation_state]++; // If move is a capture or a quiet move
 130             break;
 131     }
 132     switch (generation_state) {
 133         case GOOD_CAPTURES:
 134         case BAD_CAPTURES:
 135             score = mvv_lva_score(move);
 136             size[generation_state]++;
 137             break;
 138         case QUIET_MOVES:
 139             score = -BEST_SCORE;
 140             size[generation_state]++;
 141             break;
 142         default:
 143             //assert(mt < GOOD_CAPTURES);
 144             //size[mt]++; // If move is a best or killer move
 145             break;
 146     }
 147
 148     // Add the move and its score to moves list
 149     moves[end++] = ExtendedMove(move, score);
 150 }
 151
 152 Score Moves::mvv_lva_scores[][NB_PIECE_TYPES] = { { 0 } };
 153
 154 /*
 155  * PxK = 94,  NxK = 92,  BxK = 90,  RxK = 88,  QxK = 86,  KxK = 84,  PxQ = 78,
 156  * NxQ = 76,  BxQ = 74,  RxQ = 72,  QxQ = 70,  KxQ = 68,  PxR = 62,  NxR = 60,
 157  * BxR = 58,  RxR = 56,  QxR = 54,  KxR = 52,  PxB = 46,  NxB = 44,  BxB = 42,
 158  * RxB = 40,  QxB = 38,  KxB = 36,  PxN = 30,  NxN = 28,  BxN = 26,  RxN = 24,
 159  * QxN = 22,  KxN = 20,  PxP = 14,  NxP = 12,  BxP = 10,  RxP =  8,  QxP =  6,
 160  * KxP =  4
 161  */
 162 void Moves::init_mvv_lva_scores()
 163 {
 164     for (const PieceType& v : PIECE_TYPES) {
 165         for (const PieceType& a : PIECE_TYPES) {
 166             mvv_lva_scores[v][a] = (16 * v) - (2 * a);
 167         }
 168     }
 169 }
 170
 171 Score Moves::mvv_lva_score(Move move)
 172 {
 173     assert(move.is_capture());
 174     PieceType a = board[move.orig()].type();
 175     PieceType v = board[move.dest()].type();
 176     if (move.is_en_passant()) return mvv_lva_scores[PAWN][a];
 177     return mvv_lva_scores[v][a];
 178 }