一種優(yōu)化模型對五子棋人工智能算法的分析與應(yīng)用

摘要:該文介紹了一種模型的建立的思想及對于五子棋的實現(xiàn)方法。在對五子棋的問題解決中，本算法通過對N條規(guī)則進(jìn)行選擇以確定最佳下子點。在本算法中，每條規(guī)則就是對原始數(shù)據(jù)的一次篩選，即一次鏈表刪除操作，經(jīng)過N條規(guī)則的N次操作，最后留下的數(shù)據(jù)(一個坐標(biāo)串)就是最好的下棋位置。該方法同樣適用于其他的一些類似問題。

關(guān)鍵詞:優(yōu)化;算法;模型;五子棋;規(guī)則;篩選;鏈表操作

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2009)14-3775-02

Analysis and Application of Algirism of Five Chess Based on a Optimism Model

HAO Wei

(Department of Comtuter of Anhui University of Science and Technology， Huaina 232001，China)

Abstract: This article introduces a method of a optimism model. Based on several Rules which are the operations of original data. Through operations including finding， selecting and deleting data in the link table， the optimism point will present.It also functions well in the same question like five chess.

Key words: optimism; model; algirism; five chess; rules; link table operations

1 引言

本算法與使用語言無關(guān)，故用經(jīng)典的C語言表示，同時具有算法簡單，效率高，可擴(kuò)展性強，等特點。

2 算法分析

五子棋的規(guī)則為， 每人一對一子下， 五子橫豎斜有連續(xù)五子為勝。

如何讓計算機學(xué)會下五子棋，首先要將此問題轉(zhuǎn)化為一個計算模型，事實上從計算機角度考慮，原理圖如圖1。

讓計算機下棋事實上就是一個輸入輸出的系統(tǒng)結(jié)構(gòu)， 根據(jù)輸入數(shù)據(jù)，通過計算輸出結(jié)果的過程。

3 建立模型數(shù)據(jù)結(jié)構(gòu)

首先，應(yīng)該將棋盤進(jìn)行了數(shù)據(jù)化，五子棋采用的一般是15*15的棋盤，故采用的一個15*15的2維數(shù)組:MATRIX來存儲數(shù)據(jù)，為了方便建立的數(shù)組就是MATRIX[17][17]，直接使用從MATRIX[1][1]- MATRIX[15][15]表示每個格子。剩下的一圈為黑邊，每個數(shù)據(jù)單元為一int數(shù)據(jù)， 表示三種情況:

無子:0白子:1黑子:2

然后每次下一次， 根據(jù)下子方和下子位置，將相應(yīng)的MAXTRIX單元置1或者置2。

4算法實現(xiàn)

為了保持MATRIX中的數(shù)據(jù)，原始數(shù)據(jù)并不是MATRIX數(shù)據(jù)， 而是根據(jù)MATRIX新建一個鏈表， 首先是節(jié)點數(shù)據(jù)結(jié)構(gòu)

Struct Point

{

int state;/* 表示當(dāng)前狀態(tài) state=0表示無子，1表示白子，2表示紅子 */

int x;/* 該點的X軸坐標(biāo) */

int y: /* 該點的Y軸坐標(biāo) */

int Kb;/* 黑子該點的總權(quán)值 */

int Kw;/* 白子該點的總權(quán)值 */

Point *next;

/* 對其他規(guī)則所需要的數(shù)據(jù)在此補充 */

};

然后是鏈表結(jié)構(gòu):

設(shè)P11(x1， y1)表示 Matrix[x1][y1]

START->P11->P12->P13->…->P2020->END

通過對原始數(shù)據(jù)進(jìn)行簡單處理， 問題已經(jīng)轉(zhuǎn)化成對一個鏈表的操作，如果操作這個鏈表，如圖2所示。

所以本算法事實上就是N條規(guī)則， 每條規(guī)則就是對鏈表中的數(shù)據(jù)的一次篩選操作或者說鏈表刪除操作，經(jīng)過N條規(guī)則的N次刪除操作，最后留下的數(shù)據(jù)(鏈表中的最后幾個節(jié)點)就是最好的下棋位置。

用程序來表示如下:

void Caculate()

{

RuleNumber1();/* 規(guī)則一 */

RuleNumber2();/* 規(guī)則二 */

RuleNumber3();/* 規(guī)則三 */

……

RuleNumberN();/* 最后一條規(guī)則N */

}

本算法采用到的規(guī)則:

規(guī)則一: 如果當(dāng)前格有子， 則不考慮， 只要用個簡單一個IF就行了

設(shè)當(dāng)前指針為pt， 則只需要做一個循環(huán)，循環(huán)體內(nèi)，做如下操作:

