UCT算法在不圍棋博弈中的實現(xiàn)

《UCT算法在不圍棋博弈中的實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2015年8月韶關(guān)學(xué)院學(xué)報·自然科學(xué)Aug.2015第36卷第8期JournalofShaoguanUniversity·NaturalScienceVol.36No.8UCT算法在不圍棋博弈中的實現(xiàn)*梁國軍，謝垂益，胡伶俐，林昊，李景炤（韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，廣東韶關(guān)5120051）摘要：計算機博弈是人工智能領(lǐng)域的挑戰(zhàn)性課題，它利用計算機進行分析、判斷和推理，從而得到理性的決策.不圍棋是近年來計算機博弈競賽的一個棋種，屬于圍棋的變體，其規(guī)則是先吃子或棋子自殺的一方為負.通過分析不圍棋博弈模型的特點，提出了對上限信

2、心界樹搜索(UCT)算法的一個優(yōu)化方法，在算法的啟動過程優(yōu)先選擇評分較高的盤面進行模擬博弈，以便得到更好的落子選擇.在與著名的OASE-NoGo軟件的試驗對弈中，以該算法為核心設(shè)計的不圍棋軟件取得了90%以上的勝率，證明是可行、有效的.關(guān)鍵詞：人工智能；計算機博弈；不圍棋；UCT算法中圖分類號：TP312文獻標識碼：A文章編號：1007-5348（2015）08-0017-04棋類游戲是計算機博弈領(lǐng)域的重要研究課題，這些研究工作有助于加深對人工智能與計算機科學(xué)的認識，促進對人類認知過程的理解.不圍棋是十多年前開始出現(xiàn)

3、的一種雙人博弈游戲，屬于圍棋的變體，如［1］果一方落子后吃掉了對方的棋子、或者令已方棋子自殺，則落子一方判負.2011年起，由國際計算機博弈協(xié)會（InternationalComputerGamesAssociation，ICGA）組織的計算機奧林匹克（ComputerOlynpiad）大賽增加了不圍棋項目.2012年起，由中國人工智能學(xué)會舉辦的中國機器博弈錦標賽也將不圍棋列入比賽項目.在這些高級別賽事的推動下，不圍棋正在為人們認識并開始進行研究.筆者總結(jié)了不圍棋的研究現(xiàn)狀，分析了不圍棋的博弈模型，給出上限信心界樹搜

4、索（UCT，UCBforTreeSearch）中的UCB1子算法的一個修正，使其能更早地選擇優(yōu)勢盤面，并據(jù)此設(shè)計了一個不圍棋博弈軟件，通過與對照軟件的對弈實驗來驗證算法的有效性.1研究現(xiàn)狀早些年，計算機博弈對于棋類游戲的研究集中在基于模式識別和專家系統(tǒng)的方法上（最典型的是基于靜態(tài)評估函數(shù)的α-β博弈樹方法），并在國際象棋、中國象棋等項目中獲得了成功.但是對于圍棋類的項目，由于搜索空間巨大只能訪問博弈樹的一小部分、無法進行準確的靜態(tài)盤面評估，因此傳統(tǒng)的方法一直無法取得滿意的結(jié)果，在2000年前后，世界上最高水平的計算機

5、圍棋軟件的棋力還比不上人類的業(yè)余初段.2006年，LeventeKocsis和CsabaSzepesvári將蒙特卡洛樹搜索（Monte-CarloTreeSearch，MCTS）方法［2］［3］與UCB公式結(jié)合，提出上限信心界樹搜索（UCT，UCBforTreeSearch）算法，顯著地提高了搜索效率.UCT算法的出現(xiàn)開創(chuàng)了計算機博弈研究的新局面.此后人們圍繞MCTS方法進行研究和改進，推動圍棋軟件的棋力不斷提高.2013年3月，圍棋軟件CrazyStone在受讓四子的情況下，戰(zhàn)勝日本棋手石田芳夫九段，其棋力已達到

6、業(yè)余五、六段的水平.首次對不圍棋的研究報道出現(xiàn)在2011年，文獻［4］介紹了MCTS算法在不圍棋中的實現(xiàn).通過對比測試發(fā)現(xiàn)，在圍棋中常用的快速動作值估計（RapidAction-ValueEstimates，RAVE）、節(jié)點慢速創(chuàng)建、布局模板、UCT等方法和算法，在不圍棋中同樣有效；文獻［5］提出一個結(jié)合本體、進化計算、模糊邏輯、模糊標記語言的遺傳算法，根據(jù)收集的棋局模式和預(yù)構(gòu)建的不圍棋模糊本體，用基于模糊推理機制的遺傳模糊標記語言分析當(dāng)前棋局，得到下一個最好的棋步，并應(yīng)用了遺傳學(xué)習(xí)機制，可在與參照棋局的對壘中不斷提

7、高［收稿日期］2015-05-15［基金項目］國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(201410576018)；廣東省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(201410576060)；韶關(guān)學(xué)院科研項目(2012-16).［作者簡介］梁國軍(1992-)，男，廣東清遠人，韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院本科生；研究方向：計算機算法.*通訊作者.·18·韶關(guān)學(xué)院學(xué)報·自然科學(xué)2015年棋力；文獻［6-7］分析了棋局模板的分類和格式定義，在對弈過程中優(yōu)先使用模板進行棋步的選擇，當(dāng)出現(xiàn)模板中沒有的棋局時再使用MCTS算法；文獻［8］提出在對弈過程中

8、進行UCT樹的重用，可以增加5%～30%的搜索深度；文獻［9］通過啟發(fā)式、暴力搜索、參數(shù)調(diào)整等方式，提高UCT算法的搜索成功率；文獻［10］提出在MCTS算法中增加靜態(tài)估計方法，根據(jù)周圍棋子的類型標記出允許自由落子的點和禁止落子的點，加快博弈樹搜索速度.由于不圍棋是新的棋類，相關(guān)的研究成果較少.目前對不圍棋的主要研究方法是參考棋類尤其是圍棋的相