博弈大赛赛前培训_六棋子程序的实现

LOGO六子棋博弈程序唐志峰计算机博弈与人工智能协会计算机博弈与人工智能计算机博弈与人工智能本次大赛通信协议博弈程序整体设计思路博弈程序核心模块机器博弈交互平台本次大赛的一些相关说明讲解要点计算机博弈与人工智能机器博弈交互平台裁判系统棋盘黑方程序白方程序1112334556计算机博弈与人工智能本次大赛通信协议接受裁判系统信息：scanf(%s,Msg);传回裁判系统信息：printf(%s,Move);1.确定队名：name?“传回队名：nameBitStronger\n“2.开局：new3.确定黑白方：黑方：black白方：white4.发送、接收招法//先横向坐标，后纵向坐标黑方第一步：moveX0Y0其他步数：moveX0Y0X1Y1计算机博弈与人工智能博弈程序整体设计思路实际问题数学建模算法编程、调试得到结果计算机博弈与人工智能棋盘表示六子棋棋盘由19条横线和19条纵线组成。棋盘一共有19*19=361个交点。交点出现的可能情况：无子、黑子、白子棋盘：charposition[19][19];棋子：黑棋（BLACK）：0白棋（WHITE）：1无子（NOSTONE）：0xff示例代码宏定义：#defineGRID_NUM19//棋盘行数#defineGRID_COUNT361//可放棋子总数#defineBLACK0//黑棋#defineWHITE1//白棋#defineNOSTONE0xff//无棋全局变量：BYTEposition[GRID_NUM][GRID_NUM];//棋盘STONEMOVEm_cmBestMove;//记录着法注:#includewindows.htypedefunsignedcharBYTE计算机博弈与人工智能示例代码结构定义：//棋子位置typedefstruct_stoneposition{BYTEx;BYTEy;}STONEPOS;//走法typedefstruct_stonemove{STONEPOSStonePos[2];//棋子位置intScore;//走法的分数}STONEMOVE;计算机博弈与人工智能示例代码主函数，程序的入口voidmain(){intChessmanType;//记录棋子颜色charMsg[500];//保存接收到的消息charname[]=“name中国深度\n;//队伍信息charMove[]=moveAABB\n;//走法intx0,x1,y0,y1;//坐标//初始化棋盘memset(position,NOSTONE,GRID_COUNT);计算机博弈与人工智能示例代码while(1){//循环接收裁判平台发送的消息，注意需要发送的字符串应该//以'\n'结束，裁判平台才会认为是一次完整的输入.//发送完需要调用fflush(stdout)清空输出缓冲区，使字符串//立刻输出到裁判平台memset(Msg,0,500);scanf(%s,Msg);if(strcmp(Msg,name?)==0){printf(%s,name);fflush(stdout);continue;}计算机博弈与人工智能示例代码if(strcmp(Msg,“new”)==0)//新开局{memset(position,NOSTONE,GRID_COUNT);//初始化棋盘scanf(%s,Msg);if(strcmp(Msg,“black”)==0)//确定我方棋子的颜色{Sleep(50);//延迟一段时间发送，经测试，立即发送可//能造成平台无响应printf(moveJJ\n);position[9][9]=BLACK;fflush(stdout);ChessmanType=BLACK;continue;}计算机博弈与人工智能示例代码else//if(strcmp(Msg,“white”)==0){ChessmanType=WHITE;continue;}}//确定棋型颜色结束if(strcmp(Msg,move)==0){//接收对方的招法scanf(%s,Msg);计算机博弈与人工智能示例代码if(Msg[2]==‘\0’)//接收黑方的第一着{//moveXX\ny0=(int)(Msg[0])-(int)('A');x0=(int)('S')-(int)(Msg[1]);position[x0][y0]=!ChessmanType;}计算机博弈与人工智能示例代码else//接收对方的招法，一般招法都是一着下两个子{//moveXYXY\ny0=(int)(Msg[0])-(int)('A');x0=(int)('S')-(int)(Msg[1]);y1=(int)(Msg[2])-(int)('A');x1=(int)('S')-(int)(Msg[3]);position[x0][y0]=!ChessmanType;position[x1][y1]=!ChessmanType;}计算机博弈与人工智能示例代码if(SearchAGoodMove(position,ChessmanType)){//获得着法的坐标x0=m_cmBestMove.StonePos[0].x;y0=m_cmBestMove.StonePos[0].y;x1=m_cmBestMove.StonePos[1].x;y1=m_cmBestMove.StonePos[1].y;//将着法记录在棋盘中position[x0][y0]=ChessmanType;position[x1][y1]=ChessmanType;计算机博弈与人工智能示例代码//将着法转换成要发送的字符形式y0=(char)((int)('A')+y0);x0=(char)((int)('S')-x0);y1=(char)((int)('A')+y1);x1=(char)((int)('S')-x1);//Move[]=moveAABB\n//修改AABB并发送Move[5]=y0;Move[6]=x0;Move[7]=y1;Move[8]=x1;printf(%s,Move);fflush(stdout);计算机博弈与人工智能计算机博弈与人工智能机器博弈交互平台裁判系统棋盘黑方程序白方程序1112334556计算机博弈的设计思路SearchAGoodMove(position,ChessmanType)如何根据已有的棋盘局面和我方子的颜色，来得到我方下一步将要走的招法。计算机博弈与人工智能穷举法穷举出下一步所有可能的招法，形成不同的局面。比较一下这些局面，选取出其中最好的（对我方最有利）局面，则形成此局面对应的招法就是我方下一步“最佳”的走法。所有可能的招法：招法生成比较：评估函数选取、最好的：搜索函数（极大极小值搜索）最佳：此时对应的招法真的是最好的招法吗？计算机博弈与人工智能计算机博弈与人工智能博弈程序核心模块搜索函数招法生成评估函数AI引擎招法生成招法生成：生成一个局面的所有可能招法（合法招法）。例如：象棋中的，象走田，马走日，兵可进不可退。六子棋的合法招法：任意空格点。思考：是不是所有招法都是我们需要考虑的？可不可以舍弃一些招法？速度与准确性的矛盾。计算机博弈与人工智能评估函数评估函数：用以评价一个局面的好坏。计算机如何知道一个局面的好坏？局面的好坏实数思路：根据局面中的各方棋型，来具体分析局面好坏，给出各局面的分值。难点：1.查找棋型，保证速度与准确性。2.如何根据棋型给分值，分值如何确定。计算机博弈与人工智能六子棋的棋型长连：在棋盘的纵向、横向或斜向的任意一条线上，形成的7颗或7颗以上同色棋子不间隔地相连。六连：在棋盘的纵向、横向或斜向的任意一条线上，形成的6颗同色棋子不间隔地相连。长连和六连是规定时间内获胜的必要条件。计算机博弈与人工智能六子棋的棋型活五：在同一直线上的5颗同色棋子，符合“对方必须用两手棋才能挡住”的条件。“挡住”是指不让另一方形成六连或长连。计算机博弈与人工智能六子棋的棋型眠五：在同一直线上的5颗同色棋子，符合“对方用用一手棋才能挡住”的条件。计算机博弈与人工智能六子棋的棋型活四：在同一直线上的4颗同色棋子，符合“对方必须用两手棋才能挡住”的条件。计算机博弈与人工智能六子棋的棋型眠四：在同一直线上的4颗同色棋子，符合“对方用用一手棋才能挡住”的条件。计算机博弈与人工智能六子棋的棋型活三：在同一直线上的3颗同色棋子，符合“再下一手就能形成活四”的条件。计算机博弈与人工智能六子棋的棋型眠三：在同一直线上的3颗同色棋子，符合“再下两手棋也只能形成眠四”的条件。计算机博弈与人工智能六子棋的棋型活二：在同一直线上的2颗同色棋子，符合“再下两手棋就能形成活四”的条件。计算机博弈与人工智能六子棋的棋型眠二：在同一直线上的2颗同色棋子，符合“再下两手棋只能形成眠四”的条件。计算机博弈与人工智能搜索函数下一个最好的（评估分值最高）局面的对应的招法就是最佳招法吗？棋类高手都能看很多步！当我方生成各种局面后，对方针对我方形成的每一种局面又同样会生成许多局面，我方再针对对方形成的每一种局面同样又会生成许多对应局面，这样循环往复，就形成了一个颗博弈树。计算机博弈与人工智能博弈树计算机博弈与人工智能博弈树一棵多叉树。六子棋博弈树的复杂度很高。每个局面对应招法开始：360*359=129240结束（设50步之后）：310*309=95790设平均取105个节点。1层：1052层：105*105=10103层：1010*1010=1020……节点数随深度的增加以爆炸式方式增长博弈树提高时间效率一般一步能控制在半分钟内为宜。方法：减小博弈树的规模：1.降低搜索深度，但棋力提高有限。2.每个局面对应只生成少许有价值的节点，可能有漏选。运用高效的搜索算法，例如：α-β剪枝。提高各模块的效率，尤其是评估函数的效率。计算机博弈与人工智能极大极小值搜索建立了博弈树，我们怎样找到我们需要的招法？搜索与回溯方式：因为：局面分值越高，对我方越有利，对于