有一天在網(wǎng)上看到一個(gè)Android的五子棋，該程序的作者的GoogleTalk: lixinso@gmail.com。遂下載下來(lái)看看，可以下棋，但是沒(méi)有實(shí)現(xiàn)電腦下棋算法，所以我一時(shí)興起花了幾個(gè)小時(shí)加了個(gè)電腦下棋算法在里面，很簡(jiǎn)單。原作者的游戲繪制就不多說(shuō)了，主要講電腦下棋算法。
1、準(zhǔn)備一個(gè)數(shù)組表示當(dāng)前棋盤(pán)，另外準(zhǔn)備兩個(gè)數(shù)組分別保存電腦和玩家每個(gè)可下點(diǎn)的坐標(biāo)及其分?jǐn)?shù)(棋型數(shù)組)，每個(gè)可下點(diǎn)包括4個(gè)方向的分?jǐn)?shù)，分別是橫、豎、左斜、右斜。
private int[][] mChessTable = new int[CHESS_GRID][CHESS_GRID]; // 網(wǎng)格
private int[][][] computerTable = new int[CHESS_GRID][CHESS_GRID][CHECK_DIR]; // 電腦棋形表
private int[][][] playerTable = new int[CHESS_GRID][CHESS_GRID][CHECK_DIR]; // 電腦棋形表
2、每個(gè)可下點(diǎn)的4個(gè)方向分?jǐn)?shù)判斷，每個(gè)方向取當(dāng)前點(diǎn)左右每邊5個(gè)棋點(diǎn)的狀態(tài)，然后分析它們是否構(gòu)成五連、活四、活三等，每種棋型給予不同的分?jǐn)?shù)。 1 // -------------------------------------------------------------
2 /**
3 * 分析存在五連
4 *
5 * @param tmpChess
6 */
7 public boolean analyzeWulian(int[] tmpChess, int isWho) {
8 int count = 0;
9 for (int i = 0; i < HALF_LEN; i++) {
10 if (tmpChess[HALF_LEN - (i + 1)] == isWho) {
11 count++;
12 } else {
13 break;
14 }
15 }
16 for (int i = 0; i < HALF_LEN; i++) {
17 if (tmpChess[HALF_LEN + i] == isWho) {
18 count++;
19 } else {
20 break;
21 }
22 }
23 if (count == 4) {
24 return true;
25 }
26 return false;
27 }
28
29 /**
30 *
31 * 分析活四 return 是否存在活四
32 *
33 * @param tmpChess
34 */
35 public boolean analyzeHuosi(int[] tmpChess, int isWho) {
36 int count = 0;
37 int i = 0;
38 boolean isSpace = false;
39 for (i = 0; i < HALF_LEN; i++) {
40 if (tmpChess[HALF_LEN - (i + 1)] == isWho) {
41 count++;
42 } else {
43 break;
44 }
45 }
46 if (tmpChess[HALF_LEN - (i + 1)] == 0) {
47 isSpace = true;
48 }
49 for (i = 0; i < HALF_LEN; i++) {
50 if (tmpChess[HALF_LEN + i] == isWho) {
51 count++;
52 } else {
53 break;
54 }
55 }
56 if (tmpChess[HALF_LEN + i] == 0) {
57 isSpace = true;
58 } else {
59 isSpace = false;
60 }
61
62 if (count == 3 && isSpace) {
63 return true;
64 }
65 return false;
66 }
67
68 /**
69 *
70 * 分析活三 return 是否存在活三
71 *
72 * @param tmpChess
73 */
74 public boolean analyzeHuosan(int[] tmpChess, int isWho) {
75 int count = 0;
76 int i = 0;
77 boolean isSpace = false;
78 for (i = 0; i < HALF_LEN; i++) {
79 if (tmpChess[HALF_LEN - (i + 1)] == isWho) {
80 count++;
81 } else {
82 break;
83 }
84 }
85 if (tmpChess[HALF_LEN - (i + 1)] == 0) {
86 isSpace = true;
87 }
88 for (i = 0; i < HALF_LEN; i++) {
89 if (tmpChess[HALF_LEN + i] == isWho) {
90 count++;
91 } else {
92 break;
93 }
94 }
95 if (tmpChess[HALF_LEN + i] == 0) {
96 isSpace = true;
97 } else {
98 isSpace = false;
99 }
100
101 if (count == 2 && isSpace) {
102 return true;
103 }
104 return false;
105 }
3、將玩家棋型數(shù)組和電腦棋型數(shù)組每個(gè)元素的分?jǐn)?shù)比較，選出最大的五個(gè)放入一個(gè)降序排列的數(shù)組中。
/**
* 找到最佳點(diǎn)
*
* @return 最佳點(diǎn)
*/
private ChessPoint findBestPoint() {
int i, j;
ChessPoint point;
int maxScore = 0;
int tmpScore = 0;
for (i = 0; i < CHESS_GRID; i++) {
for (j = 0; j < CHESS_GRID; j++) {
// 電腦比較
tmpScore = computerTable[i][j][0];
tmpScore += computerTable[i][j][1];
tmpScore += computerTable[i][j][2];
tmpScore += computerTable[i][j][3];
if (maxScore <= tmpScore) {
maxScore = tmpScore;
point = new ChessPoint();
point.x = j;
point.y = i;
point.score = maxScore;
insertBetterChessPoint(point);
}
// 玩家比較
tmpScore = playerTable[i][j][0];
tmpScore += playerTable[i][j][1];
tmpScore += playerTable[i][j][2];
tmpScore += playerTable[i][j][3];
if (maxScore <= tmpScore) {
maxScore = tmpScore;
point = new ChessPoint();
point.x = j;
point.y = i;
point.score = maxScore;
insertBetterChessPoint(point);
}
}
}
// Log.v("cmaxpoint = ", "" + cMaxScore);
// Log.v("pmaxpoint = ", "" + pMaxScore);
return analyzeBetterChess();
}
4、處理降序排列的數(shù)組，如果第一個(gè)元素的分?jǐn)?shù)>=(必勝的條件的分?jǐn)?shù))，直接返回就可以了，如果小于就繼續(xù)處理我們降序排列的數(shù)組每個(gè)元素，假設(shè)每個(gè)元素已下，然后判斷其產(chǎn)生的后果，取出具有最佳后果的元素，并返回其值，作為電腦下棋點(diǎn)。判斷每個(gè)元素的產(chǎn)生后果時(shí)，其實(shí)只需要處理其產(chǎn)生作用的棋盤(pán)范圍就行了(以該元素位置為中心的正方形的棋盤(pán)范圍，正方形邊長(zhǎng)為4 + 1 + 4，我用的10)，不必要處理搜索處理整個(gè)棋盤(pán)的棋子。
private ChessPoint analyzeBetterChess() {
if(fiveBetterPoints[0].score > 30){
return fiveBetterPoints[0];
}
else
{
ChessPoint betterPoint = null;
ChessPoint tmpPoint = null;
int goodIdx = 0;
int i = 0;
int startx, starty, endx, endy;
ChessPoint[] fbpTmp = new ChessPoint[5];
for(i = 0; i < 5;i++){
fbpTmp[i] = fiveBetterPoints[i];
}
for(i = 0; i < 5;i++){
if(fbpTmp[i] == null) break;
mChessTable[fbpTmp[i].y][fbpTmp[i].x] = BLACK;
clearChessArray();
startx = fbpTmp[i].x - 5;
starty = fbpTmp[i].y - 5;
if(startx < 0){
startx = 0;
}
if(starty < 0){
starty = 0;
}
endx = startx + 10;
endy = starty + 10;
if(endx > CHESS_GRID){
endx = CHESS_GRID;
}
if(endy > CHESS_GRID){
endy = CHESS_GRID;
}
analyzeChessMater(computerTable, BLACK, startx, starty, endx, endy);
// 分析玩家的棋型/////////////////////////////////////////////////////
analyzeChessMater(playerTable, WHITE, startx, starty, endx, endy);
tmpPoint = findBetterPoint(startx, starty, endx, endy);
if(betterPoint != null){
if(betterPoint.score <= tmpPoint.score){
betterPoint = tmpPoint;
goodIdx = i;
}
}
else{
betterPoint = tmpPoint;
goodIdx = i;
}
mChessTable[fbpTmp[i].y][fbpTmp[i].x] = 0;
}
tmpPoint = null;
betterPoint = null;
return fbpTmp[goodIdx];
}
}
OK，差不多就這樣，看
源碼吧，應(yīng)該還有問(wèn)題，其實(shí)速度還算可以。我要睡覺(jué)了，明天還要上班。