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>
using namespace std;
int minx=14,miny=14,maxx=0,maxy=0;
void color(int x) {
switch(x) {
case 1:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED );
break;
case 2:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_BLUE );
break;
case 3:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_GREEN);
break;
case 4:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED |FOREGROUND_BLUE );
break;
case 5:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED |FOREGROUND_GREEN);
break;
case 6:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_BLUE |FOREGROUND_GREEN);
break;
case 7:
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;
}
}
class GameTree {
public:
class Node {
public:
enum State :uint8_t/*节省内存*/ { SPACE, BLACK, WHITE };
private:
friend class GameTree;
static const uint8_t BOARDSIZE = 15;
int value;//叶节点表示估价函数的结果，MAX节点表示α值，MIN节点表示β值
int evaluateValue;//估价函数计算的结果，用于优化
unsigned short depth;//深度
uint8_t lastX, lastY;//上一次落子的xy坐标
Node* father;//父亲节点
std::vector<Node*> children;//子节点
State **board;//棋盘
int Evaluate()const { //估价函数
static const auto EvaluateSome = [](State **board, uint8_t beginX, uint8_t endX, uint8_t beginY, uint8_t endY) {
static const auto EvaluateList = [](const std::array<State, 5>& v) { //假定自己是白方
//判断颜色并记录棋子个数
State lastColor = SPACE;
uint8_t bitList = 0;//将棋链以二进制形式表示，如01101
for (State i : v) {
if (i != lastColor) {
if (lastColor == SPACE)//遇到的第一个棋子
lastColor = i;
else//有不同颜色的棋子
return 0;
}
if (i != SPACE)
bitList = bitList * 2 + 1;
}
int result = 0;
switch (bitList) {
case 0://00000
result = 0;
break;
case 1://00001
case 2://00010
case 4://00100
case 8://01000
case 16://10000
result = 5;
break;
case 3://00011
case 24://11000
result = 80;
break;
case 6://00110
case 12://01100
result = 100;
break;
case 10://01010
result = 80;
break;
case 5://00101
case 20://10100
result = 60;
break;
case 9://01001
case 18://10010
result = 20;
break;
case 17://10001
result = 10;
break;
case 7://00111
case 28://11100
result = 800;
break;
case 14://01110
result = 1000;
break;
case 13://01101
case 26://11010
case 11://01011
case 22://10110
result = 800;
break;
case 19://10011
case 21://10101
case 25://11001
result = 600;
break;
case 15://01111
case 30://11110
result = 10000;
break;
case 29://11101
case 23://10111
result = 8000;
break;
case 27://11011
result = 6000;
break;
case 31://11111
return 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];
const int 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];
const int 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];
const int 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];
const int 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;
const int 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;
}
inline int GetEvaluateValue()const {
return evaluateValue;
}
inline bool IsMaxNode()const { //默认计算机后手
return depth & 1u;//相当于depth%2
}
void Search(unsigned short _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) {
new Node(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();
}
void DeleteAllButThis() {
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;
}
inline bool IsFull()const {
return depth == BOARDSIZE * BOARDSIZE;
}
inline State GetWinner()const {
if (this->value == INT_MAX) {
return Node::WHITE;
} else if (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;
const unsigned short maxDepth;
public:
GameTree(unsigned short _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 = new Node(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();
}
void Run() {
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 = new Node(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 <<" ";
else if (i==0 && j>=10)
cout <<j <<" ";
else if (j==0 && i<10)
cout <<" " <<i <<" ";
else if (j==0 && i>=10)
cout <<i <<" ";
else if (root->board[i-1][j-1] == Node::SPACE) {
color(5);
std::cout << "十 ";
} else if (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;
} else if (root->value == INT_MIN) {
std::cout << "玩家胜利！";
break;
} else if (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 <<" ";
else if (i==0 && j>=10)
cout <<j <<" ";
else if (j==0 && i<10)
cout <<" " <<i <<" ";
else if (j==0 && i>=10)
cout <<i <<" ";
else if (root->board[i-1][j-1] == Node::SPACE) {
color(5);
std::cout << "十 ";
} else if (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;
} else if (root->value == INT_MIN) {
std::cout << "玩家胜利！";
break;
} else if (root->IsFull()) { //不能用root->value==0判断平局，因为平局一定为0，但为0不一定平局
std::cout << "平局！";
break;
}
}
}
~GameTree() {
delete root;
}
};
int main() {
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 <<" ";
else if (i==0 && j>=10)
cout <<j <<" ";
else if (j==0 && i<10)
cout <<" " <<i <<" ";
else if (j==0 && i>=10)
cout <<i <<" ";
else {
color(5);
std::cout << "十 ";
}
}
std::cout << '\n';
}
GameTree(4).Run(); //较为智能的模式，可改为3、2（不智能模式），以及5（超级智能模式，但是特别慢）
return 0;
}
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 文件中输出。
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
代码格式化
点击 Astyle-> 格式化当前文件 或 按 Ctrl+Shift+A 进行代码格式化。
美化
字体
点击工具 -> 编辑器选项，然后选择 “显示” 选项卡。
文章来源：https://www.toymoban.com/news/detail-745755.html
主题
点击工具 -> 编辑器选项，然后选择 “语法” 选项卡，可以使用预设主题，也可以自行调整。
文章来源地址https://www.toymoban.com/news/detail-745755.html
到了这里，关于AI五子棋——超强改进版本的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
