Проблема реализации альфа-бета обрезки для шахматного движка

Недавно я работал над шахматным движком и готов внедрить какой-нибудь ИИ, чтобы реально играть в игру (поиск позиций). Я написал алгоритм сокращения альфа-бета, но он не возвращает лучшие ходы, когда я его тестирую.

Код для альфа-бета-поиска:

float Search::alphabeta(S_BOARD* pos, S_SEARCHINFO *info, int depth, float alpha, float beta){
if (depth == 0) {
    info->nodes++;
    return eval::staticEval(pos);
}

info->nodes++;

S_MOVELIST list;
MoveGeneration::validMoves(pos, list);

float value = 0;
S_MOVE bestMove;
bestMove.move = NOMOVE;
bestMove.score = 0;

float prevBound = (pos->whitesMove == WHITE) ? alpha : beta;

int pvMove = TT::probeMove(pos);
if (pvMove != NOMOVE) {
    for (int i = 0; i < list.count; i++) {
        if (list.moves[i].move == pvMove) {
            list.moves[i].score = 20000000;
            break;
        }
    }
}


if (pos->whitesMove == WHITE) {
    value = -INFINITE;
    for (int moveNum = 0; moveNum < list.count; moveNum++) {
        pickNextMove(moveNum, &list);
        MoveGeneration::makeMove(*pos, list.moves[moveNum].move);

        value = max(value, alphabeta(pos, info, depth - 1, alpha, beta));

        MoveGeneration::undoMove(*pos);

        if (value > alpha) {
            if (value >= beta) {
                if (moveNum == 0) {
                    info->fhf++;
                }
                info->fh++;
                break;
            }
            alpha = value;
            bestMove = list.moves[moveNum];

        }

    }

    if (pos->is_checkmate) {
        return -MATE + pos->ply;
    }
    else if (pos->is_stalemate) {
        return 0;
    }

    if (alpha != prevBound) {
        TT::storePvMove(pos, bestMove);
    }

    return value;
}

else {
    value = INFINITE;

    for (int moveNum = 0; moveNum < list.count; moveNum++) {
        pickNextMove(moveNum, &list);
        MoveGeneration::makeMove(*pos, list.moves[moveNum].move);

        value = min(value, alphabeta(pos, info, depth - 1, alpha, beta));

        MoveGeneration::undoMove(*pos);

        if (value < beta){
            if (beta <= alpha) {
                if (moveNum == 0) {
                    info->fhf++;
                }
                info->fh++;
                break;
            }
            beta = value;
            bestMove = list.moves[moveNum];
        }


    }

    if (pos->is_checkmate) {
        return MATE - pos->ply;
    }
    else if (pos->is_stalemate) {
        return 0;
    }

    if (beta != prevBound) {
        TT::storePvMove(pos, bestMove);
    }

    return value;
}

(MoveGeneration — это пространство имен, так что проблем с вызовом функций вне экземпляров объекта не возникает.)

Я запускаю функцию внутри итеративной функции углубления, которая выглядит следующим образом:

float Search::searchPosition(S_BOARD* pos, S_SEARCHINFO *info){

clearForSearch(pos, info);
float score = -INFINITE;
int bestMove = NOMOVE;
int pvMoves = 0;

// Iterative deepening.
for (int currDepth = 1; currDepth <= info->depth; currDepth++){
    auto start = std::chrono::high_resolution_clock::now();
    score = alphabeta(pos, info, currDepth, -INFINITE, INFINITE);
    auto end = std::chrono::high_resolution_clock::now();
    pvMoves = TT::getPvLine(pos, currDepth);
    bestMove = pos->pvArray[0];
    
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "[+] Depth: " << currDepth << " score: " << score << " move: " << printMove(bestMove)
    << " nodes: " << info->nodes << " kN/s: " << (info->nodes/elapsed.count())/1000 << std::endl;
    
    std::cout << "pv";
    for (int i = 0; i < pvMoves; i++){
        std::cout << " " << printMove(pos->pvArray[i]);
    }
    std::cout << std::endl;
    
    std::cout << "Ordering: " << info->fhf/info->fh << std::endl;
    
}


return score;}

Может ли кто-нибудь помочь мне, указав на возможные ошибки, которые я сделал?

Спасибо за вашу помощь, и просто скажите мне, нужно ли мне загрузить больше моего кода.


person BimmerBass    schedule 02.10.2020    source источник


Ответы (1)


он не возвращает ход, так как вы возвращаете только значение в нижней части вашей альфа/бета-функции. В исходном вызове поместите это:

move, score = alphabeta(pos, info, currDepth, -INFINITE, INFINITE);

В вашей глубине == 0, мат и пат вы возвращаетесь:

return None, eval

В конце ваших двух функций игрока (минимизация и максимизация игрока) вы возвращаете:

return move, value

Наконец, когда вы делаете рекурсивные вызовы из ваших двух функций игрока, вам нужно только получить значение. Я не уверен в вашем языке программирования, но, например. Python вы ставите [1] в конце, чтобы просто получить значение, а не ход, что-то вроде этого:

value = max(value, alphabeta(pos, info, depth - 1, alpha, beta))[1]
person eligolf    schedule 29.10.2020