用 Python + Pygame 实现的下落方块游戏，集成四种由简到难的 AI 算法。面向初学者的教学项目，代码注释用中文大白话解释每个 AI 概念。
pip install -r requirements.txt
# 手动模式
python main.py --mode human
# 启发式 AI（无需训练，直接运行）
python main.py --mode ai --algo heuristic
# 不带参数启动 → 显示交互菜单
python main.py| 算法 | 原理 | 是否需要训练 |
|---|---|---|
| heuristic | BFS 枚举落点，加权评分 | 否 |
| genetic | 遗传算法自动调权重 | 是 |
| dqn | 深度 Q 网络（强化学习） | 是 |
| ppo | 近端策略优化（强化学习） | 是 |
训练充分的情况下，四种算法的预期表现：
| 名次 | 算法 | 预期均值 | 说明 |
|---|---|---|---|
| 1 | Genetic | 300～600 行 | 自动搜索最优权重，效果远超手调 |
| 2 | Heuristic | 75～100 行 | 无需训练，手调权重，开箱即用 |
| 3 | DQN | 取决于训练 | 理论天花板高，但难以收敛 |
| 4 | PPO | 未能收敛 | 在本项目中训练失败，见 PPO 章节 |
为什么遗传算法最强？
遗传算法本质上是在和启发式相同的 5 维特征空间里自动搜索最优权重，用 200 个个体 × 多代进化，能找到人工难以直觉设计的权重组合。经典的 Dellacherie 权重本身就是这类优化方法的产物，可以稳定跑 600+ 行。
为什么 DQN / PPO 不一定更强？
DQN 和 PPO 理论上表达能力更强，但本项目输入同样只有 5 个棋盘特征，与启发式信息量完全相同，没有发挥神经网络优势。加上下落方块游戏奖励稀疏（只有消行才有大额正向反馈），实际训练难度高，效果不一定能超过调好的启发式。
核心思路：不需要训练，直接用人工设计的"评分函数"衡量棋盘状态的好坏。对每个合法落点模拟放置，选得分最高的执行。
评分函数（5 个维度加权求和）：
| 特征 | 权重 | 含义 |
|---|---|---|
| aggregate_height | -0.51 | 所有列高度之和，越高越危险 |
| complete_lines | +0.76 | 消行数，唯一正向收益 |
| holes | -0.46 | 空洞数，空洞无法消行是大忌 |
| bumpiness | -0.22 | 相邻列高度差之和，越平整越好 |
| max_height | -0.70 | 最高列高度，直接惩罚"尖塔" |
权重调优过程与结论：
从经典 Dellacherie 权重出发，通过无界面模拟（每组 25 局）系统测试各权重的影响：
holes：从 -0.36 逐步增大到 -0.46 时均值最优（92.8 行），更大则出现 0 行死局。填洞惩罚太弱 AI 不在意空洞，太强则 AI 宁可堆高也要躲洞。bumpiness：从 -0.18 增到 -0.22 后，最低存活行数从 2 提升到 13，有效减少极端早死局。更大（-0.30 以上）反而压低平均表现。max_height：直接惩罚最高列，防止局部尖塔越堆越高。设置 -1.30 过于激进导致 15 步即死，-0.70 是稳定上限。aggregate_height：调整对整体表现影响不显著，保持 -0.51 不变。
局限性：纯贪心只看当前一步，后期棋盘复杂时难以全局规划，容易出现列高度逐渐失衡最终崩溃。如需根治，参考遗传算法（自动寻优权重）或先读（look-ahead）策略。
实测性能（20 局均值）：约 75～95 行，无 0 行死局，最高可达 200+ 行。
核心思路：把启发式的 5 个权重当作"基因"，用进化模拟自动找到更好的权重组合，无需人工手调。
进化流程：
初始化随机种群（200套权重）
↓
评估适应度（每套权重跑5局，取平均消行数）
↓
选择精英（前10%直接保留）
↓
交叉（80%概率：两个父代权重随机混合）
↓
变异（20%概率：对各权重添加随机扰动）
↓
重复，直到连续30代无改善（Early Stopping）
关键超参数：
| 参数 | 值 | 作用 |
|---|---|---|
| POPULATION_SIZE | 200 | 每代评估 200 套权重 |
| ELITE_FRAC | 10% | 精英直接保留，防止好权重丢失 |
| EVAL_GAMES | 5 | 每套权重跑 5 局均值，平滑随机性 |
| PATIENCE | 30 代 | 无改善停止，防止过拟合随机序列 |
优势：自动搜索权重空间，无需人工调参，可以找到人类难以直觉设计的权重组合。
局限：仍依赖启发式评分框架，能力上限受 5 个特征的表达能力限制。训练时用硬降（无 BFS）评估以提高速度，与实际游戏略有差异。
核心思路：用神经网络学习"在某个棋盘状态下，价值最高的落点是哪个"。采用 After-State 方案解决动作空间不固定的问题。
After-State 方案：
传统 Q 网络输入(状态, 动作)，但下落方块游戏每步合法落点数量不固定（10～40个），无法用固定下标表示动作。
解决方法：对每个落点先模拟放置，提取放置后棋盘的 5 维特征，送进网络输出一个价值。选价值最高的落点执行。
落点1 → 模拟放置 → 5维特征 → 网络 → 价值
落点2 → 模拟放置 → 5维特征 → 网络 → 价值 → 选最大值
...
落点N → 模拟放置 → 5维特征 → 网络 → 价值
5 维特征（after-state）：
| 特征 | 含义 |
|---|---|
| aggregate_height | 所有列高度之和 |
| lines_cleared | 累计消行数 |
| holes | 空洞数 |
| bumpiness | 相邻列高度差之和 |
| max_height | 最高列高度 |
网络结构：5维 → FC(64) → ReLU → FC(64) → ReLU → 1维（价值）
训练关键设计：
- Double Network：主网络每步更新，目标网络每 1000 步同步一次，避免"追移动靶"导致训练不稳定。
- Experience Replay：回放缓冲区存 10000 条经验，每步随机采样 512 条训练，打破样本相关性。
- Reward Shaping：即使未消行，落子后棋盘质量改善（洞少、高度低）也给正向奖励，提供密集学习信号。
- Epsilon-Greedy：ε 从 1.0 按 0.9997 指数衰减至 0.01，保证足够的探索期。
奖励设计：
| 事件 | 奖励 |
|---|---|
| 消 1 行 | +1.0 |
| 消 2 行 | +3.0 |
| 消 3 行 | +5.0 |
| 消 4 行 | +8.0 |
| 存活每步 | +0.01 |
| 游戏结束 | -2.0 |
| 棋盘质量改善 | +0.1×Δ质量 |
核心思路：直接学习"在状态 s 下选择各落点的概率分布"（策略），而不是像 DQN 那样学 Q 值再间接推出动作。
Actor-Critic 架构：
状态（5维）
→ 共享主干（FC128→ReLU→FC128→ReLU）
├── Actor 头（FC→Softmax）→ 各落点选择概率
└── Critic 头（FC→1） → 当前状态价值 V(s)
- Actor（演员）：决策者，输出动作概率分布
- Critic（评论家）：评估者，告诉 Actor "这个状态有多好"，降低梯度方差
PPO 核心机制（Clip）：
普通策略梯度每次更新可能幅度过大，导致策略突然变得很差。PPO 限制新旧策略的概率比 r = π_new/π_old 在 [1-ε, 1+ε]（ε=0.2）之间，超出范围就停止增加梯度：
Loss = min(r × A, clip(r, 0.8, 1.2) × A)
好处：同一批数据可以重复训练 4 次（PPO_EPOCHS=4），不会走偏。
GAE 优势估计：
优势 A(s,a) 表示"执行动作 a 比平均水平好多少"。GAE 用 λ=0.95 混合多步估计，平衡偏差和方差：
λ=0 → 只看一步（低方差、高偏差）
λ=1 → 看完整轨迹（低偏差、高方差）
λ=0.95 → 两者折中
并行训练：启动 cpu_count() 个子进程并行收集轨迹，主进程汇总后统一更新策略，训练效率显著高于 DQN 的单步在线更新。
本项目训练结果：失败
PPO 在本项目中未能有效收敛，原因分析：
-
动作空间映射不合理：模型输出固定大小的 logits，通过
% len(valid_actions)取模映射到合法落点。这导致多个输出索引对应同一落点，梯度信号极度不均匀，策略梯度方向混乱。 -
奖励过于稀疏：下落方块游戏只有消行才有显著正向奖励，早期 agent 几乎随机落子，平均每步奖励长期在 -0.19 左右（存活奖励 0.01 × 约10步 被 -2.0 死亡惩罚淹没），GAE 优势估计无效信号。
-
与 DQN / 遗传算法输入相同（5 维特征）：PPO 的优势在于处理高维感知输入（图像、像素），当输入退化为 5 个手工特征时，其表达能力与启发式没有差异，复杂度反而更高。
-
Early Stopping 阈值错误：
MIN_DELTA=0.5远超奖励总变化范围（约 0.1），导致 200 轮后就提前终止，训练实际从未真正开始。（已修复为 0.005，但根本问题仍在。）
结论：在 5 维特征输入 + 稀疏奖励的设置下，PPO 不适合本项目。如需改善，需要改用像素输入或大幅重设计动作空间（每步构造固定长度的落点候选并直接 softmax）。
所有算法共用 core/placement.py 中的 BFS 寻路。方块从出生位置出发，通过左移、右移、旋转、逐格下落搜索所有实际可达的落点，包括需要先横移才能插进悬崖下方的位置——与人类真实操作完全一致。
直硬降（旧）：只能垂直落下，无法插入悬崖
BFS（新）：先滑进入口，再钻到悬崖底部
↓ ↓ ↓ . → → ↓
X X X X X X X X X X
. . . . . → . . . . . ← 能找到这里
. . . . . . . . . .
# 遗传算法
python algorithms/genetic/trainer.py
python main.py --mode ai --algo genetic
# DQN
python algorithms/dqn/trainer.py
python main.py --mode ai --algo dqn
# PPO
python algorithms/ppo/trainer.py
python main.py --mode ai --algo ppo训练过程中各算法会自动将日志写入 algorithms/<algo>/weights/training_log.csv。训练完成后运行：
# 画全部三个算法的对比图（输出 training_curves.png）
python plot_training.py
# 只画单个算法
python plot_training.py --algo genetic
python plot_training.py --algo dqn
python plot_training.py --algo ppo
# 指定输出路径
python plot_training.py --out results/my_curves.png图表包含三条线：原始值（浅色）、平滑均值（深色）、历史最优（红色虚线）。
python -m pytest tests/ -v| 按键 | 手动模式 | AI 模式 |
|---|---|---|
| L / R | 移动 | — |
| Up | 旋转 | — |
| Down | 软降 | — |
| Space | 硬降 | 分步执行一步 |
| +/- | — | 调节 AI 速度 |
| M | — | 切换分步模式 |
| ESC | 暂停 | 暂停 |
| R | 重新开始（结束后） | 重新开始 |
- DQN / PPO：Apple Silicon 自动使用 MPS，其他设备使用 CPU
- 遗传算法 / PPO：使用
cpu_count()进程数并行，训练有明显提速