《{企业通用培训}博弈大赛赛前培训六棋子程序的实现》由会员分享，可在线阅读，更多相关《{企业通用培训}博弈大赛赛前培训六棋子程序的实现（39页珍藏版）》请在金锄头文库上搜索。
1、六子棋博弈程序,唐志峰 计算机博弈与人工智能协会,计算机博弈与人工智能,计算机博弈与人工智能,本次大赛通信协议,博弈程序整体设计思路,博弈程序核心模块,机器博弈交互平台,本次大赛的一些相关说明,讲解要点,计算机博弈与人工智能,机器博弈交互平台,棋盘,黑方程序,白方程序,1,1,1,2,3,3,4,5,5,6,计算机博弈与人工智能,本次大赛通信协议,接受裁判系统信息：scanf(%s,Msg); 传回裁判系统信息：printf(%s,Move); 1.确定队名：name?“ 传回队名： name BitStrongern“ 2.开局：new 3.确定黑白方： 黑方：black 白方：white
2、4.发送、接收招法 /先横向坐标，后纵向坐标 黑方第一步：move X0Y0 其他步数：move X0Y0X1Y1,计算机博弈与人工智能,博弈程序整体设计思路,实际问题,数学建模,算法,编程、调试,得到结果,计算机博弈与人工智能,棋盘表示,六子棋棋盘由19条横线和19条纵线组成。 棋盘一共有19*19=361个交点。 交点出现的可能情况：无子、黑子、白子 棋盘：char position1919; 棋子： 黑棋（BLACK）：0 白棋（WHITE）：1 无子（NOSTONE）：0 xff,示例代码,宏定义： #define GRID_NUM 19 /棋盘行数 #define GRID_COUN
3、T 361 /可放棋子总数 #define BLACK 0 /黑棋 #define WHITE 1 /白棋 #define NOSTONE 0 xff /无棋 全局变量： BYTE position GRID_NUMGRID_NUM;/棋盘 STONEMOVE m_cmBestMove; /记录着法 注: #include windows.h typedef unsigned char BYTE,计算机博弈与人工智能,示例代码,结构定义： /棋子位置 typedef struct _stoneposition BYTE x; BYTE y; STONEPOS; /走法 typedef stru
4、ct _stonemove STONEPOS StonePos2; /棋子位置 int Score;/走法的分数 STONEMOVE;,计算机博弈与人工智能,示例代码,主函数，程序的入口 void main() int ChessmanType; /记录棋子颜色 char Msg500; /保存接收到的消息 char name = “name 中国深度n; /队伍信息 char Move = move AABBn; /走法 int x0,x1,y0,y1;/坐标 /初始化棋盘 memset ( position, NOSTONE, GRID_COUNT);,计算机博弈与人工智能,示例代码,wh
5、ile (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); /初始化棋盘
6、 scanf(%s,Msg); if (strcmp(Msg,“black”) = 0) /确定我方棋子的颜色 Sleep(50); /延迟一段时间发送，经测试，立即发送可 /能造成平台无响应 printf(move JJn); position99 = BLACK; fflush(stdout); ChessmanType = BLACK; continue; ,计算机博弈与人工智能,示例代码,else / if (strcmp(Msg,“white”) = 0) ChessmanType = WHITE; continue; /确定棋型颜色结束 if (strcmp(Msg,move) =
7、 0) /接收对方的招法 scanf(%s,Msg);,计算机博弈与人工智能,示例代码,if (Msg2 = 0) /接收黑方的第一着 /move XXn y0 = (int)(Msg0) - (int)(A); x0 = (int)(S) - (int)(Msg1); positionx0y0 = !ChessmanType; ,计算机博弈与人工智能,示例代码,else/接收对方的招法，一般招法都是一着下两个子 /move XYXYn y0 = (int)(Msg0) - (int)(A); x0 = (int)(S) - (int)(Msg1);y1 = (int)(Msg2) - (in
8、t)(A); x1 = (int)(S) - (int)(Msg3); positionx0y0 = !ChessmanType;positionx1y1 = !ChessmanType; ,计算机博弈与人工智能,示例代码,if (SearchAGoodMove(position,ChessmanType) /获得着法的坐标 x0 = m_cmBestMove.StonePos0.x; y0 = m_cmBestMove.StonePos0.y; x1 = m_cmBestMove.StonePos1.x; y1 = m_cmBestMove.StonePos1.y; /将着法记录在棋盘中 p
9、ositionx0y0 = ChessmanType; positionx1y1 = ChessmanType;,计算机博弈与人工智能,示例代码,/将着法转换成要发送的字符形式 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; Move6 = x0; Move7 = y1; Move8 = x1; printf(%s,Move); fflush(
10、stdout);,计算机博弈与人工智能,计算机博弈与人工智能,机器博弈交互平台,棋盘,黑方程序,白方程序,1,1,1,2,3,3,4,5,5,6,计算机博弈的设计思路,SearchAGoodMove(position,ChessmanType) 如何根据已有的棋盘局面和我方子的颜色，来得到我方 下一步将要走的招法。,计算机博弈与人工智能,？,穷举法,穷举出下一步所有可能的招法，形成不同的局面。 比较一下这些局面，选取出其中最好的（对我方最有利） 局面，则形成此局面对应的招法就是我方下一步“最佳” 的走法。 所有可能的招法：招法生成 比较：评估函数 选取、最好的：搜索函数（极大极小值搜索） 最佳
11、：此时对应的招法真的是最好的招法吗？,计算机博弈与人工智能,计算机博弈与人工智能,博弈程序核心模块,AI引擎,招法生成,招法生成：生成一个局面的所有可能招法（合法招法）。 例如： 象棋中的，象走田，马走日，兵可进不可退。 六子棋的合法招法：任意空格点。 思考： 是不是所有招法都是我们需要考虑的？可不可以舍弃一 些招法？ 速度与准确性的矛盾。,计算机博弈与人工智能,评估函数,评估函数：用以评价一个局面的好坏。 计算机如何知道一个局面的好坏？ 局面的好坏 实数 思路： 根据局面中的各方棋型，来具体分析局面好坏，给出各 局面的分值。 难点：1.查找棋型，保证速度与准确性。 2.如何根据棋型给分值，分
12、值如何确定。,计算机博弈与人工智能,六子棋的棋型,长连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的7颗或7颗以上同色棋子不间隔地相连。 六连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的6颗同色棋子不间隔地相连。 长连和六连是规定时间内获胜的必要条件。,计算机博弈与人工智能,六子棋的棋型,活五：在同一直线上的5颗同色棋子，符合“对方必须 用两手棋才能挡住”的条件。“挡住”是指不让 另一方形成六连或长连。,计算机博弈与人工智能,六子棋的棋型,眠五：在同一直线上的5颗同色棋子，符合“对方用 用一手棋才能挡住”的条件。,计算机博弈与人工智能,六子棋的棋型,活四：在同一直线上的4颗同色棋子，
13、符合“对方必须 用两手棋才能挡住”的条件。,计算机博弈与人工智能,六子棋的棋型,眠四：在同一直线上的4颗同色棋子，符合“对方用 用一手棋才能挡住”的条件。,计算机博弈与人工智能,六子棋的棋型,活三：在同一直线上的3颗同色棋子，符合“再下一手 就能形成活四”的条件。,计算机博弈与人工智能,六子棋的棋型,眠三：在同一直线上的3颗同色棋子，符合“再下两手 棋也只能形成眠四”的条件。,计算机博弈与人工智能,六子棋的棋型,活二：在同一直线上的2颗同色棋子，符合“再下两手 棋就能形成活四”的条件。,计算机博弈与人工智能,六子棋的棋型,眠二：在同一直线上的2颗同色棋子，符合“再下两手 棋只能形成眠四”的条件
14、。,计算机博弈与人工智能,搜索函数,下一个最好的（评估分值最高）局面的对应的招法就是 最佳招法吗？ 棋类高手都能看很多步！ 当我方生成各种局面后，对方针对我方形成的每一种局 面又同样会生成许多局面，我方再针对对方形成的每一 种局面同样又会生成许多对应局面，这样循环往复，就 形成了一个颗博弈树。,计算机博弈与人工智能,博弈树,计算机博弈与人工智能,博弈树一棵多叉树。 六子棋博弈树的复杂度很高。 每个局面对应招法 开始： 360*359=129240 结束（设50步之后）：310*309=95790 设平均取105 个节点。 1层： 105 2层： 105 * 105 = 1010 3层： 101
15、0 * 1010 = 1020 节点数随深度的增加以爆炸式方式增长,博弈树,提高时间效率 一般一步能控制在半分钟内为宜。 方法： 减小博弈树的规模： 1.降低搜索深度，但棋力提高有限。 2.每个局面对应只生成少许有价值的节点， 可能有漏选。 运用高效的搜索算法，例如：-剪枝。 提高各模块的效率，尤其是评估函数的效率。,计算机博弈与人工智能,极大极小值搜索,建立了博弈树，我们怎样找到我们需要的招法？ 搜索与回溯方式： 因为： 局面分值越高，对我方越有利，对于对方越不利。 局面分值越低，对我方越不利，也就是对于对方越有利。 所以： 轮到我方走时，我方会选择使下一步局面分值最高的走 法。此节点（局面）分值 = MAX所有子节点分值 轮到对方走时，对方会选择使下一步局面分值最低的走 法。此节点（局面）分值 = MIN所以子节点分值,计算机博弈与人工智能,计算机博弈与人工智能,极大极小值搜索,深度,层数,8,15,12,70,16,7,10,20,3,48,15,20,7,70,48,7,48,48,思路总结,计算机博弈与人工智能,棋盘信息,搜索函数,招法生成,查找棋型,评估函数,最佳招法,计算机博弈大赛,1.自己个人能力的提高 2.团队合作能力的提高 3.初步了解软件工程与软件项目 4.计算机博弈领域充满机遇与挑战 5.我有可以吗？ 知识是靠自己学的。 能力是从实践中锻炼出来
