Обнаружение троекратного повторения шахматного движка приводит к неправильной игре - PullRequest
Новая
       27

Обнаружение троекратного повторения шахматного движка приводит к неправильной игре

1 голос
/ 25 мая 2020

Я пытаюсь реализовать в своем шахматном движке обнаружение троекратного повторения, но используемый мной метод ведет к неправильной игре. Я проверяю одно повторение позиции в текущем пространстве поиска или два повторения «позади» root. Этот подход используется и Stockfi sh, но он делает мой движок слабее (рейтинг ELO значительно падает при тестировании).

Каждая позиция в истории игры имеет индекс zobrist ha sh.

Обнаружение троекратного повторения: 

 bool Eval::isThreefoldRepetition() const {
        const std::deque<GameState>&history=internal_board.getHistory();
        int repetitions=0;
        uint64_t hash=internal_board.getGameState().zobrist_key;

        for(int k=history.size()-2;k>=0;k-=2){
            if(history[k].zobrist_key==hash){
                if(k>=root)//found repetition in current search space
                    return true;
                //else we need 2 repetitions that happen before the root
                repetitions++;
                if(repetitions==2)
                    return  true;
            }
        }
        return  false;
    }

Поиск: 

 int Eval::negamax(int depth, int alpha, int beta, Color color) {

        if(isThreefoldRepetition())
            return threefold_repetition;

        uint64_t hash=internal_board.getGameState().zobrist_key;
        int alphaOrig=alpha;
        Transposition node=TranspositionTable::getInstance().getTransposition(hash);
        if(node.getType()!=NodeType::Null &&node.getDepth()>=depth){
            if(node.getType()==NodeType::Exact)
                return node.getValue();
            else if(node.getType()==NodeType::LowerBound)
                alpha=std::max(alpha,node.getValue());
            else if(node.getType()==NodeType::UpperBound)
                beta=std::min(beta,node.getValue());
            if(alpha>=beta)
                return node.getValue();
        }

        if (depth == 0) {
            return getHeuristicScore(color);
        }
        std::vector<Move> moves = movegen.getAllMoves();
        if (moves.size() == 0) {
            if (movegen.isInCheck(color))
                return checkmate - depth;//try to delay the checkmate
            return stalemate;
        }
        int best = -infinity;
        Move best_move;
        setRating(moves);
        std::sort(moves.begin(), moves.end(), compare);
        for (const Move &move:moves) {
            if(!hasTimeLeft()){
                premature_stop=true;
                break;
            }
            internal_board.makeMove(move);
            int down = -negamax(depth - 1, -beta, -alpha, getOpposite(color));
            internal_board.undoLastMove();
            if(down>best){
                best=down;
                best_move=move;
            }
            alpha = std::max(alpha, best);
            if (alpha >= beta)
                break;
        }

        if(!premature_stop) {
            //save the position in the transposition table
            NodeType node_type;
            if (best <= alphaOrig)//did not affect the score
                node_type = NodeType::UpperBound;
            else if (best >= beta)
                node_type = NodeType::LowerBound;
            else node_type = NodeType::Exact;
            TranspositionTable::getInstance().addEntry(Transposition(node_type, hash, depth, best, best_move));
        }
        return best;
    }

Обратите внимание, что я не могу проверить «реальное» тройное повторение, потому что позиция не будет повторяться трижды в области поиска при использовании таблиц транспонирования.

Мой метод оценки неверен?

...