用换位表改进Gomoku AI的极小极大算法？

Question

我正在为Gomoku（16x16）构建一个具有极大极小值和α-β修剪的AI，但速度非常慢。到目前为止，我已经尝试过对动作顺序进行预排序，而不是深度复制棋盘，添加和删除动作。此外，我还使用了相关移动的arraylist（距离已放置的块的半径在2以内）来减少搜索栏。然而，即使在3的深度搜索中，人工智能仍在苦苦挣扎<编辑：我发现了一个叫做换位表的东西，但我不知道从哪里开始。任何帮助都会很好！

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

Answer 1

下面是关于换位表工作原理的一个很好的解释：TT

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

一旦您有了转置表，就很容易添加更多依赖它的速度优化。