暑假的这个小学期，研究了一下AI，做了个五子棋游戏当成是小学期作业。BREW手机平台的，说来惭愧，我是不会用VC做，才想到BREW平台的，因为我比较熟悉这个平台，画图也容易啊，界面全是贴图，一个IIMAGE_DrawFrame()函数全部搞定。
这是我写的第一个完整程序，代码写的十分混乱，有的功能实现的还很傻瓜，有点费力不讨好似的。高手们平常都是怎么写程序、管理代码的呢？希望大家不吝赐教！
AI 部分也好菜，虽说是分三个级别，但其实电脑也不是很聪明，我下不过它只能说明我的水平太低了，呵呵。怎么能让电脑聪明点呢？
下面看看我的核心算法吧：
数据结构和#define
enum{ //棋盘状态
None,
Player,
Com,
};
enum{ //难度级别
Easy,
Middle,
Hard
};
enum { //游戏状态机
Splash,
Menu,
Single,
Multi,
ComWin,
PlayerWin,
Forbid,
Settings,
Score,
HelpM
};
//按键
#define K_up 1
#define K_down 2
#define K_left 4
#define K_right 8
#define K_Select 16
#define K_Soft1 32
#define K_Soft2 64
//使单人游戏和本地双人游戏能共用
#define Player1 Player
#define Player2 Com
#define Player1Win PlayerWin
#define Player2Win ComWin
//分数定义，后面还有一些没定义的，直接写的
#define Dead -65535
#define Five 65535
#define LFour 10000
#define DFour 500
#define LThree 200
#define DThree 50
#define LTwo 5
#define DTwo 3
//全局的数据结构
typedef struct _GLO{
AEEApplet a;
char number; //记录双方一共下了的步数，悔棋用
int KeyPress;
char level;
char Board[15][15];
char UnDo[225][2]; //记录双方的下子位置，悔棋用，一维坐标的奇偶表示先\后手方
char GameState;
char LastState;
char timer;
char Menu_Ptr; //菜单当前项
IImage *pISplash;
IImage *pIMenu;
IImage *pIBlack;
IImage *pIWhite;
IImage *pICB;
IImage *pIFire;
IImage *pIBb;
IImage *pIHelp;
IImage *pIScore;
IImage *pIWin;
IImage *pISetup;
IImage *pIForbid;
char who;
char First;
char WinLose;
char x, y;
}Global;
核心play及AI算法
Play()函数每100毫秒被系统调用一次（之所以要这样，是因为系统不可以把全部的资源都用在游戏上，还要预留一部分给通信，即电话和短信，毕竟游戏不能影响到手机的正常使用。这样的作法可以使游戏在每一秒内都有一定的空闲时间）
boolean Play(Global * pMe){ //单人游戏过程
char i, j;
int mark;
IIMAGE_Draw(pMe->pICB, 0, 0); //画棋盘
if(pMe->number > 1 && pMe->number%2){ //提示上一步动作(闪烁)
pMe->timer ++;
if(pMe->timer > 6){
pMe->Board[ pMe->UnDo[pMe->number-1][0]-1 ][ pMe->UnDo[pMe->number-1][1]-1 ] = None;
if(pMe->timer == 12)
pMe->timer = 0;
}
else
pMe->Board[ pMe->UnDo[pMe->number-1][0]-1 ][ pMe->UnDo[pMe->number-1][1]-1 ] = Com;
}
if(Player == pMe->First){
for(i = 0; i < 15; i++) //画出已经下了的子(玩家先手)
for(j = 0; j < 15; j++){
if(pMe->Board[i][j] == Player)
IIMAGE_Draw(pMe->pIBlack, 6 + i * 11, 6 + j * 11);
else if(pMe->Board[i][j] == Com)
IIMAGE_Draw(pMe->pIWhite, 6 + i * 11, 6 + j * 11);
}
}
else{
for(i = 0; i < 15; i++) //画出已经下了的子(电脑先手)
for(j = 0; j < 15; j++){
if(pMe->Board[i][j] == Player)
IIMAGE_Draw(pMe->pIWhite, 6 + i * 11, 6 + j * 11);
else if(pMe->Board[i][j] == Com)
IIMAGE_Draw(pMe->pIBlack, 6 + i * 11, 6 + j * 11);
}
}
if(pMe->who == Player){ //若玩家获胜，处理游戏状态机
if(pMe->WinLose == Player){
pMe->GameState = PlayerWin;
pMe->WinLose = None;
IDISPLAY_Update(pMe->a.m_pIDisplay);
return 0;
}
IIMAGE_Draw(pMe->pIBb, 6 + (pMe->x - 1) * 11, 6 + (pMe->y - 1) * 11); //画当前位置的提示符
//光标移动
if(pMe->KeyPress & K_up)
pMe->y --;
if(pMe->KeyPress & K_down)
pMe->y ++;
if(pMe->KeyPress & K_left)
pMe->x --;
if(pMe->KeyPress & K_right)
pMe->x ++;
//释放按键，以防连按（因为100毫秒就判断一次）
pMe->KeyPress &= ~K_up;
pMe->KeyPress &= ~K_down;
pMe->KeyPress &= ~K_left;
pMe->KeyPress &= ~K_right;
//边界判断
if(pMe->x < 1)
pMe->x = 1;
else if(pMe-> x > 15)
pMe->x = 15;
if(pMe->y < 1)
pMe->y = 1;
else if(pMe-> y > 15)
pMe->y = 15;
if(pMe->KeyPress & K_Soft1){ //悔棋
pMe->KeyPress &= ~K_Soft1;
if(pMe->number == 1)
return 1;
pMe->timer = 0;
pMe->Board[ pMe->UnDo[pMe->number-1][0]-1 ][ pMe->UnDo[pMe->number-1][1]-1 ] = None;
pMe->Board[ pMe->UnDo[pMe->number-2][0]-1 ][ pMe->UnDo[pMe->number-2][1]-1 ] = None;
pMe->number -= 2;
return 0;
}
if(pMe->KeyPress & K_Soft2){ //退出到菜单
pMe->KeyPress &= ~K_Soft2;
pMe->timer = 0;
pMe->GameState = Menu;
return 0;
}
//落子
if((pMe->KeyPress & K_Select) && pMe->Board[pMe->x - 1][pMe->y - 1] == None){
pMe->KeyPress &= ~K_Select;
if(pMe->number > 1){
if(pMe->x == pMe->UnDo[pMe->number-1][0]
&& pMe->y == pMe->UnDo[pMe->number-1][1])
return 0;
pMe->Board[ pMe->UnDo[pMe->number-1][0]-1 ][ pMe->UnDo[pMe->number-1][1]-1 ]
= Com; //把刚才电脑下的闪烁的子落实
}
pMe->timer = 0;
pMe->Board[pMe->x - 1][pMe->y - 1] = Player;
mark = Search(pMe, pMe->x, pMe->y, Player); //通过Search()函数，判断该点是不是禁手，获胜否
if(mark <= Dead){ //如果禁手，游戏状态机离开正常游戏状态，进入禁手状态
pMe->Board[pMe->x - 1][pMe->y - 1] = None;
pMe->GameState = Forbid;
pMe->LastState = Multi;
pMe->timer = 0;
return 0;
}
else if(mark >= Five){ //如果禁手，游戏状态机离开正常游戏状态，进入获胜状态
pMe->WinLose = Player;
return 0;
}
pMe->Board[pMe->x - 1][pMe->y - 1] = Player; //若即没获胜又不是禁手点，则正常落子
pMe->UnDo[pMe->number][0] = pMe->x; //记入悔棋的数组
pMe->UnDo[pMe->number++][1] = pMe->y;
pMe->who = Com; //把当前执子方改为电脑
}
}
else { //电脑走棋
if(pMe->WinLose == None) AI(pMe); //AI函数为人工智能
else pMe->GameState = ComWin;
}
IDISPLAY_Update(pMe->a.m_pIDisplay);
return 1;
}
boolean AI(Global * pMe){
char i, j; //循环变量
int mark;
int Hmark1, Hmark2, Hmark3, HHmark, HHHmark; //记录最高分数
char x1, y1, x2, y2, x3, y3, xx1, yy1, xx2, yy2, xx3, yy3; //记录获得最高分数的点的坐标
Hmark1 = Hmark2 = Hmark3 = HHmark = HHHmark = 0;
for(i= 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){ //搜索棋盘，遇有空点则向该空点的四个方向搜索，并计算得分
pMe->Board[i-1][j-1] = Com;
mark = Search(pMe, i, j, Com); //通过Search()函向该空点的四个方向搜索计算自己的得分
if(mark >= Five){ //得分大于五子连珠，则退出到Play()函数处理
pMe->WinLose = Com;
return 0;
}
pMe->Board[i-1][j-1] = Player;
mark += Search(pMe, i, j, Player); //通过Search()函向该空点的四个方向搜索计算阻碍对手得的分
pMe->Board[i-1][j-1] = None;
if(mark > Hmark1){ //找出得分最高的点及其坐标(初级1个点、中级2个点、高级3个点)
x1 = i;
y1 = j;
Hmark1 = mark;
}
else if(mark > Hmark2 && pMe->level != Easy){
x2 = i;
y2 = j;
Hmark2 = mark;
}
else if(mark > Hmark3 && pMe->level == Hard){
x3 = i;
y3 = j;
Hmark3 = mark;
}
}
if(Hmark1 == 0){ //这是电脑先手时的特殊情况，使其落子在棋盘中央
pMe->Board[7][7] = Com;
pMe->who = Player;
return 0;
}
if(pMe->level != Easy && Hmark1 < LFour){ //这是中级、高级算法
//主体思想就是由刚才得到的2或3个点，再推算一步，找出得分的分最高的点
Hmark1 = Hmark2 = Hmark3 = 0;
pMe->Board[x1-1][y1-1] = Com;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Player;
mark = Search(pMe, i, j, Player);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark1){
xx1 = i;
yy1 = j;
Hmark1 = mark;
}
}
pMe->Board[xx1-1][yy1-1] = Player;
Hmark1 = 0;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Com;
mark = Search(pMe, i, j, Com);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark1) Hmark1 = mark;
}
pMe->Board[x1-1][y1-1] = None;
pMe->Board[xx1-1][yy1-1] = None;
pMe->Board[x2-1][y2-1] = Com;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Player;
mark = Search(pMe, i, j, Player);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark2){
xx2 = i;
yy2 = j;
Hmark2 = mark;
}
}
pMe->Board[xx2-1][yy2-1] = Player;
Hmark2 = 0;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Com;
mark = Search(pMe, i, j, Com);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark2) Hmark2 = mark;
}
pMe->Board[x2-1][y2-1] = None;
pMe->Board[xx2-1][yy2-1] = None;
if(pMe->level == Hard){
pMe->Board[x3-1][y3-1] = Com;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Player;
mark = Search(pMe, i, j, Player);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark3){
xx3= i;
yy3 = j;
Hmark3 = mark;
}
}
pMe->Board[xx3-1][yy3-1] = Player;
Hmark3 = 0;
for(i = 1; i < 16; i++)
for(j = 1; j < 16; j++)
if(pMe->Board[i-1][j-1] == None){
pMe->Board[i-1][j-1] = Com;
mark = Search(pMe, i, j, Com);
pMe->Board[i-1][j-1] = None;
if(mark > Hmark3) Hmark3 = mark;
}
pMe->Board[x3-1][y3-1] = None;
pMe->Board[xx3-1][yy3-1] = None;
}
if(Hmark2 > Hmark1){
x1 = x2;
y1 = y2;
}
if(Hmark3 > Hmark1){
x1 = x3;
y1 = y3;
}
}
//落子
pMe->Board[x1-1][y1-1] = Com;
pMe->who = Player;
pMe->UnDo[pMe->number][0] = x1;
pMe->UnDo[pMe->number++][1] = y1;
return 0;
}
int SMark(int s, int t1, int t2, char blank){ //计算单线得分的函数(一共四个方向的一个)
if(s > 5 && !blank) return Dead; //长连
if(s == 5) //成五
return blank? 0 : Five;
if(s == 4 && !t1 && !t2) //活四
return blank? LFour - LThree : LFour;
if(s == 4 && (!t1 || !t2)) //死四
return blank? DFour - DThree : DFour;
if(s == 3 && !t1 && !t2) //活三
return blank? LThree - LTwo : LThree;
if(s == 3 && (!t1 || !t2)) //死三
return blank? DThree - DTwo : DThree;
if(s == 2 && !t1 && !t2) //活二
return blank? LTwo - DTwo : LTwo;
if(s == 2 && (!t1 || !t2)) return DTwo; //死二
return 0;
}
int Mark(int s1, int s2, int s3, int s4, char tag, char First){ //计算四个方向的总的分的函数
int i;
int si;
char mLFour, mDFour, mLThree, mDThree, mLTwo, mDTwo;
mLFour = mDFour = mLThree = mDThree = mLTwo = mDTwo = 0;
for(i = 0; i < 4; i++){
switch(i) {
case 0:
si = s1;
break;
case 1:
si = s2;
break;
case 2:
si = s3;
break;
case 3:
si = s4;
break;
}
switch(si) {
case LFour:
case LFour - LThree:
mLFour ++;
break;
case DFour:
mDFour ++;
break;
case LThree:
case LThree - LTwo:
mLThree ++;
break;
case DThree:
mDThree ++;
break;
case LTwo:
mLTwo ++;
break;
case DTwo:
mDTwo ++;
break;
}
}
if(mLThree >=2 && First == tag) //禁手
return Dead;
if(mLFour >= 2 && First == tag) //禁手
return Dead;
if(mLThree >= 2)
return 5000;
if(mDFour >= 2)
return 10000;
if(mDFour && mLThree)
return 10000;
if(mDThree && mLThree)
return 1000;
if(mLTwo >= 2)
return 100;
if(mDTwo && mLTwo)
return 10;
return (s1 + s2 + s3 + s4);
}
int Search(Global *pMe, char i, char j, char tag){
//先寻单线棋子个数，再计算单线得分，最后通过单线得分计算总得分
//这是我写的最混乱的函数了，主要是做的时候忘了判断隔一个空子连成得线的情况
//后来再加上去的时候，加了个blank参数记录隔子情况，就显得很混乱了
//t1、t2分别表示当前单线的两边的情况，0代表空位，1是对方棋子，2是边界，3是中间变量
char t1, t2; //被空位(0)or对手棋子(1)or边界(2)阻断
char m, n;
int s1, s2, s3, s4; //4个方向的连续子数
char ss; //最大连接子geshu
char temp;
char p1, p2;
char blank;
if(tag == Com) {p1 = Com; p2 = Player;}
else {p1 = Player; p2 = Com;}
s1 = s2 = s3 = s4 = 0;
//竖向
n = j;
blank = 0;
temp =0;
ss = 0;
t1 = t2 = 2;
while (--n) {
if(pMe->Board[i-1][n-1] != p1){
if(pMe->Board[i-1][n-1] == p2) {
if(t1 == 3) {t1 = 0; n++;}
else t1 = 1;
break;
}
else if(t1 == 3) {t1 = 0; break;}
else t1 = 3;
}
else t1 = 2;
}
while (++n < 16) {
if(pMe->Board[i-1][n-1] == p1){
s1 ++;
t2 = 2;
temp ++;
if(temp > ss)
ss =temp;
}
else{
temp = 0;
if(pMe->Board[i-1][n-1] == p2) {
if(t2 == 3) t2 = 0;
else t2 = 1;
break;
}
else if(t2 == 3) {t2 = 0; blank --; break;}
else t2 = 3;
if(s1) blank ++;
}
if(n == 15 && t2 == 3){
blank --;
t2 = 0;
}
}
if(ss == 5 && tag == p1)
return Five;
s1 = SMark(s1, t1, t2, blank);
//横向
m = i;
blank = 0;
temp = 0;
ss = 0;
t1 = t2 = 2;
while (--m) {
if(pMe->Board[m-1][j-1] != p1){
if(pMe->Board[m-1][j-1] == p2) {
if(t1 == 3) t1 = 0;
else t1 = 1;
break;
}
else if(t1 == 3) {t1 = 0; break;}
else t1 = 3;
}
else t1 = 2;
}
while (++m < 16) {
if(pMe->Board[m-1][j-1] == p1){
s2 ++;
t2 = 2;
temp ++;
if(temp > ss) ss = temp;
}
else{
temp = 0;
if(pMe->Board[m-1][j-1] == p2) {
if(t2 == 3) t2 = 0;
else t2 = 1;
break;
}
else if(t2 == 3) {t2 = 0; blank --; break;}
else t2 = 3;
if(s2) blank ++;
}
if(m == 15 && t2 == 3){
blank --;
t2 = 0;
}
}
if(ss == 5 && tag == p1)
return Five;
s2 = SMark(s2, t1, t2, blank);
//左上至右下
m = i; n = j;
blank = 0;
temp = 0;
ss = 0;
t1 = t2 = 2;
-- m; -- n;
while (m && n) {
if(pMe->Board[m-1][n-1] != p1){
if(pMe->Board[m-1][n-1] == p2) {
if(t1 == 3) t1 = 0;
else t1 = 1;
break;
}
else if(t1 == 3) {t1 = 0; break;}
else t1 = 3;
}
else t1 = 2;
-- m; -- n;
}
++ m; ++ n;
while (m < 16 && n < 16) {
if(pMe->Board[m-1][n-1] == p1){
s3 ++;
t2 = 2;
temp ++;
if(temp > ss) ss = temp;
}
else{
temp = 0;
if(pMe->Board[m-1][n-1] == p2) {
if(t2 == 3) t2 = 0;
else t2 = 1;
break;
}
else if(t2 == 3) {t2 = 0; blank --; break;}
else t2 = 3;
if(s3) blank ++;
}
if(m == 15 && t2 == 3 || n == 15 && t2 == 3){
blank --;
t2 = 0;
}
++ m; ++ n;
}
if(ss == 5 && tag == p1)
return Five;
s3 = SMark(s3, t1, t2, blank);
//左下至右上
m = i; n = j;
blank = 0;
temp = 0;
ss = 0;
t1 = t2 = 2;
++ m; -- n;
while (m < 16 && n) {
if(pMe->Board[m-1][n-1] != p1){
if(pMe->Board[m-1][n-1] == p2) {
if(t1 == 3) t1 = 0;
else t1 = 1;
break;
}
else if(t1 == 3) {t1 = 0; break;}
else t1 = 3;
}
else t1 = 2;
++ m; -- n;
}
-- m; ++ n;
while (m && n < 16) {
if(pMe->Board[m-1][n-1] == p1){
s4 ++;
t2 = 2;
temp ++;
if(temp > ss) ss = temp;
}
else{
temp = 0;
if(pMe->Board[m-1][n-1] == p2) {
if(t2 == 3) t2 = 0;
else t2 = 1;
break;
}
else if(t2 == 3) {t2 = 0; blank --; break;}
else t2 = 3;
if(s4) blank ++;
}
if(m == 1 && t2 == 3 || n == 15 && t2 == 3){
blank --;
t2 = 0;
}
-- m; ++ n;
}
if(ss == 5 && tag == p1)
return Five;
s4 = SMark(s4, t1, t2, blank);
return Mark(s1, s2, s3, s4, tag, pMe->First); //计算总得分
}
boolean MultiPlayer(Global *pMe){ //本地双人对战
//比较简单，根据上面的改的，本地双人对战功能的用处不大
char i, j;
int mark;
IIMAGE_Draw(pMe->pICB, 0, 0);
for(i = 0; i < 15; i++) //画出已经下了的子
for(j = 0; j < 15; j++){
if(pMe->Board[i][j] == Player1)
IIMAGE_Draw(pMe->pIBlack, 6 + i * 11, 6 + j * 11);
else if(pMe->Board[i][j] == Player2)
IIMAGE_Draw(pMe->pIWhite, 6 + i * 11, 6 + j * 11);
}
if(pMe->WinLose){
pMe->WinLose = None;
if(pMe->WinLose == Player1)
pMe->GameState = Player1Win;
else
pMe->GameState = Player2Win;
IDISPLAY_Update(pMe->a.m_pIDisplay);
return 1;
}
IIMAGE_Draw(pMe->pIBb, 6 + (pMe->x - 1) * 11, 6 + (pMe->y - 1) * 11);
//光标移动
if(pMe->KeyPress & K_up)
pMe->y --;
if(pMe->KeyPress & K_down)
pMe->y ++;
if(pMe->KeyPress & K_left)
pMe->x --;
if(pMe->KeyPress & K_right)
pMe->x ++;
pMe->KeyPress &= ~K_up;
pMe->KeyPress &= ~K_down;
pMe->KeyPress &= ~K_left;
pMe->KeyPress &= ~K_right;
//边界判断
if(pMe->x < 1)
pMe->x = 1;
else if(pMe-> x > 15)
pMe->x = 15;
if(pMe->y < 1)
pMe->y = 1;
else if(pMe-> y > 15)
pMe->y = 15;
if(pMe->KeyPress & K_Soft1){ //悔棋
pMe->KeyPress &= ~ K_Soft1;
DBGPRINTF("Cannot Undo While Multiplaying!!!");
}
if(pMe->KeyPress & K_Soft2){ //退出
pMe->KeyPress &= ~K_Soft2;
pMe->GameState = Menu;
pMe->timer = 0;
return 0;
}
if((pMe->KeyPress & K_Select) && pMe->Board[pMe->x - 1][pMe->y - 1] == None){
pMe->KeyPress &= ~K_Select;
if(pMe->who == Player1){
pMe->Board[pMe->x - 1][pMe->y - 1] = Player1;
mark = Search(pMe, pMe->x, pMe->y, Player1);
DBGPRINTF("PLAYER1: %d", mark);
if(mark <= Dead){
pMe->Board[pMe->x - 1][pMe->y - 1] = None;
pMe->GameState = Forbid;
pMe->LastState = Multi;
pMe->timer = 0;
return 0;
}
if(mark >= Five){
pMe->WinLose = Player1;
return 0;
}
pMe->who = Player2;
}
else if(pMe->who == Player2){
pMe->Board[pMe->x - 1][pMe->y - 1] = Player2;
mark = Search(pMe, pMe->x, pMe->y, Player2);
DBGPRINTF("PLAYER2: %d", mark);
if(mark <= Dead){
pMe->Board[pMe->x - 1][pMe->y - 1] = None;
pMe->GameState = Forbid;
pMe->LastState = Multi;
pMe->timer = 0;
return 0;
}
if(mark >= Five){
pMe->WinLose = Player2;
return 0;
}
pMe->who = Player1;
}
}
IDISPLAY_Update(pMe->a.m_pIDisplay);
return 1;
}
