TocHomeGithubInfo

program/tetris

由算法控制难度的俄罗斯方块

如果一个俄罗斯方块每次给你的方块不是随机的,而是暗中由算法控制,或是帮助你,或是阻止你。

开始游戏

算法实现

AI的核心思想是模拟。对于当前正在下落的方块,AI会穷举其所有可能的旋转状态和最终落点位置。对每一种可能性,它都会模拟方块下落后形成的新局面,然后使用一个评估函数来为这个新局面打分。分数越低,代表局面越优。最终,AI会选择那个能够产生最低分(即最优局面)的操作来执行。

评估函数

评估函数是AI的决策核心,它通过计算损失值来判断一个局面的好坏。这个损失值由四个指标加权计算得出:

  • 接触面:计算方块落稳后,其边缘与其他方块或边界接触的总面数。接触面越多,通常意味着方块嵌入得越好,结构越稳定。
  • 消除行: 一次操作能消除的行数,游戏的核心目标。
  • 空洞:指的是在方块下方被封闭住的空格。空洞是游戏中的坏状态,难以填补且浪费空间。
  • 高度:方块堆积的平均高度。高度越低,未来的操作空间就越大,局面越有利。

通过调整这四个指标的权重,可以改变AI的行为策略,例如让它变得更激进(专注于消行)或更稳健(专注于保持低高度和无空洞)。

实现中,算法四个权重是我选取的经验值,并不一定最优。

一些实现细节

  1. 双层模拟:AI不仅仅考虑当前方块的最佳落点,还会预读下一个即将出现的方块。 具体流程如下:
    1. 对于当前方块的每一种可能走法,AI会先计算出落子后的临时局面和损失值(loss1)。
    2. 接着,基于这个临时局面,AI会继续对下一个方块进行完全相同的模拟,找出下一个方块在该局面下的最优走法,并计算其损失值(loss2)。
    3. 最终,AI会将两个损失值相加(loss1 + loss2),并将这个总和作为评价当前方块走法的最终依据。
  2. 对称性优化:为了提高计算效率,AI在模拟旋转时利用了方块的对称群。即:
    • “O”型方块(正方形)只有1种旋转形态。
    • “I”型、“S”型、“Z”型方块只有2种有效旋转形态。
    • “L”型、“J”型、“T”型方块有4种旋转形态。

让AI决定下一个方块,以此控制难度

基于上述指标,AI可以评估不同类型的方块对于当前局面的利弊。 AI可以模拟出如果下一个方块是“I”、“L”、“T”等任意一种时,局面的最优损失值分别是多少。这样,它就能判断出:

  • 最佳方块:哪种方块是当前局面最需要的(最低loss)。
  • 最差方块:哪种方块是当前局面最不希望遇到的(最高loss)。

在游戏中,有一个难度条,当为0时,是原版默认的俄罗斯方块; 当为正数时,每个下落的方块会有难度数值的概率转交给AI决定,使用当前情况下的最差方块; 当为负数时,每个下落的方块会有难度数值绝对值的概率转交给AI决定,使用当前情况下的最佳方块。

已知bug

  • 有时玩到后期旧方块没完全下落同时生成新方块,方块相撞导致游戏结束;
  • 游玩时未暂停切出标签页不会自动暂停。
目录