博客:传统规则俄罗斯方块 AI 技术介绍

来自俄罗斯方块中文维基
这是一篇博客。博客作者是 Misakamm,发表于 2014年05月13日。
博客的著作权默认完全归作者所有,除非另有声明。未经作者授权,禁止修改或转载。

施工中。本文在使格式适当适配wiki的前提下尽量还原原文(也就不去给中西文之间一个个加空格了(逃

本文介绍了传统方块传统目标 AI 的当时状况,及基于 Standard Tetris (PC, 2003) (以下简称“ST”)的一些实验结果。此时 Misakamm 在与用户:Farter及方块社群的交流中已了解多种现代方块特性,也在制作官方对战方块的 AI(Misamino)中,故清晰指明了单双块区别,以及许多当时的论述俄罗斯方块 AI 的文章未明确说明的一些“传统”细节。

原版 ST 内部接口仅支持输出“旋转、横向位置”,且执行过程简单粗暴(只能旋,移,直接硬降),甚至不管阻挡情况失败。Misakamm 为 ST 程序本体添加了 AI 输出需要更复杂操作才能达到的位置情况的支持(作为另一种方式,保留了原有)、添加了周期更长的随机数生成器,同时又以新接口接入了 Misakamm 自制的 AI 。本文介绍了 Misakamm 取得的更高成绩,同时也有一些其他 AI 长时间运行的测试数据,具有很高参考价值。

这些改动经过细致测试,保证了原程序自带的 AI 执行结果与原版完全一致,所用规则难度没有发生任何变化。实际上规则上的细微差距就可以对(平均期望)成绩带来几倍的区别,ST 是一次严格统一规则的尝试,但其原版的粗暴代码实现,又让“AI 能做到的事”少于“人能做到的事”了。本着对“如果 AI 会软降,且在妥协时会构造好的需要软降补的坑,会不会还能创造更佳成绩”的探索,为原程序加入了这些功能。

此改造版本(包含 Misakamm 所作 AI)已开源于 GitHub,但文中未提及。

Misakamm 同时还在百度贴吧的 C 语言吧(贴子)、C++ 吧(贴子)上发起了以此为规则基准的传统俄罗斯方块 AI 比赛,然而似乎没有吸引来新的参赛选手。(ax_pokl 是看那贴子来的么?)

版权说明

待补

传统规则俄罗斯方块AI技术介绍

传统俄罗斯方块介绍

  俄罗斯方块,英文Tetris,俄语Тетрис。发明者Alexey Pajitnov (Russian: Алексей Леонидович Пажитнов, regularly Aleksei Leonidovich Pazhitnov, born 1956)于1984年6月6日发布,名字由希腊数字4的前缀tetra-与网球tennis(作者最喜爱的运动)合并而来。

  传统俄罗斯方块,指的是Alexey Pajitnov所发明的版本,游戏场地标准尺寸为10×20,而每个方块由四个小方块拼成,一共有7种不同的形状,相应的象形字母为ITOSZJL。每种形状均可以90度旋转,当一行堆满方块时,此行就会消去,在其上面的方块就会下降一行。在消除的同时,按照一次性所消除的行数,累加不同的积分,看谁能在失败之前得到最多的积分。

(图) FC俄罗斯方块

(图) Standard Tetris运行Misakamm two-piece AI,已消超过5亿行和10亿行的截图  

俄罗斯方块AI介绍

  传统的俄罗斯方块,版本有很多种,但是基本上都有一个特点,就是只能看到一个next方块,少数的甚至根本不显示next方块。也就是说,要做AI的话,也只有两个选择:考虑next和不考虑next。而不考虑next的是最多的(由于早期机器性能原因,或由于偷懒),任天堂、世嘉等的各版本俄罗斯方块中所带的AI绝大多数都是不考虑next的。当时,俄罗斯方块的AI研究,主要是围绕如何才能“不败”。在证明俄罗斯方块是NP-complete问题(于2002年11月完成证明并发表论文),以及证明完全随机的方块最终游戏一定会结束(Heidi Burgiel. How to lose at tetris. Mathematical Gazette, 81:491:194–200, July 1997)后,研究者开始围绕one-piece(单块,不考虑下一块的)算法,在只知道当前的方块的情况下,怎么样的AI平均能得到更高的积分或消除更多的行。在这里的研究中,最为出名的算法,是Pierre Dellacherie(France)于2003年1月创作的算法,当时在世界范围内取得了平均最高消行数。此AI最高消行超过200万行,平均65万行(在Colin Fahey的emulator上)。因为它们只为了得分或消行数高,不会主动的垒四行,在人的眼里看来,这些AI有时候相当的笨,除了速度快,没有多少优点。  

俄罗斯方块AI基础

  传统规则下,如果你也想制作一个one-piece(单块或只看当前块,不考虑下一块)算法,那是相当的简单的,网上也有相当多的人的不同实现。不过,这些AI程序均不考虑架空可以平移插入的情况,并且这些AI的做法也相当的一致,穷举最多10*4种可能性(不考虑下落中途横插去补洞),然后针对每一个可能性进行评分,AI按照得分最高的那个位置进行摆放即可。建议先自行实现一个评估方案后再参考Pierre Dellacherie的评分算法,也可以参阅这个pdf,介绍了现有的不同的评分方式,里面还有介绍Pierre Dellacherie的评分公式和Thiery and Scherrer的评分公式。或者也可以参阅此网友的实现,还有Colin Fahey的实现,里面包含实现源代码,有若干个实现版本。

  要注意的一点是,俄罗斯方块的AI类型与棋类AI很不一样的地方,就是俄罗斯方块不仅仅与局面相关,还与产生这个局面的行动(即最近一块的摆放位置产生的效果)有关,达到同一个局面,是消行产生的还是不通过消行产生的是完全不同的,但棋类根本不必关心产生这个局面的前一个局面是什么样子的(和棋或长将什么的例外),这个根本上的区别导致它与棋类AI会很不一样。不少的单块AI实现使用了最近一块摆放的位置和效果信息,比如高度,消行数等等,单块的AI下使用这些信息并没有什么大问题,实现上相对自由。但若打算做多块AI的话,使用的信息就要非常慎重小心了。

  局面信息的选取,并没有什么规定,纯经验类的东西。不过大部分的AI都会使用到“洞”的个数,即空格子的上方若有实心格子,那么它就定义为洞。但这个信息的选取对AI的影响非常的大,并且有很多坑。后文将对此解释。

  有了基本的理解后,就需要动手搭建一个游戏。编写的时候注意,这里有一个规范性的问题,规范性内容至少包括:

  1. 新方块出现的位置;
  2. 那7个形状旋转后的形状及位置,可参阅colin上的图;
  3. 产生碰撞而不能移动或旋转的处理(传统规则下还没有踢墙的概念);
  4. 玩家的所有可操作集合(有没有重力影响,单向旋转还是双向,单向的话是哪个方向,下落是下落一格还是直接到底还是两者均可等等);
  5. AI的可操作集合是否与人类玩家一致(不一致即使用作弊方式,比如直接移动到目的地不管事实上能不能办到);
  6. 下一块的产生算法(使用什么样的随机函数,是否带有记忆或限制条件,是否与玩家当前场地有关等等);
  7. 当前操作方块旋转时会不会高于游戏场地,允不允许高于的情况出现。

  规范若有差别,很可能是相同AI下表现却很不一样。根据以上规范性问题,在这里和读者约定一下主要的规范:

  1. 新方块的4*4矩阵出现在游戏场地内最顶部的中间,若场地宽度为奇数,则出现于偏左边;
  2. 方块旋转以上文中的图片为准;
  3. 碰撞时操作取消;
  4. 玩家可以做的操作有,左移一格,右移一格,逆时针旋转90度,直接下降到底部并固定,无重力;
  5. AI只能做人能做的事,不能作弊;
  6. 使用MT19937算法,以线性均匀分布方式产生方块序列,种子使用当前时间,仅打开程序时初始化种子,重新开始游戏不重新初始化随机数种子;
  7. 不可能出现高于顶部。

  另外,AI部分规定先旋转再移动,以便移植到colin的平台上有相同的行为,即不支持下图中的行为:

(gif)

  这里有一点需要注意的,就是随机数算法的影响。如果用随机性一般的算法,会对其AI性能有非常大的影响,有的会令其平均行数大幅提升,有的会令其大幅下降,所以建议使用随机性较好的MT19937算法,且必须以线性均匀分布方式产生。  

one-piece AI排行榜(不完整,仅参考用)

  在这里约定使用Colin Fahey(或类似)的emulator上,场地大小为10×20,one-piece(不带next块)。目前在这平台上,实现了的包括Pierre Dellacherie的算法、Colin实现的Roger LLima/Laurent Bercot/Sebastien Blondeel算法、Colin Fahey自己的、由Misakamm实现的Thiery and Scherrer算法、Misakamm实现的两个版本的算法。之所以直接用这个平台,是因为这个实现在one-piece AI里很有代表性,同时Misakamm也懒得再自己搭建一个了,除了少许地方与前面所说的规范在随机数略有区别外,其它几乎都一样。而且它不会硬生成10*4种摆法,而是会验证在以上规范下能不能移动达到再去计算。

单块规则排行榜(Updated on: 12 April, 2014)
AI名称及年代
A.I. name & year
平均行数
average rows
运行局数
total games
历史最高行数
max rows
Misakamm Ver2.0 (2014) 2,727,734 577 15,219,733
Misakamm Ver1.0 (2014) 1,309,011 1752 11,048,999
Thiery and Scherrer (2009)[注 1] 867,695 2086 7,256,062
James and Glen one-piece (2004) 592,334 1226 5,180,342
Pierre Dellacherie (2003) 578,921 1959 4,109,278
James and Glen one-piece (2004) 568,595 1412 4,330,312
Roger LLima etc. (2005) 42,000 - -
Roger LLima etc. (1996) 19,406 2224 123,020
Kakade (2001) 6,800 - -
Farias and van Roy (2006) 4,700 - -
Bertsekas and Tsitsiklis (1996) 3,200 - -
Lagoudakis et al. (2002) 2,000 - -
Colin Fahey (2003) 644 464 4,905
Ramon and Driessens (2004) 50 - -

注:历史最高行数只限于本人运行的结果里,只要运行局数更多便可能运行出更高的成绩。

没有运行局数和历史最高行数的,其平均行数来自于论文中的数据。平均行数为运行的结果值,每一百局的平均值的误差约为±20%。

运行效率方面,在我的机子上,James and Glen one-piece约为800 row/s,Pierre Dellacherie 的约为 2200 rows/s,Misakamm Ver1.0 约为 2400 rows/s,Misakamm Ver2.0 约为 5700 rows/s。

以上数据由Misakamm及其网友使用4台4核或8核PC同时运行10多个验证程序,运行多天收集的数据,数据全部真实有效。

Colin Fahey的算法主要用于两块(有next预览)的情况,评估方式和单块的不一样,在单块下显得偏低。

Pierre Dellacherie对自己的算法的运行结果:运行了20局,平均631,167行。这个算法为2003年的单块AI世界冠军。

Thiery and Scherrer的算法自称平均35,000,000行,是在新方块出现位置完全在场地外(即方块直接到达目的地不考虑阻挡的方式)打出来的,接近于在colin的规范下打10×24的场地,而在10×16下论文称平均能打出910,000行,与Misakamm的实现版本的实际运行结果接近。

Thiery and Scherrer的算法基于Pierre的算法基础上添加更多的评估然后使用CE(cross-entropy method)优化参数而得。这个算法为2009年的单块AI世界冠军。

有些AI的目的是实验新的自学习算法,不应该单纯看结果来评估其好坏。

James and Glen的由于不开源,只有测试程序,只能测出结果,目前也找不到相关的论文。

Misakamm版本验证程序,修改自Colin Fahey的Standard Tetris 2007,除原生算法外,另加入Misakamm两个版本的AI,即还包含Colin的AI、Pierre Dellacherie的AI、Roger等的AI。

以上两个验证程序的基本操作说明:shift+A切换AI;A键启用AI;N键启用next块(不启用时AI不知道next块);+-键游戏变速;ctrl+方向键调整场地大小。Misakamm Ver2.0算法因为使用了二进制优化手段,不支持超过16×32的场地。

场地高度与平均行数的关系

Pierre Dellacherie (2003)
场地高度(宽10) 平均行数(误差±20%每百局) 历史最高行数(仅参考)
7 15 175
8 42 425
9 105 1,194
10 250 1,955
11 540 3,938
12 1,240 8,549
13 2,700 13,471
14 5,800 37,696
15 13,000 69,243
Misakamm Ver1.0 (2014)
场地高度(宽10) 平均行数(误差±20%每百局) 历史最高行数(仅参考)
7 23 182
8 63 448
9 170 1,138
10 370 2,061
11 770 4,001
12 1,900 11,702
13 4,500 18,618
14 10,000 40,080
15 24,000 191,058

  可以看出,高度大于9的时候,高度每增加1,平均行数就要乘以2.2左右,我称之为增长系数。这个系数不同的算法下会不一样,我们可以根据这点来猜测行数更大的时候的结果。比如Pierre算法的表中,高15的时候平均13000行,我们又知道高为10的时候平均250行,那么可以估计出高为20的时候,约为 13000 / 250 * 13000 ≈ 676,000 行 (实际值600,000行),又或者Misakamm算法中,由 24000 / 370 * 24000 ≈ 1,560,000 行(实际值1,300,000行)。估算时不要使用高度小于10的数据,否则误差会很大。  

AI设计与优化

  在AI设计的部分,最重要就是形势评估了。不过小心等效评估,比如你使用消行数,和场地内的实心格子数,实质上,假设宽是w,消一行就等于减去(w-4)的格子数,不消行则增加4格,也就是说消一行与不消的差别就是w;若消行数乘以宽度,差别也正好是w,两者效果完全相等。也就是说,若分值与宽度相关,直接使用实心格子数,无关的话直接使用消行数(实际经验表明直接使用消行数比使用实心格子数好得多,因为宽度较大的时候,使用实心格子数的评估会导致为了消个行不惜其它代价),避免使用消行数乘以宽度的同时又使用实心格子数这种愚蠢的行为。还有一类愚蠢行为是使用相对分,比如评估使用方块放下前,与放下后的两个局面做对比,对比洞的变化数。为什么说这是愚蠢行为呢,其实这种相对分差的比较与直接比较放下后的局面的分完全等效,比如放下前的局面有A个洞,放下后其中两个局面,洞数分别为B1和B2,那么相对方式的分就是比较B1-A与B2-A的大小关系,直接比较的方式就是比较B1与B2的大小关系,可以看出为了判断B1-A与B2-A的关系,只需要直接比较B1与B2就可以了,不管A是多少,根本没有任何影响。

  那么光是洞的数量,和消的行数这两个信息够不够用呢?如果只使用这两个,那么AI在某些情况下,会摆出又高又多的“塔”来避免产生洞,结果是输得非常的快。一个好的AI还需要考虑什么时候合理的制造洞,不可避免的产生洞时怎么处理,为了解洞在它上方建立什么形状等等,把这些感性的形状方面的理解,一点点归纳为程序逻辑。为了帮助理解可以自行做一个大小为10×9甚至更小的场地的游戏来打,找找感觉。

  有了基本的评估后,我们就可以开始做优化了。有不少人做俄罗斯方块AI,在他会点遗传算法/模拟退火/神经网络/粒子群/CE等等后,往往他会草草的选择若干个评估然后直接套用以上算法跑出较优参数或直接训练他的n层神经网络然后直接跑出结果。问题是,由于其结果的极其不稳定性(100局的平均行数也有20%甚至更大的偏差),同样会导致训练结果的不稳定性,找出的参数往往在一个范围里徘徊却极难找到更优结果。而ANN的实现目前还没有找到实现得比较理想的。盲目的添加较多的评估让算法寻找参数的做法,容易因个别的参数不合理造成错误导向,跑到局部较优解上。于是程序训练其实还是次要的,最终决定还在于评估组合的设计上。而AI的强弱关键有三点,1是能不能正确处理造洞和解洞的矛盾关系,2是这个AI会不会做出极其反常的行为迅速自杀,3是在于AI处于不利环境时的决策。比如,现在由于很久等不到I块,留了一个很深的坑,如果继续留,等不到I来的话就很快挂掉了,而拿一个方块去堵洞,或者造好形状用SZLJ填进去消行,均比只等待I块要好得多。而一但决定去堵洞,就会同样的面临着什么时候去解洞的问题,因为在解出这个洞并开始向下消行以前,从那个洞开始的行以下的形状无法产生影响,自然就完全不会变化。若有一个评分能驱使AI在某种条件下去堵洞(即不堵就分数低),那么解洞时就会有同样的低分数,很容易会让AI宁愿在上面摆也不去解洞,处理得不好的时候会让AI一但堵了那种深坑,就再也不去解了,这种处理不好造洞和解洞的AI显然会很快输掉。再比如,你能正确处理宽度为1的坑,但没有管宽度为2的情况(Pierre Dellacherie的算法正是这样),于是某些条件下构造了宽度为2的坑后,就再也不向坑里放方块了,很快的自杀掉。对于第三点,见下图:

(图)

对于这种情况,你的AI会放在如图中的位置吗?还是会左移一格或右移一格的位置呢?图中的位置会导致要等待LJI这三种方块中的两块才能不出现洞,不得不造多于一个洞的概率很高,而左移或右移一格的话,虽然造了一个洞,但形状较好,解洞也容易。Pierre的算法会选择左移一格的位置,你的选择呢?还有你的AI的选择呢?类似的情况数不胜数。

  Pierre的算法较好的处理了第1第3点,却在第2点留有问题,Misakamm在V1.0算法中把他的算法里对Well的定义进行了调整,宽度从1至6的坑都能识别出来,三点都较好的解决以后,其表现大幅提升,在10×20下平均是原算法的两倍行数。但至于有没有更多的关键点,现在还在探索中。

  传统俄罗斯方块的one-piece(单块)AI的能力上限可以到哪里,到现在也没有人知道,事实上这个依旧处于初步探索中,有人猜测现在的最好成绩(平均260万行)还远远没到上限。  

two-piece AI测试

  本测试的测试对象,为Colin Fahey two-piece (2003)、James and Glen two-piece (2004)和Misakamm two-piece (2014)三个AI,场地高度从7开始。

Colin Fahey two-piece (2003)
场地高度(宽10) 平均行数(误差±20%每百局) 历史最高行数(仅参考)
7 18 133
8 60 394
9 155 1,060
10 400 3,790
11 1,100 8,904
12 2,600 12,310
13 6,000 28,686
14 10,000 106,715
James and Glen two-piece (2004)
场地高度(宽10) 平均行数(误差±20%每百局) 历史最高行数(仅参考)
7 18 123
8 55 282
9 160 861
10 400 2,190
11 1,100 5,437
12 2,500 13,014
13 6,000 23,206
Misakamm two-piece (2014)
场地高度(宽10) 平均行数(误差±20%每百局) 历史最高行数(仅参考)
7 150 1,383
8 700 5,003
9 4,000 12,242
10 20,000 84,675
11 100,000 357,970
12 500,000 1,181,462
13 3,000,000 12,735,286

  之所以使用较低的高度,是因为10×20情况下,运行时间太长,于是可以通过较低高度的结果来推算出10×20时候的结果。其中Misakamm的算法运行高度为13的情况时,只运行了8局,所以数据只作参考,不参与后面的计算。在我的机子上运行,Misakamm的算法速度约500rows/s。而James and Glen的算法速度约80rows/s,Colin的算法速度约150rows/s。根据上表,Colin的算法的增长系数约为2.4,据此可估算出10×20下,平均行数约为 15000 * 2.4 ^ 6 ≈ 2,860,000 行,而Colin自己曾运行过一局,成绩为7,216,290行。James and Glen的算法与Colin的接近得不忍直视(除了速度慢了近一倍),就不必去估算了。而Misakamm的算法的增长系数约为5,据此可估算出10×20下,平均行数约为 500000 * 5 ^ 8 = 195,312,500,000 行,即大约0.2T行或2千亿行,也就是说如果你真的在10×20运行这个AI,那么除非运气极度不好,否则以现在计算机的速度你等不到它输掉的那一刻。以上所有数据提供windows下的验证程序,验证程序参阅前文AI排行榜一节。  

AI的发展及现代俄罗斯方块

  前文中所提及的AI,均不支持下降到中途然后平移或旋转用于填补的情况,若AI支持此类操作,则AI的策略更为丰富,且洞的判定也更为复杂,明显的有两类不同的洞,一种是封闭的,一种是开放(有机会填补)的。不过由于要支持这种操作,生成所有摆法时需要BFS搜索,对算法要求稍高一些,且没有大力优化的话搜索速度会慢很多,同时在这方面研究的相关资料相当的少。尽管已经有这类的AI,但把它进行总结并写成文章的太少,没有多少相关经验的总结和累积,所以说这部分的研究依然还是一大片的空白。

  另外,根据前文我们可以知道在多一个预览方块的情况下,生存压力大大降低,这时候单纯考虑消更多的行的价值不大,这个时候可以考虑更复杂的规则,比如尽可能多的消三消四,则会更为精彩。而现代俄罗斯方块竞技规则复杂得多,它需要玩家做出不同难度的消行然后给予对手攻击,如消三消四,连锁,T-spin等等。这种规则下AI不但需要懂得向下挖掘,还需要会进攻前的形状构造,以及掌握攻防转换时机。若AI掌握以上复杂的策略,则看起来会很像人类在游戏。这些都给传统AI提出了巨大的挑战。不过此类AI的相关论文和资料还非常的少。虽然说俄罗斯方块的在线对战游戏的外挂很多,但那些外挂绝大多数都是依靠比人快得多的摆放速度,以提高消二消三行的频率来赢,一看就知道是作弊,它并不是以与人类相近的速度来对战,这样的AI价值不大。若以人类相近甚至一样的速度对战,即AI需要考虑攻击效率和防守效率,如何以更少的方块,既攻击对手,同时让自己的场地高度快速降低减少输的可能性,甚至可以帮助人类像棋类一样分析局面,找出较优决策的话,这样的AI才更符合俄罗斯方块竞技的初衷,对游戏改进方向以及更智能AI的发展也有很大帮助。

  Misakamm自己制作了一个AI,能支持中途平移和旋转此类操作,也支持大部分高级战术,已经能成功接入知名的在线俄罗斯方块对战游戏TOP(Tetris Online Poland)平台上运行,允许玩家自由进入这些房间与之进行等速对战,且现在受到世界各地高水平玩家广泛好评,可以参阅这个游戏视频,左边的是AI,右边是人类玩家。

其它问题

  Misakamm的源代码会在经过更为严格的验证和数据分析后,再经过其它语言(C#)的实现能重现相同的统计结果后,将由Colin发布于他的程序源码包里。对以上统计结果有任何疑问(包括数据偏差较大或错误,或实现的算法与原论文中的算法不一致导致效果有偏差,或资料有误,或需要更多的数据等),欢迎通过邮件联系,邮件地址:(邮箱截图,隐去,防spam,而且也不知道还在用不)

参考资料

  1. 得去网页时光机找