使用极小极大搜索搜索不完全信息的纸牌游戏

Question

我想使用极小极大搜索（带有alpha-beta修剪），或者更确切地说是内极大搜索，来使计算机程序玩纸牌游戏。

纸牌游戏实际上由4个玩家组成。所以为了能够使用极小极大等等。，我把游戏简化为“我”对抗“别人”。每次“走位”后，你都可以从游戏本身客观地读出当前状态的评价。当所有4个玩家都放好牌后，最高的玩家赢得所有人，并且牌的价值也算在内。

由于您不知道其他 3 名玩家之间的卡牌分布情况，我认为您必须使用不属于您的卡牌模拟所有可能的分布（“世界”）。你有12张牌，其他3个玩家总共有36张牌。

所以我的方法是这个算法，其中< code>player是一个介于1和3之间的数字，代表程序可能需要寻找移动的三个计算机玩家。< code>-player代表对手，即所有其他三名玩家。

private Card computerPickCard(GameState state, ArrayList<Card> cards) {
    int bestScore = Integer.MIN_VALUE;
    Card bestMove = null;
    int nCards = cards.size();
    for (int i = 0; i < nCards; i++) {
        if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
            int score;
            GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
            score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            if (score > bestScore) {
                bestScore = score;
                bestMove = cards.get(i);
            }
        }
    }
    // now bestMove is the card to place
}

private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
    ArrayList<Card> cards;
    if (player >= 1 && player <= 3) {
        cards = state.getCards(player);
    }
    else {
        if (player == -1) {
            cards = state.getCards(0);
            cards.addAll(state.getCards(2));
            cards.addAll(state.getCards(3));
        }
        else if (player == -2) {
            cards = state.getCards(0);
            cards.addAll(state.getCards(1));
            cards.addAll(state.getCards(3));
        }
        else {
            cards = state.getCards(0);
            cards.addAll(state.getCards(1));
            cards.addAll(state.getCards(2));
        }
    }
    if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
        if (player >= 1 && player <= 3) {
            return state.getCurrentPoints(player); // player's points as a positive value (for self)
        }
        else {
            return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
        }
    }
    else {
        int score;
        int nCards = cards.size();
        if (player > 0) { // make one move (it's player's turn)
            for (int i = 0; i < nCards; i++) {
                GameState futureState = state.testMove(cards.get(i));
                if (futureState != null) { // wenn Zug gültig ist
                    score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
                    if (score >= beta) {
                        return score;
                    }
                    if (score > alpha) {
                        alpha = score; // alpha acts like max
                    }
                }
            }
            return alpha;
        }
        else { // make three moves (it's the others' turn)
            for (int i = 0; i < nCards; i++) {
                GameState futureState = state.testMove(cards.get(i));
                if (futureState != null) { // if move is valid
                    for (int k = 0; k < nCards; k++) {
                        if (k != i) {
                            GameState futureStateLevel2 = futureState.testMove(cards.get(k));
                            if (futureStateLevel2 != null) { // if move is valid
                                for (int m = 0; m < nCards; m++) {
                                    if (m != i && m != k) {
                                        GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
                                        if (futureStateLevel3 != null) { // if move is valid
                                            score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
                                            if (score >= beta) {
                                                return score;
                                            }
                                            if (score > alpha) {
                                                alpha = score; // alpha acts like max
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return alpha;
        }
    }
}

这看起来很好，但对于深度1（depthLeft=1），程序已经需要平均计算50000次移动（放置的牌）。当然，这太过分了！

所以我的问题是：

1. 实现完全正确吗？你能模拟这样的游戏吗？关于不完善的信息，尤其是？
2. 如何提高算法的速度和工作量？
3. 例如，我可以将可能的移动集合减少到50%的随机集合以提高速度，同时保持良好的结果吗？
4. 我发现UCT算法是一个很好的解决方案（也许）。你知道这个算法吗？你能帮我实现它吗？

Answer 1

对于存在如此多不确定性的游戏来说，Minimax搜索是一种错误的方法。由于你不知道其他玩家之间的卡牌分布情况，你的搜索将花费指数级的时间来探索在卡牌实际分布情况下不可能发生的游戏。

我认为一个更好的方法是，当你对其他球员的手牌信息很少或没有时，从良好的比赛规则开始。例如：

1. 如果你在一轮中先出牌，请出你的最低牌，因为你赢得这一轮的机会很小。
2. 如果你在一轮中打最后一名，打你的最低牌，这将赢得这一轮。如果你不能赢得这一轮，那就打你的最低牌。

让你的程序最初不打扰搜索，只是按照这些规则进行游戏，并假设所有其他玩家也将使用这些启发式方法。当程序观察每轮的第一个和最后一个玩家玩什么牌时，它可以建立一个关于每个玩家可能持有的牌的信息表。例如，9 会赢得这一轮，但玩家 3 没有玩，所以他不能有任何牌 9 或更高。随着每个玩家手牌信息的收集，搜索空间最终将被限制到对可能游戏的最小最大搜索可以产生有关下一张牌的有用信息。

Answer 2

我想澄清一些细节，公认的答案并没有真正深入。

在许多纸牌游戏中，你可以对对手可能拥有的未知纸牌进行抽样，而不是生成所有纸牌。在进行抽样时，你可以考虑短花色等信息，以及到目前为止持有特定牌的概率，以权衡每张可能的牌的可能性（每张牌都是一个可能的世界，我们将独立求解）。然后，你使用完美的信息搜索解决每一手牌。在所有这些世界中，最好的移动通常是整体上最好的移动——但有一些警告。

在像扑克这样的游戏中，这不会很好地发挥作用——游戏是关于隐藏信息的。你必须精确地平衡你的动作，以隐藏你手上的信息。

但是，在像基于技巧的纸牌游戏这样的游戏中，这种方法效果很好——尤其是因为新的信息一直在透露。真正优秀的玩家对每个人都有一个很好的想法。所以，相当强大的Skat和Bridge程序就是基于这些想法。

如果你能完全解决底层世界，那是最好的，但如果你不能，你可以使用极大极小或UCT来选择每个世界中的最佳移动。也有混合算法(ISMCTS)试图将这一过程混合在一起。小心这里的说法。简单的采样方法更容易编码——您应该先尝试简单的方法，然后再尝试更复杂的方法。

以下是一些研究论文，它们将提供有关不完全信息的抽样方法何时运作良好的更多信息：

理解完美信息蒙特卡罗采样在博弈树搜索中的成功（本文分析了采样方法何时可能起作用）

改进基于技巧的纸牌游戏中的状态评估、推理和搜索（本文描述了 Skat 中采样的使用）

具有计算挑战性的游戏中的不完美信息(本文描述了桥牌中的抽样)

信息集蒙特卡罗树搜索(本文合并了抽样和UCT/蒙特卡罗树搜索，以避免第一篇参考文献中的问题。)

在公认的答案中，基于规则的方法的问题是，它们不能利用创建初始规则所需的计算资源之外的计算资源。此外，基于规则的方法将受到您可以编写的规则的限制。基于搜索的方法可以利用组合搜索的力量产生比程序作者更强的效果。