0

我想用 minimax 算法实现 PacMan 游戏，但我不能流利地理解算法的含义。我写了这段代码

public MOVE miniMax(Game game,Node[] nodes,int depth,Boolean pacMan){

        int value;
        MOVE thisMove;
        int bestValue;
        int score=0;

        EnumMap<MOVE, MOVE[]> possibleMoves = nodes[game.getPacmanCurrentNodeIndex()].allPossibleMoves;
        MOVE[] moves = possibleMoves.get(MOVE.NEUTRAL);

        if(depth == 0)
            score = evaluationFunction(game);
        if(pacMan){
            bestValue = -INF;
        for(int i=0;i<moves.length;i++){
            game.copy();
            game.updatePacMan(moves[i]);
            thisMove= miniMax(game,nodes,depth-1,Boolean.FALSE);
            //bestValue = Math.max(bestValue, value);

        }
        return thisMove;

    }else{
            bestValue = INF;
            for(int i=0;i<moves.length;i++){
                game.copy();
                game.updatePacMan(moves[i]);
                thisMove= miniMax(game,nodes,depth-1,Boolean.TRUE);
                //bestValue = Math.min(bestValue, value);
            }
            //return bestValue;
            return thisMove;
        }
    }

    public int evaluationFunction(Game game){

        return 0;
}

我已经考虑到 Wikipedia 伪代码编写了这段代码，但是我有一个问题，我不知道如何将评估函数计算为整数，然后决定返回一个动作，我应该只返回一个动作。评估函数是计算一次移动还是在节点的所有可能移动中选择一个？

4

1 回答 1

0

首先，极小极大适用于国际象棋等回合制游戏。以离散增量分解连续游戏（例如吃豆人）并应用此算法很诱人，但您会发现您正试图在两个对立目标之间达到平衡，并且可能都不满足：

  • 小增量有助于更好的评估，但在计算需求方面会增长太快（特别是如果您考虑所有幽灵的同时移动）
  • 较大的增量使树更易于管理，但不会提供此类街机游戏所需的细粒度反应

不过，如果只是为了看看结果，这仍然是一个有趣的问题。

评估函数是一个启发式函数，它试图估计当前棋盘状态的强度，其中给定玩家的得分越高越好。这将是一个相当大的挑战，因为在 pacman 中没有明显的方法来估计一个位置的强度，但这里有一些想法：

  • 吃豆人不是无敌的，离鬼远点比较好
  • 吃豆人无敌的话，离鬼更近
  • 在板上收集的规则点越少越好
  • 有更多的“无敌点”仍然留在板上更好
  • 监狱里有更多的鬼魂更好

这当然是从 pacman 的角度来看的。对于鬼来说，情况正好相反。微调这些特征各自的权重是成功实现极小极大的难点之一。

顺便说一句，直接进行 alpha-beta 剪枝或 negascout（有点棘手），它将在性能方面产生天壤之别，而不会损失评估质量。

于 2014-05-19T17:10:14.433 回答