如何讓AI教機(jī)器自己玩俄羅斯方塊？

人工智能大火的今天，如果還是自己玩俄羅斯方塊未免顯得太 LOW，為什么不對(duì)游戲升級(jí)，讓機(jī)器自己去玩俄羅斯方塊呢？有了這個(gè)想法之后，我用了兩天時(shí)間去搜集了大量資料，在電腦死機(jī)好多次之后終于將 AI 俄羅斯方塊實(shí)現(xiàn)了。

程序介紹

所謂讓機(jī)器自己去玩俄羅斯方塊，就是讓機(jī)器計(jì)算當(dāng)前方塊的所有形態(tài)可放置的所有位置，然后根據(jù)統(tǒng)一的評(píng)價(jià)標(biāo)準(zhǔn)，計(jì)算出最優(yōu)的位置進(jìn)行放置。這個(gè)評(píng)價(jià)的標(biāo)準(zhǔn)簡(jiǎn)單的來(lái)說(shuō)就是：板塊放置的位置越靠下越好，方塊之間越緊密越好，自身對(duì)消除行的方塊貢獻(xiàn)數(shù)量越多越好，但是這里還要注意的是不可為了追求消除行數(shù)，而去造成過(guò)多的空洞，這樣也是不合理的。

關(guān)于 AI 算法主要有兩種：一種是經(jīng)典的 Pierre Dellacherie 算法，一種基于基于深度搜索的算法。深度搜索需要優(yōu)化的地方很多，假如計(jì)算的層數(shù)不夠、沒有高效剪枝，一不小心容易寫成人工智障，時(shí)間復(fù)雜度也不好。Pierre Dellacherie 算法更加清晰，復(fù)雜度更低。但是該算法只考慮當(dāng)前，不對(duì)未來(lái)的情況進(jìn)行計(jì)算，注重的是“不死性”，追求方塊的“密集”，有時(shí)就算可以一次性消除 3 行，卻會(huì)使全局方塊更加“疏”，即過(guò)多的空洞。

代碼由Tetris.py、AI.py和Utils.py三部分組成，游戲的主要邏輯由 Tetis 控制，Utils 定義了方塊的樣式，AI 顧名思義實(shí)現(xiàn)了主要的 AI算法。

具體介紹

Pierre Dellacherie 算法

只考慮當(dāng)前方塊，不對(duì)未來(lái)的情況進(jìn)行計(jì)算，注重的是“不死性”，算法每次生成一個(gè)方塊，便窮舉該方塊所有旋轉(zhuǎn)的落點(diǎn)。一種方塊最多有 4 種旋轉(zhuǎn)，并且由于游戲界面是 10*20 的，所以對(duì)于每個(gè)旋轉(zhuǎn)形狀，只需要考慮 10 種落點(diǎn)。算法的核心是一個(gè)評(píng)估函數(shù)，對(duì)窮舉出的每一種下落情況，計(jì)算 6 個(gè)參數(shù)值，用評(píng)估函數(shù)加權(quán)求和得到一個(gè)值，該值最大的情況便是目前方塊的最優(yōu)下落位置，六個(gè)參數(shù)分別是：

1. 下落高度（Landing Height）

當(dāng)前方塊落下去之后，方塊中點(diǎn)距底部的方格數(shù)（事實(shí)上，不求中點(diǎn)也是可以的）。

2. 消行數(shù)（Rows eliminated）

消行層數(shù)與當(dāng)前方塊貢獻(xiàn)出的方格數(shù)乘積。

3. 行變換（Row Transitions）

從左到右（或者反過(guò)來(lái)）檢測(cè)一行，當(dāng)該行中某個(gè)方格從有方塊到無(wú)方塊（或無(wú)方塊到有方塊），視為一次變換。游戲池邊界算作有方塊。行變換從一定程度上反映出一行的平整程度，越平整值越小；

該指標(biāo)為所有行的變換數(shù)之和；

如圖：■ 表示有方塊，□ 表示空格（游戲池邊界未畫出）

■■□□■■□□■■□□ 變換數(shù)為 6

□□□□□■□■□■□■ 變換數(shù)為 9

■■■■□□□□□□■■ 變換數(shù)為 2

■■■■■■■■■■■■ 變換數(shù)為 0

4. 列變換（Column Transitions）

大意同上，列變換從一定程度上反映出一列中空洞的集中程度，空洞越集中值越小。

5. 空洞數(shù)（Number of Holes）

6. 井的總和（Well Sums）

井指兩邊皆有方塊的空列。該指標(biāo)為所有井的深度連加到 1 再求總和。

注意一列中可能有多個(gè)井，如圖：

■□□

■□■

■□■

■■■

■□■

■□■

■□■

中間一列為井，深度連加到一的和為 (2+1)+(3+2+1)=9

評(píng)估函數(shù)如下 (首字母簡(jiǎn)寫)：

關(guān)于方塊形態(tài)

這里對(duì) AI 俄羅斯方塊的形態(tài)做一下特別說(shuō)明，各個(gè)方塊都是根據(jù)中心點(diǎn)的坐標(biāo)來(lái)生成的，以（0，0）為中心點(diǎn)，在 x、y 軸加減 1 則是其他方格的坐標(biāo)，這樣的好處就是只要確定中心點(diǎn)坐標(biāo)，其他的方格位置就能隨即生成。

看圖就懂：

1#每種塊包含的四個(gè)小方塊相對(duì)坐標(biāo)分布 2self.shapes_relative_coords=[ 3[[0,0],[0,0],[0,0],[0,0]], 4[[0,-1],[0,0],[0,1],[0,2]], 5[[0,-1],[0,0],[0,1],[1,1]], 6[[0,-1],[0,0],[0,1],[-1,1]], 7[[0,-1],[0,0],[0,1],[1,0]], 8[[0,0],[0,-1],[1,0],[1,-1]], 9[[0,0],[0,-1],[-1,0],[1,-1]],10[[0,0],[0,-1],[1,0],[-1,-1]]11]

基于深度搜索的方法暫不介紹。

收獲成果

以上，感興趣的同學(xué)可通過(guò)網(wǎng)盤獲取源代碼：https://pan.baidu.com/s/1gC6sF62Pz5D6rh6eicOZUw，提取碼: k17b。