AI五子棋的改进版本来啦~~
我们发现，原版的AI五子棋如果调成4的话，非常之慢！！下面给出原版的链接
AI五子棋（原版本）
因此我对其进行了改进，由于正常人下五子棋不会东下一颗棋，西下一颗棋。
因此我们可以大幅度缩小搜索的范围，只要搜索已经下了的棋子的周围就可以了（2×2或3×3）。
下面的程序会是2×2的4，尽管还是有点慢，但相比原程序快很多。
另外，关于人机强度、人机耗时的修改，我放在原版的链接里了
我们可以做一个对比：让这两个程序同时运行4，会发现：改进后的程序用了1:17下了一步，但是原版的用了3:04（4GB内存，i3cpu情况下）
#include<iostream>#include<vector>#include<array>#include<fstream>#include<algorithm>#include<bits/stdc++.h>#include<windows.h>usingnamespace std;int minx=14,miny=14,maxx=0,maxy=0;voidcolor(int x){switch(x){case1:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED );break;case2:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_BLUE );break;case3:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_GREEN);break;case4:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED |FOREGROUND_BLUE );break;case5:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED |FOREGROUND_GREEN);break;case6:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_BLUE |FOREGROUND_GREEN);break;case7:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_GREEN|FOREGROUND_BLUE |FOREGROUND_RED);break;default:SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_GREEN|FOREGROUND_BLUE |FOREGROUND_RED);break;}}classGameTree{public:classNode{public:enumState:uint8_t/*节省内存*/{ SPACE, BLACK, WHITE };private:friendclassGameTree;staticconstuint8_t BOARDSIZE =15;int value;//叶节点表示估价函数的结果，MAX节点表示α值，MIN节点表示β值int evaluateValue;//估价函数计算的结果，用于优化unsignedshort depth;//深度uint8_t lastX, lastY;//上一次落子的xy坐标
Node* father;//父亲节点
std::vector<Node*> children;//子节点
State **board;//棋盘intEvaluate()const{//估价函数staticconstauto EvaluateSome =[](State **board,uint8_t beginX,uint8_t endX,uint8_t beginY,uint8_t endY){staticconstauto EvaluateList =[](const std::array<State,5>& v){//假定自己是白方//判断颜色并记录棋子个数
State lastColor = SPACE;uint8_t bitList =0;//将棋链以二进制形式表示，如01101for(State i : v){if(i != lastColor){if(lastColor == SPACE)//遇到的第一个棋子
lastColor = i;else//有不同颜色的棋子return0;}if(i != SPACE)
bitList = bitList *2+1;}int result =0;switch(bitList){case0://00000
result =0;break;case1://00001case2://00010case4://00100case8://01000case16://10000
result =5;break;case3://00011case24://11000
result =80;break;case6://00110case12://01100
result =100;break;case10://01010
result =80;break;case5://00101case20://10100
result =60;break;case9://01001case18://10010
result =20;break;case17://10001
result =10;break;case7://00111case28://11100
result =800;break;case14://01110
result =1000;break;case13://01101case26://11010case11://01011case22://10110
result =800;break;case19://10011case21://10101case25://11001
result =600;break;case15://01111case30://11110
result =10000;break;case29://11101case23://10111
result =8000;break;case27://11011
result =6000;break;case31://11111return lastColor == WHITE ? INT_MAX : INT_MIN;}return lastColor == WHITE ? result :-result;//对手返回负值，我方返回正值};int result =0;for(uint8_t i = beginX; i < endX; i++){//分别从四个方向判断for(uint8_t j = beginY; j < endY; j++){if(j +4< endY){
std::array<State,5>v;for(uint8_t k =0; k <5; k++)
v[k]= board[i][j + k];constint t =EvaluateList(v);if(t == INT_MAX || t == INT_MIN)//决出胜负直接返回return t;
result += t;}if(i +4< endX){
std::array<State,5>v;for(uint8_t k =0; k <5; k++)
v[k]= board[i + k][j];constint t =EvaluateList(v);if(t == INT_MAX || t == INT_MIN)//决出胜负直接返回return t;
result += t;}if(i +4< endX && j +4< endY){
std::array<State,5>v;for(uint8_t k =0; k <5; k++)
v[k]= board[i + k][j + k];constint t =EvaluateList(v);if(t == INT_MAX || t == INT_MIN)//决出胜负直接返回return t;
result += t;}if(i +4< endX && j >=4){
std::array<State,5>v;for(uint8_t k =0; k <5; k++)
v[k]= board[i + k][j - k];constint t =EvaluateList(v);if(t == INT_MAX || t == INT_MIN)//决出胜负直接返回return t;
result += t;}}}return result;};uint8_t beginX, endX, beginY, endY;if(lastX <=5)
beginX =0;else
beginX = lastX -5;
endX = lastX +5;if(endX > BOARDSIZE)
endX = BOARDSIZE;if(lastY <=5)
beginY =0;else
beginY = lastY -5;
endY = lastY +5;if(endY > BOARDSIZE)
endY = BOARDSIZE;constint t =EvaluateSome(board, beginX, endX, beginY, endY);if(t == INT_MAX || t == INT_MIN)//决出胜负直接返回return t;return t -EvaluateSome(father->board, beginX, endX, beginY, endY)+ father->evaluateValue;}public://非根节点的构造函数Node(Node* nf,uint8_t x,uint8_t y):father(nf),lastX(x),lastY(y),depth(nf->depth +1),value(0),board(new State*[BOARDSIZE]){
father->children.push_back(this);for(int i =0; i < BOARDSIZE;++i){
board[i]=new State[BOARDSIZE];memcpy(board[i], father->board[i], BOARDSIZE *sizeof(State));}
board[lastX][lastY]=IsMaxNode()? BLACK : WHITE;
evaluateValue =Evaluate();for(int i =0; i < BOARDSIZE;++i){delete[] board[i];}delete[] board;
board =nullptr;}//根节点的构造函数Node(int _depth,uint8_t x,uint8_t y):father(nullptr),depth(_depth),lastX(x),lastY(y),value(0),evaluateValue(0),board(new State*[BOARDSIZE]){for(int i =0; i < BOARDSIZE;++i){
board[i]=new State[BOARDSIZE];memset(board[i],0, BOARDSIZE *sizeof(State));}
board[x][y]=IsMaxNode()? BLACK : WHITE;}inlineintGetEvaluateValue()const{return evaluateValue;}inlineboolIsMaxNode()const{//默认计算机后手return depth &1u;//相当于depth%2}voidSearch(unsignedshort _depth){if(_depth ==0||this->evaluateValue == INT_MAX ||this->evaluateValue == INT_MIN){this->value =this->evaluateValue;return;}bool created =false;//记录是否new出新的Node，如果没有就不用排序了。if(!board){//不是根节点
board =new State *[BOARDSIZE];for(int i =0; i < BOARDSIZE;++i){
board[i]=new State[BOARDSIZE];memcpy(board[i], father->board[i], BOARDSIZE *sizeof(State));}
board[lastX][lastY]=IsMaxNode()? BLACK : WHITE;}for(int i =max(minx-2,0); i <min(maxx+2,14); i++){for(int j =max(miny-2,0); j <min(maxy+2,14); j++){if(!board[i][j]){bool flag =false;if(_depth >=2){//若剩余深度小于2，则下一层肯定没有搜索过for(Node* child :this->children){if(child->lastX == i && child->lastY == j){//已经被搜索过
flag =true;break;}}}if(!flag){newNode(this, i, j);
minx=min(minx,i);
maxx=max(maxx,i);
miny=min(miny,j);
maxy=max(maxy,j);
created =true;}}}}if(IsMaxNode()){this->value = INT_MIN;if(created){
std::sort(this->children.begin(),this->children.end(),[](Node* a, Node* b){return a->GetEvaluateValue()> b->GetEvaluateValue();});//按照估价从大到小排序，增加剪枝的概率}}else{this->value = INT_MAX;if(created){
std::sort(this->children.begin(),this->children.end(),[](Node* a, Node* b){return a->GetEvaluateValue()< b->GetEvaluateValue();});//按照估价从小到大排序，增加剪枝的概率}}auto ReleaseMemory =[this]{if(father){//不是根节点for(int i =0; i < BOARDSIZE;++i){delete[] board[i];}delete[] board;
board =nullptr;}};for(Node* child :this->children){
child->Search(_depth -1);//α - β 剪枝if(IsMaxNode()){if(child->value >this->value){this->value = child->value;if(this->father &&this->value >=this->father->value &&this!=this->father->children.front()){ReleaseMemory();return;//剪枝}}}else{//MIN节点if(child->value <this->value){this->value = child->value;if(this->father &&this->value <=this->father->value &&this!=this->father->children.front()){ReleaseMemory();return;//剪枝}}}}ReleaseMemory();}voidDeleteAllButThis(){if(!father->board)//父节点不是根节点throw std::invalid_argument("this->father必须是根节点！");for(Node* n : father->children){if(n !=this)delete n;}
board =new State *[BOARDSIZE];for(int i =0; i < BOARDSIZE;++i){
board[i]=new State[BOARDSIZE];memcpy(board[i], father->board[i], BOARDSIZE *sizeof(State));delete[] father->board[i];}delete[] father->board;
board[lastX][lastY]=IsMaxNode()? BLACK : WHITE;free(father);//避免调用析构函数
father =nullptr;}inlineboolIsFull()const{return depth == BOARDSIZE * BOARDSIZE;}inline State GetWinner()const{if(this->value == INT_MAX){return Node::WHITE;}elseif(this->value == INT_MIN){return Node::BLACK;}return Node::SPACE;}~Node(){if(board){for(int i =0; i < BOARDSIZE;++i){delete[] board[i];}delete[] board;}for(Node* n : children){delete n;}}};private:
Node* root;constunsignedshort maxDepth;public:GameTree(unsignedshort _maxDepth):root(nullptr),maxDepth(_maxDepth){if(_maxDepth <2)throw std::invalid_argument("最大层数必须大于等于2！");}
std::pair<uint8_t,uint8_t>AIGetNextPos(uint8_t x,uint8_t y){if(root){for(Node* node : root->children){//进入用户选择的分支if(node->lastX == x && node->lastY == y){
node->DeleteAllButThis();
root = node;break;}}}else{//第一次开局
root =newNode(1, x, y);}
root->Search(maxDepth);if(root->IsFull())return std::make_pair(19,19);for(Node* node : root->children){//选择分值最大的if(node->value == root->value){
node->DeleteAllButThis();
root = node;break;}}return std::make_pair(root->lastX, root->lastY);}
Node::State GetWinner()const{return root->GetWinner();}voidRun(){while(1){int x, y;do{color(7);
std::cout <<"输入x,y坐标";color(3);
std::cin >> y >> x;
y-=1;
x-=1;}while(x <0|| y <0|| x >=15|| y >=15||(root && root->board[x][y]!= Node::SPACE));
minx=min(minx,y);
maxx=max(maxx,y);
miny=min(miny,x);
maxy=max(maxy,x);if(root){for(Node* node : root->children){//进入用户选择的分支if(node->lastX == x && node->lastY == y){
node->DeleteAllButThis();
root = node;break;}}}else{//第一次开局
root =newNode(1, x, y);}system("cls");for(int i =0; i <=15; i++){for(int j =0; j <=15; j++){color(6);if(i==0&& j<10)
cout <<" "<<j <<" ";elseif(i==0&& j>=10)
cout <<j <<" ";elseif(j==0&& i<10)
cout <<" "<<i <<" ";elseif(j==0&& i>=10)
cout <<i <<" ";elseif(root->board[i-1][j-1]== Node::SPACE){color(5);
std::cout <<"十 ";}elseif(root->board[i-1][j-1]== Node::BLACK){color(2);
std::cout <<"○ ";}else{color(7);
std::cout <<"○ ";}}
std::cout <<'\n';}
root->Search(maxDepth);if(root->value == INT_MAX){
std::cout <<"电脑胜利！";break;}elseif(root->value == INT_MIN){
std::cout <<"玩家胜利！";break;}elseif(root->IsFull()){//不能用root->value==0判断平局，因为平局一定为0，但为0不一定平局
std::cout <<"平局！";break;}for(Node* node : root->children){//选择分值最大的if(node->value == root->value){
node->DeleteAllButThis();
root = node;break;}}system("cls");for(int i =0; i <=15; i++){for(int j =0; j <=15; j++){color(6);if(i==0&& j<10)
cout <<" "<<j <<" ";elseif(i==0&& j>=10)
cout <<j <<" ";elseif(j==0&& i<10)
cout <<" "<<i <<" ";elseif(j==0&& i>=10)
cout <<i <<" ";elseif(root->board[i-1][j-1]== Node::SPACE){color(5);
std::cout <<"十 ";}elseif(root->board[i-1][j-1]== Node::BLACK){color(2);
std::cout <<"○ ";}else{color(7);
std::cout <<"○ ";}}
std::cout <<'\n';}if(root->value == INT_MAX){
std::cout <<"电脑胜利！";break;}elseif(root->value == INT_MIN){
std::cout <<"玩家胜利！";break;}elseif(root->IsFull()){//不能用root->value==0判断平局，因为平局一定为0，但为0不一定平局
std::cout <<"平局！";break;}}}~GameTree(){delete root;}};intmain(){
cout <<"\n\n\n\n\n\n ";color(6);Sleep(1000);
cout <<"游";Sleep(1000);
cout <<"戏";Sleep(1000);
cout <<"开";Sleep(1000);
cout <<"始";Sleep(1000);
cout <<"!";Sleep(2000);system("cls");for(int i =0; i <=15; i++){for(int j =0; j <=15; j++){color(6);if(i==0&& j<10)
cout <<" "<<j <<" ";elseif(i==0&& j>=10)
cout <<j <<" ";elseif(j==0&& i<10)
cout <<" "<<i <<" ";elseif(j==0&& i>=10)
cout <<i <<" ";else{color(5);
std::cout <<"十 ";}}
std::cout <<'\n';}GameTree(4).Run();//较为智能的模式，可改为3、2（不智能模式），以及5（超级智能模式，但是特别慢） return0;}
c++介绍
Dev-C++ 是一套用于开发 C/C++ 程序的自由的集成开发环境（IDE），并以 GPL 作为分发许可，使用 MinGW 及 GDB 作为编译系统与调试系统。Dev-C++ 运行在 Microsoft Windows 下。
Dev-C++ 的优点在于界面简洁友好，安装便捷，支持单文件编译，因此成为了许多入门 OI 选手以及 C++ 语言初学者的首选。在 NOIP 中，提供 Windows 作为比赛系统的省份一般预置 Dev-C++。
Dev-C++ 起源于 Colin Laplace 编写的 Bloodshed Dev-C++。该版本自 2005 年 2 月 22 日停止更新。2006 年，Dev-C++ 主要开发者 Colin Laplace 曾经对此作出了解释：「因忙于现实生活的事务，没有时间继续 Dev-C++ 的开发。」
Orwell Dev-C++ 是 Dev-C++ 的一个衍生版本，由独立程序员 Orwell (Johan Mes) 开发并维护。其对原版 Dev-C++ 进行了错误修正，并更新了编译器版本。一般而言，Dev-C++ 5.x 均为 Orwell Dev-C++。其最后一次更新于 2015 年，版本为 5.11。
Embarcadero Dev-C++1是 Bloodshed Dev-C++ 和 Orwell Dev-C++ 的继任者。2020 年，Embarcadero 赞助并接手了原有的 Dev-C++ 项目，继续开发。Embarcadero Dev-C++ 加入了对高 DPI 的支持，更新了编译器以加入更新版本的 C++ 标准支持，以及暗色模式。
以上的 Dev-C++ 分发都被认为是「官方的」。此外，在 2015 年 Orwell Dev-C++ 停止更新后，因为教学需要，一位来自中国的个人开发者 royqh1979 决定继续开发他的 Dev-C++ 个人分支，命名为小熊猫 Dev-C++2，集成了智能提示和高版本的 MinGW64，非常便于国内的个人使用和学习。
小熊猫 Dev-C++ 6.7.5 版本发布后，作者使用 qt5 开发了全新的小熊猫 C++3，可在 windows、linux 和 macos 等系统下原生运行。小熊猫 C++ 的界面与 Dev-C++ 相似，除了提供和 Dev-C++ 相似但更加完善的单文件编译、调试、语法高亮、搜索/替换等功能外，还提供了诸如 暗色主题、代码智能提示、变量/函数重命名、切换/自动识别文件编码 等现代 IDE 常见的基本功能。此外小熊猫 C++ 还具备与 CP Editor 类似的试题集功能，可以自行编写或 从常见的 OJ 竞赛网站上下载试题样例，自动运行和测试程序。
使用教程
常用快捷键
文件部分
- Ctrl + N: 创建源代码
- Ctrl + O: 打开文件
- Ctrl + W: 关闭文件
- Ctrl + P: 打印文件
格式部分
- **Ctrl + /**：注释和取消注释
- Tab: 缩进
- Shift + Tab: 取消缩进
行操作
- Ctrl + E: 复制行
- Ctrl + D: 删除行
- Ctrl + Shift + Up: 向上移动
- Ctrl + Shift + Down: 向下移动
跳转部分
- Ctrl + F: 搜索
- Ctrl + R: 替换
- F3: 搜索下一个
- Shift + F3: 搜索上一个
- Ctrl + G: 到指定行号
- Shift + Ctrl + G: 到指定函数
- Ctrl + [1 ~ 9]: 设置书签
- Alt + [1 ~ 9]: 跳转书签
显示部分
- Ctrl + 滚轮：字号放大或缩小
- Ctrl + F11: 全屏或恢复
运行部分
- F9: 只编译
- F10: 只运行
- F11: 编译并运行
- F12: 全部重新编译
调试部分
- F2: 转到断点
- F4: 设置断点或取消
- F5: 调试运行
- F6: 停止
- F7: 逐步调试
调试流程
- 将编译器配置设定为 TDM-GCC 4.9.2 64-bit Debug
- 按 F4 设置或取消调试断点
- 将光标放置在变量上，按 Alt + A 向调试窗口添加监控变量
- 按 F5 启动调试
- 按 F7 或 Alt + N 逐步调试
- 按 Alt + S 跳至下一个调试断点
- 按 F6 停止调试
扩展
增加编译选项
点击工具 -> 编译选项，然后选择 “代码生成/优化” 选项卡，下面介绍我自己常用的几个编译选项。
开启优化
优化代码运行时间或占用空间。
选择 “代码生成” 子选项卡中的 “优化级别（-Ox）” 选项标签。
更换语言标准
使用新语言特性或试图让代码在旧标准下编译。
选择 “代码生成” 子选项卡中的 “语言标准（-std）” 选项标签。
显示最多警告信息
查错小助手。
选择 “代码警告” 子选项卡中的 “显示最多警告信息（-Wall）” 选项标签。
生成调试信息
当显示 “项目没有调试信息，您想打开项目调试选项并重新生成吗？” 点击后闪退或想使用调试功能时需开启此功能。
选择 “连接器” 子选项卡中的 “产生调试信息” 选项标签。
编译小 trick
点击工具 -> 编译选项，然后选择 “编译器” 选项卡，接下来介绍几个常用 trick。
开大栈
防止 DFS 爆系统栈之类的情况出现。
在 “连接器命令行加入以下命令” 中加入 -Wl,–stack=128000000 命令。
此命令将栈开到了约 128MB 的大小，有需要可以自行增加。
定义宏
方便本地评测使用文件输入输出或作其他用途。
在 “连接器命令行加入以下命令” 中加入 -D[String] 命令。
其中 [String] 改为你需要的宏名。
如图，当开启编译选项后便可将以下代码从 test.in 文件读入数据并在 test.out 文件中输出。
#ifdefLOCALfreopen("test.in","r",stdin);freopen("test.out","w",stdout);#endif
代码格式化
点击 Astyle-> 格式化当前文件 或 按 Ctrl+Shift+A 进行代码格式化。
美化
字体
点击工具 -> 编辑器选项，然后选择 “显示” 选项卡。
主题
点击工具 -> 编辑器选项，然后选择 “语法” 选项卡，可以使用预设主题，也可以自行调整。
本文转载自: https://blog.csdn.net/DUXS11/article/details/132149850
版权归原作者 Sirius·Black 所有， 如有侵权，请联系我们删除。
版权归原作者 Sirius·Black 所有， 如有侵权，请联系我们删除。