愛恩斯坦棋計算機博弈系統(tǒng)的研究與實現(xiàn).pdf

1、計算機博弈，也稱機器博弈，是一個極具挑戰(zhàn)與發(fā)展前景的計算機研究領(lǐng)域，其作為人工智能領(lǐng)域一個極其重要的課題，素有人工智能領(lǐng)域“果蠅”之稱。而對于棋類游戲的研究又是計算機博弈研究過程中的一個標準且極為重要的問題。現(xiàn)有的很多重要理論和技術(shù)方法諸如各類搜索算法及智能方法，最初的提出都是為了解決存在于棋類博弈中的某些問題。對于計算機博弈的研究最早可以追溯到半個世紀之前，在過去的五六十年里，人工智能的學(xué)者們嘔心瀝血的研究了計算機博弈中的包括奧賽羅、

2、國際象棋、跳棋、五子棋、圍棋等等，取得了大量傲人的成果。97年IBM的“深藍”戰(zhàn)勝棋王卡斯帕羅夫更是引起了世人的矚目與震動，讓世人第一次意識到冰冷的機器在棋類博弈上的智能超越了人類;而在不久之前，人機圍棋大戰(zhàn)巔峰對決——谷歌圍棋人工智能AlphaGo VS人類頂尖棋手李世石剛剛落幕，AlphaGo以4∶1擊敗李世石，從某種層面上來說機器的智能已經(jīng)遠遠超過了人類。相比于國外，國內(nèi)對于此方面的研究起步較晚，但是隨著這幾年的國內(nèi)各種博弈比賽的

3、開展，吸引了越來越多的學(xué)生與學(xué)者參與博弈的研究，國內(nèi)的計算機博弈研究迎來了黃金期，極大的促進了國內(nèi)計算機博弈研究的發(fā)展。
　　傳統(tǒng)的機器博弈模型多是完全信息博弈，即在對弈過程中完全了解其他對手的狀態(tài)特征、策略和得益方式，現(xiàn)有的機器博弈研究大多以此類為研究載體，如五子棋、象棋等等。此種棋類的數(shù)據(jù)結(jié)構(gòu)和局面狀態(tài)描述設(shè)計依賴于準確的狀態(tài)策略信息，搜索引擎也有現(xiàn)成的模板可供參考。本文的研究對象愛恩斯坦棋博弈屬于不完全信息博弈，對博弈過程中

4、的信息了解不完全，在進行數(shù)據(jù)結(jié)構(gòu)和局面狀態(tài)描述設(shè)計之前，需要先對其他對手的狀態(tài)特征等信息進行一個估計，讓博弈信息“偽完全化”，然后再進行相關(guān)設(shè)計，同樣，需要對傳統(tǒng)的博弈搜索算法進行修改，使其適應(yīng)于不完全信息博弈。
　　本文以愛恩斯坦棋博弈平臺為研究載體，研究了計算機博弈關(guān)鍵技術(shù)，包括基本概念、研究對象分析和搜索引擎，設(shè)計了愛恩斯坦棋機器博弈系統(tǒng)。在棋盤數(shù)據(jù)結(jié)構(gòu)設(shè)計過程中，對對手的狀態(tài)信息等進行了預(yù)判和估計量化，使其信息完全化，從攻

5、擊和防守兩個方向同時評估，得到了攻防兼?zhèn)涞墓乐岛瘮?shù);同時，還研究了估值函數(shù)的參數(shù)優(yōu)化方法，保證估值函數(shù)設(shè)計的準確性和合理性;在搜索算法方面，基于傳統(tǒng)的完全信息博弈算法——極大極小算法，參考期望搜索算法，在極大層與極小層之間人為加入一層骰子層，并將上述估值函數(shù)應(yīng)用到算法中同時加入置換表優(yōu)化技術(shù)，設(shè)計了適應(yīng)于愛恩斯坦棋的攻防兼?zhèn)涞钠谕惴ǎ鉀Q了使用傳統(tǒng)博弈算法無法構(gòu)建博弈樹的問題，提高博弈水平。
　　從搜索效率和博弈水平兩個角度攻防

6、兼?zhèn)涞钠谕惴?，雖然在搜索效率有所下降，但是在博弈水平方面卻有較好的突破，博弈水平明顯提高證明了應(yīng)用了攻防兼?zhèn)涞墓乐岛瘮?shù)的期望算法在一定深度范圍內(nèi)博弈水平和博弈效率取得了較好的平衡，既具有較高的博弈水平，又充分利用了博弈時間。同時，加入置換表優(yōu)化方法之后，搜索效率與博弈水平都有一定的提升，本文的創(chuàng)新點如下:
　　(1)研究并設(shè)計了適用愛恩斯坦棋的不完全信息博弈的數(shù)據(jù)結(jié)構(gòu)，深入研究估值函數(shù)的構(gòu)成，針對傳統(tǒng)的估值函數(shù)存在的估值片面不準

7、確的問題，從攻擊防守兩個方向同時考慮并結(jié)合愛恩斯坦棋的兩種贏棋方式，設(shè)計了準確且效率較好的攻防兼?zhèn)涞墓乐岛瘮?shù);同時分析研究了一些應(yīng)用于估值參數(shù)優(yōu)化的方法和策略。在設(shè)計估值函數(shù)時，使用了攻擊因子和威脅度因子來調(diào)整著法路徑，有效的提高了博弈水平。
　　(2)具體上采用爬山法結(jié)合手工調(diào)整對攻防兼?zhèn)涞墓乐颠M行參數(shù)優(yōu)化，將優(yōu)化之后的估值應(yīng)用到算法中去，極大的提高了博弈水平。
　　(3)基于傳統(tǒng)的極大極小博弈算法，參考期望搜索算法，改進

8、并設(shè)計了適用于愛恩斯坦棋的攻防兼?zhèn)涞钠谕惴?，在原有的極大極小層中加入一層骰子層，來模擬投骰子的過程，解決了博弈過程中信息不完全的問題，并將(1)中的估值函數(shù)應(yīng)用到算法中，加入置換表來優(yōu)化算法，降低搜索過程中的節(jié)點數(shù)量，提高了搜索算法的效率。
　　上述方法均在愛恩斯坦棋博弈系統(tǒng)“行云流水”與“流刃若火”程序中成功應(yīng)用，其中“行云流水”在2014年“成理杯”全國大學(xué)生計算機博弈大賽愛恩斯坦棋項目榮獲季軍（一等獎），實踐上證明本文提出