• 
    

    
    

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

      ?

      機(jī)器博弈中搜索策略和估值函數(shù)的設(shè)計(jì)

      2019-03-04 11:05:01何軒洪迎偉王開譯彭耶萍
      電腦知識(shí)與技術(shù) 2019年34期
      關(guān)鍵詞:搜索算法

      何軒 洪迎偉 王開譯 彭耶萍

      摘要:機(jī)器博弈是人工智能的頭部領(lǐng)域。該文以六子棋為例,重點(diǎn)介紹了搜索策略和估值函數(shù)的設(shè)計(jì),主要介紹了博弈樹,極大極小值算法,α-β剪枝,MCTS以及基于“路”和“棋型”結(jié)合的估值函數(shù)。

      關(guān)鍵詞:六子棋;搜索算法;估值函數(shù)

      中圖分類號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼:A

      文章編號(hào):1009-3044(2019)34-0053-02

      1 概述

      作為二十一世紀(jì)三大尖端技術(shù)之一的人工智能,其頭部研究領(lǐng)域的機(jī)器博弈被認(rèn)為是最富有挑戰(zhàn)性的項(xiàng)目之一。而由吳毅成教授所提出的六子棋,以其玩法簡(jiǎn)單,情況多變,豐富的樂趣性吸引了大量玩家,并且成為機(jī)器博弈的競(jìng)賽項(xiàng)目之一。

      2 搜索算法

      2.1 博弈樹搜索

      搜索的目的不僅是找出當(dāng)前所有可以落子的地方,還要考慮到之后更多步數(shù)所產(chǎn)生的情況。博弈樹指的是以樹的形式把對(duì)手和計(jì)算機(jī)所有落子的情況表示出來。

      該博弈樹以當(dāng)前局面為根節(jié)點(diǎn),每一個(gè)節(jié)點(diǎn)表示一個(gè)推導(dǎo)的局面,每一層表示一方所有可能的落子情況,樹的層數(shù)表示搜索深度。該樹描述的是以當(dāng)前局面為起始,走n步以后的所有情況。

      單純的博弈樹效率很低,所以真正的棋手那樣,過濾掉許多不需要考慮的情況,降低搜索的深度,通過改進(jìn)算法實(shí)現(xiàn)在規(guī)定時(shí)間求出最佳路徑。

      2.2 極大極小值搜索

      假設(shè)雙方都采用最佳的策略,每一種局面都通過估值函數(shù)來確定局面的好壞,那么對(duì)于己方來說每次都要選擇最好的,每次都認(rèn)為對(duì)方選擇的是最佳策略,選擇估值最低的局面展開博弈樹。

      2.3 α-β剪枝

      α—β剪枝是在極大極小值搜索的基礎(chǔ)上,舍棄每一次局面沒有必要繼續(xù)搜索下去的情況。對(duì)于MAX的情況來說,只保留最大的分支,對(duì)于MIN的情況,只保留最小的分支。

      2.4 MCTS樹搜索

      如果直接把α-β剪枝算法直接應(yīng)用于實(shí)際的機(jī)器博弈,會(huì)有幾個(gè)問題。

      1)即使剪枝過后,推導(dǎo)的局面還是太多。

      2)對(duì)于每一個(gè)局面,如果為了得出每一層準(zhǔn)確的估值,而進(jìn)行相同時(shí)間的搜索,會(huì)導(dǎo)致搜索的深度不夠,無法建立更加深層次的博弈樹。

      舍棄絕對(duì)不合理的局面后,人類棋手一般會(huì)選擇一個(gè)看起來特別有價(jià)值的局面做深入推演,而并不是同時(shí)推演幾個(gè)待選局面。

      蒙特卡羅樹分為四個(gè)部分,圖中每一個(gè)結(jié)點(diǎn)代表一種推導(dǎo)出來的局面,左邊是總勝利次數(shù),右邊是總模擬次數(shù)。

      1)選擇

      從根節(jié)點(diǎn)開始依次遍歷孩子節(jié)點(diǎn)中勝率最高的,直到葉子節(jié)點(diǎn)。

      2)擴(kuò)展

      給該葉子節(jié)點(diǎn)添加一個(gè)新的孩子節(jié)點(diǎn)。

      3)模擬

      新的孩子節(jié)點(diǎn)進(jìn)行勝率模擬。

      4)回溯

      把模擬結(jié)果從孩子節(jié)點(diǎn)開始一直回溯到根節(jié)點(diǎn)本身。

      蒙特卡羅樹能夠快速深入推演比較有價(jià)值的局面,舍棄獲勝概率比較小的節(jié)點(diǎn),不推演其子節(jié)點(diǎn),使得搜索深度大大增加,但是也有可能一開始就誤人歧途,因?yàn)榭赡芡蒲莸阶詈蟀l(fā)現(xiàn)推演的這個(gè)分支的勝率沒有其他分支的高。

      3 估值函數(shù)

      3.1 基于“路”和“棋型”結(jié)合的估值函數(shù)設(shè)計(jì)

      現(xiàn)在大部分的棋博弈中,都是基于棋形結(jié)構(gòu)的分析,這種結(jié)構(gòu)有一種高度模型匹配的算法在里面,所以這就對(duì)于準(zhǔn)確定位棋形的模型的要求很高。不僅模型構(gòu)建對(duì)空間的占用率大,而且后期計(jì)算機(jī)對(duì)棋形的匹配費(fèi)時(shí)較大,這樣使得算法的時(shí)間和空間復(fù)雜度都很高。因此對(duì)棋形的預(yù)判效率是衡量“棋型”估值函數(shù)算法好壞的關(guān)鍵。六子棋常見棋形有19種,常用的位置信息有眠五、眠四、活五、活四,每一種棋形又存在多種交叉情況如圖1、圖2,這就更加使得對(duì)棋形的預(yù)判難度加大,所以如何有效和精準(zhǔn)地預(yù)判,搜索棋形,已經(jīng)成為六子棋機(jī)器博弈的難題。

      下面,我們分析一下“路”這種思想是如何在棋盤中進(jìn)行模擬的?我們現(xiàn)實(shí)當(dāng)中的路,有彎曲的、有筆直的,但是在棋盤當(dāng)中,“路”的思想,其實(shí)就是數(shù)學(xué)理論中的一個(gè)結(jié)論,即若知道兩個(gè)點(diǎn),那么在兩點(diǎn)之間必定可以確定一條直線。所以在棋盤中的“路”,就是指在棋盤上存在兩顆棋子,在這兩顆棋子之間,還經(jīng)過了4枚同色的棋子。由于每條“路”都是連續(xù)的6個(gè)點(diǎn)位,如果把每一個(gè)位點(diǎn)換成0和1的二進(jìn)制碼,白棋是10,黑棋是01,空格是00,然后用計(jì)算機(jī)的空間數(shù)組存儲(chǔ)每一條路的串碼,那么對(duì)于計(jì)算機(jī)的預(yù)判和運(yùn)算是不是得到了很大的優(yōu)化。例如,某“路”中已經(jīng)存在4顆子,就不用再去判斷它到底是活四、眠四、跳四等棋形。同時(shí),如果把“路”定義為一種類,“路”的一些特點(diǎn)是類的屬性,那么我們就可以利用面向?qū)ο蟮乃枷?,?duì)“路”的估值函數(shù)進(jìn)行優(yōu)化。這樣能方便地予以實(shí)現(xiàn)“路”的特點(diǎn),以便于預(yù)判。

      “路”的總數(shù)較少?,F(xiàn)在我們以六子棋為例,按照橫向、縱向、左斜、右斜4個(gè)方向的特點(diǎn),可以分別計(jì)算出六子棋在各個(gè)方向的“路”的數(shù)目和情況:

      1)橫向,19行x (19 - 6+1)路/行=266路,如圖3的三種情況;

      2)縱向,19列x(19- 6+1)路/列=266路;如圖4的四種情況;

      3)左斜,14行x (19 - 6+1)路/行=196路;如圖5的四種情況;

      4)右斜,14列x (19- 6+1)路/列=196路;如圖6的四種情況。

      因此,在19x19圍棋盤上,總共有266x2+ 196x2= 924(路)。如果我們采用“路”來預(yù)判棋形狀態(tài)值,那么對(duì)于六子棋的估值評(píng)估函數(shù)設(shè)計(jì)則是一種優(yōu)化,它不再需要消耗大量的時(shí)間對(duì)棋形進(jìn)行匹配。

      到了這里,我們又要回到之前對(duì)“棋形”模型匹配的估值函數(shù)算法的問題和不足,前面講的“路”值估值方法,可以說是對(duì)棋局評(píng)估函數(shù)的一種建立和優(yōu)化。

      參考文獻(xiàn):

      [1]李學(xué)俊.六子棋中基于局部“路”掃描方式的博弈樹生成算法[J].智能系統(tǒng)學(xué)報(bào),2015,10(2):267-272.

      [2]周新林.六子棋博弈系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].軟件導(dǎo)刊,2015,14(3):92-94.

      [3]閔文杰.六子棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)研究[D].重慶:重慶交通大學(xué),2010:88.

      [4]陳光年.基于智能算法的六子棋博弈行為選擇的應(yīng)用研究[D].重慶:重慶理工大學(xué)2010:76.

      [5]王小龍.連珠模式棋類博弈的搜索優(yōu)化[D].合肥:安徽大學(xué),2014:74.

      [6]張小川.六子棋博弈的評(píng)估函數(shù)[J].重慶:重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版,2010,24(2):64-68.

      【通聯(lián)編輯:朱寶貴】

      收稿日期:2019-10-15

      作者簡(jiǎn)介:何軒(1999-),男,吉首大學(xué)軟件工程專業(yè)本科在讀;洪迎偉(2001-),男,吉首大學(xué)軟件工程專業(yè)本科在讀;王開譯(1999—),男,吉首大學(xué)軟件工程專業(yè)本科在讀;彭耶萍(1981-),女,主要研究方向?yàn)閿?shù)據(jù)挖掘及算法。

      猜你喜歡
      搜索算法
      現(xiàn)代電力(2022年2期)2022-05-23 12:46:08
      基于改進(jìn)禁忌搜索算法的整車混裝配載優(yōu)化方法
      改進(jìn)的非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)動(dòng)態(tài)搜索算法
      改進(jìn)的和聲搜索算法求解凸二次規(guī)劃及線性規(guī)劃
      基于改進(jìn)布谷鳥搜索算法的配電網(wǎng)重構(gòu)
      不確定環(huán)境下多無人機(jī)協(xié)同區(qū)域搜索算法
      基于和聲庫擇優(yōu)的和聲搜索算法的配電網(wǎng)重構(gòu)
      基于二次插值法的布谷鳥搜索算法研究
      基于汽車接力的潮流轉(zhuǎn)移快速搜索算法
      基于差分和聲搜索算法的輸電網(wǎng)差異化規(guī)劃
      404 Not Found

      404 Not Found


      nginx
      土默特右旗| 茂名市| 深州市| 昌乐县| 信丰县| 左贡县| 乐陵市| 迭部县| 清涧县| 德庆县| 菏泽市| 社会| 阜新| 双柏县| 永城市| 海口市| 阳曲县| 靖西县| 绩溪县| 南昌县| 安宁市| 灵山县| 托克逊县| 如皋市| 巴彦淖尔市| 大足县| 鄂伦春自治旗| 张家界市| 阳江市| 绥化市| 新巴尔虎右旗| 巧家县| 焦作市| 桃江县| 马边| 永安市| 永州市| 来安县| 枞阳县| 五常市| 岳池县|