Шахматный алгоритм Negamax: как использовать финальный возврат?

Question

Я сделал алгоритм Negamax для шахматоподобной игры, и я хочу знать, как использовать итоговый результат на доске. Я понимаю, что окончательный результат алгоритма negamax показывает, какое значение получит доска после того, как игрок сделает свой лучший ход, но это не совсем полезная информация. Мне нужно знать, что это за шаг, а не то, чего он стоит.

Вот код:

public int negamax(Match match, int depth, int alpha, int beta, int color) {
    if(depth == 0) {
        return color*stateScore(match);
    }

    ArrayList<Match> matches = getChildren(match, color);

    if(matches.size() == 0) {
        return color*stateScore(match);
    }

    int bestValue = Integer.MIN_VALUE;

    for(int i = 0; i != matches.size(); i++) {
        int value = -negamax(matches.get(i), depth-1, -beta, -alpha, -color);

        if(value > bestValue) {
            bestValue = value;
        }

        if(value > alpha) {
            alpha = value;
        }

        if(alpha >= beta) {
            break;
        }
    }

    return bestValue;
}

public void getBestMove(Match match, int color) {

    int bestValue = negamax(match, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, color);

    // What to do with bestValue???

}

Я думал о переоценке дочерних элементов текущего состояния соответствия после определения bestValue. Затем я перебираю их и выясняю, у кого из этих детей оценка состояния равна bestValue. Но это не сработает, потому что многие из них в любом случае будут иметь одинаковые оценки состояния, это то, к чему они могут привести...

Answer 1

Я вижу, что вы делаете qsearch и альфа-бета. Ваш алгоритм хорошо известен, но вам не хватает ключевой части.

Позвольте мне набросать основной алгоритм поиска в шахматах, он применим даже к Stockfish (самый сильный движок в мире).

search(Position p) {

    if (leaf node)
        qsearch(p)

    if (need to do move reduction)
        do_move_reduction_and_cut_off(p)

    moves = generate_moves(p)

    for_each(move in moves) {            
        p.move(move)
        v = -search(p, -beta, -alpha)
        p.undo(move)

        store the score and move into a hash table

        if (v > beta)
           cutoff break;           
    }

Это просто очень короткий набросок, но все шахматные алгоритмы следуют ему. Сравните свою версию с ней, замечаете ли вы, что вы не сделали p.move (move) и p.undo(move)?

В основном, традиционный подход генерирует список ходов для данной позиции. Перебирайте ходы, играйте, отменяйте и ищите. Если вы делаете это, вы точно знаете, какой ход дает какой счет.

Также обратите внимание на строку для хранения хода и оценки в хэш-таблицу. Если вы сделаете это, вы можете легко восстановить весь основной вариант из корневого узла.

Я не знаю, что именно находится внутри вашего класса Java Match, но в любом случае ваша попытка была близкой, но не совсем классическим способом поиска. Помните, что вам нужно дать объект позиции в алгоритме поиска, но вместо этого вы дали ему объект Match, что неправильно.