Шахматный алгоритм 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. Затем я перебираю их и нахожу, у какого из этих дочерних элементов stateScore равен bestValue. Но это не сработает, потому что многие из них все равно будут иметь одинаковый stateScore, важно то, к чему они могут привести...


java algorithm alpha-beta-pruning negamax
person Community    schedule 02.09.2014    source источник
comment
возможный дубликат Как получить фактический ход, а не значение хода из алгоритма мини-макс   -  person David Eisenstat    schedule 02.09.2014

Ответы (1)


arrow_upward
3
arrow_downward

Я вижу, вы делаете 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(переместить) и p.undo(переместить)?

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

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

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

person SmallChess    schedule 02.09.2014
comment
о, да... Видите ли, я подумал, что если бы я использовал метод getChildren(), чтобы получить все возможные ходы, а затем применить каждый из этих ходов по очереди к копии состояния игры, а затем вернуть все эти возможные результирующие состояния игры , тогда мне не нужно было бы делать и отменять ходы в середине цикла. Я просто сильно ошибаюсь, думая, что могу просто перебрать все состояния матча и забить их? Будет ли это работать, если после рекурсивного вызова negamax будет вызов метода getParent()? - person ; 02.09.2014
comment
Кстати, каждый матч содержит список фигур на доске, а также 2d-массив, описывающий саму доску, который может меняться в ходе матча — так что это, по сути, просто объект Position с несколькими прибамбасами. . - person ; 02.09.2014