X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.h;h=317a0fc9165beed06c70d777f2f59f67fc26fc8b;hp=af34711df40e15e6892b748ff9e1cf9409d91c08;hb=b40e45c1cc51bd228898314264d6d241478b23d8;hpb=cf8ee79b767771bfb9c0ad06de1362400ea0ee5d diff --git a/src/movepick.h b/src/movepick.h index af34711d..afd573ea 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -1,114 +1,124 @@ /* - Glaurung, a UCI chess playing engine. - Copyright (C) 2004-2008 Tord Romstad + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2017 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad - Glaurung is free software: you can redistribute it and/or modify + Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. - - Glaurung is distributed in the hope that it will be useful, + + Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with this program. If not, see . */ - -#if !defined MOVEPICK_H_INCLUDED +#ifndef MOVEPICK_H_INCLUDED #define MOVEPICK_H_INCLUDED -//// -//// Includes -//// +#include -#include "depth.h" -#include "lock.h" +#include "movegen.h" #include "position.h" +#include "types.h" +/// StatBoards is a generic 2-dimensional array used to store various statistics +template +struct StatBoards : public std::array, Size1> { -//// -//// Types -//// + void fill(const T& v) { + T* p = &(*this)[0][0]; + std::fill(p, p + sizeof(*this) / sizeof(*p), v); + } +}; -/// MovePicker is a class which is used to pick one legal move at a time from -/// the current position. It is initialized with a Position object and a few -/// moves we have reason to believe are good. The most important method is -/// MovePicker::pick_next_move(), which returns a new legal move each time it -/// is called, until there are no legal moves left, when MOVE_NONE is returned. -/// In order to improve the efficiency of the alpha beta algorithm, MovePicker -/// attempts to return the moves which are most likely to be strongest first. +/// ButterflyBoards are 2 tables (one for each color) indexed by the move's from +/// and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards +typedef StatBoards ButterflyBoards; -class MovePicker { +/// PieceToBoards are addressed by a move's [piece][to] information +typedef StatBoards PieceToBoards; -public: +/// ButterflyHistory records how often quiet moves have been successful or +/// unsuccessful during the current search, and is used for reduction and move +/// ordering decisions. It uses ButterflyBoards as backing store. +struct ButterflyHistory : public ButterflyBoards { - enum MovegenPhase { - PH_TT_MOVE, // Transposition table move - PH_MATE_KILLER, // Mate killer from the current ply - PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= 0 - PH_BAD_CAPTURES, // Queen promotions and captures with SEE valuse <= 0 - PH_KILLER_1, // Killer move 1 from the current ply (not used yet). - PH_KILLER_2, // Killer move 2 from the current ply (not used yet). - PH_NONCAPTURES, // Non-captures and underpromotions - PH_EVASIONS, // Check evasions - PH_QCAPTURES, // Captures in quiescence search - PH_QCHECKS, // Checks in quiescence search - PH_STOP - }; - - MovePicker(const Position& p, bool pvnode, Move ttm, Move mk, Move k1, Move k2, Depth d); - Move get_next_move(); - Move get_next_move(Lock &lock); - int number_of_moves() const; - int current_move_score() const; - MovegenPhase current_move_type() const; - Bitboard discovered_check_candidates() const; - - static void init_phase_table(); + void update(Color c, Move m, int bonus) { -private: - void score_captures(); - void score_noncaptures(); - void score_evasions(); - void score_qcaptures(); - Move pick_move_from_list(); - int find_best_index(); - - const Position& pos; - Move ttMove, mateKiller, killer1, killer2; - Bitboard pinned, dc; - MoveStack moves[256], badCaptures[64]; - bool pvNode; - Depth depth; - int phaseIndex; - int numOfMoves, numOfBadCaptures; - int movesPicked, badCapturesPicked; - bool finished; + const int D = 324; + auto& entry = (*this)[c][from_to(m)]; + + assert(abs(bonus) <= D); // Consistency check for below formula + + entry += bonus * 32 - entry * abs(bonus) / D; + + assert(abs(entry) <= 32 * D); + } +}; + +/// PieceToHistory is like ButterflyHistory, but is based on PieceToBoards +struct PieceToHistory : public PieceToBoards { + + void update(Piece pc, Square to, int bonus) { + + const int D = 936; + auto& entry = (*this)[pc][to]; + + assert(abs(bonus) <= D); // Consistency check for below formula + + entry += bonus * 32 - entry * abs(bonus) / D; + + assert(abs(entry) <= 32 * D); + } }; +/// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous +/// move, see chessprogramming.wikispaces.com/Countermove+Heuristic +typedef StatBoards CounterMoveHistory; -//// -//// Inline functions -//// +/// ContinuationHistory is the history of a given pair of moves, usually the +/// current one given a previous one. History table is based on PieceToBoards +/// instead of ButterflyBoards. +typedef StatBoards ContinuationHistory; -/// MovePicker::number_of_moves() simply returns the numOfMoves member -/// variable. It is intended to be used in positions where the side to move -/// is in check, for detecting checkmates or situations where there is only -/// a single reply to check. -inline int MovePicker::number_of_moves() const { - return numOfMoves; -} +/// MovePicker class is used to pick one pseudo legal move at a time from the +/// current position. The most important method is next_move(), which returns a +/// new pseudo legal move each time it is called, until there are no moves left, +/// when MOVE_NONE is returned. In order to improve the efficiency of the alpha +/// beta algorithm, MovePicker attempts to return the moves which are most likely +/// to get a cut-off first. -/// MovePicker::discovered_check_candidates() returns a bitboard containing -/// all pieces which can possibly give discovered check. This bitboard is -/// computed by the constructor function. +class MovePicker { +public: + MovePicker(const MovePicker&) = delete; + MovePicker& operator=(const MovePicker&) = delete; + MovePicker(const Position&, Move, Value); + MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Square); + MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Move, Move*); + Move next_move(bool skipQuiets = false); + +private: + template void score(); + ExtMove* begin() { return cur; } + ExtMove* end() { return endMoves; } -inline Bitboard MovePicker::discovered_check_candidates() const { - return dc; -} + const Position& pos; + const ButterflyHistory* mainHistory; + const PieceToHistory** contHistory; + Move ttMove, countermove, killers[2]; + ExtMove *cur, *endMoves, *endBadCaptures; + int stage; + Square recaptureSquare; + Value threshold; + Depth depth; + ExtMove moves[MAX_MOVES]; +}; -#endif // !defined(MOVEPICK_H_INCLUDED) +#endif // #ifndef MOVEPICK_H_INCLUDED