1. 项目缘起当“吃豆人”遇上“遗传算法”最近在重温一些经典游戏时突然冒出一个想法如果让一个AI来玩《吃豆人》Pac-Man它会怎么玩是像我们小时候那样横冲直撞还是能发展出一套更高效的策略更进一步如果这个AI不是被预先编程好每一步而是像生物进化一样通过“优胜劣汰”自己学会玩结果会怎样这个想法催生了“Genetic Packman”这个项目。简单来说它是一个用遗传算法Genetic Algorithm, GA来训练AI玩《吃豆人》游戏的模拟实验。项目的核心目标不是复现一个完美的游戏AI而是想亲眼看看一个简单的“吃豆人”智能体如何从一群完全随机的“傻瓜”开始通过模拟自然选择的过程一步步进化出躲避幽灵、高效吃豆的策略。这个过程本身比最终的游戏得分更有趣它像是一个微观的进化实验让我们能直观地理解“适者生存”在代码世界里的运作方式。对于开发者、游戏爱好者或者任何对人工智能、进化计算感兴趣的朋友来说这个项目都是一个绝佳的入门和实践案例。它不涉及复杂的深度学习框架核心逻辑清晰却能生动展示智能是如何从无到有“涌现”出来的。接下来我就把自己从零搭建、调试到最终看到AI进化的全过程以及背后的思考、踩过的坑毫无保留地分享出来。2. 核心战场吃豆人游戏环境的建模与抽象要让遗传算法发挥作用首先得为它搭建一个“训练场”——即一个可编程、可交互的《吃豆人》游戏环境。这里的关键不是做出多么炫酷的图形界面而是如何将复杂的游戏状态抽象成算法能够理解和处理的“数据”。2.1 游戏状态的数据化表示一个完整的《吃豆人》游戏状态包含大量信息吃豆人的位置、四个幽灵的位置和状态追逐/逃跑、豆子的分布、能量豆的存在、地图布局等等。如果把这些信息全部原封不动地喂给算法维度会爆炸训练将无法进行。因此特征工程是第一步也是决定AI“智商”上限的关键。在我的实现中我为每个吃豆人智能体即一个“个体”构建了一个简化但有效的感知向量。这个向量就像吃豆人的“感官”告诉它周围世界的状况。一个典型的8维感知向量设计如下到最近豆子的距离和方向2维计算吃豆人当前位置到地图上所有剩余豆子的欧几里得距离取最小值及其对应的方向上、下、左、右。这驱动吃豆人去寻找食物。到最近幽灵的距离和方向2维同样计算到每个幽灵的距离取最小值及方向。这是最重要的生存指标。最近幽灵的状态1维是处于正常的“追逐”模式还是吃了能量豆后的“逃跑”模式这直接影响吃豆人的行为是应该规避还是主动出击。能量豆的存在与方向1维附近是否有能量豆在哪个方向这提供了反杀和获取高分的机会。前方路径是否畅通1维在当前移动方向上下一个格子是否是墙这防止了无意义的撞墙行为。当前分数与剩余豆子比例1维一个全局的激励信号鼓励高效吃豆。注意这个感知向量的设计充满了权衡。维度太少比如只关心幽灵AI可能会变得极度保守躲着不动维度太多则训练缓慢且容易过拟合到特定地图。我经过多次试验发现8-12维是一个比较理想的区间既能捕捉关键信息又不会让搜索空间过于庞大。2.2 决策机制从感知到行动有了感知向量接下来需要一套机制将其转化为行动上、下、左、右、停止。这里我采用了最简单的前馈神经网络作为每个吃豆人个体的“大脑”。这个网络结构非常浅输入层节点数等于感知向量的维度例如8。隐藏层通常只有一层包含4-8个神经元使用ReLU激活函数引入非线性。输出层4个节点分别对应四个移动方向的“倾向值”使用Softmax函数转换为概率分布。每次游戏进行一步即一帧系统就会根据当前游戏状态计算该吃豆人的感知向量。将感知向量输入其独有的神经网络。网络输出四个动作的概率然后按此概率随机选择一个动作执行也可以选择概率最高的动作但引入随机性有助于探索。为什么用神经网络而不是直接查表或规则因为遗传算法优化的对象是神经网络的连接权重。一个拥有几十个权重的网络其策略空间是连续且巨大的非常适合遗传算法进行搜索和优化。而一条固定的“如果幽灵近就逃”的规则则没有进化的余地。2.3 游戏模拟器的搭建为了高效运行成百上千次的游戏模拟我选择使用Python并优先考虑计算效率。图形显示不是重点因此我使用了pygame库但仅在需要观察时才开启渲染大部分训练时间关闭渲染以提升速度。游戏的核心逻辑包括地图表示用一个二维数组表示其中不同的数字代表墙、通道、豆子、能量豆。碰撞检测吃豆人与幽灵的碰撞、吃豆人与豆子的碰撞。幽灵AI为了提供合理的环境压力我为幽灵实现了经典的《吃豆人》幽灵行为模式简化版——布林克Blinky会直接追击 Pinky会预判拦截 Inky和Clyde的行为则更随机一些。这保证了环境的挑战性相对稳定便于算法评估。一个重要的设计点是单次模拟的终止条件。除了吃豆人被抓住游戏结束我还设置了最大步数限制例如2000步。这是为了防止个别个体采取极端保守策略比如躲在角落无限期地拖延模拟浪费计算资源。达到最大步数时会根据已吃豆子比例给予一个分数并结束。3. 进化引擎遗传算法的设计与调参有了环境和个体接下来就是设计“进化”的规则。遗传算法模仿自然进化主要包括选择Selection、交叉Crossover和变异Mutation三个核心操作循环迭代。3.1 适应度函数定义什么是“好”在自然界适应度是个体生存和繁殖能力的体现。在我们的数字世界里适应度函数Fitness Function就是衡量一个吃豆人AI好坏的唯一标准。设计它需要格外小心因为它直接引导着进化的方向。我最初尝试了一个简单的函数适应度 最终游戏得分。结果进化很快陷入了局部最优AI们发现只要一动不动虽然得分是0但也不会被幽灵抓到从而避免了得负分被抓住有时会扣分。这显然不是我们想要的。经过几次迭代我设计了一个更有效的复合适应度函数适应度 (基础分数 * 权重1) (存活时间 * 权重2) (吃掉豆子的百分比 * 权重3) - (无意义移动惩罚)基础分数游戏本身的得分吃豆、吃幽灵得分。存活时间鼓励生存但单纯生存不会给太高权重否则又会催生“躲藏策略”。吃掉豆子的百分比这是核心驱动力之一直接鼓励完成游戏目标。无意义移动惩罚对于连续在死胡同里来回移动或撞墙的行为进行小幅扣分鼓励有效探索。通过调整权重例如权重11.0 权重20.1 权重32.0我成功地将进化方向引导至“积极且聪明地吃豆并生存”。适应度函数的设计是遗传算法的艺术所在往往需要根据具体问题反复调整。3.2 种群初始化与选择策略第一代种群我随机生成了100个吃豆人个体。每个个体的神经网络权重完全随机这意味着它们最初的行为完全是乱来的大部分会迅速撞上幽灵。每一代模拟结束后需要根据适应度选择出优秀的个体作为“父母”产生下一代。我对比了两种常见策略轮盘赌选择个体被选中的概率与其适应度成正比。这保持了种群的多样性但可能让一些中等偏上的个体产生过多后代。锦标赛选择随机从种群中抽取k个个体比如k3让它们中适应度最高的胜出成为父母。这种方法选择压力更强能更快收敛但多样性损失也快。实测中对于《吃豆人》这个问题锦标赛选择的效果更好。因为我们需要快速淘汰那些完全无用的随机策略让有潜力的个体脱颖而出。我通常设置锦标赛规模k3。3.3 交叉与变异创造新可能选出的“父母”们需要通过交叉和变异产生“后代”。交叉单点交叉随机选取神经网络中的一个连接点将两个父代的权重向量在此点切开并交换后半部分生成两个子代。这相当于融合了父母的“策略”。交叉概率我通常设置得较高~0.8以促进优良特性的混合。变异这是创新的源泉。对子代神经网络中的每个权重以一个很小的概率~0.05将其随机重置为一个小范围内的随机值。变异概率不能太高否则进化会变成随机搜索也不能太低否则种群会失去探索新策略的能力。一个关键的调参经验是在进化早期可以适当提高变异率鼓励探索在进化后期当种群适应度趋于稳定时可以降低变异率进行精细优化。我实现了一个简单的自适应机制当连续5代最佳适应度没有显著提升时轻微提升变异率。3.4 世代交替与精英保留新一代种群由经过选择、交叉、变异产生的子代完全替换旧种群这就是简单遗传算法。但这里有一个风险可能意外地丢失掉当代最好的个体精英。因此我引入了精英保留策略每一代结束后无条件地将适应度最高的前2个个体直接复制到下一代中不经过交叉和变异。这保证了已发现的最优解不会丢失大大加快了收敛速度。这2个精英个体约占种群100的2%是一个经验值。4. 训练过程实录从混沌到有序的涌现理论设计完毕接下来就是激动人心的训练环节。我将种群大小设为100总共运行了约150代并记录了关键指标。4.1 早期阶段第1-20代混乱与死亡最初的几代景象堪称“惨烈”。100个吃豆人在屏幕上表现出各种匪夷所思的行为疯狂撞墙、对着幽灵直冲、在原地转圈……它们的平均存活时间极短经常在10秒内全军覆没。此时的平均适应度曲线在底部徘徊。然而遗传算法正在默默工作。即使是在完全的随机中也会有极少数个体因为权重的巧合表现出一点点“躲避”或“向前”的倾向。比如某个个体的神经网络权重恰好让它对“前方有墙”这个输入信号产生强烈的“转向”输出。虽然它可能还是很快会死但它的适应度存活时间会略高于那些直接撞墙的个体。通过锦标赛选择这些“稍微不那么差”的个体有了更高的繁殖机会。进化的第一步不是变得“好”而是先淘汰“最差的”。4.2 中期阶段第21-80代策略的萌芽与分化大约在第30代左右变化开始显现。平均适应度曲线开始有了缓慢但明确的上升趋势。观察实时模拟你会发现大部分吃豆人已经很少撞墙了它们学会了在通道里移动。更有趣的是策略开始分化。我通过记录个体的行为轨迹发现了至少两种初期策略“贴边流”一部分个体倾向于沿着地图的边缘移动。这或许是因为边缘通常幽灵较少且移动决策更简单往往只有两个方向可选。“绕圈流”另一部分个体喜欢在某个区域绕小圈。这可能是它们在探索过程中偶然发现了一个相对安全的循环路径通过不断绕圈可以吃到重新刷新的豆子如果模拟设置允许并避开幽灵。这个阶段交叉操作的作用凸显出来。一个擅长“贴边”的个体和一个擅长在开阔地转向的个体结合可能会产生一个既能利用边缘安全区又能在必要时切入内场吃豆的后代。进化开始像搭积木一样组合那些微小的、有效的行为模块。4.3 中后期阶段第81-130代学会与幽灵共舞进入80代以后最佳个体的表现常常让人眼前一亮。它们不仅会吃豆还开始展现出对幽灵行为的反应。规避当感知向量显示附近有幽灵时它们会明显地向反方向或侧向移动而不是继续前进。利用能量豆当能量豆出现且幽灵状态变为“逃跑”时最佳个体会主动向幽灵方向移动尝试“反杀”得分。这说明进化出的策略已经能区分幽灵的两种状态并加以利用。路径规划雏形虽然谈不上真正的规划但你能看到它们不再是无头苍蝇。它们会朝着豆子密集的区域移动并在吃完一小片区域后转向下一个区域表现出一种局部的“贪婪”策略。此时的适应度曲线上升斜率变缓说明进化进入了平台期。种群中的多样性降低大部分个体都共享着类似的优秀基因。进一步的提升需要更精细的权重调整依赖变异或者等待一个突破性的创新结构出现。4.4 后期阶段第131-150代与瓶颈到150代时最佳个体已经能够在一个固定的简单地图上稳定地吃完70%以上的豆子并且存活很长时间。它已经是一个合格的“初级玩家”了。然而我也清晰地看到了瓶颈全局策略缺失进化出的AI缺乏真正的长远规划。它不会为了吃一个远处的能量豆而冒险穿越幽灵巡逻区也不会“调虎离山”。它的策略本质上是基于当前瞬间感知的反应式策略。过拟合风险这个AI是在一张特定地图上训练出来的。当我把它放到一个结构迥异的新地图时它的表现会大幅下降因为它学习的权重高度适配了旧地图的几何结构和幽灵出生点。这就像一只在特定丛林里进化得很好的动物到了草原可能无法生存。局部最优种群似乎收敛到了一个局部最优解。即使增加变异率产生的新奇个体也因其策略不如现有的精英而被迅速淘汰难以突破。5. 突破瓶颈高级技巧与优化方向看到瓶颈也就看到了下一步改进的方向。遗传算法本身非常灵活可以通过多种方式提升其性能。5.1 增加种群多样性与环境复杂度为了防止过早收敛可以增大种群规模从100增加到300或500。更大的种群意味着更大的基因库更不容易丢失潜在的有用基因。但计算成本会线性增加。引入“物种”概念小生境技术通过计算个体之间的基因距离如权重向量的欧氏距离将相似的个体归为同一物种。在选择时分别在每个物种内部进行并保证每个物种都能留下一定数量的后代。这可以保护一些暂时不够优秀但独特的策略维持探索能力。动态调整地图或幽灵行为每隔若干代轻微改变地图布局或幽灵的追击算法。这相当于给进化环境增加了“变化”迫使AI进化出更通用、更鲁棒的策略而不是针对固定环境的特化策略。5.2 优化神经网络结构与输入特征当前的简单神经网络可能限制了策略的表达能力。增加网络深度或宽度尝试加入第二个隐藏层或增加隐藏层神经元数量。更复杂的网络可以表示更复杂的函数但也会让搜索空间急剧扩大需要更长的进化时间。改进感知向量引入更抽象的特征。例如不仅仅是“到最近豆子的距离”而是“到最近三个豆子的平均距离和方向”或者加入“当前通道是否是死胡同”这样的拓扑特征。更好的特征表示能让学习事半功倍。引入记忆机制最简单的可以将上一帧的动作或部分感知信息也作为当前帧的输入。这相当于给了网络一个“瞬时记忆”使其能感知状态的变化趋势比如幽灵是在靠近还是远离从而做出更优决策。5.3 算法层面的混合与改进纯粹的遗传算法在精细优化上效率较低。可以结合其他方法与局部搜索结合Memetic Algorithm在每一代中对精英个体或部分优秀个体额外运行几次梯度下降如果适应度函数可微或其他局部搜索算法对其进行“微调”。这相当于让个体在繁殖前先进行“学习”将习得的经验调整后的权重遗传下去。调整选择压力在进化早期使用高选择压力如锦标赛规模k较大快速提升后期降低选择压力k变小以保持多样性进行精细搜索。6. 项目总结与实用心得回顾整个“Genetic Packman”项目它不仅仅是一个游戏AI实验更是一个理解进化计算和智能涌现的绝佳窗口。从一堆随机权重中通过简单的选择、交叉、变异最终涌现出能玩转《吃豆人》的策略这个过程本身就充满了魅力。几点核心心得适应度函数是指挥棒你的算法会不择手段地优化你定义的“好”。如果定义不当结果往往会令人啼笑皆非。务必花时间思考什么才是真正期望的行为并用数学公式清晰地表达出来。多设计几个版本进行对比实验。多样性是进化的燃料一旦种群失去多样性进化就基本停止了。精英保留策略是双刃剑在加速收敛的同时也压制了多样性。务必使用锦标赛选择、小生境等技术并密切关注种群基因的相似度。可视化与日志至关重要不要只盯着最终的数字曲线。一定要实时观看最佳个体的游戏回放观察它的行为模式。保存每一代最佳个体的基因组权重你甚至可以手动“扮演上帝”将不同代的优秀个体拿出来对战观察策略的演变。这些直观的感受是调整参数时最宝贵的依据。从简单开始逐步增加复杂度一开始就在复杂地图上用复杂网络训练很可能得不到任何有意义的结果。我的路径是固定幽灵模式 - 简单矩形地图 - 小规模种群 - 浅层网络。等到在这个简单环境下能稳定进化出合理策略后再逐步增加地图复杂度、幽灵AI的智能度、网络规模等。这保证了每一步调试都有明确的目标和可理解的结果。遗传算法不是万能的对于《吃豆人》这种部分可观测、需要一定规划能力的游戏纯反应式的策略有其天花板。它非常适合用来寻找一个庞大、复杂空间中的“不错”的解但要找到“完美”或“通用”的解可能需要与其他方法如强化学习结合或者需要难以承受的计算时间。这个项目的代码并不复杂但其背后关于进化、适应和优化的思考却非常深刻。它让我真切体会到即使没有预设的“智能”程序通过简单的规则和迭代复杂性也能从简单中诞生。如果你也对AI和进化感兴趣不妨亲手实现一个自己的“Genetic Packman”亲自调整参数观察那些数字生命是如何一步步学会生存和游戏的这绝对是一次难忘的体验。