While(!EOF)

{

if(pt->state) deletepoint;

pt = pt->next;

}

規(guī)則二: 如果當(dāng)前格的根據(jù)當(dāng)前位置的權(quán)值來刪除節(jié)點

在判斷每個點的價值的方法，本算法所采取的辦法是用權(quán)值來確實最好的下子位置的方法。 五子棋不管是橫豎斜， 只要滿五個子就可以了， 由于橫豎斜(正斜， 反斜)四個方向獨立的， 可以分別考慮， 即計算一個方向上的權(quán)值， 然后四個方向再相加。

對單一方向的權(quán)值計算方法，以橫向右邊為例對當(dāng)前位置左右四子范圍進(jìn)行判斷:

a) 默認(rèn)權(quán)值為2

b) 無子 不靠邊權(quán)值 +0

靠邊 權(quán)值 -1

c) 有子 己方子每一子權(quán)值 +1

對方子有且只有一次加權(quán) -1

如圖3所示。

單一方向的權(quán)值計算共有四個， 由于他們之間是獨立的， 但是該點的價值應(yīng)該體現(xiàn)在最大權(quán)值的方向， 并且同樣對于兩個點， 同樣最大權(quán)值的情況下， 又要考慮其他方向， 所以采用如下計算公式計算總權(quán)值:

K = a0*4^0+a1*4^1+a2*4^2+a3*4^3+a4*4^4+a5*4^5

利用此公式即可計算出的權(quán)值就可以基本上反映出當(dāng)前位置的價值

利用K的計算方法， 計算出每一點的Kw和Kb然后再確實下子， 假設(shè)下一步是黑棋走， 有如下規(guī)則:

a)計算權(quán)值最大的權(quán)是多少(kbmax， kwmax)

b)如果該點沒有一個達(dá)到最大權(quán)的， 刪除該節(jié)點

更多規(guī)則:為了增加計算機的水平， 還可以在算法中繼續(xù)增加規(guī)則， 如對一下步的預(yù)測， 在幾個比較合適的點中， 對對手的下一步進(jìn)行， 預(yù)測對手下一步可能下的位置， 不管從精簡算法角度， 還是從實際效果考慮， 都沒有必要對所有位置考慮， 事實上只需要對對手最可能下的一兩個位置， 然后對此位置后進(jìn)行預(yù)測即可， 其他位置正常算法就可以， 不需要用推測下一步去年。 對于需要預(yù)測的位置， 再次計算新的棋局的權(quán)值， 設(shè)本步為KT1， 下一步為KT2(在節(jié)點的數(shù)據(jù)結(jié)構(gòu)中增加此變量即可)， 以此類推， 根據(jù)需要預(yù)測計算步數(shù)， 然后再根據(jù)KT1和KT2等的權(quán)值綜合計算出最合適的點， 將會計算機下棋的水平更具有策略性。

規(guī)則N:根據(jù)所有的計算結(jié)果所留下的最后幾個節(jié)點，綜合關(guān)系，選出最合適的點。

5 輸出結(jié)果

本程序計算機使用是紅子，所以最后根據(jù)計算的最后輸出結(jié)果將結(jié)果指向的坐標(biāo)矩陣MATRIX置1，然后顯示。等待下次對手下子。

6 其他一些問題

6.1判斷勝負(fù)

每下一次子都要判斷一次， 從精簡算法角度考慮， 只需要計算最后下子的位置即可. 計算最后下子的位置的橫豎斜四個方向， 有滿五子則給出相應(yīng)處理， 無則繼續(xù)。

6.2 算法的智能性

對于算法中最可能會出現(xiàn)低級錯誤(比如說邊角問題)， 可以通過追加相應(yīng)規(guī)則來解決。

6.3 算法的強壯性

本算法沒有過多循環(huán)， 沒有跳轉(zhuǎn)， 不會出現(xiàn)嚴(yán)重錯誤。

6.4 算法效率

本算法效率非常高， 即使在移植到手機上也會瞬間給出結(jié)果。

7 總結(jié)

本文主要介紹了五子棋算法的設(shè)計，實現(xiàn)和編碼整個過程。對五子棋的算法進(jìn)行了簡單的分析，并設(shè)計出一套數(shù)據(jù)模型。

參考文獻(xiàn):

[1] (美)萊維丁.算法設(shè)計與分析基礎(chǔ)[M].北京:清華大學(xué)出版社，2007.

[2] 李家同.算法設(shè)計與分析導(dǎo)論[M].北京:機械工業(yè)出版社，2008.

[3] 王曉東.計算機算法設(shè)計與分析[M].北京:清華大學(xué)出版社，2007.