六子棋
——人工智能系統(tǒng)的設(shè)計(jì)與研究

周菁菁

（蘭州資源環(huán)境職業(yè)技術(shù)學(xué)院，甘肅 蘭州 730021）

六子棋
——人工智能系統(tǒng)的設(shè)計(jì)與研究

周菁菁

（蘭州資源環(huán)境職業(yè)技術(shù)學(xué)院，甘肅 蘭州 730021）

本系統(tǒng)是對(duì)六子棋計(jì)算機(jī)博弈技術(shù)的一次嘗試。此系統(tǒng)主要通過(guò)對(duì)當(dāng)前局面的所有的棋型進(jìn)行了靜態(tài)估值，然后再采用優(yōu)化 Alpha-Bate搜索技術(shù)實(shí)現(xiàn)了AI。最后，本文探討一些提高電腦智能的方法。并相信隨著科技的發(fā)展，人工智能對(duì)我們的幫助將會(huì)越來(lái)越顯著，越來(lái)越大。

計(jì)算機(jī)博弈；六子棋；Java；Alpha-Bate搜索技術(shù)；人工智能

一、引言

人工智能，英文縮寫(xiě)：AI。是研究、開(kāi)發(fā)、用于模擬、延伸以及擴(kuò)展人的智能的理論、方法、技術(shù)、應(yīng)用系統(tǒng)地一門(mén)新興技術(shù)科學(xué)。

計(jì)算機(jī)博弈則是被認(rèn)為在人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一，其涉及了人工智能中的推理技術(shù)、搜索方法以及決策規(guī)劃等等，計(jì)算機(jī)博弈的研究為人工智能帶來(lái)了很多重要的方法與理論，產(chǎn)生了廣泛的社會(huì)影響和學(xué)術(shù)影響以及大量的研究成果。六子棋作為最近幾年才興起的棋類游戲，對(duì)其計(jì)算機(jī)博弈技術(shù)和算法的研究相對(duì)比較少。所以基于Java的智能六子棋系統(tǒng)的實(shí)現(xiàn)是對(duì)計(jì)算機(jī)博弈問(wèn)題的一次探索研究。

二、系統(tǒng)的總體設(shè)計(jì)

1.在界面方面：應(yīng)該簡(jiǎn)單化，做到實(shí)用化、方便化，這樣以來(lái)就可以滿足不同層次的使用者的需要了。

2.在實(shí)現(xiàn)方面：對(duì)六子棋其數(shù)據(jù)結(jié)構(gòu)，棋子觸發(fā)，搜索算法，評(píng)估函數(shù)等進(jìn)行了設(shè)計(jì)和實(shí)現(xiàn)的過(guò)程。

3.在系統(tǒng)規(guī)范方面：刪除了不必要的冗余，實(shí)現(xiàn)了程序代碼的標(biāo)準(zhǔn)化，以及軟件的統(tǒng)一化，確保此軟件的可擴(kuò)展性，可維護(hù)性以及其實(shí)用性。

三、主要技術(shù)

第一，是界面設(shè)計(jì)及事件的響應(yīng)方面，系統(tǒng)界面包括了棋盤(pán)部分，用戶面板部分與游戲信息及選項(xiàng)部分，當(dāng)前狀態(tài)部分和系統(tǒng)選項(xiàng)這六個(gè)部分。其中為了系統(tǒng)的實(shí)現(xiàn)的方便，棋盤(pán)的背景與棋盤(pán)的觸發(fā)面板是分開(kāi)設(shè)計(jì)地，也就是在主框架中增加了背景，并且放置了用戶面板部分，當(dāng)前狀態(tài)部分以及系統(tǒng)選項(xiàng)的部分，再就是單獨(dú)設(shè)計(jì)了棋盤(pán)觸發(fā)面板，其覆蓋于棋盤(pán)的背景之上。至于棋子信息的部分，就隱藏在了棋盤(pán)觸發(fā)面板里了。同時(shí)，為了方便觸發(fā)，當(dāng)前狀態(tài)部分、系統(tǒng)選項(xiàng)部分、游戲選項(xiàng)部分都是直接得嵌入到了主框架中了。

第二，就是評(píng)估函數(shù)的設(shè)計(jì)，從理論上分析，評(píng)估函數(shù)就是對(duì)棋局的綜合評(píng)估，換句話說(shuō)，是給當(dāng)前局面黑白棋分別的評(píng)分，從而可以確定當(dāng)前的形勢(shì)，為搜索引擎提供了評(píng)判標(biāo)準(zhǔn)。該函數(shù)的好壞與否直接決定了解題能力的強(qiáng)與弱，所以只有好的評(píng)估函數(shù)才能對(duì)結(jié)果予以保證，否則，搜索所得到的結(jié)果就有可能與期望相距很大。就像是一個(gè)好的棋手通常都能夠?qū)Ξ?dāng)前棋局做出判斷，以最好的方式進(jìn)行進(jìn)攻，并控制整盤(pán)棋局的發(fā)展方向。由此可見(jiàn)，僅憑幾個(gè)簡(jiǎn)單的評(píng)估函數(shù)是不可能很好的抽象這整套評(píng)價(jià)模式的，因?yàn)橛刑嗟囊蛩匾紤]到。

第三，是走法生成（告訴其他部分下一步往哪里走的模塊）方面，每種棋類的規(guī)則都不同，走法生成的復(fù)雜程度也是大相徑庭。舉個(gè)例子，在一種棋類游戲中，棋子種類越多，棋子的走法與規(guī)則也就越多，要是在程序中實(shí)現(xiàn)的話就越復(fù)雜。

