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

1、LOGO六子棋博弈程序六子棋博弈程序唐志峰唐志峰计算机博弈与人工智能协会计算机博弈与人工智能协会 计算机博弈与人工智能计算机博弈与人工智能 本次大赛通信协议本次大赛通信协议博弈程序整体设计思路博弈程序整体设计思路 博弈程序核心模块博弈程序核心模块 机器博弈交互平台机器博弈交互平台本次大赛的一些相关说明本次大赛的一些相关说明讲解要点讲解要点计算机博弈与人工智能机器博弈交互平台机器博弈交互平台裁判系统裁判系统棋盘棋盘黑方程序黑方程序白方程序白方程序1112334556计算机博弈与人工智能本次大赛通信协议本次大赛通信协议接受裁判系统信息：接受裁判系统信息：scanf(%s,Msg);传回裁判系统信息

2、：传回裁判系统信息：printf(%s,Move);1.1.确定队名：确定队名：name?“ 传回队名：传回队名： name BitStrongern“2.2.开局：开局：new3.3.确定黑白方：确定黑白方： 黑方：黑方：black 白方：白方：white4.4.发送、接收招法发送、接收招法 /先横向坐标，后纵向坐标先横向坐标，后纵向坐标 黑方第一步：黑方第一步：move X0Y0 其他步数：其他步数：move X0Y0X1Y1 计算机博弈与人工智能博弈程序整体设计思路博弈程序整体设计思路 实际问题实际问题数学建模数学建模算法算法编编程、程、调试调试得到结果得到结果计算机博弈与人工智能棋盘表

3、示棋盘表示 六子棋棋盘由六子棋棋盘由1919条横线和条横线和1919条纵线组成。条纵线组成。棋盘一共有棋盘一共有1919* *1919= =361361个交点。个交点。交点出现的可能情况：交点出现的可能情况：无子、黑子、白子无子、黑子、白子棋盘棋盘：char positionposition1919;棋子：棋子： 黑棋（BLACK）：0 白棋（WHITE）：1 无子（NOSTONE）：0 xff示例代码示例代码宏定义：宏定义：#define GRID_NUM 19 /棋盘行数#define GRID_COUNT 361 /可放棋子总数#define BLACK 0 /黑棋#define WHI

4、TE 1 /白棋#define NOSTONE 0 xff /无棋全局变量：全局变量：BYTE position GRID_NUMGRID_NUM;/棋盘STONEMOVE m_cmBestMove; /记录着法注: #include windows.h typedef unsigned char BYTE 计算机博弈与人工智能示例代码示例代码结构定义：结构定义：/棋子位置typedef struct _stonepositionBYTE x;BYTE y;STONEPOS;/走法typedef struct _stonemoveSTONEPOS StonePos2; /棋子位置int Sco

5、re;/走法的分数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); 计算机博弈与人工智能示例代码示例代码while (1)/循环接收裁判平台发送的消息，注意需要发送的字符串应该/以n结束，裁判

6、平台才会认为是一次完整的输入./发送完需要调用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) /确定我方

7、棋子的颜色 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) = 0) /接收对方的招法scanf(%s,Msg); 计算机博弈与人工智能示例代码示例代码 if (M

8、sg2 = 0) /接收黑方的第一着/move XXny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1); positionx0y0 = !ChessmanType;计算机博弈与人工智能示例代码示例代码else/接收对方的招法，一般招法都是一着下两个子 /move XYXYny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1);y1 = (int)(Msg2) - (int)(A);x1 = (int)(S) - (int)(Msg3);positionx0y0 = !Ches

9、smanType;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; /将着法记录在棋盘中positionx0y0 = ChessmanType;positionx1y1 = ChessmanType;计算机博弈与

10、人工智能示例代码示例代码/将着法转换成要发送的字符形式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(stdout);计算机博弈与人工智能计算机博弈与人工智能机器博弈交互平台机器博弈交互平台裁判系统裁判系统棋盘棋盘黑方程序黑方程序白方程序白方程序1

11、112334556计算机博弈的设计思路计算机博弈的设计思路SearchAGoodMove(position,ChessmanType)如何根据已有的棋盘局面和我方子的颜色，来得到我方下一步将要走的招法。计算机博弈与人工智能穷举法穷举法穷举出下一步穷举出下一步所有可能的招法所有可能的招法，形成不同的局面。，形成不同的局面。比较比较一下这些局面，一下这些局面，选取选取出其中出其中最好最好的（对我方最有利）的（对我方最有利）局面，则形成此局面对应的招法就是我方下一步局面，则形成此局面对应的招法就是我方下一步“最佳最佳”的走法。的走法。所有可能的招法：所有可能的招法：招法生成招法生成 比较：比较：评估

12、函数评估函数 选取、最好的：选取、最好的：搜索函数（极大极小值搜索）搜索函数（极大极小值搜索）最佳最佳：此时对应的招法真的是最好的招法吗？：此时对应的招法真的是最好的招法吗？计算机博弈与人工智能计算机博弈与人工智能博弈程序核心模块博弈程序核心模块搜索函数搜索函数招法生成招法生成评估函数评估函数AIAI引擎引擎招法生成招法生成招法生成招法生成：生成一个局面的所有可能招法（合法招法）。生成一个局面的所有可能招法（合法招法）。例如：例如：象棋中的，象走田，马走日，兵可进不可退。象棋中的，象走田，马走日，兵可进不可退。六子棋的合法招法：六子棋的合法招法：任意空格点。任意空格点。思考：思考：是不是所有招

