使用极大极小算法实现牛角棋

一、实验目的

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)估算人/计算机的移动代价。该函数的参数为:当前深度,alphabate(剪枝使用的两个参数)

             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-42-5都可以维持原状。而我觉得这是因为,我们的代价分段不明显所致。当取<=时,value会取到最后一个符合的值,在预制表中,最后一个值代表的是同一位置可选的最差着点,这样,我们就会选到代价同为1/-1中优势薄弱的着点。将<=改为=后,每次选择的都是同为代价1/-1中优势最大的点,然而我们也可以用更清晰的代价分层来解决这个问题。(这个比较麻烦,但是不需要预制表中提前预置的顺序)

      使用极大极小算法实现牛角棋

     2 出现只有B1棋子可以移动,B2棋子不可以移动的现象。

这个问题困扰了我很久,后来发现是一个小小的笔误。我错误的在 evaluateHumanMove函数中展开了蓝色棋子的着法表,这样就是蓝色棋子一直在自我迭代了,而B1棋子标号排在B2前,这样value>maxvalue<min的判断中总是先走B1棋子。 

四、实验结果总结

      电脑是蓝色棋子,人是红色棋子。

红色棋子现行。实验结果如图:

   使用极大极小算法实现牛角棋

 

          使用极大极小算法实现牛角棋

五、 创新的部分

   AlphaBate剪枝:

使用极大极小算法可以有效的解决牛角棋的问题,但是计算机每走一步棋都要计算上万次,这样算下来空间,时间成本是十分高的,我们可以使用去掉完全不可能取到的分支进行算法的优化。这里我使用了AlphaBate剪枝来减少计算机的计算次数,从而提高效率。经过优化,计算机每次行棋计算的次数已经减少到几百次,小了一个数量级。

在算法的开始我设置alpha=-3(小于最小代价),bate=3(大于最大代价)。然后alpha每次在评估计算机着法的函数int evaluateComputerMove(int depth,int alpha,int bate)里将最大value赋予alphaalpha大于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;

}




 

上一篇:KMeans算法的Mapreduce实现


下一篇:CDN百科第八期 | 我的网站到底需不需要CDN加速?