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

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

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

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

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

5、擊和防守兩個方向同時評估，得到了攻防兼?zhèn)涞墓乐岛瘮?shù);同時，還研究了估值函數(shù)的參數(shù)優(yōu)化方法，保證估值函數(shù)設(shè)計的準(zhǔn)確性和合理性;在搜索算法方面，基于傳統(tǒng)的完全信息博弈算法——極大極小算法，參考期望搜索算法，在極大層與極小層之間人為加入一層骰子層，并將上述估值函數(shù)應(yīng)用到算法中同時加入置換表優(yōu)化技術(shù)，設(shè)計了適應(yīng)于愛恩斯坦棋的攻防兼?zhèn)涞钠谕惴?，解決了使用傳統(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ù)存在的估值片面不準(zhǔn)

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

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