src/moves.cpp

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