Transposition Tables如何与Hypermax一起工作？

Question

我想知道是否有人可以帮助我理解如何将转换表合并到Hypermax算法中。任何示例、伪代码、技巧或实现参考都将不胜感激！

一点背景：

• Hypermax是一种递归游戏树搜索算法，用于n人游戏，通常用于3人游戏。它是最小最大和α-β修剪的扩展
• 通常，在游戏树中的每个节点，当前玩家（选择者）将查看其可以做出的所有移动，并选择一个最大化其自身效用的移动。不同于最小值/最大值
• 我理解换位表是如何工作的，但我不知道当找到换位表条目时，存储在其中的值将如何用于启动截断。带换位的minimax中需要换位标志

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;
        }
    }
}

引用：

• 不带换位表的Hypermax实现：https://meatfighter.com/spotai/#references_2
• 带α-β修剪和换位表的Minimax（negamax变量）：https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning_and_transposition_tables
• Hypermax的原始推导和证明：http://uu.diva-portal.org/smash/get/diva2:761634/FULLTEXT01.pdf

Answer 1

这个问题相当宽泛，所以这是一个同样宽泛的答案——如果有具体的东西，请澄清你不明白的地方。

在多人游戏中，不能保证转置表是正确的，但是如果你小心地实现它们，它们是正确的。本文对此进行了简要讨论:

多人游戏、算法和方法

总之，关于多玩家游戏树中的换位表，有三点需要注意。首先，他们要求我们与节点排序保持一致。第二，由于换位需要更多的动作，所以它们可能比两人游戏中的效果差。最后，投机修剪可以从换位表中受益，因为它们可以抵消重新搜索游戏树部分的成本。

除了排序问题之外，您可能需要在分支下方存储搜索深度、下一个要玩的玩家，以及用于修剪子树的边界。例如，如果您在第一次搜索中修剪树的边界不同，则在第二次搜索中可能不会产生正确的结果。

HyperMax只是Max^n的一个轻微变体，带有推测性修剪，因此您可能希望查看该上下文，看看是否可以在Max^n中实现某些内容。