From 0ae9d6de3ae1337a831511d7dadeeebd01eada2a Mon Sep 17 00:00:00 2001 From: Fabian Fichter Date: Sat, 12 Jan 2019 18:48:31 +0100 Subject: [PATCH] Refactor game end detection Support customization of n-fold repetition and n-move rule. - Fix fourfold rule for minishogi and other shogi variants. - Adjust n-move rule to 70 for shatranj. - Disable n-move rule for makruk and shogi variants. --- src/evaluate.cpp | 2 +- src/movegen.cpp | 2 +- src/position.cpp | 120 +++++++++++++++++++++++++++++++++++++++++++++-------- src/position.h | 90 +++++++++------------------------------- src/search.cpp | 18 ++++----- src/variant.cpp | 15 +++++-- src/variant.h | 4 ++ 7 files changed, 146 insertions(+), 105 deletions(-) diff --git a/src/evaluate.cpp b/src/evaluate.cpp index a607a08..7c1784b 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -1024,7 +1024,7 @@ namespace { Value Evaluation::value() { assert(!pos.checkers()); - assert(!pos.is_variant_end()); + assert(!pos.is_immediate_game_end()); // Probe the material hash table me = Material::probe(pos); diff --git a/src/movegen.cpp b/src/movegen.cpp index 19834bd..18fb999 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -476,7 +476,7 @@ ExtMove* generate(const Position& pos, ExtMove* moveList) { template<> ExtMove* generate(const Position& pos, ExtMove* moveList) { - if (pos.is_variant_end()) + if (pos.is_immediate_game_end()) return moveList; ExtMove* cur = moveList; diff --git a/src/position.cpp b/src/position.cpp index e5828ee..9922efc 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -1539,31 +1539,115 @@ bool Position::see_ge(Move m, Value threshold) const { } -/// Position::is_draw() tests whether the position is drawn by 50-move rule -/// or by repetition. It does not detect stalemates. +/// Position::is_optinal_game_end() tests whether the position may end the game by +/// 50-move rule, by repetition, or a variant rule that allows a player to claim a game result. -bool Position::is_draw(int ply) const { +bool Position::is_optional_game_end(Value& result, int ply) const { - if (st->rule50 > 99 && (!checkers() || MoveList(*this).size())) + // n-move rule + if (n_move_rule() && st->rule50 > (2 * n_move_rule() - 1) && (!checkers() || MoveList(*this).size())) + { + result = VALUE_DRAW; return true; + } - int end = captures_to_hand() ? st->pliesFromNull : std::min(st->rule50, st->pliesFromNull); + // n-fold repetition + if (n_fold_rule()) + { + int end = captures_to_hand() ? st->pliesFromNull : std::min(st->rule50, st->pliesFromNull); - if (end < 4) - return false; + if (end < 4) + return false; - StateInfo* stp = st->previous->previous; - int cnt = 0; + StateInfo* stp = st->previous->previous; + int cnt = 0; - for (int i = 4; i <= end; i += 2) - { - stp = stp->previous->previous; + for (int i = 4; i <= end; i += 2) + { + stp = stp->previous->previous; + + // Return a draw score if a position repeats once earlier but strictly + // after the root, or repeats twice before or at the root. + if ( stp->key == st->key + && ++cnt + 1 == (ply > i ? 2 : n_fold_rule())) + { + result = convert_mate_value(var->nFoldValueAbsolute && sideToMove == BLACK ? -var->nFoldValue : var->nFoldValue, ply); + return true; + } + } + } + + return false; +} + +/// Position::is_immediate_game_end() tests whether the position ends the game +/// immediately by a variant rule, i.e., there are no more legal moves. +/// It does not not detect stalemates. - // Return a draw score if a position repeats once earlier but strictly - // after the root, or repeats twice before or at the root. - if ( stp->key == st->key - && ++cnt + (ply > i) == 2) - return true; +bool Position::is_immediate_game_end(Value& result, int ply) const { + + // bare king rule + if ( bare_king_value() != VALUE_NONE + && !bare_king_move() + && !(count(sideToMove) - count(sideToMove))) + { + result = bare_king_value(ply); + return true; + } + if ( bare_king_value() != VALUE_NONE + && bare_king_move() + && !(count(~sideToMove) - count(~sideToMove))) + { + result = -bare_king_value(ply); + return true; + } + // extinction + if (extinction_value() != VALUE_NONE) + { + for (PieceType pt : extinction_piece_types()) + if (!count(WHITE, pt) || !count(BLACK, pt)) + { + result = !count(sideToMove, pt) ? extinction_value(ply) : -extinction_value(ply); + return true; + } + } + // capture the flag + if ( capture_the_flag_piece() + && !flag_move() + && (capture_the_flag(~sideToMove) & pieces(~sideToMove, capture_the_flag_piece()))) + { + result = mated_in(ply); + return true; + } + if ( capture_the_flag_piece() + && flag_move() + && (capture_the_flag(sideToMove) & pieces(sideToMove, capture_the_flag_piece()))) + { + result = (capture_the_flag(~sideToMove) & pieces(~sideToMove, capture_the_flag_piece())) + && sideToMove == WHITE ? VALUE_DRAW : mate_in(ply); + return true; + } + // nCheck + if (max_check_count() && st->checksGiven[~sideToMove] == max_check_count()) + { + result = mated_in(ply); + return true; + } + // Connect-n + if (connect_n() > 0) + { + Bitboard b; + for (Direction d : {NORTH, NORTH_EAST, EAST, SOUTH_EAST}) + { + b = pieces(~sideToMove); + for (int i = 1; i < connect_n() && b; i++) + b &= shift(d, b); + if (b) + { + result = mated_in(ply); + return true; + } + } } return false; @@ -1608,7 +1692,7 @@ bool Position::has_game_cycle(int ply) const { int end = std::min(st->rule50, st->pliesFromNull); - if (end < 3) + if (end < 3 || var->nFoldValue != VALUE_DRAW) return false; Key originalKey = st->key; diff --git a/src/position.h b/src/position.h index c351f86..d05ffc0 100644 --- a/src/position.h +++ b/src/position.h @@ -124,6 +124,8 @@ public: bool shogi_doubled_pawn() const; bool immobility_illegal() const; // winning conditions + int n_move_rule() const; + int n_fold_rule() const; Value stalemate_value(int ply = 0) const; Value checkmate_value(int ply = 0) const; Value bare_king_value(int ply = 0) const; @@ -136,8 +138,6 @@ public: CheckCount max_check_count() const; int connect_n() const; CheckCount checks_given(Color c) const; - bool is_variant_end() const; - bool is_variant_end(Value& result, int ply = 0) const; // Variant-specific properties int count_in_hand(Color c, PieceType pt) const; @@ -217,7 +217,10 @@ public: int game_ply() const; bool is_chess960() const; Thread* this_thread() const; - bool is_draw(int ply) const; + bool is_immediate_game_end() const; + bool is_game_end(Value& result, int ply = 0) const; + bool is_optional_game_end(Value& result, int ply = 0) const; + bool is_immediate_game_end(Value& result, int ply = 0) const; bool has_game_cycle(int ply) const; bool has_repeated() const; int rule50_count() const; @@ -461,6 +464,16 @@ inline bool Position::immobility_illegal() const { return var->immobilityIllegal; } +inline int Position::n_move_rule() const { + assert(var != nullptr); + return var->nMoveRule; +} + +inline int Position::n_fold_rule() const { + assert(var != nullptr); + return var->nFoldRule; +} + inline Value Position::stalemate_value(int ply) const { assert(var != nullptr); return convert_mate_value(var->stalemateValue, ply); @@ -552,76 +565,13 @@ inline CheckCount Position::checks_given(Color c) const { return st->checksGiven[c]; } -inline bool Position::is_variant_end() const { +inline bool Position::is_immediate_game_end() const { Value result; - return is_variant_end(result); + return is_immediate_game_end(result); } -inline bool Position::is_variant_end(Value& result, int ply) const { - // bare king rule - if ( bare_king_value() != VALUE_NONE - && !bare_king_move() - && !(count(sideToMove) - count(sideToMove))) - { - result = bare_king_value(ply); - return true; - } - if ( bare_king_value() != VALUE_NONE - && bare_king_move() - && !(count(~sideToMove) - count(~sideToMove))) - { - result = -bare_king_value(ply); - return true; - } - // extinction - if (extinction_value() != VALUE_NONE) - { - for (PieceType pt : extinction_piece_types()) - if (!count(WHITE, pt) || !count(BLACK, pt)) - { - result = !count(sideToMove, pt) ? extinction_value(ply) : -extinction_value(ply); - return true; - } - } - // capture the flag - if ( capture_the_flag_piece() - && !flag_move() - && (capture_the_flag(~sideToMove) & pieces(~sideToMove, capture_the_flag_piece()))) - { - result = mated_in(ply); - return true; - } - if ( capture_the_flag_piece() - && flag_move() - && (capture_the_flag(sideToMove) & pieces(sideToMove, capture_the_flag_piece()))) - { - result = (capture_the_flag(~sideToMove) & pieces(~sideToMove, capture_the_flag_piece())) - && sideToMove == WHITE ? VALUE_DRAW : mate_in(ply); - return true; - } - // nCheck - if (max_check_count() && st->checksGiven[~sideToMove] == max_check_count()) - { - result = mated_in(ply); - return true; - } - // Connect-n - if (connect_n() > 0) - { - Bitboard b; - for (Direction d : {NORTH, NORTH_EAST, EAST, SOUTH_EAST}) - { - b = pieces(~sideToMove); - for (int i = 1; i < connect_n() && b; i++) - b &= shift(d, b); - if (b) - { - result = mated_in(ply); - return true; - } - } - } - return false; +inline bool Position::is_game_end(Value& result, int ply) const { + return is_immediate_game_end(result, ply) || is_optional_game_end(result, ply); } inline Color Position::side_to_move() const { diff --git a/src/search.cpp b/src/search.cpp index 5411834..c21f317 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -204,7 +204,7 @@ void MainThread::search() { rootMoves.emplace_back(MOVE_NONE); Value variantResult; sync_cout << "info depth 0 score " - << UCI::value( rootPos.is_variant_end(variantResult) ? variantResult + << UCI::value( rootPos.is_game_end(variantResult) ? variantResult : rootPos.checkers() ? rootPos.checkmate_value() : rootPos.stalemate_value()) << sync_endl; } @@ -568,12 +568,11 @@ namespace { if (!rootNode) { Value variantResult; - if (pos.is_variant_end(variantResult, ss->ply)) + if (pos.is_game_end(variantResult, ss->ply)) return variantResult; // Step 2. Check for aborted search and immediate draw if ( Threads.stop.load(std::memory_order_relaxed) - || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW; @@ -1243,14 +1242,13 @@ moves_loop: // When in check, search starts from here inCheck = pos.checkers(); moveCount = 0; - Value variantResult; - if (pos.is_variant_end(variantResult, ss->ply)) - return variantResult; + Value gameResult; + if (pos.is_game_end(gameResult, ss->ply)) + return gameResult; - // Check for an immediate draw or maximum ply reached - if ( pos.is_draw(ss->ply) - || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW; + // Check for maximum ply reached + if (ss->ply >= MAX_PLY) + return !inCheck ? evaluate(pos) : VALUE_DRAW; assert(0 <= ss->ply && ss->ply < MAX_PLY); diff --git a/src/variant.cpp b/src/variant.cpp index 73f76fb..84260f5 100644 --- a/src/variant.cpp +++ b/src/variant.cpp @@ -46,6 +46,7 @@ VariantMap variants; // Global object v->promotionPieceTypes = {MET}; v->doubleStep = false; v->castling = false; + v->nMoveRule = 0; return v; } Variant* asean_variant() { @@ -81,6 +82,7 @@ VariantMap variants; // Global object v->bareKingValue = -VALUE_MATE; v->bareKingMove = true; v->stalemateValue = -VALUE_MATE; + v->nMoveRule = 70; return v; } Variant* amazon_variant() { @@ -238,10 +240,9 @@ VariantMap variants; // Global object v->immobilityIllegal = false; return v; } - Variant* minishogi_variant() { + Variant* minishogi_variant_base() { Variant* v = fairy_variant_base(); v->variantTemplate = "shogi"; - v->pocketSize = 5; v->maxRank = RANK_5; v->maxFile = FILE_E; v->reset_pieces(); @@ -268,11 +269,15 @@ VariantMap variants; // Global object v->immobilityIllegal = true; v->shogiPawnDropMateIllegal = true; v->stalemateValue = -VALUE_MATE; + v->nFoldRule = 4; + v->nMoveRule = 0; return v; } - Variant* minishogi_variant_base() { - Variant* v = minishogi_variant(); - v->pocketSize = 0; + Variant* minishogi_variant() { + Variant* v = minishogi_variant_base(); + v->pocketSize = 5; + v->nFoldValue = -VALUE_MATE; + v->nFoldValueAbsolute = true; return v; } Variant* kyotoshogi_variant() { diff --git a/src/variant.h b/src/variant.h index 537a608..cd7421f 100644 --- a/src/variant.h +++ b/src/variant.h @@ -69,6 +69,10 @@ struct Variant { bool shogiDoubledPawn = true; bool immobilityIllegal = false; // game end + int nMoveRule = 50; + int nFoldRule = 3; + Value nFoldValue = VALUE_DRAW; + bool nFoldValueAbsolute = false; Value stalemateValue = VALUE_DRAW; Value checkmateValue = -VALUE_MATE; bool shogiPawnDropMateIllegal = false; -- 1.7.0.4