TocHomeGithubInfo

program/tetris

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


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

开始游戏

算法实现

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

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

  • 接触面 (Contacts): 计算方块落稳后,其边缘与其他方块或边界接触的总面数。接触面越多,通常意味着方块嵌入得越好,结构越稳定。因此,在损失函数中,这是一个增益项(计算时取负值)。
  • 消除行 (Cleared Lines): 一次操作能消除的行数。这是游戏的核心目标,因此它在评估中占有最高的权重,是一个非常强的增益项。
  • 空洞 (Holes): 指的是在方块下方被封闭住的空格。空洞是游戏中的“坏”状态,难以填补且浪费空间,因此它是一个惩罚项。
  • 高度 (Height): 方块堆积的平均高度。高度越低,未来的操作空间就越大,局面越有利。因此,高度也是一个惩罚项。

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

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

一些实现细节

  1. 双层前瞻:AI仅仅考虑当前方块的最佳落点,还会预读下一个即将出现的方块。 具体流程如下:
    1. 对于当前方块的每一种可能走法,AI会先计算出落子后的临时局面和损失值(loss1)。
    2. 接着,基于这个临时局面,AI会继续对下一个方块进行完全相同的模拟,找出下一个方块在该局面下的最优走法,并计算其损失值(loss2)。
    3. 最终,AI会将两个损失值相加(loss1 + loss2),并将这个总和作为评价当前方块走法的最终依据。
    • 这种“走一步,看两步”的策略让AI具备了更强的规划能力。它会避免那些虽然对当前方块有利,但可能会给下一个方块制造麻烦的短视操作,从而做出更具战略性的决策。
  2. 对称性优化:为了提高计算效率,AI在模拟旋转时利用了方块的对称性。即:
    • “O”型方块(正方形)只有1种旋转形态。
    • “I”型、“S”型、“Z”型方块只有2种有效旋转形态。
    • “L”型、“J”型、“T”型方块有4种旋转形态。

让AI决定下一个方块

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

  • 最佳方块:哪种方块是当前局面最需要的“救星”(最低loss)。
  • 最差方块:哪种方块是当前局面最不希望遇到的“麻烦制造者”(最高loss)。

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

已知bug

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