2023年7月9日发(作者：)

基于C++的不围棋NOGO代码-PKU计算概论A⼤作业-MCTS算法Minimax算法关于评论区提出的问题，我补充⼀下，这篇代码是pku同学《计算概论A2020》的⼤作业，代码是需要提交在botzone上的，⽂章中有些代码是与botzone的交互，具体交互过程与规则见维基百科。⽬录1. 不围棋规则简介某⽇，助教MorroWind遇到了围棋⼗连败。他看着因为被围失⽓被迫出具的我⽅棋⼦，感觉围棋这个游戏⼗分不讲武德，武林要以和为贵。MorrowWind越想越⽓，很快啊，他“啪”的⼀声站了起来，怒⽬圆睁，指着对⼿的⿐⼦吼道：“天天围我的⼦搞偷袭，算什么能耐，有本事咱们谁都不围对⼿的棋⼦，谁围上谁输！” 他的对⼿歪嘴⼀笑 “年轻⼈，你要耗⼦尾汁”各位同学，你们能写⼀个程序，帮⼀帮MorroWind来打败他的对⼿么？【规则】

⽬标：想⽅设法不要让⾃⼰提⾛对⽅的棋⼦（围住），尽可能让⾃⼰的棋⼦被对⽅提⾛（围住）。什么是“⽓：**要理解“提⾛”，⾸先要理解什么是“⽓”。⼀个棋⼦在棋盘上，与它 直线紧邻的空点是这个棋⼦的“⽓”。 棋⼦直线紧邻的点上，如果有同⾊棋⼦存在，则 它们便相互连接成⼀个不可分割的整体。它们的⽓也应⼀并计算。什么是“提⾛”：当⼀个棋⼦没有“⽓”的时候它就要被提⾛。棋⼦直线紧邻的点上，如果有异⾊棋⼦存在，这⼝⽓就不复存在。如所有的⽓均为对⽅所占据，便呈⽆⽓状态。⽆⽓状态的棋⼦不能在棋盘上存在，也就是提⼦。把⽆⽓之⼦提出盘外的⼿段叫“提⼦”。棋盘的规格：如图所⽰，不围棋的棋盘⼤⼩是99。注意，这⾥的99 指的是格点的数⽬，并不是格⼦的数量，因为棋⼦要下在格点上。落⼦先后：⿊⼦先⼿，双⽅轮流落⼦，落⼦后棋⼦不可移动。判负条件：不围棋没有平局。⼀⽅输掉⽐赛，当且仅当以下⾄少⼀条发⽣： 1）如果⼀⽅落⼦后吃掉了对⽅的棋⼦，则落⼦⼀⽅判负； 2）对弈禁⽌⾃杀，落⼦⾃杀⼀⽅判负； 3）对弈禁⽌空⼿(pass)，空⼿⼀⽅判负。开局限制：⿊棋第⼀⼿禁⽌下在棋盘正中央（待议）。2. 思路提⽰【最直接的⼈⼯策略设计】 助教MorroWind话⾳刚落，就有⾼⼿“啪”地站起来了：“棋盘上的格点，要么⿊⽅下或⽩⽅下必输，要么随便下不影响输赢。最简单的想法，你让棋盘上只剩下那些对⽅⼀下就输的格点就完了。不过，有些格点不管⿊的还是⽩的，谁下都会输。棋盘长成这种类型，你就这样……”⾼⼿到⿊板上开始画棋谱，这些棋谱都体现出了⼀些特征，根据这些特征，有⼀些应对的策略。这些策略，有的很直观，有的很难懂。很快啊，⿊板就被画满了。有勤奋的同学就把棋谱抄了下来，写成程序让助教去PK。⾯对有备⽽来的AI，助教⼀次都没赢过。不过后来这些棋谱失传了，江湖上只剩下了“眼”，“打吃”等不知道是什么意思的名词。【简单步法搜索】 ⼀位同学说，这样设计规则太不“计算机”了，⽐的是谁下棋能⼒强。咱们应该让计算机⼲更多的活。 鲁迅曾经说过，第⼀层的打不过第五层的。想要起飞就必须懂得这个道理。具体来说，你在做决策的时候必须要考虑到对⼿的决策，⾃⼰根据对⼿的决策做出的决策，对⼿根据你对于对⼿的决策做出的决策所做出的决策，，，如此套娃。如果两个⼈都⾜够聪明，只不过记忆⼒有差别，你⽐他能够记住多套⼀层的结果，那么你就赢了。如果现在是你要下棋，你⾯对的场⾯是n，你应该考虑你的对⼿将如何对你有差别，你⽐他能够记住多套⼀层的结果，那么你就赢了。如果现在是你要下棋，你⾯对的场⾯是n，你应该考虑你的对⼿将如何对你的决定进⾏反应。假设你可以做出m种合法的下⼦⽅法，下⼦⽅法i对应的棋盘场⾯是n!，那么你的对⼿⼀定会采取在场⾯n!下对他最有利的⾛法，假设这种⾛法对他的收益是v!。显⽽易见，你下棋的⽬的是为了让对⼿即便使⽤了最好的策略也得收获最少的好处，因此你在这⼀步做的决策应该是让棋盘变成对⼿采⽤最优解获得的收益最⼩的那个场⾯的决策。对⼿收益最⼩，你的收益就是最⼤的，⽽你下棋的决策就应该是让你获得最⼤收益的决策。假设对⼿最⼩的收益是v= min{v", v#,…v$}，那么你的收益就是−v。但你如何获得v!，你就要想象你是对⼿，正在根据你的决策，运⽤同样的决策过程进⾏他的选择。如此往复循环下去，直到你不想继续了，或者游戏结束了，分出胜负了。显然这是⼀个递归的过程，以上的⽅法叫做负极⼤值搜索。不过这样设计有两个问题。其⼀，搜索空间太⼤了。这⼀点我们可以设计剪枝和限制搜索层数来部分解决；其⼆，根据课上学的，这⾥的搜索是⼀个递归的过程，递归要有⼀个终结的点，也就是搜索树的叶⼦节点，那叶⼦节点的值我们怎样评估呢？ MorroWind说： “我要是会，我还要问你？”【MCTS 搜索】有同学说，我规则不会写，剪枝⼜不会判，只能在第⼆层，别⼈都在第五层，只能退课才能维持的了绩点这样⼦（可能这个作业发布的时候退课已经截⽌了）不过题还是要做的。我们想⼀想，⽐别⼈层数低的原因是什么，不就是追求了搜索的覆盖⾯导致不够深⼊。那么我们为什么不收紧⼀些搜索的宽度，去追求⼀些搜索的深度呢？⼀个最基础的想法是，从当前局⾯出发，我们进⾏K个完整的对局，每个对局的每⼀步的产⽣，可以是随机的，也可以是根据⼀定规则的（⽐如著名的UCT算法）。接下来我们要选择我们的动作。假如我们要选择的动作是a!，那么我们就看看这完成的K个对局中有哪些是以a!开始的，这些以a!开始的对局中有哪些是胜利的，这样我们就粗略地估计了a!的胜率。我们选择胜率最⾼的那个动作即可。不过这⾥也有很多技巧，⽐如说，我们进⾏的对局数越多越好，但是时间不允许，我们是不是可以每次不把对局下完，⽤其他的估值⽅式取代对胜率的计算；或者是，在模拟对局时采⽤的⽣成的动作的⽅法更精细⼀些，或者……说到这⾥，⼀些同学开始Google各种论⽂，⼀些同学默默地退出了直播间，掏出草纸，认真地构造剪枝⽅法、估值函数和棋盘特征。“菜鸡助教，你等着，你这辈⼦都打不赢我的AI。”⼀个讨厌这个装杯助教的学⽣如是说。3. 作业要求【基本要求】1. 有菜单选择（选择，新开始，存盘，读盘，结束）2. ⽤字符实现画棋盘和棋⼦。3. ⼀⽅选⼿是⼈员（助教），另⼀⽅选⼿是计算机AI。4. 程序输⼊是⼈员落⼦(x", y")。程序要根据输⼊，在棋盘上显⽰变化。程序根据算法决定AI⽅下⼀步棋⼦所放的位置，并显⽰新的棋盘布局。5. 允许中途停⽌游戏。6. 有复盘的功能（玩到⼀半，存储棋盘的状态）【分组】：7. 可以⼀个⼈⼀组，最多两⼈⼀组。8. 两个⼈⼀组时，最多只能⼀位同学的成绩是优秀。9. ⿎励两⼈⼀组，程度好的同学帮助基础差⼀些的同学。优秀率向着两⼈⼀组的情况倾斜。【成绩评定】10. 程序质量：完成基本要求的基础上，⿎励⾃⾏发挥。欢迎同学们多动脑，做出好的实验题。11. ⼯作量：分⼯要明确，两个⼈⼀组时，每个⼈的⼯作的最⼩单位是函数，在源程序上注明每个函数的完成⼈，以便提问。12. 提交内容：将源程序或程序包（包含源程序）压缩，提交到⽹站上。13. 实验报告：对程序的设计思路和功能做⼀个⼤概的说明，尤其⾃⼰认为有独特的地⽅，在实验报告中突出出来，提交到⽹站上。14. 验收形式：在规定的时间内，到机房找助教，演⽰程序，并回答助教提出的问题。15. 评分标准：满分10 分。助教会根据程序质量、回答问题的正确性、功能的完善等指标评定分数。没有参加botzone ⽐赛的作品不能超过8 分【提⽰】16. 在word⽂档中，把制表符拷贝下来，粘贴到C程序⾥。⽤cout输出，可以画出棋盘17. ⽤数组记录棋盘上的位置18. 每次输出棋盘的状态，都要⽤刷新命令system(“cls”);关于不围棋（NOGO）的更多规则以及botzone交互，请见维基百科的4. 代码这⾥有四种不同层次的代码，看你能理解到哪⼀层了！加油随机策略（random)⾸先是随机⾛棋，代码来源botzone，有⼀定的修改并添加了注释：//

不围棋（NoGo）样例程序//

随机策略//

作者：fffasttime//

游戏信息：/games#NoGo#include "jsoncpp/json.h"#include #include #include #include using namespace std;int board[9][9]; //棋盘，表⽰有⽆棋⼦，1是⿊⼦，-1是⽩⼦，0是⽆⼦bool dfs_air_visit[9][9]; //棋盘上每⼀点有没有⽓，false表⽰有⽓，true表⽰没有⽓const int cx[] = {-1, 0, 1, 0};const int cy[] = {0, -1, 0, 1};bool inBorder(int x, int y) { return x >= 0 && y >= 0 && x < 9 && y < 9; } //判断是否在边界以内//true: has air有⽓bool air_judge(int fx, int fy){ dfs_air_visit[fx][fy] = true; //标记，表⽰这个位置已经搜过有⽆⽓了 bool flag = false; for (int dir = 0; dir < 4; dir++) { int dx = fx + cx[dir], dy = fy + cy[dir]; if (inBorder(dx, dy)) //界内 { if (board[dx][dy] == 0) //旁边这个位置没有棋⼦ flag = true; if (board[dx][dy] == board[fx][fy] && !dfs_air_visit[dx][dy]) //旁边这个位置是没被搜索过的同⾊棋 if (air_judge(dx, dy)) flag = true; } } return flag;}//true: availablebool judgeAvailable(int fx, int fy, int col) //col-color表⽰棋⼦的颜⾊{ if (board[fx][fy]) //该位置有棋⼦了 return false; board[fx][fy] = col; memset(dfs_air_visit, 0, sizeof(dfs_air_visit)); if (!air_judge(fx, fy)) //fx，fy没⽓ { board[fx][fy] = 0; return false; } for (int dir = 0; dir < 4; dir++) { int dx = fx + cx[dir], dy = fy + cy[dir]; if (inBorder(dx, dy)) { if (board[dx][dy] && !dfs_air_visit[dx][dy]) if (!air_judge(dx, dy)) { board[fx][fy] = 0; return false; } } } board[fx][fy] = 0; //回溯 return true;}int main(){ srand((unsigned)time(0)); string str; int x, y; //

读⼊JSON getline(cin, str); //getline(cin, str); Json::Reader reader; Json::Value input; (str, input); //

分析⾃⼰收到的输⼊和⾃⼰过往的输出，并恢复状态 int turnID = input["responses"].size(); for (int i = 0; i < turnID; i++) //下⼀回合，复原上⼀回合的棋局 { x = input["requests"][i]["x"].asInt(), y = input["requests"][i]["y"].asInt(); if (x != -1) board[x][y] = 1; x = input["responses"][i]["x"].asInt(), y = input["responses"][i]["y"].asInt(); if (x != -1) board[x][y] = -1; } x = input["requests"][turnID]["x"].asInt(), y = input["requests"][turnID]["y"].asInt(); if (x != -1) board[x][y] = 1; //

输出决策JSON Json::Value ret; Json::Value action; //以下为随机策略 vector available_list; //合法位置表 for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (judgeAvailable(i, j, x == -1 ? 1 : -1)) available__back(i * 9 + j); int result = available_list[rand() % available_()]; action["x"] = result / 9; action["y"] = result % 9; ret["response"] = action; Json::FastWriter writer; cout << (ret) << endl; return 0;}贪⼼算法（greedy algorithm)贪⼼算法，⽐随机⾛棋多了⼀点点“启发性”，然⽽“⿏⽬⼨光”的特点让它往往“格局⼩了”。。。//不围棋（NoGo)//贪⼼算法//作者：Hoven Chen#include "jsoncpp/json.h"#include #include #include #include using namespace std;int board[9][9] = {0}; //棋盘，⿊⼦1，⽩⼦-1，没有棋⼦是0bool visited_by_air_judge[9][9] = {false}; //在air_judge函数判断某⼀点有⽆⽓时作标记，防⽌重复⽽死循环int value[9][9] = {0}; //储存每个位置的“权利值int dx[4] = {-1, 0, 1, 0}; //⾏位移int dy[4] = {0, -1, 0, 1}; //列位移//对⼿的colorint opponent_color(int color){ if (color == 1) return -1; else return 1;}//判断点(x,y)是否在棋盘内bool inBoard_judge(int x, int y) { return 0 <= x && x < 9 && 0 <= y && y < 9; }//判断是否有⽓bool air_judge(int x, int y){ visited_by_air_judge[x][y] = true; //标记，表⽰这个位置已经搜过有⽆⽓了 bool flag = false; for (int dir = 0; dir < 4; dir++) { int x_dx = x + dx[dir], y_dy = y + dy[dir]; if (inBoard_judge(x_dx, y_dy)) //界内 { if (board[x_dx][y_dy] == 0) //旁边这个位置没有棋⼦ flag = true; if (board[x_dx][y_dy] == board[x][y] && !visited_by_air_judge[x_dx][y_dy]) //旁边这个位置是没被搜索过的同⾊棋 if (air_judge(x_dx, y_dy)) flag = true; } } return flag;}//判断能否下颜⾊为color的棋bool put_available(int x, int y, int color) //no problem{ if (board[x][y]) //如果这个点本来就有棋⼦ return false; board[x][y] = color; memset(visited_by_air_judge, 0, sizeof(visited_by_air_judge)); //重置 if (!air_judge(x, y)) //如果下完这步这个点没⽓了,说明是⾃杀步，不能下 { board[x][y] = 0; return false; } for (int i = 0; i < 4; i++) //判断下完这步周围位置的棋⼦是否有⽓ { int x_dx = x + dx[i], y_dy = y + dy[i]; if (inBoard_judge(x_dx, y_dy)) //在棋盘内 { if (board[x_dx][y_dy] && !visited_by_air_judge[x_dx][y_dy]) //对于有棋⼦的位置（标记访问过避免死循环） if (!air_judge(x_dx, y_dy)) //如果导致(x_dx,y_dy)没⽓了，则不能下 { board[x][y] = 0; //回溯 return false; } } } } board[x][y] = 0; //回溯 return true;}//估值函数，对当前局⾯进⾏评估，计算颜⾊为color的⼀⽅⽐另⼀⽅可落⼦的位置数⽬多多少（权利值⽐较）int evaluate(int color){ int right = 0; int op_color = opponent_color(color); for (int x = 0; x < 9; x++) { for (int y = 0; y < 9; y++) { if (put_available(x, y, color)) right++; if (put_available(x, y, op_color)) right--; } } return right;}int main(){ srand((unsigned)time(0)); string str; int x, y; //

读⼊JSON getline(cin, str); int start = clock(); //时间 int timeout = (int)(0.9 * (double)CLOCKS_PER_SEC); //getline(cin, str); Json::Reader reader; Json::Value input; (str, input); //

分析⾃⼰收到的输⼊和⾃⼰过往的输出，并恢复状态 int turnID = input["responses"].size(); //复原棋盘 for (int i = 0; i < turnID; i++) //下⼀回合，复原上⼀回合的棋局 { x = input["requests"][i]["x"].asInt(), y = input["requests"][i]["y"].asInt(); if (x != -1) board[x][y] = 1; x = input["responses"][i]["x"].asInt(), y = input["responses"][i]["y"].asInt(); if (x != -1) board[x][y] = -1; } x = input["requests"][turnID]["x"].asInt(), y = input["requests"][turnID]["y"].asInt(); if (x != -1) board[x][y] = 1; //

输出决策JSON Json::Value ret; Json::Value action; //以下是搜索策略:贪⼼算法 int color = -1; int max_value = INT_MIN; int best_i[81] = {0}, best_j[81] = {0}, best_num = 0; memset(value, 0, sizeof(value)); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) for (int j = 0; j < 9; j++) { if (put_available(i, j, color)) { board[i][j] = color; value[i][j] = evaluate(color); if (value[i][j] > max_value) max_value = value[i][j]; board[i][j] = 0; } else value[i][j] = INT_MIN; if (clock() - start > timeout) break; } //if (clock() - start > timeout) //break; //cout << clock() - start << endl; } for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (value[i][j] == max_value) { best_i[best_num] = i; best_j[best_num] = j; best_num++; } int random = rand() % best_num; //在所有最⼤value⾥⾯随机选 int decision_x = best_i[random]; int decision_y = best_j[random]; action["x"] = decision_x; action["y"] = decision_y; ret["response"] = action; Json::FastWriter writer; cout << (ret) << endl; //cout << clock() - start << endl; //cout<#include #include #include using namespace std;int MaxDepth = 8; //回形遍历的层数,如果觉得浪费可以设计⼀个函数在前期（已⾏步数）适当减⼩，但后期⼀定要保证等于8，不然可能会导致出错

int start = 0; //时间int timeout = (int)(0.90 * (double)CLOCKS_PER_SEC);int board[9][9] = {0}; //棋盘，⿊⼦1，⽩⼦-1，没有棋⼦是0bool visited_by_air_judge[9][9] = {false}; //在air_judge函数判断某⼀点有⽆⽓时作标记，防⽌重复⽽死循环int dx[4] = {-1, 0, 1, 0}; //⾏位移int dy[4] = {0, -1, 0, 1}; //列位移//打印棋盘，⽤于调试/*void cout_board(){ for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) cout << setw(3) << board[j][i]; cout << endl; } cout << endl;}*///对⼿的colorint opponent_color(int color){ if (color == 1) return -1; else return 1;}//判断点(x,y)是否在棋盘内bool inBoard_judge(int x, int y) { return 0 <= x && x < 9 && 0 <= y && y < 9; }//判断是否有⽓bool air_judge(int x, int y){ visited_by_air_judge[x][y] = true; //标记，表⽰这个位置已经搜过有⽆⽓了 bool flag = false; for (int dir = 0; dir < 4; dir++) { int x_dx = x + dx[dir], y_dy = y + dy[dir]; if (inBoard_judge(x_dx, y_dy)) //界内 { if (board[x_dx][y_dy] == 0) //旁边这个位置没有棋⼦ flag = true; if (board[x_dx][y_dy] == board[x][y] && !visited_by_air_judge[x_dx][y_dy]) //旁边这个位置是没被搜索过的同⾊棋 if (air_judge(x_dx, y_dy)) flag = true; } } return flag;}//判断能否下颜⾊为color的棋bool put_available(int x, int y, int color) //no problem{ if (!inBoard_judge(x, y)) return false; if (board[x][y]) //如果这个点本来就有棋⼦ return false; board[x][y] = color; memset(visited_by_air_judge, 0, sizeof(visited_by_air_judge)); //重置 if (!air_judge(x, y)) //如果下完这步这个点没⽓了,说明是⾃杀步，不能下 { board[x][y] = 0; return false; } for (int i = 0; i < 4; i++) //判断下完这步周围位置的棋⼦是否有⽓ { int x_dx = x + dx[i], y_dy = y + dy[i]; if (inBoard_judge(x_dx, y_dy)) //在棋盘内 { if (board[x_dx][y_dy] && !visited_by_air_judge[x_dx][y_dy]) //对于有棋⼦的位置（标记访问过避免死循环） if (!air_judge(x_dx, y_dy)) //如果导致(x_dx,y_dy)没⽓了，则不能下 { board[x][y] = 0; //回溯 return false; } } } board[x][y] = 0; //回溯 return true;}//估值函数，对当前局⾯进⾏评估，计算颜⾊为color的⼀⽅⽐另⼀⽅可落⼦的位置数⽬多多少（权利值⽐较）int evaluate(int color){ int right = 0; int op_color = opponent_color(color); for (int x = 0; x < 9; x++) { for (int y = 0; y < 9; y++) { if (put_available(x, y, color)) right++; if (put_available(x, y, op_color)) right--; } } return right;}//Alpha剪枝和Beta剪枝+MaxMin搜索int AlphaBeta(int color, int depth, int nAlpha, int nBeta, int op_LastMove_x, int op_LastMove_y){ if (depth == 0) return evaluate(-1); //叶⼦节点返回估值 //还需要继续往下搜索 int now_available_list_x[81] = {0}, now_available_list_y[81] = {0}; //可下位置 int now_available_num = 0; //回型遍历可下的位置，在对局前期能够先遍历对⼿刚刚落⼦的点附近的可⾏点，提⾼搜索效率 for (int level = 1; level <= MaxDepth; level++) //i是往外的层数 { int testMove_x = 0; int testMove_y = 0; //正⽅形左上顶点 testMove_x = op_LastMove_x - level; testMove_y = op_LastMove_y - level; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } //正⽅形左边 //正⽅形左边 for (int i = -level + 1; i < level; i++) { testMove_x = op_LastMove_x - level; testMove_y = op_LastMove_y + i; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } else //⼀条边要么都在board，要么都不在（端点特判） break; } //左下端点 testMove_x = op_LastMove_x - level; testMove_y = op_LastMove_y + level; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } //正⽅形的下边 for (int i = -level + 1; i < level; i++) { int testMove_x = op_LastMove_x + i; int testMove_y = op_LastMove_y + level; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } else break; } //右下端点 testMove_x = op_LastMove_x + level; testMove_y = op_LastMove_y + level; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } //正⽅形的右边 for (int i = level - 1; i > -level; i--) { int testMove_x = op_LastMove_x + level; int testMove_x = op_LastMove_x + level; int testMove_y = op_LastMove_y + i; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } else //⼀条边要么都在board，要么都不在（端点特判） break; } //右上端点 testMove_x = op_LastMove_x + level; testMove_y = op_LastMove_y - level; if (inBoard_judge(testMove_x, testMove_y)) { if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } //正⽅形的上边 for (int i = level - 1; i > -level; i--) { int testMove_x = op_LastMove_x + i; int testMove_y = op_LastMove_y - level; if (inBoard_judge(testMove_x, testMove_y)) if (put_available(testMove_x, testMove_y, color)) { now_available_list_x[now_available_num] = testMove_x; now_available_list_y[now_available_num] = testMove_y; now_available_num++; } } } //胜负已分，返回估值 if (now_available_num == 0) return evaluate(-1); if (color == 1) //判断

节点类型 { //

极⼩值节点 MIN层 int score = INT_MAX; for (int i = 0; i < now_available_num; i++) { board[now_available_list_x[i]][now_available_list_y[i]] = color; //⽣成新节点 int temp_score = AlphaBeta(opponent_color(color), depth - 1, nAlpha, nBeta, now_available_list_x[i], now_available_list_y[i]); //递归搜索⼦节点 board[now_available_list_x[i]][now_available_list_y[i]] = 0; //撤销搜索过的节点 if (temp_score < score) score = temp_score; if (score < nBeta) nBeta = score; //取极⼩值 //if (nAlpha >= nBeta) // break; //alpha剪枝，抛弃后继节点 //没时间了，撤！ //if (clock() - start >= timeout) // return nBeta; } return nBeta; //返回最⼩值 return nBeta; //返回最⼩值 } else { //取极⼤值的节点 MAX层 int score = INT_MIN; for (int i = 0; i < now_available_num; i++) //对每个⼦节点 { board[now_available_list_x[i]][now_available_list_y[i]] = color; //⽣成新节点 int temp_score = AlphaBeta(opponent_color(color), depth - 1, nAlpha, nBeta, now_available_list_x[i], now_available_list_y[i]); //递归搜索⼦节点 board[now_available_list_x[i]][now_available_list_y[i]] = 0; //撤销搜索过的节点 if (temp_score > score) score = temp_score; if (score > nAlpha) nAlpha = score; //取极⼤值 if (nAlpha >= nBeta) break; //nBeta剪枝，抛弃后继节点 //没时间了，快跑！ if (clock() - start >= timeout) return nAlpha; } return nAlpha; //返回最⼤值 }}//end of AlphaBeta pseudocodeint main(){ srand((unsigned)time(0)); string str; int x, y; //

读⼊JSON getline(cin, str); start = clock(); //getline(cin, str); Json::Reader reader; Json::Value input; (str, input); //

分析⾃⼰收到的输⼊和⾃⼰过往的输出，并恢复状态 int turnID = input["responses"].size(); //复原棋盘 for (int i = 0; i < turnID; i++) //下⼀回合，复原上⼀回合的棋局 { x = input["requests"][i]["x"].asInt(), y = input["requests"][i]["y"].asInt(); if (x != -1) board[x][y] = 1; //对⽅棋⼦ //cout << evaluate(-1) << endl; x = input["responses"][i]["x"].asInt(), y = input["responses"][i]["y"].asInt(); if (x != -1) board[x][y] = -1; //我⽅棋⼦ } x = input["requests"][turnID]["x"].asInt(), y = input["requests"][turnID]["y"].asInt(); if (x != -1) board[x][y] = 1; //cout << evaluate(-1) << endl; //cout_board(); //

输出决策JSON Json::Value ret; Json::Value action; //搜索层数增加 //MaxDepth += (int)(0.04 * turnID); //以下是搜索策略:极⼤极⼩算法 //以下是搜索策略:极⼤极⼩算法 int color = -1; //我⽅棋⼦颜⾊ int max_value = INT_MIN; int op_LastMove_x = x, op_LastMove_y = y; //对⼿上⼀步下的位置 int available_list_x[81] = {0}, available_list_y[81] = {0}; //可下位置 int available_num = 0; int best_i[81] = {0}, best_j[81] = {0}, best_num = 0; //如果是⿊棋的第⼀步，那就假设上⼀步⽩棋⾛在左上⾓（这样设置胜率会⾼⼀点点，也可以根据⾃⼰兴趣设置） if (x == -1) op_LastMove_x = 0, op_LastMove_y = 1; //搜索可下位置,回型往外遍历，从最接近对⼿上⼀步的地⽅开始 for (int level = 1; level < 9; level++) //i是往外的层数 { //正⽅形左边 for (int i = -level; i < level; i++) { int testMove_x = op_LastMove_x - level; int testMove_y = op_LastMove_y + i; if (inBoard_judge(testMove_x, testMove_y)) { /* if (testMove_x == 0 && testMove_y == 3) { for (int i = 0; i < 9; i++) { cout << endl; for (int j = 0; j < 9; j++) cout << board[i][j] << ' '; } }*/ if (put_available(testMove_x, testMove_y, color)) { available_list_x[available_num] = testMove_x; available_list_y[available_num] = testMove_y; available_num++; } } } //正⽅形的下边 for (int i = -level; i < level; i++) { int testMove_x = op_LastMove_x + i; int testMove_y = op_LastMove_y + level; if (inBoard_judge(testMove_x, testMove_y)) if (put_available(testMove_x, testMove_y, color)) { available_list_x[available_num] = testMove_x; available_list_y[available_num] = testMove_y; available_num++; } } //正⽅形的右边 for (int i = level; i > -level; i--) { int testMove_x = op_LastMove_x + level; int testMove_y = op_LastMove_y + i; if (inBoard_judge(testMove_x, testMove_y)) if (put_available(testMove_x, testMove_y, color)) { available_list_x[available_num] = testMove_x; available_list_y[available_num] = testMove_y; available_num++; } } //正⽅形的上边 for (int i = level; i > -level; i--) for (int i = level; i > -level; i--) { int testMove_x = op_LastMove_x + i; int testMove_y = op_LastMove_y - level; if (inBoard_judge(testMove_x, testMove_y)) if (put_available(testMove_x, testMove_y, color)) { available_list_x[available_num] = testMove_x; available_list_y[available_num] = testMove_y; available_num++; } } } //在限定时间内挑选出最优解 for (int i = 0; i < available_num; i++) { board[available_list_x[i]][available_list_y[i]] = color; int temp = AlphaBeta(color, MaxDepth, INT_MIN, INT_MAX, op_LastMove_x, op_LastMove_y); if (max_value < temp) { max_value = temp; memset(best_i, 0, sizeof(best_i)); memset(best_j, 0, sizeof(best_j)); best_num = 0; best_i[best_num] = available_list_x[i]; best_j[best_num] = available_list_y[i]; best_num++; } else if (max_value == temp) { best_i[best_num] = available_list_x[i]; best_j[best_num] = available_list_y[i]; best_num++; } board[available_list_x[i]][available_list_y[i]] = 0; if (clock() - start >= timeout) break; //cout << clock() - start << endl; } //在所有最优解⾥⾯随机选 int random = rand() % best_num; int decision_x = best_i[random]; int decision_y = best_j[random]; action["x"] = decision_x; action["y"] = decision_y; ret["response"] = action; Json::FastWriter writer; cout << (ret) << endl; //cout << clock() - start << endl; //cout << max_value << endl; return 0;}蒙特卡洛树搜索（MCTS算法）MCTS算法的优越性在于使⽤了UCB公式，利⽤概率学的知识对“赢⾯更⼤”的点分配更多的模拟机会（启发式搜索），在时间有限的情况下做出⼀点让步，从⽽更快找到“近似最优解”。如果要了解蒙特卡洛树搜索和UCB公式，建议先观看这个视频学习⼀下（众所周知，b站是个学习⽹站）：//不围棋（NoGo)//蒙特卡洛树搜索（MCTS），UCB算法//作者：Hoven Chen#pragma GCC optimize(3)#include "./jsoncpp/json.h"#include #include #include #include #include #include #include #define MAXBranchNum 81using namespace std;int dx[4] = {-1, 0, 1, 0}; //⾏位移int dy[4] = {0, -1, 0, 1}; //列位移bool visited_by_air_judge[9][9] = {false}; //在air_judge函数判断某⼀点有⽆⽓时作标记，防⽌重复⽽死循环//判断是否在棋盘内bool inBoard_judge(int x, int y) { return 0 <= x && x < 9 && 0 <= y && y < 9; }//判断是否有⽓bool air_judge(int board[9][9], int x, int y){ visited_by_air_judge[x][y] = true; //标记，表⽰这个位置已经搜过有⽆⽓了 bool flag = false; for (int dir = 0; dir < 4; ++dir) { int x_dx = x + dx[dir], y_dy = y + dy[dir]; if (inBoard_judge(x_dx, y_dy)) //界内 { if (board[x_dx][y_dy] == 0) //旁边这个位置没有棋⼦ flag = true; if (board[x_dx][y_dy] == board[x][y] && !visited_by_air_judge[x_dx][y_dy]) //旁边这个位置是没被搜索过的同⾊棋 if (air_judge(board, x_dx, y_dy)) flag = true; } } return flag;}//判断能否下颜⾊为color的棋bool put_available(int board[9][9], int x, int y, int color){ if (!inBoard_judge(x, y)) return false; if (board[x][y]) //如果这个点本来就有棋⼦ return false; board[x][y] = color; memset(visited_by_air_judge, 0, sizeof(visited_by_air_judge)); //重置 if (!air_judge(board, x, y)) //如果下完这步这个点没⽓了,说明是⾃杀步，不能下 { board[x][y] = 0; return false; } for (int i = 0; i < 4; ++i) //判断下完这步周围位置的棋⼦是否有⽓ { int x_dx = x + dx[i], y_dy = y + dy[i]; if (inBoard_judge(x_dx, y_dy)) //在棋盘内 { if (board[x_dx][y_dy] && !visited_by_air_judge[x_dx][y_dy]) //对于有棋⼦的位置（标记访问过避免死循环） if (!air_judge(board, x_dx, y_dy)) //如果导致(x_dx,y_dy)没⽓了，则不能下 { board[x][y] = 0; //回溯 return false; } } } board[x][y] = 0; //回溯 return true;}//找到能下的位置,result[9][9]表⽰各个位置的情况，0不能下，1可以下；该函数返回值是可下的位置数，也即result==1的点数int getValidPositions(int board[9][9], int result[9][9]){ memset(result, 0, MAXBranchNum * 4); int right = 0; for (int x = 0; x < 9; ++x) { for (int y = 0; y < 9; ++y) { if (put_available(board, x, y, 1)) { right++; result[x][y] = 1; } } } return right;}//关于类如果有不清楚的知识点建议访问菜鸟教程：//[类的相关知识](/cplusplus/)//类定义树节点class treeNode{public: treeNode *parent; //⽗节点 treeNode *children[MAXBranchNum]; //⼦节点 int board[9][9]; int childrenAction[MAXBranchNum][2]; int childrenCount; int childrenCountMax; double value; //该节点的总value int n; //当前节点探索次数，UCB中的ni double UCB; //当前节点的UCB值 int *countPointer; //总节点数的指针 //构造函数 treeNode(int parentBoard[9][9], int opp_action[2], treeNode *parentPointer, int *countp) //构造函数 treeNode *p是⽗类指针, int *countp应该是总探索次数的指针 { for (int i = 0; i < 9; ++i) //把棋盘反过来，要落⼦⽅是1

，对⼿是-1 { for (int j = 0; j < 9; ++j) { board[i][j] = -parentBoard[i][j]; } } if (opp_action[0] >= 0 && opp_action[0] < 9 && opp_action[1] >= 0 && opp_action[1] < 9) board[opp_action[0]][opp_action[1]] = -1; parent = parentPointer; value = 0; n = 0; childrenCount = 0; //已经拓展的⼦节点数 countPointer = countp; //count的指针 evaluate(); //计算能下的位置,修改了childrenCountMax、childrenAction } treeNode *treeRules() //搜索法则 { //如果没有位置下了（终局） if (childrenCountMax == 0) { return this; //到达终局当前叶节点 } //如果是叶节点，Node Expansion，拓展下⼀层节点 if (childrenCountMax > childrenCount) { treeNode *newNode = new treeNode(board, childrenAction[childrenCount], this, countPointer); //拓展⼀个⼦节点 children[childrenCount] = newNode; childrenCount++; //已拓展的⼦节点数++ return newNode; } //计算当前节点的每个⼦节点的UCB值（点亮某个节点） for (int i = 0; i < childrenCount; ++i) { children[i]->UCB = children[i]->value / double(children[i]->n) + 0.2 * sqrt(log(double(*countPointer)) / double(children[i]->n)); //UCB公式 } int bestChild = 0; double maxUCB = 0; //找出所有⼦节点中UCB值最⼤的⼦节点 for (int i = 0; i < childrenCount; ++i) { if (maxUCB < children[i]->UCB) { bestChild = i; maxUCB = children[i]->UCB; } } return children[bestChild]->treeRules(); //对UCB最⼤的⼦节点进⾏下⼀层搜索 } //模拟 double simulation() { int board_opp[9][9]; //对⼿棋盘 int res[9][9]; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { board_opp[i][j] = -board[i][j]; } } int x = getValidPositions(board, res); //落⼦⽅可下位置数 int y = getValidPositions(board_opp, res); //⾮落⼦⽅可下位置数 return x - y; } void backup(double deltaValue) //回传估值,从当前叶节点以及往上的每⼀个⽗节点都加上估值 { treeNode *node = this; int side = 0; while (node != nullptr) //当node不是根节点的⽗节点时 { if (side == 1) //落⼦⽅ { node->value += deltaValue; side--; } else //⾮落⼦⽅ { node->value -= deltaValue; node->value -= deltaValue; side++; } node->n++; //当前节点被探索次数++ node = node->parent; } }private: void evaluate() //计算能下的位置,修改了childrenCountMax、childrenAction { int result[9][9]; int validPositionCount = getValidPositions(board, result); //能下的位置数 int validPositions[MAXBranchNum]; //能下的位置坐标 int availableNum = 0; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (result[i][j]) { validPositions[availableNum] = i * 9 + j; //可下的位置 availableNum++; //可下的位置数 } } } childrenCountMax = validPositionCount; //总共能下的位置数 for (int i = 0; i < validPositionCount; ++i) { childrenAction[i][0] = validPositions[i] / 9; childrenAction[i][1] = validPositions[i] % 9; } }};//类定义结束 end of class definitionint main(){ int count = 0; //总计算的节点数（总探索次数，UCB中的N） int board[9][9] = {0}; srand(clock()); string str; getline(cin, str); int start = clock(); int timeout = (int)(0.98 * (double)CLOCKS_PER_SEC); Json::Reader reader; Json::Value input; (str, input); int turnID = input["responses"].size(); int x, y; for (int i = 0; i < turnID; ++i) { x = input["requests"][i]["y"].asInt(), y = input["requests"][i]["x"].asInt(); if (x != -1) board[x][y] = 1; x = input["responses"][i]["y"].asInt(), y = input["responses"][i]["x"].asInt(); if (x != -1) board[x][y] = -1; } x = input["requests"][turnID]["y"].asInt(), y = input["requests"][turnID]["x"].asInt(); int opp_action[2] = {x, y}; //对⾯上⼀步⾛了哪⾥ treeNode rootNode(board, opp_action, nullptr, &count); //创建根节点，根节点的⽗节点为空 while (clock() - start < timeout) { { count++; //计算的节点数++ treeNode *node = les(); //拓展⼀次，node指向的是⼀次拓展的叶节点 double result = node->simulation(); //结果估值 node->backup(result); } int bestChildren[MAXBranchNum] = {0}; //所有最优⼦节点的序号 int bestChildrenNum = 0; //最优⼦节点个数 int maxValue = INT_MIN; //当前最优⼦节点分数 for (int i = 0; i < enCount; ++i) { if (maxValue < en[i]->value) { //重置 memset(bestChildren, 0, sizeof(bestChildren)); bestChildrenNum = 0; bestChildren[bestChildrenNum++] = i; maxValue = en[i]->value; } else if (maxValue == en[i]->value) { bestChildren[bestChildrenNum++] = i; } } int random = rand() % bestChildrenNum; //在所有最优中任选⼀个 int *bestAction = enAction[bestChildren[random]]; //最优⼦节点对应⾛法 Json::Value ret; Json::Value action; action["x"] = bestAction[1]; action["y"] = bestAction[0]; ret["response"] = action; char buffer[4096]; sprintf(buffer, "搜索节点数:%d,平均value:%.5f,⽤时：%.3f", count, (((double)(en[bestChildren[random]]->value)) / ((double)en[bestChildren[random]]->n) + 1.0) * 0.5, (double)(clock() - start) / 1000); ret["debug"] = buffer; Json::FastWriter writer; cout << (ret) << endl;}以上就是关于《不围棋》的代码，欢迎⼤家在评论区批评指正！