• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      一種2048游戲自動“玩游戲”算法的實現(xiàn)

      2018-05-14 13:45:51許子明
      科技風 2018年16期
      關鍵詞:剪枝數(shù)組格子

      許子明

      摘 要:人工智能是近年來計算機研究的一個熱門領域,2048游戲是風靡一時的數(shù)字益智游戲。本文提出一種2048游戲“自動游戲”功能實現(xiàn)。通過設定局面的評價指標得到當前局面分數(shù),再通過格局樹搜索和alphabeta剪枝,確定最佳移動方向,通過不斷移動,最終得到數(shù)字2048。

      關鍵詞:人工智能;2048游戲;自動游戲

      1 2048游戲簡介

      2048游戲是一款數(shù)字益智游戲。游戲背景是在4*4的方格內(nèi),玩家通過不斷上下左右移動,在16個方格內(nèi),拼出“2048”數(shù)字方格。游戲的規(guī)則為:游戲開始時隨機出現(xiàn)兩個數(shù)字2的格子,玩家向上下左右一個方向移動,所有數(shù)字格子向該方向靠攏,剩余的空白格子隨機出現(xiàn)一個2或4,相同數(shù)字相撞會合并,然后經(jīng)過不斷的上下左右移動,不斷的合并最終合成2048這個數(shù)字就算成功。

      2 自動游戲功能的原理

      2.1 數(shù)據(jù)結(jié)構(gòu)

      建立二維數(shù)組map[4][4]用來記錄每一個格子的數(shù)字,二維數(shù)組map[i][J]表示第i行第j列格子中的數(shù)字,初始化數(shù)組中所有的格子數(shù)字為0。

      2.2 游戲局面評價指標與實現(xiàn)

      (1)單調(diào)性。單調(diào)性指方塊從左到右、從上到下均遵從遞增或遞減。一般來說,越單調(diào)的格局越好。首先將數(shù)組map中的每一項取以2為底的對數(shù)。先計算橫向的單調(diào)性,即每一行的單調(diào)性。首先從每一行的第一列的數(shù)字開始(map[i][J]),向后尋找最近第一個非零數(shù)字map[i][jj],然后判斷兩個數(shù)的大小,用小的數(shù)字減去大的數(shù)字,并記錄結(jié)果,然后將jj的值賦給j(跳過其中的空白格子),向后尋找非零數(shù)字格子,用小的減去大的,將結(jié)果相加保存。依次計算第一到第四行的所有結(jié)果??v向計算單調(diào)性與橫向類似,即計算每一列的單調(diào)性。

      (2)平滑性。平滑性是指每個方塊與其直接相鄰方塊數(shù)值的差,其中差越小越平滑,一般認為越平滑的格局越好。同樣將數(shù)組map中的每一項取以2為底的對數(shù)。然后遍歷數(shù)組map中每一個格子,如果map[i][J]為零,則跳過循環(huán)繼續(xù)下一次。如果map[i][J]不為零,則向下、右尋找最近的非空格子map[i][jj]和map[ii][J],計算map[i][J]和向下和向右非空格子數(shù)字相減的絕對值,并記錄。

      (3)最大值。最大值即所有數(shù)字格子中數(shù)值最大的數(shù)值,通過遍歷數(shù)組map,比較大小即可得到。

      (4)空格子數(shù)目。即為16個方格中沒有數(shù)字的方格的數(shù)目,通過遍歷二維數(shù)組map,并記錄其中數(shù)字為0的格子的數(shù)目。

      (5)局面得分。將上述四個指標分別計算后,再乘以各指標對應的不同權值,作為當前局面的得分。

      2.3 游戲最佳移動方向的實現(xiàn)

      確定最佳移動方向的算法采取格局樹,max節(jié)點表示游戲玩家,min節(jié)點表示電腦,在隨機空白位置出現(xiàn)2或4。在樹中采用ab(alphabeta)剪枝,a表示搜索到當前節(jié)點時已知最好選擇的下界,即max節(jié)點可以做出的最好選擇,b表示從這個節(jié)點往下搜索最壞結(jié)局的上界,即min節(jié)點可做出的最好選擇(max節(jié)點為最壞選擇)。當b小于a時會進行剪枝,表示從此處開始不論最終結(jié)局是哪一個,其上限價值也要低于已知的最優(yōu)解,也就是說已經(jīng)不可能此處向下找到更好的解,則回溯到父節(jié)點繼續(xù)搜索。

      在max節(jié)點搜索中,分為葉結(jié)點和非葉結(jié)點的處理方法。

      對于葉結(jié)點,即當前搜索深度大于等于最深搜索深度時,遍歷上下左右,然后計算移動后各局面分數(shù)。如果計算出的分數(shù)大于a,即當前最好選擇大于傳入的最好選擇的值,則把分數(shù)的值賦給a,并修改最佳移動方向。再選擇下一個方向進行移動后計算分數(shù),四個方向遍歷完畢后,記錄最佳方向,并將最好的a、b的值返回。

      對于非葉結(jié)點,上下左右遍歷后,再向下對min節(jié)點搜索,將搜索得到的a、b的值記錄。如果min節(jié)點b大于父節(jié)點a,則將min節(jié)點b賦給父節(jié)點的a,說明電腦做出最好選擇的分數(shù)大于當前可做出的最好選擇,則更新最好選擇的值,并修改最佳移動方向。最后再判斷a>=b,若成立,則如果向這個方向移動,則min節(jié)點做出最壞選擇,由此向下移動的局面分數(shù)不會超過b,即不會超過已有最好選擇,則進行剪枝,不再向下計算,跳出循環(huán),將最佳方向和a、b的值返回。若不成立,再選擇下一個方向移動計算分數(shù),四個方向遍歷后,記錄最佳方向,將最好的a、b的值返回。

      在min節(jié)點搜索中,在每一個空格子中賦值2,即考慮電腦隨機在空白格子出2的情況(本算法中只考慮最差位置出2的情況)。賦值之后,再向下搜索max節(jié)點,搜索最佳移動方向。如果向下搜素的a小于b,則說明min節(jié)點可以做出更差的選擇,將a賦給b,更新b的值。更新b的值后,再判斷a>=b,若成立,則剪枝并返回當前a、b,否則的話,將賦值2的格子恢復為零,再將數(shù)字2賦給下一個空白格子,尋找使當前局面變得最差時的局面(即電腦完美出現(xiàn)2)。最后經(jīng)過深度搜索、計算、遞歸后,決定最佳移動方向。

      3 自動游戲算法結(jié)果統(tǒng)計

      分析:該算法基本上能使得2048及以上數(shù)字的概率在65%以上,當單調(diào)性所分配的權值為1.5時,合成2048及以上數(shù)字的概率達到70%。通過不斷的調(diào)整各評價指標所占的權值,可以提高合成2048及以上數(shù)字的概率。

      猜你喜歡
      剪枝數(shù)組格子
      人到晚年宜“剪枝”
      JAVA稀疏矩陣算法
      電腦報(2022年13期)2022-04-12 00:32:38
      基于YOLOv4-Tiny模型剪枝算法
      JAVA玩轉(zhuǎn)數(shù)學之二維數(shù)組排序
      電腦報(2020年24期)2020-07-15 06:12:41
      數(shù)格子
      填出格子里的數(shù)
      格子間
      女友(2017年6期)2017-07-13 11:17:10
      剪枝
      天津詩人(2017年2期)2017-03-16 03:09:39
      格子龍
      尋找勾股數(shù)組的歷程
      抚远县| 鄂伦春自治旗| 光山县| 南华县| 民和| 白沙| 高尔夫| 汾阳市| 和顺县| 福州市| 南靖县| 广昌县| 赫章县| 越西县| 当雄县| 高要市| 景宁| 合阳县| 永平县| 思茅市| 长宁县| 南阳市| 博罗县| 白沙| 呼玛县| 琼中| 大足县| 沂源县| 达拉特旗| 兴海县| 肥城市| 从化市| 吴忠市| 凤凰县| 信阳市| 阳江市| 栖霞市| 乐陵市| 化德县| 炎陵县| 裕民县|