使用minimax搜索具有不完全信息的纸牌游戏

Question

我想使用minimax搜索(使用alpha-beta修剪),或者更确切地说是使用negamax搜索来使计算机程序玩纸牌游戏.

纸牌游戏实际上由4名玩家组成.因此,为了能够使用minimax等,我将游戏简化为"我"以对抗"其他人".在每次"移动"之后,您可以客观地从游戏本身读取当前状态的评估.当所有4名玩家都已经放置了这张牌时,最高赢得了所有牌 - 并且牌的价值计算在内.

由于你不知道其他3个玩家之间的牌分布是如何确切的,我认为你必须使用不属于你的牌来模拟所有可能的分布("世界").你有12张卡,其他3个玩家共有36张牌.

所以我的方法是这个算法,其中player1到3之间的数字表示程序可能需要找到移动的三个计算机玩家.并-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),程序已经需要平均计算50,000次移动(放置卡).当然,这太过分了!

所以我的问题是:

1. 实施是否正确？你能模拟这样的游戏吗？关于不完善的信息,特别是？
2. 如何在速度和工作负载方面改进算法？
3. 例如,我可以将可能移动的集合减少到50%的随机设置以提高速度,同时保持良好的结果吗？
4. 我发现UCT算法是一个很好的解决方案(也许).你知道这个算法吗？你能帮我实现吗？

Answer 1

我想澄清接受的答案没有真正涉及的细节.

在许多纸牌游戏中,您可以对对手可能拥有的未知卡进行采样,而不是生成所有卡.到目前为止,您可以考虑短途套装等信息以及持有某些牌的可能性,以便对每个可能的牌进行加权(每一手牌都是我们独立解决的可能世界).然后,您使用完美的信息搜索解决每只手.对所有这些世界的最好的举动往往是最好的举措 - 有一些警告.

在像扑克这样的游戏中,这种效果不会很好 - 游戏就是隐藏的信息.您必须精确平衡您的操作,以隐藏有关您手的信息.

但是,在基于技巧的纸牌游戏等游戏中,这种效果非常好 - 特别是因为新信息一直在被曝光.无论如何,真正优秀的球员都知道每个人都拥有什么.因此,相当强大的Skat和Bridge计划基于这些想法.

如果你可以完全解决潜在的世界,那就是最好的,但如果你不能,你可以使用minimax或UCT来选择每个世界中最好的动作.还有混合算法(ISMCTS)试图将这个过程混合在一起.这里的说法要小心.简单的采样方法更容易编码 - 您应该在更复杂的方法之前尝试更简单的方法.

以下是一些研究论文,可以提供有关不完全信息的抽样方法何时运作良好的更多信息:

在游戏树搜索中理解完美信息蒙特卡洛抽样的成功(本文分析了抽样方法何时可行.)

改进基于特技的纸牌游戏中的状态评估,推理和搜索(本文介绍了在Skat中使用抽样)

计算具有挑战性的游戏中的信息不完整(本文描述了Bridge中的采样)

信息集蒙特卡罗树搜索(本文合并采样和UCT /蒙特卡罗树搜索以避免第一次参考中的问题.)

在接受的答案中基于规则的方法的问题在于它们不能利用超出创建初始规则所需的计算资源.此外,基于规则的方法将受到您可以编写的规则的力量的限制.基于搜索的方法可以使用组合搜索的功能来产生比程序作者更强大的游戏.

Answer 2

您实施的Minimax搜索对于不确定性很大的游戏是错误的方法。由于您不知道其他玩家之间的纸牌分布，因此您的搜索将花费大量时间探索在实际分配纸牌的情况下不会发生的游戏。

我认为更好的方法是从对其他玩家的手很少或没有任何信息的良好比赛规则入手。像：

1. 如果您在一轮比赛中排名第一，请打出最低的牌，因为您几乎没有机会赢得比赛。
2. 如果您在回合中打最后一局，请打出最低的纸牌以赢得该回合。如果您无法赢得本回合，请打出最低的牌。

让您的程序最初不打扰搜索，而只是遵循这些规则，并假设所有其他参与者也将使用这些启发式方法。 当程序观察每个回合的第一张和最后一张纸牌时，它可以建立一张有关每张纸牌可能持有的纸牌的信息表。例如，一个9会赢得本回合，但是玩家3没有参加，因此他必须没有9或更高的牌。随着收集有关每个玩家手牌的信息，搜索空间最终将受到限制，以至于可能游戏的极小极大搜索可能产生有关下一张要玩的纸牌的有用信息。