src/moves.cpp

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