13、法都是我们需要考虑的？可不可以舍弃一是不是所有招法都是我们需要考虑的？可不可以舍弃一些招法？些招法？速度与准确性的矛盾。速度与准确性的矛盾。计算机博弈与人工智能评估函数评估函数评估函数：评估函数：用以评价一个局面的好坏。用以评价一个局面的好坏。计算机如何知道一个局面的好坏？计算机如何知道一个局面的好坏？局面的好坏局面的好坏 实数实数思路：思路：根据局面中的各方棋型，来具体分析局面好坏，给出各根据局面中的各方棋型，来具体分析局面好坏，给出各局面的分值。局面的分值。难点：难点：1.1.查找棋型，保证速度与准确性。查找棋型，保证速度与准确性。 2. 2.如何根据棋型给分值，分值如何确定。如何根据棋型

14、给分值，分值如何确定。计算机博弈与人工智能六子棋的棋型六子棋的棋型长连：长连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的7颗或7颗以上同色棋子不间隔地相连。六连：六连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的6颗同色棋子不间隔地相连。长连长连和六连六连是规定时间内获胜的必要条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型活五：活五：在同一直线上的在同一直线上的5 5颗颗同色棋子，符合同色棋子，符合“对方必须对方必须 用两手棋才能挡住用两手棋才能挡住”的条件。的条件。“挡住挡住”是指不让是指不让 另一方形成六连或长连。另一方形成六连或长连。计算机博弈与人工智能六子棋的棋型六子棋的

15、棋型眠五：眠五：在同一直线上的在同一直线上的5 5颗颗同色棋子，符合同色棋子，符合“对方用对方用 用一手棋才能挡住用一手棋才能挡住”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型活四：活四：在同一直线上的在同一直线上的4 4颗颗同色棋子，符合同色棋子，符合“对方必须对方必须 用两手棋才能挡住用两手棋才能挡住”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型眠四：眠四：在同一直线上的在同一直线上的4 4颗颗同色棋子，符合同色棋子，符合“对方用对方用 用一手棋才能挡住用一手棋才能挡住”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型活三：活三：在同一直线上的在

16、同一直线上的3 3颗颗同色棋子，符合同色棋子，符合“再下一手再下一手 就能形成活四就能形成活四”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型眠三：眠三：在同一直线上的在同一直线上的3 3颗颗同色棋子，符合同色棋子，符合“再下两手再下两手 棋也只能形成眠四棋也只能形成眠四”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型活二：活二：在同一直线上的在同一直线上的2 2颗颗同色棋子，符合同色棋子，符合“再下两手再下两手 棋就能形成活四棋就能形成活四”的条件。的条件。计算机博弈与人工智能六子棋的棋型六子棋的棋型眠二：眠二：在同一直线上的在同一直线上的2 2颗颗同色棋子，符合

17、同色棋子，符合“再下两手再下两手 棋只能形成眠四棋只能形成眠四”的条件。的条件。计算机博弈与人工智能搜索函数搜索函数下一个最好的（评估分值最高）局面的对应的招法就是下一个最好的（评估分值最高）局面的对应的招法就是最佳招法吗？最佳招法吗？棋类高手都能看很多步！棋类高手都能看很多步！当我方生成各种局面后，对方针对我方形成的当我方生成各种局面后，对方针对我方形成的每一种局每一种局面面又同样会生成许多局面，我方再针对对方形成的每一又同样会生成许多局面，我方再针对对方形成的每一种局面同样又会生成许多对应局面，这样循环往复，就种局面同样又会生成许多对应局面，这样循环往复，就形成了一个颗形成了一个颗博弈树博

18、弈树。计算机博弈与人工智能博弈树博弈树计算机博弈与人工智能博弈树一棵博弈树一棵多叉树多叉树。六子棋博弈树的复杂度很高。六子棋博弈树的复杂度很高。每个局面对应招法每个局面对应招法 开始：开始： 360360* *359=129240359=129240 结束（设结束（设5050步之后）：步之后）：310310* *309=95790309=95790设平均取设平均取10105 5 个节点。个节点。1 1层：层： 10 105 52 2层：层： 10 105 5 * * 10 105 5 = 10 = 1010103 3层：层： 10101010 * * 10 1010 10 = 10= 1020

19、20 节点数随深度的增加以节点数随深度的增加以爆炸式爆炸式方式增长方式增长博弈树博弈树提高时间效率提高时间效率一般一步能控制在半分钟内为宜。一般一步能控制在半分钟内为宜。方法：方法：减小博弈树的规模：减小博弈树的规模： 1.1.降低搜索深度，但棋力提高有限降低搜索深度，但棋力提高有限。 2.2.每个局面对应只生成少许有价值的节点，每个局面对应只生成少许有价值的节点， 可能有漏选。可能有漏选。运用高效的搜索算法，例如：运用高效的搜索算法，例如：-剪枝。剪枝。提高各模块的效率，尤其是评估函数的效率。提高各模块的效率，尤其是评估函数的效率。计算机博弈与人工智能极大极小值搜索极大极小值搜索建立了博弈树，我们怎样找到我们需要的招法？建立了博弈树，我们怎样找到我们需要的招法？搜索与回溯方式：搜索与回溯方式：因为：因为：局面分值越高，对我方越有利，对于对方越不利。局面分值越高，对我方越有利，对于对方越不利。局面分值越低，对我方越不利，也就是对于对方越有利。局面分值越低，对我方越不利，也就是对于对方越有利。所以：所以：轮到我方走时，我方会选择使下一步局面分值