遗传算法 训练俄罗斯方块策略

代码见仓库https://github.com/hereisaway/Tetris_AIvibe coding出来的可能有点小问题但能跑。思想游戏策略也是一个启发式算法大展拳脚的领域。对于很多游戏策略可以简化为需要一个估值函数对当前局面下每一种操作进行估值然后选择估值最高的操作执行。这样的关键是这个估值函数输入是当前局面操作输出一个估值复杂的策略可能对当前局面参数做复杂的处理比较简单的策略就把这个问题当成一个回归预测输入的局面和操作当成特征只需要找到一组合适的特征再对于特征找到一组合适的权重即可。到了这一步就是要优化一组参数得到一个函数这玩意启发式算法熟啊。直接把特征放到遗传算法的基因里跑遗传算法来优化这个参数。实现整体思路是得到一个种群取出个体基因解码得到一组权重用这个权重去模拟一局俄罗斯方块直到失败或者到达模拟轮数上限计算这局的表现分作为基因的适应度通过遗传算法产生下一代俄罗斯方块模拟器首先需要写一个俄罗斯方块模拟器传入一个策略函数模拟指定轮数每一轮随机生成一个下落方块并可以提示下一步的方块是什么对于当前局面下枚举当前方块下落到哪个位置计算下落后考虑消行的新局面把新局面作为输入传给估值函数对每一种下落位置计算出一个得分选择得分最高的操作执行。由于只想知道得分不需要可视化可以在模拟中做一些加速。实际上这个模拟器就是整个训练的瓶颈遗传算法杂交变异跑得很快。但模拟这个阶段由于策略很快就能达到一个较高的水平可以存活几千轮甚至几万轮每次的模拟都会耗时很久。一个朴素的想法是设置一个轮数上限但这样又有新的问题可能很快所有的个体都能达到这个轮数上限了得分都差不多环境失去选择压力趋于随机化而不是优化。所以这里原本的demodemodemo用pypypy写后面改写成cppcppcpp了模拟阶段实现了约60x的加速比每秒可以模拟几千轮轮模拟一万轮的时间也可以接受。加上遗传算法可以并行化每个线程负责部分个体的模拟开了323232线程后即使遗传算法超参数较大耗时也在一两分钟这个级别。特征工程估值函数的特征选择直接收益lines_cleared、eroded_cells堆叠风险aggregate_height、covered_cells、max_height、well_sum结构平整度bumpiness、row_transitions、column_transitions洞相关holes、hole_depth、rows_with_holes直接收益比较好理解就是这一块落下去能消几行。但这样不够剩下的特征考虑的是这一块落下后会不会产生不太好的结构不利于后面的消除比如产生了一个洞或者导致表面不平。遗传算法设计遗传算法比较关键的设计在于如何指定适应度计算这里选择fitness 1000 * avg_lines 0.1 * avg_score 0.5 * avg_pieces - 50 * survival_rate其中avg_lines 多局平均总清行avg_pieces 多局平均存活块数avg_score 多局平均简化分数survival_rate 多局里有多少比例“活到了 max_pieces 上限”取平均是因为模拟器一局游戏有随机性生成的块序列是随机的为例避免运气好带来的偏差多取几个种子跑取随机。消行数和存活块数很简单分数的定义是score_episode Σ_t (lines_cleared_on_move_t)^也就是每一次消除的行数的平方和这样鼓励一次消多行。运行框架设计最近和别的项目学六一下运行设计为了便于以后更新阅读。设计成每次运行都会新开一个目录记录输出搜索到的最优参数运行用的超参数运行日志记录运行了几轮每一轮的时间总结文件一个md记录配置启动指令优化效果