有一天在網上看到一個Android的五子棋，該程序的作者的GoogleTalk: lixinso@gmail.com。遂下載下來看看，可以下棋，但是沒有實現電腦下棋算法，所以我一時興起花了幾個小時加了個電腦下棋算法在里面，很簡單。原作者的游戲繪制就不多說了，主要講電腦下棋算法。
1、準備一個數組表示當前棋盤，另外準備兩個數組分別保存電腦和玩家每個可下點的坐標及其分數(棋型數組)，每個可下點包括4個方向的分數，分別是橫、豎、左斜、右斜。
private int[][] mChessTable = new int[CHESS_GRID][CHESS_GRID]; // 網格
private int[][][] computerTable = new int[CHESS_GRID][CHESS_GRID][CHECK_DIR]; // 電腦棋形表
private int[][][] playerTable = new int[CHESS_GRID][CHESS_GRID][CHECK_DIR]; // 電腦棋形表
2、每個可下點的4個方向分數判斷，每個方向取當前點左右每邊5個棋點的狀態，然后分析它們是否構成五連、活四、活三等，每種棋型給予不同的分數。 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、將玩家棋型數組和電腦棋型數組每個元素的分數比較，選出最大的五個放入一個降序排列的數組中。
/**
* 找到最佳點
*
* @return 最佳點
*/
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、處理降序排列的數組，如果第一個元素的分數>=(必勝的條件的分數)，直接返回就可以了，如果小于就繼續處理我們降序排列的數組每個元素，假設每個元素已下，然后判斷其產生的后果，取出具有最佳后果的元素，并返回其值，作為電腦下棋點。判斷每個元素的產生后果時，其實只需要處理其產生作用的棋盤范圍就行了(以該元素位置為中心的正方形的棋盤范圍，正方形邊長為4 + 1 + 4，我用的10)，不必要處理搜索處理整個棋盤的棋子。
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，差不多就這樣，看
源碼吧，應該還有問題，其實速度還算可以。我要睡覺了，明天還要上班。