Как будут работать таблицы транспозиции с Hypermax? - PullRequest
Новая
       13

Как будут работать таблицы транспозиции с Hypermax?

1 голос
/ 10 июля 2019

Мне было интересно, может ли кто-нибудь помочь мне понять, как Таблицы транспонирования могут быть включены в алгоритм Hypermax. Будем очень благодарны за любые примеры, псевдокод, советы или ссылки на реализацию!

Небольшой фон:

  • Hypermax - алгоритм поиска дерева рекурсивных игр, используемый для n-игрока. игры, как правило, для 3+ игроков. Это расширение минимакса и альфа-бета-обрезка.
  • Обычно на каждом узле в дереве игры текущий игрок (выборщик) будет смотреть на все ходы, которые он может сделать и выберите тот, который максимизирует его собственную полезность. Отличающийся от минимакс / негамакс.
  • Я понимаю, как работают таблицы транспозиции, но я не знаю, как значения, хранящиеся в них будут использоваться для инициирования обрезания при обнаружении записи таблицы транспозиции. Транспозиция Флаг требуется в минимаксе с транспонированием и альфа-бета-обрезкой. Я не могу обернуться вокруг того, как это будет включено здесь.

Алгоритм Hypermax без таблиц транспонирования в Javascript: 

/**
 * @param {*} state A game state object.
 * @param {number[]} alphaVector The alpha vector.
 * @returns {number[]} An array of utility values for each player.
 */
function hypermax(state, alphaVector) {
    // If terminal return the utilities for all of the players
    if (state.isTerminal()) {
        return state.calculateUtilities();
    }

    // Play out each move
    var moves = state.getLegalMoves();
    var bestUtilityVector = null;
    for (var i = 0; i < moves.length; ++i) {
        var move = moves[i];
        state.doMove(move);     // move to child state - updates game board and advances player 1
        var utilityVector = hypermax(state, alphaVector.slice(0));  // copy the alpha values down
        state.undoMove(move);   // return to this state - remove board updates and rollsback player 1

        // Select this as best utility if first found
        if (i === 0) {
            bestUtilityVector = utilityVector;
        }

        // Update alpha
        if (utilityVector[state.currentPlayer] > alpha[state.currentPlayer]) {
            alpha[state.currentPlayer] = utilities[state.currentPlayer];
            bestUtilities = utilityVector;
        }

        // Alpha prune
        var sum = 0;
        for (var j = 0; j < alphaVector.length; ++j) {
            sum += alpha[j];
        }
        if (sum >= 0) {
            break;
        }
    }
}

Ссылка:

1 Ответ

0 голосов
/ 11 июля 2019

Вопрос довольно широкий, так что это аналогично широкий ответ - если есть что-то конкретное, уточните, что вы не понимаете.

Таблицы транспонирования не гарантируются правильными в многопользовательских играх, но если вы их тщательно реализуете, они могут быть правильными. Это кратко обсуждается в этом тезисе:

Многопользовательские игры, алгоритмы и подходы

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

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

HyperMax - это всего лишь небольшой вариант Max ^ n с умозрительным сокращением, поэтому вы можете захотеть взглянуть на этот контекст и посмотреть, сможете ли вы реализовать вещи в Max ^ n.

...