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

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

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

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

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