java - 用换位表改进Gomoku AI的minimax算法？

我正在使用minimax和alpha-beta修剪为Gomoku（16x16）构建AI，但是速度非常慢。到目前为止，我已经尝试过对移动的顺序进行预排序，而不是深入复制木板，而是添加并随后删除这些移动。另外，我使用相关移动的数组列表（半径在2以内的半径已放置的碎片）来缩小搜索板。然而，即使在深度搜索为3时，AI仍然仍在挣扎。
编辑：我发现了所谓的换位表，但我不知道从哪里开始。任何帮助将是巨大的！

private double minimax(Board node, String player, int depth, double lowerBound, double upperBound){
    if (depth==3){
        return node.evaluate();
    }

    if (player.equals(humanPiece)) {// min node
        // sort setup
        ArrayList<int[]> relevantMoves = node.relevantMoves();
        HashMap<int[], Double> moveValueTable = new HashMap<>();

        for (int[] move: relevantMoves){
            node.addMove(move[0], move[1], player);
            double val = node.evaluate();
            moveValueTable.put(move, val);
            node.retractMove(move[0], move[1]);
        }
        // insertion sort from small to big (alpha-beta optimization)
        insertionSort(relevantMoves, moveValueTable);
        result = Double.POSITIVE_INFINITY;
        // minimax
        for (int[] move : relevantMoves) {  // y first, x second
            node.addMove(move[0], move[1], player);
            double score = minimax(node, node.getEnemy(player), depth+1, lowerBound, upperBound);
            node.retractMove(move[0], move[1]);
            if (score < upperBound) {
                upperBound = score;
            }
            if (score < result) result = score;
            if (lowerBound > upperBound) {
                break;
            }
        }
        return result;
    }

    else{// max node
        // sort setup
        ArrayList<int[]> relevantMoves = node.relevantMoves();
        HashMap<int[], Double> moveValueTable = new HashMap<>();

        for (int[] move: relevantMoves){
            node.addMove(move[0], move[1], player);
            double val = node.evaluate();
            moveValueTable.put(move, val);
            node.retractMove(move[0], move[1]);
        }
        // insertion sort from big to small (alpha-beta optimization)
        reversedInsertionSort(relevantMoves, moveValueTable);
        result = Double.NEGATIVE_INFINITY;
        // minimax
        for (int[] move : relevantMoves) {  // y first, x second
            node.addMove(move[0], move[1], player);
            double score = minimax(node, node.getEnemy(player), depth+1, lowerBound, upperBound);
            node.retractMove(move[0], move[1]);
            if (score > lowerBound) {
                lowerBound = score;
            }
            if (score > result) result = score;
            if (lowerBound > upperBound) {
                break;
            }
        }
        return result;
    }
}

最佳答案

这是关于换位表如何工作的很好的解释：TT

通过从搜索树中消除转置，可以提高搜索速度。换位是可以通过两个或多个不同的移动序列获得的位置。有些游戏，例如国际象棋或西洋跳棋，具有大量的换位，而其他游戏则很少甚至没有。

一旦放置了转置表，就可以轻松添加更多依赖它的速度优化。

关于java - 用换位表改进Gomoku AI的minimax算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42970902/