在六子棋地對(duì)弈程序當(dāng)中，黑白雙方交換下子，其中，沒(méi)有吃子、提子、等規(guī)則的存在，哪一方在棋盤(pán)的水平、垂直、斜線方向上首先形成了連續(xù)的六顆棋子，就獲勝了。因此，六子棋規(guī)則的方法生成來(lái)說(shuō)，棋盤(pán)上的空白位置就是合法的位置。不過(guò)在現(xiàn)實(shí)中，有些位置是不該首先考慮的，比如說(shuō)對(duì)局時(shí)是不會(huì)把棋子直接放在下邊界上。在這里，有一點(diǎn)需要注意的，那就是我們當(dāng)下的棋子的位置與對(duì)方下的棋子的位置是有很大關(guān)聯(lián)的，也就是說(shuō)我們當(dāng)下的棋子有可能是用來(lái)限制對(duì)方的棋子，并阻止其連成六顆，亦或是躲開(kāi)對(duì)方的棋子，讓自己的棋子連成六顆，這樣，較優(yōu)的走法生成的位置就應(yīng)該考慮在上一次對(duì)方下子的周圍。

第四是搜索技術(shù)方面，先來(lái)了解一下博弈樹(shù)。

基本上所有的棋類問(wèn)題，都可以用博弈樹(shù)來(lái)描述的。博弈樹(shù)，是把計(jì)算機(jī)和用戶所有可能的走法和局面一一羅列出來(lái)的一顆樹(shù)。黑白雙方交替的按相對(duì)合理走法把樹(shù)展開(kāi)，樹(shù)的每個(gè)節(jié)點(diǎn)都表示一個(gè)局面。根節(jié)點(diǎn)是當(dāng)前需要進(jìn)行計(jì)算的局面，中間節(jié)點(diǎn)是對(duì)弈過(guò)程中的某個(gè)局面，最下面的節(jié)點(diǎn)是推導(dǎo)出的局面。整個(gè)博弈樹(shù)是從當(dāng)前局面出發(fā)的，包含所有可能的對(duì)弈過(guò)程的搜索樹(shù)。所以六子棋博弈問(wèn)題也就轉(zhuǎn)化成了尋求最佳路徑的問(wèn)題了。假設(shè)博弈樹(shù)是很有限的，這樣，就不會(huì)碰到永無(wú)止境的棋局或一步有無(wú)限種算法的棋局了。

舉個(gè)例子，如果有兩個(gè)玩家對(duì)弈，他們分別為 max和min。讓max先走，然后兩人交替走，一直到游戲結(jié)束。我們用產(chǎn)生式系統(tǒng)來(lái)進(jìn)行描述。由于不可能對(duì)一個(gè)完整解圖進(jìn)行搜索，我們需要定義一個(gè)靜態(tài)估計(jì)函數(shù)g，以便對(duì)游戲狀態(tài)進(jìn)行估值。在此我們假設(shè)有利于max的狀態(tài)取g（a）＞0，并且有利于min的狀態(tài)取g（a）＜0。這樣得出以下搜索的五個(gè)步驟。

1.首先生成了整個(gè)博弈樹(shù)（擴(kuò)展樹(shù)的每個(gè)節(jié)點(diǎn)）。

2.用函數(shù)g對(duì)每個(gè)子節(jié)點(diǎn)進(jìn)行估值，得終節(jié)點(diǎn)的評(píng)價(jià)值。

3.使用終節(jié)點(diǎn)的估值 g，得到其搜索樹(shù)上一層節(jié)點(diǎn)的估值。

4.重復(fù)三過(guò)程在max層取其分支的最大值，min層取其分支的最小值，一直回溯到根結(jié)點(diǎn)。

5.根結(jié)點(diǎn)選擇分支值最大的走步走。

四、設(shè)計(jì)進(jìn)的方案

目前有以下幾種方法可以提高電腦的棋力：

第一，動(dòng)態(tài)估值。主要在于攻守的轉(zhuǎn)換和急手的處理，這個(gè)要綜合很多方面的因素，并且要從以往的經(jīng)驗(yàn)為基礎(chǔ)多加嘗試，但是工作量很大并且不易拿捏。

第二，增加細(xì)致的特定棋形的判斷。增加棋型判斷，程序中的判斷還不是很全面，與實(shí)際存在一些差異，不過(guò)，這是個(gè)數(shù)學(xué)問(wèn)題。

第三，將局部最優(yōu)和全局最優(yōu)結(jié)合起來(lái)。這種方法是最容易實(shí)現(xiàn)的，就是增加搜索深度，然后考慮整體以及局部的估值，用遞歸可以實(shí)現(xiàn)。

第四，完善開(kāi)局庫(kù)和增加學(xué)習(xí)功能。在對(duì)局中十分有用，帶有完善開(kāi)局庫(kù)和有學(xué)習(xí)功能的六子棋將是難以戰(zhàn)勝的，不過(guò)，這是一個(gè)十分復(fù)雜的過(guò)程，其中，完善開(kāi)局庫(kù)的學(xué)習(xí)功能比較容易實(shí)現(xiàn)。

[1] 李果.六子棋計(jì)算機(jī)博弈及其系統(tǒng)的研究與實(shí)現(xiàn)[D].重慶大學(xué)，2007.

[2] 王小春.PC游戲編程（人機(jī)博弈）[M].重慶大學(xué)出版社，2003.

TP311.1

A

1008-7427（2011）10-0159-01

2011-08-10