《博弈大赛赛前培训六棋子程序的实现》由会员分享，可在线阅读，更多相关《博弈大赛赛前培训六棋子程序的实现（39页珍藏版）》请在金锄头文库上搜索。
1、LOGO六子棋博弈程序六子棋博弈程序计算机博弈与人工智能协会计算机博弈与人工智能协会 计算机博弈与人工智能1 本次大赛通信协议本次大赛通信协议博弈程序整体设计思路博弈程序整体设计思路 博弈程序核心模块博弈程序核心模块 机器博弈交互平台机器博弈交互平台本次大赛的一些相关说明本次大赛的一些相关说明讲解要点解要点2机器博弈交互平台机器博弈交互平台裁判系统裁判系统棋盘棋盘黑方程序黑方程序白方程序白方程序11123345563本次大赛通信协议本次大赛通信协议接受裁判系统信息：接受裁判系统信息：scanf(%s,Msg);传回裁判系统信息：传回裁判系统信息：printf(%s,Move);1.1.确定队名
2、：确定队名：name?“ 传回队名：传回队名： name BitStrongern“2.2.开局：开局：new3.3.确定黑白方：确定黑白方： 黑方：黑方：black 白方：白方：white4.4.发送、接收招法发送、接收招法 /先横向坐标，后纵向坐标先横向坐标，后纵向坐标 黑方第一步：黑方第一步：move X0Y0 其他步数：其他步数：move X0Y0X1Y1 4博弈程序整体设计思路博弈程序整体设计思路 实际问题实际问题数学建模数学建模算法算法编程、程、调试得到结果得到结果5棋盘表示棋盘表示 六子棋棋盘由六子棋棋盘由1919条横线和条横线和1919条纵线组成。条纵线组成。棋盘一共有棋盘一共
3、有19*1919*19= =361361个交点。个交点。交点出现的可能情况：交点出现的可能情况：无子、黑子、白子无子、黑子、白子棋盘棋盘：char positionposition1919;棋子：棋子： 黑棋（BLACK）：0 白棋（WHITE）：1 无子（NOSTONE）：0xff6示例代码示例代码宏定义：宏定义：#define GRID_NUM 19 /棋盘行数#define GRID_COUNT 361 /可放棋子总数#define BLACK 0 /黑棋#define WHITE 1 /白棋#define NOSTONE 0xff /无棋全局变量：全局变量：BYTE position
4、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 Chess
5、manType; /记录棋子颜色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(%
6、s,Msg);if (strcmp(Msg,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(s
7、tdout); ChessmanType = 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 = !Chessma
8、nType;13示例代码示例代码else/接收对方的招法，一般招法都是一着下两个子 /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_cmBestMov
9、e.StonePos0.x;y0 = m_cmBestMove.StonePos0.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);
10、/Move = move AABBn/修改AABB 并发送Move5 = y0;Move6 = x0;Move7 = y1;Move8 = x1;printf(%s,Move);fflush(stdout);16机器博弈交互平台机器博弈交互平台裁判系统裁判系统棋盘棋盘黑方程序黑方程序白方程序白方程序111233455617计算机博弈的算机博弈的设计思路思路SearchAGoodMove(position,ChessmanType)如何根据已有的棋盘局面和我方子的颜色，来得到我方下一步将要走的招法。？18穷举法法穷举出下一步穷举出下一步所有可能的招法所有可能的招法，形成不同的局面。，形成不同的局
11、面。比较比较一下这些局面，一下这些局面，选取选取出其中出其中最好最好的（对我方最有利）的（对我方最有利）局面，则形成此局面对应的招法就是我方下一步局面，则形成此局面对应的招法就是我方下一步“最佳最佳”的走法。的走法。所有可能的招法：所有可能的招法：招法生成招法生成 比较：比较：评估函数评估函数 选取、最好的：选取、最好的：搜索函数（极大极小值搜索）搜索函数（极大极小值搜索）最佳最佳：此时对应的招法真的是最好的招法吗？：此时对应的招法真的是最好的招法吗？19博弈程序核心模块博弈程序核心模块搜索函数搜索函数招法生成招法生成评估函数评估函数AIAI引擎引擎20招法生成招法生成招法生成招法生成：生成一
12、个局面的所有可能招法（合法招法）。生成一个局面的所有可能招法（合法招法）。例如：例如：象棋中的，象走田，象棋中的，象走田，马走日，兵可走日，兵可进不可退。不可退。六子棋的合法招法：六子棋的合法招法：任意空格点。任意空格点。思考：思考：是不是所有招法都是我是不是所有招法都是我们需要考需要考虑的？可不可以舍弃一的？可不可以舍弃一些招法？些招法？速度与准确性的矛盾。速度与准确性的矛盾。21评估函数估函数评估函数：评估函数：用以评价一个局面的好坏。用以评价一个局面的好坏。计算机如何知道一个局面的好坏？计算机如何知道一个局面的好坏？局面的好坏局面的好坏 实数数思路：思路：根据局面中的各方棋型，来具体分析
13、局面好坏，给出各根据局面中的各方棋型，来具体分析局面好坏，给出各局面的分值。局面的分值。难点：难点：1.1.查找棋型，保证速度与准确性。查找棋型，保证速度与准确性。 2. 2.如何根据棋型给分值，分值如何确定。如何根据棋型给分值，分值如何确定。22六子棋的棋型六子棋的棋型长连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的7颗或7颗以上同色棋子不间隔地相连。六六连：在棋盘的纵向、横向或斜向的任意一条线上，形 成的6颗同色棋子不间隔地相连。长连和六六连是规定时间内获胜的必要条件。23六子棋的棋型六子棋的棋型活五：活五：在同一直线上的在同一直线上的5 5颗颗同色棋子，符合同色棋子，符合“对方必须
14、对方必须 用两手棋才能挡住用两手棋才能挡住”的条件。的条件。“挡住挡住”是指不让是指不让 另一方形成六连或长连。另一方形成六连或长连。24六子棋的棋型六子棋的棋型眠五：眠五：在同一直线上的在同一直线上的5 5颗颗同色棋子，符合同色棋子，符合“对方用对方用 用一手棋才能挡住用一手棋才能挡住”的条件。的条件。25六子棋的棋型六子棋的棋型活四：活四：在同一直线上的在同一直线上的4 4颗颗同色棋子，符合同色棋子，符合“对方必须对方必须 用两手棋才能挡住用两手棋才能挡住”的条件。的条件。26六子棋的棋型六子棋的棋型眠四：眠四：在同一直线上的在同一直线上的4 4颗颗同色棋子，符合同色棋子，符合“对方用对方
15、用 用一手棋才能挡住用一手棋才能挡住”的条件。的条件。27六子棋的棋型六子棋的棋型活三：活三：在同一直线上的在同一直线上的3 3颗颗同色棋子，符合同色棋子，符合“再下一手再下一手 就能形成活四就能形成活四”的条件。的条件。28六子棋的棋型六子棋的棋型眠三：眠三：在同一直线上的在同一直线上的3 3颗颗同色棋子，符合同色棋子，符合“再下两手再下两手 棋也只能形成眠四棋也只能形成眠四”的条件。的条件。29六子棋的棋型六子棋的棋型活二：活二：在同一直线上的在同一直线上的2 2颗颗同色棋子，符合同色棋子，符合“再下两手再下两手 棋就能形成活四棋就能形成活四”的条件。的条件。30六子棋的棋型六子棋的棋型眠
16、二：眠二：在同一直线上的在同一直线上的2 2颗颗同色棋子，符合同色棋子，符合“再下两手再下两手 棋只能形成眠四棋只能形成眠四”的条件。的条件。31搜索函数搜索函数下一个最好的（评估分值最高）局面的对应的招法就是下一个最好的（评估分值最高）局面的对应的招法就是最佳招法吗？最佳招法吗？棋类高手都能看很多步！棋类高手都能看很多步！当我方生成各种局面后，对方针对我方形成的当我方生成各种局面后，对方针对我方形成的每一种局每一种局面面又同样会生成许多局面，我方再针对对方形成的每一又同样会生成许多局面，我方再针对对方形成的每一种局面同样又会生成许多对应局面，这样循环往复，就种局面同样又会生成许多对应局面，这
17、样循环往复，就形成了一个颗形成了一个颗博弈树博弈树。32博弈树博弈树博弈树一棵博弈树一棵多叉树多叉树。六子棋博弈树的复杂度很高。六子棋博弈树的复杂度很高。每个局面对应招法每个局面对应招法 开始：开始： 360*359=129240360*359=129240 结束（设结束（设5050步之后）：步之后）：310*309=95790310*309=95790设平均取设平均取10105 5 个节点。个节点。1 1层：层： 10 105 52 2层：层： 10 105 5 * 10 * 105 5 = 10 = 1010103 3层：层： 10101010 * 10 * 1010 10 = 10= 1
18、02020 节点数随深度的增加以节点数随深度的增加以爆炸式爆炸式方式增长方式增长33博弈树博弈树提高时间效率提高时间效率一般一步能控制在半分钟内为宜。一般一步能控制在半分钟内为宜。方法：方法：减小博弈树的规模：减小博弈树的规模： 1.1.降低搜索深度，但棋力提高有限降低搜索深度，但棋力提高有限。 2.2.每个局面对应只生成少许有价值的节点，每个局面对应只生成少许有价值的节点， 可能有漏选。可能有漏选。运用高效的搜索算法，例如：运用高效的搜索算法，例如：-剪枝。剪枝。提高各模块的效率，尤其是评估函数的效率。提高各模块的效率，尤其是评估函数的效率。34极大极小极大极小值搜索搜索建立了博弈树，我们怎
19、样找到我们需要的招法？建立了博弈树，我们怎样找到我们需要的招法？搜索与回溯方式：搜索与回溯方式：因为：因为：局面分值越高，对我方越有利，对于对方越不利。局面分值越高，对我方越有利，对于对方越不利。局面分值越低，对我方越不利，也就是对于对方越有利。局面分值越低，对我方越不利，也就是对于对方越有利。所以：所以：轮到我方走时，我方会选择使下一步局面分值最高的走轮到我方走时，我方会选择使下一步局面分值最高的走法。法。此节点（局面）分值此节点（局面）分值 = MAX= MAX所有子节点分值所有子节点分值 轮到对方走时，对方会选择使下一步局面分值最低的走轮到对方走时，对方会选择使下一步局面分值最低的走法。
20、法。此节点（局面）分值此节点（局面）分值 = MIN= MIN所以子节点分值所以子节点分值 35极大极小极大极小值搜索搜索局面（取局面（取极极大大值）局面（取局面（取极极小小值）RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：例：深度深度层数层数815127016710 2034815 20770487484836思路总结思路总结棋盘信息棋盘信息搜索函数搜索函数招法生成招法生成查找棋型查找棋型评估函数评估函数最佳招法最佳招法37计算机博弈大算机博弈大赛1.1.自己个人能力的提高自己个人能力的提高2.2.团队合作能力的提高团队合作能力的提高3.3.初步了解软件工程与软件项目初步了解软件工程与软件项目4.4.计算机博弈领域充满机遇与挑战计算机博弈领域充满机遇与挑战5.5.我有可以吗？我有可以吗？ 知识是靠自己学的。知识是靠自己学的。 能力是从实践中锻炼出来的。能力是从实践中锻炼出来的。38LOGO计算机博弈与人工智能算机博弈与人工智能协会会39
