640?wx_fmt=gif

640?wx_fmt=jpeg

作者 | Ahab
责编 | 仲培艺

人工智能大火的今天,如果还是自己玩俄罗斯方块未免显得太 LOW,为什么不对游戏升级,让机器自己去玩俄罗斯方块呢?有了这个想法之后,我用了两天时间去搜集了大量资料,在电脑死机好多次之后终于将 AI 俄罗斯方块实现了。


640?wx_fmt=png

程序介绍


所谓让机器自己去玩俄罗斯方块,就是让机器计算当前方块的所有形态可放置的所有位置,然后根据统一的评价标准,计算出最优的位置进行放置。这个评价的标准简单的来说就是:板块放置的位置越靠下越好,方块之间越紧密越好,自身对消除行的方块贡献数量越多越好,但是这里还要注意的是不可为了追求消除行数,而去造成过多的空洞,这样也是不合理的。

关于 AI 算法主要有两种:一种是经典的 Pierre Dellacherie 算法,一种基于基于深度搜索的算法。深度搜索需要优化的地方很多,假如计算的层数不够、没有高效剪枝,一不小心容易写成人工智障,时间复杂度也不好。Pierre Dellacherie 算法更加清晰,复杂度更低。但是该算法只考虑当前,不对未来的情况进行计算,注重的是“不死性”,追求方块的“密集”,有时就算可以一次性消除 3 行,却会使全局方块更加“疏”,即过多的空洞。

代码由 Tetris.pyAI.pyUtils.py 三部分组成,游戏的主要逻辑由 Tetis 控制,Utils 定义了方块的样式,AI 顾名思义实现了主要的 AI 算法。


640?wx_fmt=png

具体介绍


Pierre Dellacherie 算法

只考虑当前方块,不对未来的情况进行计算,注重的是“不死性”,算法每次生成一个方块,便穷举该方块所有旋转的落点。一种方块最多有 4 种旋转,并且由于游戏界面是 10*20 的,所以对于每个旋转形状,只需要考虑 10 种落点。算法的核心是一个评估函数,对穷举出的每一种下落情况,计算 6 个参数值,用评估函数加权求和得到一个值,该值最大的情况便是目前方块的最优下落位置,六个参数分别是:

1. 下落高度(Landing Height)

当前方块落下去之后,方块中点距底部的方格数(事实上,不求中点也是可以的)。

2. 消行数(Rows eliminated)

消行层数与当前方块贡献出的方格数乘积。

3. 行变换(Row Transitions)

  • 从左到右(或者反过来)检测一行,当该行中某个方格从有方块到无方块(或无方块到有方块),视为一次变换。游戏池边界算作有方块。行变换从一定程度上反映出一行的平整程度,越平整值越小;

  • 该指标为所有行的变换数之和;

  • 如图:■ 表示有方块,□ 表示空格(游戏池边界未画出)

    • ■■□□■■□□■■□□ 变换数为 6

    • □□□□□■□■□■□■ 变换数为 9

    • ■■■■□□□□□□■■ 变换数为 2

    • ■■■■■■■■■■■■ 变换数为 0

4. 列变换(Column Transitions)

大意同上,列变换从一定程度上反映出一列中空洞的集中程度,空洞越集中值越小。

5. 空洞数(Number of Holes)


6. 井的总和(Well Sums)

井指两边皆有方块的空列。该指标为所有井的深度连加到 1 再求总和。

注意一列中可能有多个井,如图:

 
 
  •   ■□□

  •    ■□■ 
    
  •    ■□■ 
    
  •    ■■■ 
    
  •    ■□■ 
    
  •    ■□■ 
    
  •    ■□■ 

中间一列为井,深度连加到一的和为 (2+1)+(3+2+1)=9

640?wx_fmt=png

评估函数如下 (首字母简写):

640?wx_fmt=gif

关于方块形态

这里对 AI 俄罗斯方块的形态做一下特别说明,各个方块都是根据中心点的坐标来生成的,以(0,0)为中心点,在 x、y 轴加减 1 则是其他方格的坐标,这样的好处就是只要确定中心点坐标,其他的方格位置就能随即生成。

看图就懂:

640?wx_fmt=png

 1# 每种块包含的四个小方块相对坐标分布
2        self.shapes_relative_coords = [
3                                         [[00], [00], [00], [00]],
4                                         [[0-1], [00], [01], [02]],
5                                         [[0-1], [00], [01], [11]],
6                                         [[0-1], [00], [01], [-11]],
7                                         [[0-1], [00], [01], [10]],
8                                         [[00], [0-1], [10], [1-1]],
9                                         [[00], [0-1], [-10], [1-1]],
10                                         [[00], [0-1], [10], [-1-1]]
11                                      ]
基于深度搜索的方法暂不介绍。


640?wx_fmt=png

收获成果


以上,感兴趣的同学可通过网盘获取源代码:https://pan.baidu.com/s/1gC6sF62Pz5D6rh6eicOZUw,提取码: k17b。

作者简介:公众号【Ahab杂货铺】号主,在校学生沉迷于Python编程。

【完】

640?wx_fmt=jpeg

 热 文 推 荐 

极客头条

未来五年,iOS 开发如何前行?

☞ 单身暴击!程序员用 Python 给女朋友写了个翻译软件

☞ 35 岁程序员,年后第一天被辞退

☞ 云漫圈 | 学Python还是Java, 8张漫画带你全面分析

☞ 一次性掌握机器学习基础知识脉络 | 公开课笔记

☞ 骗局翻新, 暗网活跃度倍增, 2018加密货币犯罪报告敢看吗?

☞ 程序员年后离职跳槽指南

 
 

print_r('点个好看吧!');
var_dump('点个好看吧!');
NSLog(@"点个好看吧!");
System.out.println("点个好看吧!");
console.log("点个好看吧!");
print("点个好看吧!");
printf("点个好看吧!\n");
cout << "点个好看吧!" << endl;
Console.WriteLine("点个好看吧!");
fmt.Println("点个好看吧!");
Response.Write("点个好看吧!");
alert("点个好看吧!")
echo "点个好看吧!"

640?wx_fmt=gif点击“阅读原文”,打开 CSDN App 阅读更贴心!

640?wx_fmt=png 喜欢就点击“好看”吧!
Logo

20年前,《新程序员》创刊时,我们的心愿是全面关注程序员成长,中国将拥有新一代世界级的程序员。20年后的今天,我们有了新的使命:助力中国IT技术人成长,成就一亿技术人!

更多推荐