基于ATL的博弈模型檢測研究及其在圍棋中的應(yīng)用.pdf

1、模型檢測是由美國Clarke教授等提出的一種用于自動化驗證有窮狀態(tài)并發(fā)系統(tǒng)的技術(shù)。該技術(shù)通過窮舉搜索狀態(tài)空間的模型檢測算法來驗證系統(tǒng)模型是否符合預(yù)期屬性。由于狀態(tài)空間隨著系統(tǒng)規(guī)模急劇增長，符號化模型檢測被提出從而有效地緩解狀態(tài)空間爆炸問題。
　　驗證對弈中某方是否存在必勝策略是博弈論中研究的一個主要問題?；诜柲Ｐ蜋z測的高效性，模型檢測可以應(yīng)用于博弈游戲的驗證。交互時序邏輯ATL對計算樹邏輯進(jìn)行了擴(kuò)充，可以用來描述開放系統(tǒng)的性質(zhì)

2、。利用ATL符號模型檢測算法可以對博弈游戲模型進(jìn)行驗證。然而，一些博弈游戲的狀態(tài)空間過于龐大，需要對博弈模型檢測方法進(jìn)一步改進(jìn)來擴(kuò)大可驗證系統(tǒng)的規(guī)模。
　　本課題組前期在NSFC的支持下，在圍棋中引入模型檢測技術(shù)從而在一定范圍內(nèi)實施窮舉搜索。然而，實施圍棋模型檢測的關(guān)鍵在于狀態(tài)空間，如何約簡狀態(tài)空間是當(dāng)前迫切需要解決的問題。針對以上的問題，本文做了一些工作如下：
　　1）在博弈游戲的必勝策略檢測驗證中引入了ATL模型檢測技術(shù)