一、实验目的
1.掌握极大极小算法,并能够独立求解。
2.深入了解零和博弈的原理以及思路
3.对于博弈算法有进一步的认识,深刻理解启发的含义。
二、实验内容与实验步骤
实验内容、原理分析
1ï¼ 给出数据结构或函数定义
(1)获取红色棋子的着法。输入参数为空
void getHumanMove()
在该函数中从键盘读取两个char类型的字符,然后将这两个字符分别转换为数字,如下
from=selection[0]-'0';
to=selection[1]-'0';
如果得到的数字符合行棋规范
if(from<=9&&from>=0&&to<=9&&to>=0)
if (putCell(from, to,RED) == -1)
break;
将得到的数字作为红棋的下一步走法,若不符合规范,则重新输入
(2)获取蓝色棋子的着法。输入参数为空
void getComputerMove()
该函数调用int evaluateComputerMove(int depth,int alpha,int bate)函数来进行蓝色棋子下一步走法的计算,蓝色棋子代表计算机。
在通过evaluateHumanMove函数计算得到 bestRootMove 之后,将 bestRootMove 的值通过以下语句进行在棋盘以及棋盘表的显示与更新。
piece=(bestRootMove&48)>>4;
from=stoneIntersection[piece];
to=bestRootMove&15;
putCell(from,to,piece);
(3)估算人/计算机的移动代价。该函数的参数为:当前深度,alpha与bate(剪枝使用的两个参数)
int evaluateHumanMove(int depth,int alpha,int bate);
int evaluateComputerMove(int depth,int alpha,int bate);
再进行数据的准备之后,首先生成当前层的着法列表:
pList[ply+1]=MoveGen(RED,pList[ply]);
然后,进行判断对方是否已经获胜,如果获胜则终止当前迭代层次,如果没有继续进行算法
逐层展开,在最大深度时在进行逐层向上返回值,最终找到最好的着点。
(4)主函数main:控制整个牛角棋算法流程。
在函数中,首先打印棋盘,然后调用 getHumanMove();,红棋先行,判断是否胜利,若胜利,则此时是因为红棋的行为引发了胜利的结果,由比赛规则知,为红棋胜利。若红色棋没有胜利,则调用函数 getComputerMove();,蓝色(电脑)行棋,判断是否有人胜利,若有则此时是因为蓝色棋的行为引发了胜利的结果,由比赛规则知,为蓝色棋胜利。当没有人胜利时,则循环:红棋走棋,判断,蓝棋走棋,判断这样的过程,直到有一方胜利。
2.用流程图表示出来程序设计的思想
如下图所示:
2ï¼ 给出具体实验步骤
(1)在实验的开始我首先研究了极大极小算法
(2)写出getComputerMove(),getHumanMove()函数
(3)写出算法核心函数int evaluateHumanMove(int depth,int alpha,int bate)和int evaluateComputerMove(int depth,int alpha,int bate)
(4)写出mian()主函数
(5)调试
(6)修改出现的问题
(7)完成
三、实验过程与分析
在试验的过程中,我主要遇到了以下比较难调试的问题,他们的出现原因、解决办法如下:
1 红色棋子不能步步紧逼,而是在保证不丧失优势的情况下,或维持现状或加大优势。
在如图所示的棋局中,B2棋子不能有效的马上从3-1,而是会3-5。这个问题经过排查,我发现是在value值得选取位置出现了问题:
if(value<=min)
min=value;
当把<=改为<时,以上问题就不存在了。在图示位置2-1乐意马上结束棋局;而2-4,2-5都可以维持原状。而我觉得这是因为,我们的代价分段不明显所致。当取<=时,value会取到最后一个符合的值,在预制表中,最后一个值代表的是同一位置可选的最差着点,这样,我们就会选到代价同为1/-1中优势薄弱的着点。将<=改为=后,每次选择的都是同为代价1/-1中优势最大的点,然而我们也可以用更清晰的代价分层来解决这个问题。(这个比较麻烦,但是不需要预制表中提前预置的顺序)
2 出现只有B1棋子可以移动,B2棋子不可以移动的现象。
这个问题困扰了我很久,后来发现是一个小小的笔误。我错误的在 evaluateHumanMove函数中展开了蓝色棋子的着法表,这样就是蓝色棋子一直在自我迭代了,而B1棋子标号排在B2前,这样value>max与value<min的判断中总是先走B1棋子。
åã实验结果总结
电脑是蓝色棋子,人是红色棋子。
红色棋子现行。实验结果如图:
äºã 创新的部分
Alpha与Bate剪枝:
使用极大极小算法可以有效的解决牛角棋的问题,但是计算机每走一步棋都要计算上万次,这样算下来空间,时间成本是十分高的,我们可以使用去掉完全不可能取到的分支进行算法的优化。这里我使用了Alpha和Bate剪枝来减少计算机的计算次数,从而提高效率。经过优化,计算机每次行棋计算的次数已经减少到几百次,小了一个数量级。
在算法的开始我设置alpha=-3(小于最小代价),bate=3(大于最大代价)。然后alpha每次在评估计算机着法的函数int evaluateComputerMove(int depth,int alpha,int bate)里将最大value赋予alpha当alpha大于bate时终止本次迭代,返回alpha。
if(value>alpha)
alpha=value;
if(alpha>=bate)
return alpha;
而bate每次在int evaluateHumanMove(int depth,int alpha,int bate)函数中取得value的最小值,当bate小于alpha时,返回bate。
经过这样处理就完成了alpha-bate剪枝过程。
å ã 对实验的意见与建议
经过这次实验我对极大极小算法有了深刻的理解,对算法的优化有了一定的探索,学会了使用alpha-bate剪枝的方法减少算法的时间复杂度与空间复杂度。双人博弈是一个非常有实用价值的问题,而零和博弈更是经典,如果我们能够运用好算法的思想,那么对我们今后问题的解决思想都是有很大帮助的。
七、代码部分
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHILD_NODES 9//结点书数
//color
#define RED 0 //红方的编号
#define BLUE 1 //蓝方的编号
//stone
#define REDSTONE 0 //红子的编号
#define BLUESTONE1 1 //蓝子1的编号
#define BLUESTONE2 2 //蓝子2的编号
#define INV -1
#define MAXDEPTH 10 //最大搜索深度
#define MAX_INFINITY 1
#define DRAW 0
#define MIN_INFINITY -1
#define INFINITEVAL 1000 //用于给bestRootMove初始化
int alpha;
int bate;
//对照上面的棋盘编码图,并参照牛角棋的规则,可有如下预置表
int preTable[2][10][5] =
{
{ /*red stone moves table*/
{2, 1, INV}, {2, 3, 0, INV},
{4, 3, 1, 0, INV}, {5, 4, 2, 1, INV},
{6, 5, 3, 2, INV}, {7, 6, 4, 3, INV},
{8, 7, 5, 4, INV}, {9, 8, 6, 5, INV},
{9, 7, 6, INV}, {8, 7, INV},
},
{ /*blue stone moves table*/
{INV}, {0, INV},
{3, 1, 0, INV}, {2, 1, INV},
{2, 3, 5, INV}, {3, 4, INV},
{4, 5, 7, INV}, {5, 6, INV},
{6, 7, 9, INV}, {7, 8, INV},
},
};
//初始棋盘
int stoneIntersection[3] = {0, 8, 9};
//着法列表
int moveList[1024];
//各层着法列表的首地址
int* pList[MAXDEPTH+2];
//当前的最大搜索深度
int maxDepth;
//最好的着法
int bestRootMove;
//电脑思考次数
int boards_checked;
/*
*************************************************************************
功能描述:将“着法”转化为用于显示的操作信息
参数: move 着法(6位整型表示,前四位存to信息,后三位存piece信息)
返回值: 用于显示的操作信息
*************************************************************************
*/
int getCell( int move)
{
int computer_move;
int piece, from, to;
piece = (move & 48) >> 4;
from = stoneIntersection[piece];
to = move & 15;
computer_move = from*10+to;
return computer_move;
}
/*
*************************************************************************
功能描述:检查操作合法性,并将“着法”更新到棋盘数组中
参数: from , to, wtm:轮到谁走棋
返回值: 是否合法,不合法返回1
*************************************************************************
*/
int putCell(int from, int to, int wtm)
{
int i;
int rVal = 1;
//非法着法,返回继续等待输入的状态
if((from < 0) || (from > 9))
return 1;
if((to < 0) || (to > 9))
return 1;
if( RED == wtm &&
(from != stoneIntersection[REDSTONE] ||
to == stoneIntersection[BLUESTONE1] ||
to == stoneIntersection[BLUESTONE2] ))
return 1;
else if(BLUE == wtm &&
((from != stoneIntersection[BLUESTONE1] &&
from != stoneIntersection[BLUESTONE2])
|| to == stoneIntersection[REDSTONE]
|| to == stoneIntersection[BLUESTONE1]
|| to == stoneIntersection[BLUESTONE2]))
return 1;
if(2 < abs(from - to))
return 1;
//合法着法
for(i = 0; i < 3; ++i)
{
if(from == stoneIntersection[i])
{
stoneIntersection[i] = to;
rVal = -1;
}
}
return rVal;
}
/*
*************************************************************************
功能描述:输出棋盘
参数: si[] 当前棋盘局面
返回值: 无
*************************************************************************
*/
void emitBoard( int is[ ] )
{
char board[10][4] = {
"0 ","1 ","2 ","3 ","4 ",
"5 ","6 ","7 ","8 ","9 ",
};
memcpy(board[is[0]], "R*", 2);
memcpy(board[is[1]], "B1", 2);
memcpy(board[is[2]], "B2", 2);
printf(" \n");
printf(" %s\n",board[0]);
printf(" ∣﹨\n");
printf(" ∣ %s\n",board[1]);
printf(" ∣/ ﹨\n");
printf(" %s—— %s\n", board[2], board[3]);
printf(" ∣ /∣\n");
printf(" ∣/ ∣\n");
printf(" %s—— %s\n", board[4], board[5]);
printf(" ∣ /∣\n");
printf(" ∣/ ∣\n");
printf(" %s—— %s\n", board[6], board[7]);
printf(" ∣ /∣\n");
printf(" ∣/ ∣\n");
printf(" %s—— %s\n", board[8], board[9]);
printf("\n");
return;
}
/*
*************************************************************************
着法列表中的move格式如下:
含义: |piece| to |
6 bit: | 5 4 | 3 2 1 0|
*************************************************************************
功能描述:调用MoveGen()产生一个着法列表。在[addr1,addr2-1]之间的着法,构成当前局
面的着法列表。其中,addr1是第ply层着法列表的首地址;addr2是第ply+1层着法列表的首
地址。
参数: color:是红方,还是蓝方;mList:着法列表起始地址addr1。
返回值: 着法列表的结束地址addr2。
*************************************************************************
*/
int* MoveGen(int color, int *mList)
{
int i = 0;
int from;
int to;
int count = 0;
#ifdef _DEBUG
int ok = 1;
int *p = mList;
#endif
if (color == RED) /*red move gen*/
{
from = stoneIntersection[REDSTONE];
to = preTable[color][from][i];
while (to != INV)
{
if((to != stoneIntersection[BLUESTONE1])
&& (to != stoneIntersection[BLUESTONE2]))
{
mList[count++] = to;
}
to = preTable[color][from][++i];
}
}
else /*blue move gen*/
{
//blue stone1
from = stoneIntersection[BLUESTONE1];
to = preTable[color][from][i];
while (to != INV)
{
if ((to != stoneIntersection[REDSTONE])
&& (to != stoneIntersection[BLUESTONE2]))
{
mList[count++] = to|16;
}
to = preTable[color][from][++i];
}
//blue stone2
i = 0;
from = stoneIntersection[BLUESTONE2];
to = preTable[color][from][i];
while (to != INV)
{
if ((to != stoneIntersection[REDSTONE])
&& (to != stoneIntersection[BLUESTONE1]))
{
mList[count++] = to|32;
}
to = preTable[color][from][++i];
}
}
#ifdef _DEBUG //检查着法列表是否包含了非法着法
for(; p < mList[count]; ++p)
{
if((0 <= (*p)&15) && (((*p)&15) <= 9))
ok = 0;
}
assert(ok);
#endif
return &mList[count];
}
/*
*************************************************************************
功能描述:检查是否获胜
参数: wtm:待评估方;si:待估局面。
返回值: 局面的估值(如wtm为RED,如果红胜,则返回1)。
*************************************************************************
*/
int checkPlayerWin( int wtm, int *si )
{
if((si[RED] == 8) || (si[RED] == 9))
//红胜
{
return ((wtm==RED) ? 1 : -1);
}
else if ((si[RED] == 0) && //红子被逼死在牛角尖上
((si[BLUESTONE1] + si[BLUESTONE2]) == 3))
//红负
{
return ((wtm==RED) ? -1 : 1);
}
return 0;
}
/*
*************************************************************************
功能描述:为局面打分。
参数: wtm:待评估方;si:待估局面
返回值: 局面的估值(如wtm为RED,如果局面对红子有利,则返回1)。
*************************************************************************
*/
int Evaluation(int wtm, int *si)
{
int value = 0;
#ifdef _DEBUG //局面合法性检查
int good = 1;
if(stoneIntersection[REDSTONE] ==
stoneIntersection[BLUESTONE1])
good = 0;
if(stoneIntersection[REDSTONE] ==
stoneIntersection[BLUESTONE2])
good = 0;
if(stoneIntersection[BLUESTONE1] ==
stoneIntersection[BLUESTONE2])
good = 0;
assert(good);
#endif
if ((si[RED] > si[BLUESTONE1]) || //红子成功突围
(si[RED] > si[BLUESTONE2]))
//红胜
{
value = ((wtm==RED) ?
MAX_INFINITY : MIN_INFINITY);
}
else if (
(wtm == RED) && //评估红色,则下一步该蓝子走棋,且红子和两个蓝子构成三角
((stoneIntersection[BLUESTONE1] == si[RED] + 1 ) &&
(stoneIntersection[BLUESTONE2] == si[RED] + 2 ) ||
(stoneIntersection[BLUESTONE1] == si[RED] + 2 ) &&
(stoneIntersection[BLUESTONE2] == si[RED] + 1 ))
)
//红胜
{
value = MAX_INFINITY;
}
else if (
(wtm == BLUE) && //评估蓝色,则下一步该红子走棋,且红子和蓝子构成三角
((1 == si[REDSTONE] || 2 == si[REDSTONE] || 3 == si[REDSTONE]) &&
((stoneIntersection[BLUESTONE1] == si[RED] + 1 ) &&
(stoneIntersection[BLUESTONE2] == si[RED] + 2 ) ||
(stoneIntersection[BLUESTONE1] == si[RED] + 2 ) &&
(stoneIntersection[BLUESTONE2] == si[RED] + 1 )))
)
//蓝胜
{
value = MAX_INFINITY;
}
return value;
}
//生成新局面
int MakeMove(int piece, int to)
{
int tmp = stoneIntersection[piece];
#ifdef _DEBUG
//合法性检查
int i = 0;
assert((0 <= (to&15)) && ((to&15) <= 9));
for(i = 0; i < 3; ++i)
assert(to ==stoneIntersection[i]);
#endif
stoneIntersection[piece] = to;
return tmp;
}
//撤销局面
void UnmakeMove(int piece, int from)
{
#ifdef _DEBUG
assert((0 <= (from&15)) && ((from&15) <= 9));
#endif
stoneIntersection[piece] = from;
}
//获得电脑的着法
void getComputerMove()
{
//1 to do
boards_checked = 0;
evaluateComputerMove(maxDepth,-3,3);
printf("Blue's move is %d (%d boards checked)\n", getCell(bestRootMove), boards_checked);
int piece,from,to;
piece=(bestRootMove&48)>>4;
//printf("%d",piece);
from=stoneIntersection[piece];
to=bestRootMove&15;
putCell(from,to,piece);
emitBoard(stoneIntersection);
return;
}
//获取玩家的着法
void getHumanMove()//没有问题
{
//2to do
char selection[200];
/* Get human move */
while (1) {//直到输入正确为止
printf("Scanf a piece please(from+to)");
scanf("%s", &selection);
printf("\n");
int piece,from,to;
from=selection[0]-'0';
to=selection[1]-'0';
if(from<=9&&from>=0&&to<=9&&to>=0)
if (putCell(from, to,RED) == -1) break;
printf("cell taken -- choose again.\n");
}
emitBoard(stoneIntersection);
return;
}
//评估玩家着法
int evaluateHumanMove(int depth,int alpha,int bate)
{
int move;
int piece;
int from;
int ply=maxDepth-depth;
int *pMove=pList[ply];
int value;
boards_checked++;
short min = MAX_INFINITY+1;
pList[ply+1]=MoveGen(RED,pList[ply]);//生成着法列表
if(checkPlayerWin(BLUE,stoneIntersection)==1)//检查红色是不是已经赢了,如果人类赢了则停止
return MAX_INFINITY;
if(pList[ply]==pList[ply+1]//看当前层是否有不同的棋局走法
||depth==0)
{
return Evaluation(BLUE,stoneIntersection);
}
for(;pMove<pList[ply+1];++pMove)
{
move=*pMove;
piece=move>>4;
from=MakeMove(piece,move&15);
value=evaluateComputerMove(depth-1,alpha,bate);
UnmakeMove(piece,from);
if(value<min)
{
min=value;
// if(!ply)
// {
// bestRootMove=move;
// }
}
/*****************************进一步拓展部分*****************************************/
/*****************************alpha-bate剪枝*****************************************/
if(value<bate)
bate=value;
if(bate<=alpha)
return bate;
}
if (min == MAX_INFINITY+1) {
return DRAW;
}
return min;
}
//评估电脑着法
int evaluateComputerMove(int depth,int alpha,int bate)
{
int move;//着法
int piece;//代表棋子
int from;//原来的位置
int ply=maxDepth-depth;
int *pMove=pList[ply];
int value;//估值
boards_checked++;
short max=MIN_INFINITY-1;
pList[ply+1]=MoveGen(BLUE,pList[ply]);//生成着法列表
if(checkPlayerWin(RED,stoneIntersection)==1)//检查红色是不是已经赢了,如果人类赢了则停止
return MIN_INFINITY;
if(pList[ply]==pList[ply+1]||depth==0)//看当前层是否有不同的棋局走法
{
return -Evaluation(RED,stoneIntersection);
}
for(;pMove<pList[ply+1];++pMove)
{
move=*pMove;
piece=move>>4;
// printf("%d",piece);
from=MakeMove(piece,move&15);
value=evaluateHumanMove(depth-1,alpha,bate);
UnmakeMove(piece,from);
if(value>max)
{
max=value;
if(!ply)
{
bestRootMove=move;
}
}
/*****************************进一步拓展部分*****************************************/
/*****************************alpha-bate剪枝*****************************************/
if(value>alpha)
alpha=value;
if(alpha>=bate)
return alpha;
}
if (max == MIN_INFINITY-1) {
return DRAW;
}
//4to do
return max;
}
int main()
{
bestRootMove=INFINITEVAL;
maxDepth=MAXDEPTH;
pList[0]=moveList;
int won = 0;
emitBoard(stoneIntersection);
while (!won) {
getHumanMove();
won = checkPlayerWin( RED, stoneIntersection);
//moves++;
if (!won)
{
won=0;
/* Build the game tree */
getComputerMove();
won = checkPlayerWin( BLUE, stoneIntersection);
if (won)
{
printf("\nYou lose!\n");
}
}
else
{
printf("\nYou win!\n");
}
}
emitBoard( stoneIntersection );
//5
return 0;
}