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

1、六子棋博弈程序计算机博弈与人工智能协会 计算机博弈与人工智能1 本次大赛通信协议博弈程序整体设计思路 博弈程序核心模块 机器博弈交互平台本次大赛的一些相关说明讲解要点2机器博弈交互平台裁判系统棋盘黑方程序白方程序11123345563本次大赛通信协议接受裁判系统信息：scanf(%s,Msg);传回裁判系统信息：printf(%s,Move);1.确定队名：name?“ 传回队名： name BitStrongern“2.开局：new3.确定黑白方： 黑方：black 白方：white4.发送、接收招法 /先横向坐标，后纵向坐标 黑方第一步：move X0Y0 其他步数：move X0Y0X1

2、Y1 4博弈程序整体设计思路 实际问题数学建模算法编程、调试得到结果5棋盘表示 六子棋棋盘由19条横线和19条纵线组成。棋盘一共有19*19=361个交点。交点出现的可能情况：无子、黑子、白子棋盘：char position1919;棋子： 黑棋（BLACK）：0 白棋（WHITE）：1 无子（NOSTONE）：0 xff6示例代码宏定义：#define GRID_NUM 19 /棋盘行数#define GRID_COUNT 361 /可放棋子总数#define BLACK 0 /黑棋#define WHITE 1 /白棋#define NOSTONE 0 xff /无棋全局变量：BYTE p

3、osition GRID_NUMGRID_NUM;/棋盘STONEMOVE m_cmBestMove; /记录着法注: #include windows.h typedef unsigned char BYTE 7示例代码结构定义：/棋子位置typedef struct _stonepositionBYTE x;BYTE y;STONEPOS;/走法typedef struct _stonemoveSTONEPOS StonePos2; /棋子位置int Score;/走法的分数STONEMOVE;8示例代码主函数，程序的入口void main()int ChessmanType; /记录棋子

4、颜色char Msg500; /保存接收到的消息char name = “name 中国深度n; /队伍信息char Move = move AABBn; /走法int x0,x1,y0,y1;/坐标 /初始化棋盘memset ( position, NOSTONE, GRID_COUNT); 9示例代码while (1)/循环接收裁判平台发送的消息，注意需要发送的字符串应该/以n结束，裁判平台才会认为是一次完整的输入./发送完需要调用fflush(stdout)清空输出缓冲区，使字符串/立刻输出到裁判平台memset(Msg,0,500);scanf(%s,Msg);if (strcmp(M

5、sg,name?) = 0) printf(%s,name); fflush(stdout); continue;10示例代码if (strcmp(Msg,“new”) = 0) /新开局memset(position,NOSTONE,GRID_COUNT); /初始化棋盘scanf(%s,Msg);if (strcmp(Msg,“black”) = 0) /确定我方棋子的颜色 Sleep(50); /延迟一段时间发送，经测试，立即发送可/能造成平台无响应 printf(move JJn); position99 = BLACK; fflush(stdout); ChessmanType =

6、BLACK; continue;11示例代码 else / if (strcmp(Msg,“white”) = 0) ChessmanType = WHITE; continue; /确定棋型颜色结束if (strcmp(Msg,move) = 0) /接收对方的招法scanf(%s,Msg); 12示例代码 if (Msg2 = 0) /接收黑方的第一着/move XXny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1); positionx0y0 = !ChessmanType;13示例代码else/接收对方的招法，一般招法都是一

7、着下两个子 /move XYXYny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1);y1 = (int)(Msg2) - (int)(A);x1 = (int)(S) - (int)(Msg3);positionx0y0 = !ChessmanType;positionx1y1 = !ChessmanType;14示例代码if (SearchAGoodMove(position,ChessmanType) /获得着法的坐标x0 = m_cmBestMove.StonePos0.x;y0 = m_cmBestMove.StonePos

8、0.y;x1 = m_cmBestMove.StonePos1.x;y1 = m_cmBestMove.StonePos1.y; /将着法记录在棋盘中positionx0y0 = ChessmanType;positionx1y1 = ChessmanType;15示例代码/将着法转换成要发送的字符形式y0 = (char)(int)(A) + y0);x0 = (char)(int)(S) - x0);y1 = (char)(int)(A) + y1);x1 = (char)(int)(S) - x1);/Move = move AABBn/修改AABB 并发送Move5 = y0;Move

