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  * MVV/LVA scores:
 156  *
 157  *     PxP =  7, PxN = 15, PxB = 23, PxR = 31, PxQ = 39, PxK = 47
 158  *     NxP =  6, NxN = 14, NxB = 22, NxR = 30, NxQ = 38, NxK = 46
 159  *     BxP =  5, BxN = 13, BxB = 21, BxR = 29, BxQ = 37, BxK = 45
 160  *     RxP =  4, RxN = 12, RxB = 20, RxR = 28, RxQ = 36, RxK = 44
 161  *     QxP =  3, QxN = 11, QxB = 19, QxR = 27, QxQ = 35, QxK = 43
 162  *     KxP =  2, KxN = 10, KxB = 18, KxR = 26, KxQ = 34, KxK = 42
 163  */
 164 void Moves::init_mvv_lva_scores()
 165 {
 166     for (const PieceType& a : PIECE_TYPES) {
 167         for (const PieceType& v : PIECE_TYPES) {
 168             mvv_lva_scores[a][v] = (8 * v) - a;
 169         }
 170     }
 171 }
 172
 173 Score Moves::mvv_lva_score(Move move)
 174 {
 175     assert(move.is_capture());
 176     PieceType a = board[move.orig()].type();
 177     PieceType v = move.is_en_passant() ? PAWN : board[move.dest()].type();
 178     return mvv_lva_scores[a][v];
 179 }