我想使用极小化极大算法实现《吃豆人》游戏，但我对算法的理解不够流利。我已经编写了以下代码
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;}我参考维基百科的伪代码编写了这段代码，但我有一个问题，我不知道如何将评估函数计算为一个整数，然后决定返回一个移动，我应该只返回一个移动。评估函数是为一个移动计算的，还是在节点的所有可能移动中选择一个？
回答：
首先，极小化极大算法适用于像国际象棋这样的回合制游戏。将连续游戏（如《吃豆人》）分解成离散增量并应用此算法是很有诱惑力的，但你会发现自己试图在两个对立目标之间达到平衡，可能两者都无法满足：
- 小的增量可以带来更好的评估，但计算需求会迅速增长（特别是如果你考虑到所有鬼魂的同时移动）
- 大的增量可以使树更易于管理，但无法提供这种街机游戏所需的细粒度反应
尽管如此，这仍然是一个有趣的问题，至少可以看看结果。
评估函数是一个启发式函数，试图估计当前棋盘状态的强度，其中较高的分数对给定玩家更有利。这将是一个相当大的挑战，因为在《吃豆人》中没有明显的方法来估计位置的强度，但这里有一些想法：
- 如果吃豆人不是无敌的，远离鬼魂更好
- 如果吃豆人是无敌的，靠近鬼魂更好
- 棋盘上剩余的普通点越少越好
- 棋盘上剩余的“无敌点”越多越好
- 监狱中的鬼魂越多越好
当然，这是从吃豆人的角度来说的。对于鬼魂来说，情况正好相反。成功实现极小化极大算法的难点之一是微调这些特性的各自权重。
顺便说一下，直接使用alpha-beta剪枝或negascout（稍微复杂一些），这将在性能上带来巨大的差异，而不会损失评估质量。
