How would Transposition Tables work with Hypermax?

Question

I was wondering if someone out there could help me understand how Transposition Tables could be incorporated into the Hypermax algorithm. Any examples, pseudo-code, tips, or implementation references would be much appreciated!

A little background:

Hypermax is a recursive game tree search algorithm used for n-player games, typically for 3+ players. It's an extension of minimax and alpha beta pruning.
Generally at each node in the game tree the current player (chooser) will look at all of the moves it can make and choose the one that maximizes it's own utility. Different than minimax / negamax.
I understand how transposition tables work, but I don't know how the values stored in them would be used to initiate cutoffs when a transposition table entry is found. A transposition flag is required in minimax with transposition & alpha-beta pruning. I can't seem to wrap my head around how that would be incorporated here.

Hypermax Algorithm without Transposition Tables in 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;
        }
    }
}

References:

An implementation of Hypermax without Transposition Tables: https://meatfighter.com/spotai/#references_2
Minimax (negamax variant) with alpha-beta pruning and transposition tables: https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning_and_transposition_tables
Original derivation and Proofs of Hypermax: http://uu.diva-portal.org/smash/get/diva2:761634/FULLTEXT01.pdf

Nathan S. Nathan S. · Accepted Answer · 2019-07-11T01:36:48

The question is quite broad, so this is a similarly broad answer - if there is something specific, please clarify what you don't understand.

Transposition tables are not guaranteed to be correct in multi-player games, but if you implement them carefully they can be. This is discussed briefly in this thesis:

Multi-Player Games, Algorithms and Approaches

To summarize, there are three things to note about transposition tables in multi-player game trees. First, they require that we be consistent with our node-ordering. Second, they can be less effective than in two-player games, due to the fact that it takes more moves for a transposition to occur. Finally, speculative pruning can benefit from transposition tables, as they can offset the cost of re-searching portions of the game tree.

Beyond ordering issues, you may need to store things like the depth of search underneath a branch, the next player to play, and the bounds used for pruning the subtree. If, for instance, you have different bounds for pruning a tree in your first search, you may not produce correct results in the second search.

HyperMax is only a slight variant of Max^n with speculative pruning, so you might want to look at that context to see if you can implement things in Max^n.

How would Transposition Tables work with Hypermax?

1 Answers