|
|
这个脑洞起源于一道题目。大意是有固定的格子，制作一个AI来让游戏不死。
这题的格子很少，于是可以分类讨论，只要8种情况（好像是？）
先后我去找了一些资料。
发现实现AI的大概思路都是利用启发函数来得到每种状态每个位置的最优解，只考虑当前的一个方块。
对于俄罗斯方块游戏的设计，我用了wiki上面的规定和游戏规则：
1.10个格子宽+22个格子的高，通常情况下21-22个格子被挡住。
2.有 “I”, “O”, “J”, “L”, “S”, “Z”, “T”.七种方块。
3.允许获得下一个方块的形状（因为我设计的AI不许要考虑下一个方块，所以我没有在界面中实现）
4.更多具体参见：http://tetris.wikia.com/wiki/Tetris_Guideline
游戏部分具体的实现不细说，方法很多。
AI部分：
我试过多种启发，后来找到了一种Pierre Dellacherie's Algorithm，这里我主要说。
这种算法有如下评价
1.Landing Height）：本次下落的方块中点地板的距离
2.Row eliminiated)：本次下落后此方块贡献（参与完整行组成的个数）*完整行的行数
3.Row transitions）：在同一行，方块 从无到有 或 从有到无 算一次（边界算有方块）
4.Column transition）：在同一列，方块 从无到有 或 从有到无 算一次（边界算有方块）
5.Hole num）：空洞的数量。空洞无论有多大，只算一个。一个图中可能有多个空洞
6.Well sum）：井就是两边都有方块的空列。（空洞也可以是井，一列中可能有多个井）。此值为所有的井以1为公差首项为1的等差数列的总和
例：共三个井，2，3，1 wellsum=（1+2）+（1+2+3）+1；
它们的权值分别为
1 | -4.500158825082766 | 2 | 3.4181268101392694 | 3 | -3.2178882868487753 | 4 | -9.348695305445199 | 5 | -7.899265427351652 | 6 | -3.3855972247263626 |
分数为所有评价和权值的乘积的和
经过多次实验发现这个启发非常可靠。在目前的测试看来100W行后还在稳定运行。
源码
AItetris (4).zip
(79.57 KB, 下载次数: 948)
参考资料：
http://imake.ninja/el-tetris-an- ... acheries-algorithm/
https://codemyroad.wordpress.com ... ear-perfect-player/
http://tetris.wikia.com/wiki/Tetris_Guideline
|
|
发表于 2017-3-4 22:10:11
发表于 2017-6-26 21:03:52
