博弈树

alpha & beta剪枝算法实现一字棋

剪枝算法首先就是要理解，把这个算法彻底弄清楚，我觉得这是一件非常有意义的事情！为后续书写其它棋类的AI打下了坚实的基础

剪枝操作的实现，遍历下一步所有可能取到的点，找出评估值最大的那一步就是我们下一步所需要的做的。
剪枝算法

int Tree::alphaBeta(int &value,int deep,bool MAX){if(isWin()==1){value=10000;return 0;}//递归的终点if(deep+this->count==9){return this->evaluate();}//一开始不剪枝bool prune=false;int temp,flag;//max结点我开始落子，电脑希望flag越大越好if(MAX)flag=10000;//min结点电脑开始落子，我希望flag越小越好elseflag=-10000;for(int i=0;i<NUM && !prune;i++){for(int j=0;j<NUM && !prune;j++){//找出一个空位置下棋if(this->s[i][j]==' '){//如果当前结点是max结点,下一步是我下棋if(MAX){this->s[i][j]='X';//如果我下这一步我赢了，是电脑最不希望看到的，直接值取-100if(this->isWin()==-1)temp=-10000;elsetemp=this->alphaBeta(flag,deep+1,!MAX);if(temp<flag)	flag=temp;//如果我下棋让评分变的低了，电脑完全没必要走这一步，剪枝if(flag<=value) prune=true;}//min结点电脑开始下棋else{this->s[i][j]='O';//如果这一步对于电脑来说直接取得胜利，对于机器来说是十分想看到的if(this->isWin()==1)temp=10000;elsetemp=this->alphaBeta(flag,deep+1,!MAX);//我们希望的flag小于实际的评分，此时flag应该更新if(temp>flag)	flag=temp;//此时对于我来说是十分不利的，我不可能走这一步让电脑获取胜利，我这一步应该被剪枝//或结点的alpha值不能降低其父结点的beta值，剪枝if(flag>=value) prune=true;}this->s[i][j]=' ';}}}//max（或）结点的扩展要是能提高value值if(MAX){if(flag>value)value=flag;}//min（与）结点的扩展要是能降低value值else{if(flag<value)value=flag;}return flag;
}

剪枝算法是一字棋程序中的核心部分，此外还需要定义一个棋类，用于初始化和实现下棋操作
棋类部分代码以及所有函数和变量

class Chess{
private:char a[3][3];		//棋盘的状态int count;          //已经下棋的步数
public:std::string computer,player;        //电脑与玩家int x,y;            				//下棋的位置std::string str,winner;       		//当前落子的对象void initial();     				//初始化函数void getMove();     				//获取走棋的位置bool makeMove(int,int,std::string);	//走棋函数void showStatus();  				//展示棋盘当前的状态bool isGameOver();  				//判断游戏是否结束void getStatus(char[][3]);          //获取当前的状态int getCount();                     //获取当前已经走棋的步数
};
void Chess::initial(){this->computer="Computer";this->player="Player";this->winner=" ";this->count=0;this->str=this->player;for(int i=0;i<NUM;i++){for(int j=0;j<NUM;j++){this->a[i][j]=' ';}}
}

主函数部分

	Onechess.initial();while(!Onechess.isGameOver() && Onechess.getCount()!=9){Onechess.showStatus();if(Onechess.str==Onechess.player){Onechess.getMove();Onechess.makeMove(Onechess.x,Onechess.y,Onechess.str);}else{tree.getChessStatus(Onechess);//不断的去试探，找出一个最大的value的值的走法for(int i=0;i<NUM;i++){for(int j=0;j<NUM;j++){if(tree.s[i][j]==' '){tree.s[i][j]='O';tree.alphaBeta(value,deep,1);if(value>temp){temp=value;row=i;column=j;}tree.s[i][j]=' ';}}}value=-10000;temp=-10000;Onechess.makeMove(row+1,column+1,Onechess.str);}printf("\n**************");}Onechess.showStatus();//并没有分出胜负，但是下棋的步数已经到达了9步，此时判定平局if(!Onechess.isGameOver() && Onechess.getCount()==9){printf("There are no winner! Is Draw!!!");}elseprintf("The winner is %s,let's congratulate!",Onechess.winner.c_str());