當前位置:
首頁 > 科技 > 如何讓AI教機器自己玩俄羅斯方塊?

如何讓AI教機器自己玩俄羅斯方塊?

作者 |Ahab

人工智慧大火的今天,如果還是自己玩俄羅斯方塊未免顯得太 LOW,為什麼不對遊戲升級,讓機器自己去玩俄羅斯方塊呢?有了這個想法之後,我用了兩天時間去搜集了大量資料,在電腦死機好多次之後終於將 AI 俄羅斯方塊實現了。


程序介紹

所謂讓機器自己去玩俄羅斯方塊,就是讓機器計算當前方塊的所有形態可放置的所有位置,然後根據統一的評價標準,計算出最優的位置進行放置。這個評價的標準簡單的來說就是:板塊放置的位置越靠下越好,方塊之間越緊密越好,自身對消除行的方塊貢獻數量越多越好,但是這裡還要注意的是不可為了追求消除行數,而去造成過多的空洞,這樣也是不合理的。

關於 AI 演算法主要有兩種:一種是經典的 Pierre Dellacherie 演算法,一種基於基於深度搜索的演算法。深度搜索需要優化的地方很多,假如計算的層數不夠、沒有高效剪枝,一不小心容易寫成人工智障,時間複雜度也不好。Pierre Dellacherie 演算法更加清晰,複雜度更低。但是該演算法只考慮當前,不對未來的情況進行計算,注重的是「不死性」,追求方塊的「密集」,有時就算可以一次性消除 3 行,卻會使全局方塊更加「疏」,即過多的空洞。

代碼由Tetris.py、AI.py和Utils.py三部分組成,遊戲的主要邏輯由 Tetis 控制,Utils 定義了方塊的樣式,AI 顧名思義實現了主要的 AI 演算法。

具體介紹


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

評估函數如下 (首字母簡寫):

關於方塊形態

這裡對 AI 俄羅斯方塊的形態做一下特別說明,各個方塊都是根據中心點的坐標來生成的,以(0,0)為中心點,在 x、y 軸加減 1 則是其他方格的坐標,這樣的好處就是只要確定中心點坐標,其他的方格位置就能隨即生成。

看圖就懂:

1# 每種塊包含的四個小方塊相對坐標分布

2self.shapes_relative_coords = [

3[[,], [,], [,], [,]],

4[[,-1], [,], [,1], [,2]],

5[[,-1], [,], [,1], [1,1]],

6[[,-1], [,], [,1], [-1,1]],

7[[,-1], [,], [,1], [1,]],

8[[,], [,-1], [1,], [1,-1]],

9[[,], [,-1], [-1,], [1,-1]],

10[[,], [,-1], [1,], [-1,-1]]

11]

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


收穫成果

以上,感興趣的同學可通過網盤獲取源代碼:https://pan.baidu.com/s/1gC6sF62Pz5D6rh6eicOZUw,提取碼: k17b。

(本文為AI科技大本營轉載文章,轉載請聯繫原作者)

喜歡這篇文章嗎?立刻分享出去讓更多人知道吧!

本站內容充實豐富,博大精深,小編精選每日熱門資訊,隨時更新,點擊「搶先收到最新資訊」瀏覽吧!


請您繼續閱讀更多來自 AI科技大本營 的精彩文章:

一個App賣了4億美元,這家聽聲識曲公司為何得到Apple的青睞?
對標Bert?刷屏的GPT 2.0意味著什麼

TAG:AI科技大本營 |