C語(yǔ)言五子棋算法

2019-11-17 05:41:20

字體：大中小

供稿：網(wǎng)友

　　任何一種棋類游戲其要害是對(duì)當(dāng)前棋局是否有正確的評(píng)分,評(píng)分越準(zhǔn)確則電腦的AI越高。五子棋游戲也是如此，但在打分之前，我們先掃描
整個(gè)棋盤，把每個(gè)空位從八個(gè)方向上的棋型填入數(shù)組gStyle(2, 15, 15, 8, 2)，其中第一個(gè)下標(biāo)為1時(shí)表示黑棋，為2時(shí)表示白棋，第二和第三
個(gè)下標(biāo)表示(x,y)，第四個(gè)下標(biāo)表示8個(gè)方向，最后一個(gè)下標(biāo)為1時(shí)表示棋子數(shù)，為2時(shí)表示空格數(shù)，如： gStyle(1,2,2,1,1)=3表示與坐標(biāo)(2,2)在第1個(gè)方向上相鄰的黑棋棋子數(shù)為3
gstyle(1,2,2,1,2)=4表示與坐標(biāo)(2,2)在第1個(gè)方向上的最近的空格數(shù)為4
在定義方向時(shí)，也應(yīng)該注重一定的技巧，表示兩個(gè)相反的方向的數(shù)應(yīng)該差4，在程序中我是這樣定義的：
Const DIR_UP = 1
Const DIR_UPRIGHT = 2
Const DIR_RIGHT = 3
Const DIR_RIGHTDOWN = 4
Const DIR_DOWN = 5
Const DIR_DOWNLEFT = 6
Const DIR_LEFT = 7
Const DIR_LEFTUP = 8
這樣我們前四個(gè)方向可以通過(guò)加四得到另一個(gè)方向的值。假如你還是不太明白，請(qǐng)看下面的圖：
---------
---------
---oo----
-ox*xx---
---------
---------
圖中的*點(diǎn)從標(biāo)為(4,4),（打*的位置是空位）,則:
gStyle(2,4,4,1,1)=1在(4,4)點(diǎn)相鄰的上方白棋數(shù)為1
gStyle(2,4,4,1,2)=2在(4,4)點(diǎn)的上方距上方白棋最近的空格數(shù)為2
gStyle(1,4,4,3,1)=2在(4,4)點(diǎn)相鄰的右方黑棋數(shù)為2
gStyle(1,4,4,3,2)=1在(4,4)點(diǎn)的右方距右方黑棋最近的空格數(shù)為3
... 　　一旦把所有空點(diǎn)的棋型值填完，我們很輕易地得出黑棋水平方向上點(diǎn)(4,4)的價(jià)值，由一個(gè)沖1（我把有界的棋稱為沖）和活2（兩邊無(wú)界的
棋稱為活）組成的。對(duì)于而白棋在垂直方向上點(diǎn)(4,4)的價(jià)值是一個(gè)活1，而在/方向也是活1所以，只要我們把該點(diǎn)的對(duì)于黑棋和白棋的價(jià)值算出
來(lái)，然后我們就取棋盤上各個(gè)空點(diǎn)的這兩個(gè)值的和的最大一點(diǎn)作為下棋的點(diǎn)。然而，對(duì)各種棋型應(yīng)該取什么值呢？我們可以先作如下假設(shè)：
　 Fn 表示先手n個(gè)棋子的活棋型，如：F4表示先手活四
　 Fn'表示先手n個(gè)棋子的沖棋型，如：F4'表示先手沖四
　 Ln 表示后手n個(gè)棋子的活棋型，如：L3表示后手活三
　 Ln'表示后手n個(gè)棋子的沖棋型，如：L3'表示后手沖三
　 .
　 .
　 .
　　根據(jù)在一行中的棋型分析，得到如下關(guān)系：
L1'<=F1'<L2'<=F2'<=L1<F1<L2<F2<L3'<=F3'<L4'<F4'=F4
　　從這個(gè)關(guān)系包含了進(jìn)攻和防守的關(guān)系（當(dāng)然，這個(gè)關(guān)系是由我定的，你可以自己定義這些關(guān)系）。對(duì)這些關(guān)系再進(jìn)一步細(xì)化，如在一個(gè)可下
棋的點(diǎn)，其四個(gè)方向上都有活三，也比不上一個(gè)沖四，所以我們可以又得到4*F3<L4'這個(gè)關(guān)系，同樣，我們還可以得到其它的關(guān)系，如：4*F2<L3、4*L3<F3...，這些的關(guān)系由于你的定法和我的定法制可能不一樣，這樣計(jì)算機(jī)的AI也就不一樣，最后我們把分值最小的L1'值定為1，則我們就得
到了下面各種棋型的分值，由C語(yǔ)言表示為：
F[2][5]={{0,2,5,50,16000},{0,10,30,750,16000}};
L[2][5]={{0,1,5,50,3750},{0,10,30,150,4000}};
　　 F數(shù)組表示先手，第一個(gè)下標(biāo)為0時(shí)表示沖型，第二個(gè)下標(biāo)表示棋子數(shù)，則F2'對(duì)應(yīng)F[0][2]L數(shù)組表示后手，第一個(gè)下標(biāo)為0時(shí)表示沖型，第二
個(gè)下標(biāo)表示棋子數(shù)，則L2對(duì)應(yīng)F[1][2]Ok，棋型的分值關(guān)系確定好了以后，我們把每一個(gè)可下點(diǎn)的四個(gè)方向的棋型值相加（包括先手和后手的分
值），最后選擇一個(gè)最大值，并把這一點(diǎn)作為計(jì)算機(jī)要下的點(diǎn)就OK了:)。后話：
1、得到最大值也許不止一個(gè)點(diǎn)，但在我的程序中只選擇第一個(gè)最大點(diǎn)，當(dāng)然你可以用于個(gè)隨機(jī)數(shù)來(lái)決定
選擇那一個(gè)最大值點(diǎn)，也可以對(duì)這些最大值點(diǎn)再作進(jìn)一步的分析。
2、在這個(gè)算法中我只考慮了四周有棋子的點(diǎn)，而其它點(diǎn)我沒(méi)有考慮。
3、可以再更進(jìn)一步，用這個(gè)算法來(lái)猜測(cè)以后的幾步棋，再選擇猜測(cè)值最好的一步，這樣電腦的AI就更高了
4、這個(gè)算法沒(méi)有考慮黑棋的禁手（雙3、雙四和多于五子的連棋）。因?yàn)樵谄綍r(shí)我下的五子棋是沒(méi)有這些
禁手的。

上一篇：HANOI塔問(wèn)題的遞歸解

下一篇：C語(yǔ)言陰陽(yáng)歷算法