1. 从Minimax到Expectimax吃豆人算法的进化之路第一次运行吃豆人游戏时看着那个黄色圆点毫无章法地撞向幽灵我就知道这背后大有学问。在CS188的Project 2中我们需要让吃豆人学会思考而Minimax算法就是它的第一堂思维课。这个算法教会吃豆人用最悲观的角度看待世界——假设每个幽灵都会做出最不利于自己的选择。听起来很丧对吧但这就是博弈论的经典思维在最坏情况下争取最好结果。Minimax的核心是交替进行最大化吃豆人回合和最小化幽灵回合的递归搜索。想象你和朋友下棋你每走一步都假设对方会走对你最不利的棋然后在这个前提下选择对自己最有利的走法。在代码中getMax()和getMin()两个函数就像两个互相较劲的对手一个拼命找最高分一个使劲压最低分。有趣的是这种被迫害妄想症式的算法在简单场景下效果出奇地好。但问题也随之而来。当我在深夜调试代码时发现吃豆人有时会莫名其妙冲向幽灵自杀。原来在Minimax的世界观里当死亡不可避免时早点结束痛苦比赌一把幽灵犯错更符合逻辑。这种极端保守的策略暴露了算法的局限性——现实世界中对手并不总是完美的。2. Alpha-Beta剪枝给算法装上加速器当游戏地图变大时Minimax的搜索时间呈指数级增长。这时Alpha-Beta剪枝就像给算法吃了兴奋剂。我还记得第一次看到剪枝效果时的震撼——同样的搜索深度状态评估次数减少了70%原理其实很直观如果已经知道某条路径不可能比已知最优解更好就果断放弃搜索。在代码实现中alpha记录当前最大下界beta记录最小上界。当getMax()中发现某个值大于beta就可以立即停止搜索因为这个分支对手肯定不会选同理getMin()中发现值小于alpha时也能剪枝。这就像玩猜价格游戏时主持人告诉你已经有人出价低于100了那你报120就毫无意义。但剪枝有个重要前提节点顺序影响效率。如果把最好的走法放在最后评估就几乎无法剪枝。实践中我发现在吃豆人游戏中优先评估靠近食物的方向剪枝效果最好。这也让我明白算法优化往往需要结合具体场景的领域知识。3. Expectimax拥抱不确定性的智慧前两种算法都假设幽灵永远理智但现实中对手可能犯错。Expectimax的魅力在于它承认世界的不确定性——幽灵可能随机移动。算法不再寻找最坏情况而是计算期望值。在代码中原本的getMin()变成了getExp()最小值操作变为求平均值。这个改变带来了有趣的行为变化。同样的迷宫布局Minimax版吃豆人会绕远路躲避所有幽灵而Expectimax版则可能冒险穿过幽灵附近——因为它计算了幽灵可能错过抓捕的概率。这就像现实生活中过度悲观的人会错过太多机会而合理评估风险的人反而走得更远。实现时要注意概率分布的设计。项目中假设幽灵随机移动所以采用均匀分布。但在进阶版本中可以给不同移动方向设置不同概率比如幽灵更倾向朝吃豆人移动这样模型会更贴近真实游戏AI的行为模式。4. 评估函数算法的大脑皮层无论哪种算法都依赖评估函数给游戏状态打分。好的评估函数就像给算法安装了价值判断系统。最初我只会用简单指标食物距离越近越好、幽灵距离越远越好。结果吃豆人变得神经质——看见食物就冲发现幽灵就跑完全不会利用能量豆让幽灵恐慌的机制。后来设计的betterEvaluationFunction加入了多个考量因素基础游戏分数最近食物的倒数距离乘以权重系数幽灵距离的调节正常幽灵负分恐慌幽灵正分恐慌幽灵的剩余时间避免在幽灵恢复前撞上调试权重就像调节化学配方需要反复试验。比如WEIGHT_SCARED_GHOST设得过高吃豆人会不顾一切追捕恐慌幽灵反而陷入陷阱。最终采用的数值是通过上百局游戏测试找到的平衡点。5. 算法实战对比当理论遇上现实在标准迷宫测试中三种算法表现出明显差异Minimax最保守存活时间最长但得分中等Alpha-Beta版表现相似但决策速度快3-5倍Expectimax最激进可能早死但也容易得高分但当我把幽灵AI从确定性改为部分随机时局面反转了。Minimax因为过度防范实际不存在的威胁而表现最差Expectimax反而因为符合实际场景假设而胜出。这个对比生动说明了没有放之四海皆准的算法关键要匹配问题特性。在代码层面三种算法的类结构高度一致主要区别在于递归搜索的逻辑。MinimaxAgent和AlphaBetaAgent共享getMin/getMax方法后者多了剪枝参数而ExpectimaxAgent需要重写幽灵回合的处理逻辑。这种设计让算法演进变得清晰可见。6. 从代码到思考AI教给我们的人生算法调试吃豆人的过程像极了个体成长。早期的Minimax阶段我们像青少年总觉得世界充满恶意Alpha-Beta阶段学会高效过滤无效选择最后的Expectimax阶段才真正理解随机性的价值。每次算法升级都让吃豆人更接近成熟智能体的状态。有个深夜当我看着优化后的吃豆人灵活穿梭于幽灵之间突然意识到这些算法折射出不同的处世哲学。Minimax是悲观主义者Expectimax是概率思维者而好的评估函数教会我们多维度权衡利弊。也许人工智能的终极价值就是给我们一面镜子照见自己思维模式的局限与可能。
