基于UCT算法的非完備信息多人軍棋博弈系統(tǒng).pdf

1、博弈游戲的分類方法之一是根據(jù)其游戲的參與者是否擁有完備的游戲信息。據(jù)此，博弈游戲可以被分為完備信息博弈和非完備信息博弈兩個大類。在非完備信息博弈過程中，每個游戲者擁有自己單獨的信息集，也就是說，他只擁有整個游戲的部分信息。
　　圍繞著完備信息博弈的研究已經(jīng)取得了相對成熟的結(jié)果。很多人工智能程序的核心架構(gòu)是：當(dāng)電腦走棋的時候，根據(jù)當(dāng)前棋局創(chuàng)建一個部分的博弈樹，利用估值函數(shù)對葉結(jié)點進行估值，通過估值的結(jié)果來進行極大極小值搜索，找到一個

2、在根結(jié)點的最佳走步。然而，迄今為止非完備信息下的非常成功的人工智能博弈程序很少。非完備信息博弈問題的解決技術(shù)和完備信息有很大的差異，應(yīng)用于完備信息的技術(shù)不一定能夠成功的應(yīng)用到非完備信息博弈中。
　　蒙特卡羅抽樣算法是現(xiàn)今應(yīng)用于非完備信息博弈中的一個基本方法，它通過隨機抽樣將非完備信息博弈問題轉(zhuǎn)換為完備信息博弈問題，同時通過大規(guī)模的抽樣次數(shù)來逼近真實的情況。該方法在一些非完備信息博弈游戲中，例如Alberta的橋牌程序，已經(jīng)取得了較

3、好的效果。
　　UCT(Upper Confidence Bound Apply to Tree)：應(yīng)用于博弈搜索樹的上限置信區(qū)間算法。這種新興的搜索算法采用以上限置信值為依據(jù)的先深于先廣搜索相結(jié)合的方法，在超大規(guī)模博弈樹的搜索過程中相對于傳統(tǒng)的搜索算法有著時間和空間方面的優(yōu)勢。在與風(fēng)險評估模型相結(jié)合的基礎(chǔ)上，可以在可控的時間內(nèi)得到當(dāng)前局勢下的相對較優(yōu)的解決方案。
　　本文探討了UCT算法在非完備信息博弈中超大規(guī)模搜索樹搜索

4、過程中的應(yīng)用，并基于該算法結(jié)合蒙特卡羅抽樣技術(shù)和風(fēng)險評估模型實現(xiàn)了一個具有自動網(wǎng)上掛載功能的四國軍棋博弈系統(tǒng)。本文的主要研究成果和創(chuàng)新之處在于：
　　1．實現(xiàn)了UCT搜索算法，并將之應(yīng)用為博弈系統(tǒng)的搜索核心。提高了系統(tǒng)的搜索速度和深度；
　　2．進一步擴充和精確化了四國軍旗博弈中的蒙特卡羅抽樣技術(shù)；
　　3．在已有四國軍棋的框架系統(tǒng)上，將蒙特卡羅抽樣技術(shù)、UCT算法和一個簡單的風(fēng)險模型有效結(jié)合成了一個具有更強的博弈能力