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

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

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

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

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

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

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