9、6 = x0;Move7 = y1;Move8 = x1;printf(%s,Move);fflush(stdout);16机器博弈交互平台裁判系统棋盘黑方程序白方程序111233455617计算机博弈的设计思路SearchAGoodMove(position,ChessmanType)如何根据已有的棋盘局面和我方子的颜色，来得到我方下一步将要走的招法。？18穷举法穷举出下一步所有可能的招法，形成不同的局面。比较一下这些局面，选取出其中最好的（对我方最有利）局面，则形成此局面对应的招法就是我方下一步“最佳”的走法。所有可能的招法：招法生成 比较：评估函数 选取、最好的：搜索函数（极大极小值搜索

10、）最佳：此时对应的招法真的是最好的招法吗？19博弈程序核心模块搜索函数招法生成评估函数AI引擎20招法生成招法生成：生成一个局面的所有可能招法（合法招法）。例如：象棋中的，象走田，马走日，兵可进不可退。六子棋的合法招法：任意空格点。思考：是不是所有招法都是我们需要考虑的？可不可以舍弃一些招法？速度与准确性的矛盾。21评估函数评估函数：用以评价一个局面的好坏。计算机如何知道一个局面的好坏？局面的好坏 实数思路：根据局面中的各方棋型，来具体分析局面好坏，给出各局面的分值。难点：1.查找棋型，保证速度与准确性。 2.如何根据棋型给分值，分值如何确定。22六子棋的棋型长连：在棋盘的纵向、横向或斜向的任

11、意一条线上，形 成的7颗或7颗以上同色棋子不间隔地相连。六连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的6颗同色棋子不间隔地相连。长连和六连是规定时间内获胜的必要条件。23六子棋的棋型活五：在同一直线上的5颗同色棋子，符合“对方必须 用两手棋才能挡住”的条件。“挡住”是指不让 另一方形成六连或长连。24六子棋的棋型眠五：在同一直线上的5颗同色棋子，符合“对方用 用一手棋才能挡住”的条件。25六子棋的棋型活四：在同一直线上的4颗同色棋子，符合“对方必须 用两手棋才能挡住”的条件。26六子棋的棋型眠四：在同一直线上的4颗同色棋子，符合“对方用 用一手棋才能挡住”的条件。27六子棋的棋型活三：

12、在同一直线上的3颗同色棋子，符合“再下一手 就能形成活四”的条件。28六子棋的棋型眠三：在同一直线上的3颗同色棋子，符合“再下两手 棋也只能形成眠四”的条件。29六子棋的棋型活二：在同一直线上的2颗同色棋子，符合“再下两手 棋就能形成活四”的条件。30六子棋的棋型眠二：在同一直线上的2颗同色棋子，符合“再下两手 棋只能形成眠四”的条件。31搜索函数下一个最好的（评估分值最高）局面的对应的招法就是最佳招法吗？棋类高手都能看很多步！当我方生成各种局面后，对方针对我方形成的每一种局面又同样会生成许多局面，我方再针对对方形成的每一种局面同样又会生成许多对应局面，这样循环往复，就形成了一个颗博弈树。32

13、博弈树博弈树一棵多叉树。六子棋博弈树的复杂度很高。每个局面对应招法 开始： 360*359=129240 结束（设50步之后）：310*309=95790设平均取105 个节点。1层： 1052层： 105 * 105 = 10103层： 1010 * 1010 = 1020 节点数随深度的增加以爆炸式方式增长33博弈树提高时间效率一般一步能控制在半分钟内为宜。方法：减小博弈树的规模： 1.降低搜索深度，但棋力提高有限。 2.每个局面对应只生成少许有价值的节点， 可能有漏选。运用高效的搜索算法，例如：-剪枝。提高各模块的效率，尤其是评估函数的效率。34极大极小值搜索建立了博弈树，我们怎样找到我们需要的招法？搜索与回溯方式：因为：局面分值越高，对我方越有利，对于对方越不利。局面分值越低，对我方越不利，也就是对于对方越有利。所以：轮到我方走时，我方会选择使下一步局面分值最高的走法。此节点（局面）分值 = MAX所有子节点分值轮到对方走时，对方会选择使下一步局面分值最低的走法。此节点（局面）分值 = MIN所以子节点分值35极大极小值搜索局面（取极大值）局面（取极小值）RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3De