一、实验目的
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;
}
