點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn).pdf

1、2016年3月谷歌AlphaGo擊敗世界圍棋冠軍李世石九段，使人工智能、機(jī)器博弈再次成為大眾焦點(diǎn)。人工智能是計(jì)算機(jī)科學(xué)的重要研究方向，主要研究用機(jī)器來(lái)模擬和執(zhí)行人腦的智力功能，開(kāi)發(fā)相關(guān)的理論和技術(shù)，從而達(dá)到讓機(jī)器可以能像人一樣進(jìn)行學(xué)習(xí)、思考、判斷等各種腦力活動(dòng)的目標(biāo)。機(jī)器博弈因使用計(jì)算機(jī)解決博弈問(wèn)題而得名，它將博弈思想和計(jì)算機(jī)科學(xué)相融合，希望計(jì)算機(jī)能像人一樣做出理性決策。機(jī)器博弈作為人工智能極具挑戰(zhàn)的分支之一，一直以來(lái)都被譽(yù)為人工智能的

2、“果蠅”，機(jī)器博弈的研究對(duì)于人工智能的發(fā)展具有積極的推動(dòng)作用。機(jī)器博弈在國(guó)外的發(fā)展較早，并取得了一定的成就;在國(guó)內(nèi)的發(fā)展還比較緩慢，以棋類為載體是目前研究機(jī)器博弈的主要方法。
　　點(diǎn)格棋是法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯在1891年提出的二人紙筆游戲。點(diǎn)格棋博弈系統(tǒng)主要由知識(shí)表示、著法生成、搜索算法和估值函數(shù)四部分組成，其中搜索算法是核心。搜索算法根據(jù)當(dāng)前局面生成一顆一定深度的博弈樹(shù)，對(duì)博弈樹(shù)進(jìn)行向下搜索，傳統(tǒng)的點(diǎn)格棋博弈系統(tǒng)所采用的搜索

3、算法多為α-β剪枝算法，采用α-β剪枝算法存在搜索深度淺、浪費(fèi)時(shí)間等問(wèn)題。另一方面α-β剪枝算法必須有一個(gè)估值函數(shù)對(duì)棋盤的優(yōu)劣進(jìn)行評(píng)估。目前常采用的估值方法當(dāng)棋盤中不存在安全邊的時(shí)候會(huì)比較準(zhǔn)確，但是如果棋盤中含有安全邊，估值會(huì)由于安全邊占領(lǐng)的順序不同而存在誤差，所以點(diǎn)格棋博弈系統(tǒng)的估值函數(shù)設(shè)計(jì)相對(duì)較難。
　　UCT算法是蒙特卡洛算法的一種延伸算法，根據(jù)大數(shù)定理以多次模擬的方式實(shí)現(xiàn)對(duì)博弈樹(shù)中節(jié)點(diǎn)的價(jià)值評(píng)估，同時(shí)將UCB算法應(yīng)用到博弈

4、樹(shù)搜索上，通過(guò)UCB算法選擇進(jìn)行評(píng)估的節(jié)點(diǎn)，引導(dǎo)博弈樹(shù)向更好的方向生長(zhǎng)，有利于更快的獲得最優(yōu)解。UCT算法根據(jù)大量模擬棋局的結(jié)果以概率的方法進(jìn)行盤面優(yōu)劣的判斷，預(yù)估節(jié)點(diǎn)的好壞，優(yōu)先選擇表現(xiàn)好的節(jié)點(diǎn)。這種方法解決了點(diǎn)格棋目前存在的盤面評(píng)估問(wèn)題。將UCT算法應(yīng)用到點(diǎn)格棋博弈，最后通過(guò)實(shí)驗(yàn)證明采用UCT算法的點(diǎn)格棋博弈系統(tǒng)博弈水平高于α-β剪枝算法。
　　根據(jù)點(diǎn)格棋博弈過(guò)程中棋盤會(huì)存在許多價(jià)值相同的邊即等價(jià)邊，這些邊選擇其中任意一條邊進(jìn)

5、行搜索，與對(duì)這些全部進(jìn)行搜索產(chǎn)生的結(jié)果相同，在進(jìn)行博弈樹(shù)搜索時(shí)只需要對(duì)其中一條邊進(jìn)行搜索，據(jù)此提出基于等價(jià)邊裁剪的UCT算法在UCT算法拓展節(jié)點(diǎn)階段進(jìn)行等價(jià)邊裁剪。最后通過(guò)實(shí)驗(yàn)證明改進(jìn)算法能夠減少博弈樹(shù)搜索時(shí)搜索節(jié)點(diǎn)的數(shù)量，大幅度提高UCT算法的博弈水平。
　　在UCT算法模擬棋局階段，為提高模擬棋局結(jié)束后收益值計(jì)算的準(zhǔn)確性，在原有計(jì)算方法的基礎(chǔ)上提出了基于修正值的收益值計(jì)算方法，不僅對(duì)模擬棋局勝負(fù)進(jìn)行了區(qū)分，還對(duì)勝負(fù)的程度進(jìn)行了

6、量化，使收益值更加的精確;其次，為提高模擬棋局的次數(shù)，實(shí)現(xiàn)了基于多核CPU的UCT算法的并行化，充分利用了多核CPU的計(jì)算性能，提高棋局的模擬數(shù)量。綜合以上兩點(diǎn)改進(jìn)提出基于修正收益值的并行UCT算法，通過(guò)實(shí)驗(yàn)證明基于修正收益值的并行UCT算法可以提高博弈樹(shù)搜索深度和模擬棋局?jǐn)?shù)量，使UCT算法的博弈水平更高。
　　本文的創(chuàng)新點(diǎn)如下:
　　1.在認(rèn)真分析點(diǎn)格棋博弈中經(jīng)常使用的搜索算法后，發(fā)現(xiàn)UCT算法相對(duì)于傳統(tǒng)的α-β剪枝算法有