有一天在网上看到一个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，差不多就这样，看
源码吧，应该还有问题，其实速度还算可以。我要睡觉了，明天还要上班。