一種優化模型對五子棋人工智能算法的分析與應用

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

關鍵詞:優化;算法;模型;五子棋;規則;篩選;鏈表操作

中圖分類號:TP311文獻標識碼: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 引言

本算法與使用語言無關，故用經典的C語言表示，同時具有算法簡單，效率高，可擴展性強，等特點。

2 算法分析

五子棋的規則為， 每人一對一子下， 五子橫豎斜有連續五子為勝。

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

讓計算機下棋事實上就是一個輸入輸出的系統結構， 根據輸入數據，通過計算輸出結果的過程。

3 建立模型數據結構

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

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

然后每次下一次， 根據下子方和下子位置，將相應的MAXTRIX單元置1或者置2。

4算法實現

為了保持MATRIX中的數據，原始數據并不是MATRIX數據， 而是根據MATRIX新建一個鏈表， 首先是節點數據結構

Struct Point

{

int state;/* 表示當前狀態 state=0表示無子，1表示白子，2表示紅子 */

int x;/* 該點的X軸坐標 */

int y: /* 該點的Y軸坐標 */

int Kb;/* 黑子該點的總權值 */

int Kw;/* 白子該點的總權值 */

Point *next;

/* 對其他規則所需要的數據在此補充 */

};

然后是鏈表結構:

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

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

通過對原始數據進行簡單處理， 問題已經轉化成對一個鏈表的操作，如果操作這個鏈表，如圖2所示。

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

用程序來表示如下:

void Caculate()

{

RuleNumber1();/* 規則一 */

RuleNumber2();/* 規則二 */

RuleNumber3();/* 規則三 */

……

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

}

本算法采用到的規則:

規則一: 如果當前格有子， 則不考慮， 只要用個簡單一個IF就行了

設當前指針為pt， 則只需要做一個循環，循環體內，做如下操作:

While(!EOF)

{

if(pt->state) deletepoint;

pt = pt->next;

}

規則二: 如果當前格的根據當前位置的權值來刪除節點

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

對單一方向的權值計算方法，以橫向右邊為例對當前位置左右四子范圍進行判斷:

a) 默認權值為2

b) 無子 不靠邊權值 +0

靠邊 權值 -1

c) 有子 己方子每一子權值 +1

對方子有且只有一次加權 -1

如圖3所示。

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

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

利用此公式即可計算出的權值就可以基本上反映出當前位置的價值

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

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

b)如果該點沒有一個達到最大權的， 刪除該節點

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

規則N:根據所有的計算結果所留下的最后幾個節點，綜合關系，選出最合適的點。

5 輸出結果

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

6 其他一些問題

6.1判斷勝負

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

6.2 算法的智能性

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

6.3 算法的強壯性

本算法沒有過多循環， 沒有跳轉， 不會出現嚴重錯誤。

6.4 算法效率

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

7 總結

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

參考文獻:

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

[2] 李家同.算法設計與分析導論[M].北京:機械工業出版社，2008.

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