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

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

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

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

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

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

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

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

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