卖货网站平台,WordPress添加精华贴图,中国建设银行吉林省分行官网站,揭阳高端网站建设价格AI五子棋的改进版本来啦~~ 我们发现#xff0c;原版的AI五子棋如果调成4的话#xff0c;非常之慢#xff01;#xff01;下面给出原版的链接
AI五子棋#xff08;原版本#xff09;
因此我对其进行了改进#xff0c;由于正常人下五子棋不会东下一颗棋#xff0c;西下…AI五子棋的改进版本来啦~~ 我们发现原版的AI五子棋如果调成4的话非常之慢下面给出原版的链接
AI五子棋原版本
因此我对其进行了改进由于正常人下五子棋不会东下一颗棋西下一颗棋。 因此我们可以大幅度缩小搜索的范围只要搜索已经下了的棋子的周围就可以了2×2或3×3。 下面的程序会是2×2的4尽管还是有点慢但相比原程序快很多。
另外关于人机强度、人机耗时的修改我放在原版的链接里了
我们可以做一个对比让这两个程序同时运行4会发现改进后的程序用了1:17下了一步但是原版的用了3:044GB内存i3cpu情况下
#includeiostream
#includevector
#includearray
#includefstream
#includealgorithm
#include bits/stdc.h
#include windows.h
using namespace std;
int minx14,miny14,maxx0,maxy0;
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::vectorNode* 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::arrayState, 5 v) { //假定自己是白方//判断颜色并记录棋子个数State lastColor SPACE;uint8_t bitList 0;//将棋链以二进制形式表示如01101for (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://00000result 0;break;case 1://00001case 2://00010case 4://00100case 8://01000case 16://10000result 5;break;case 3://00011case 24://11000result 80;break;case 6://00110case 12://01100result 100;break;case 10://01010result 80;break;case 5://00101case 20://10100result 60;break;case 9://01001case 18://10010result 20;break;case 17://10001result 10;break;case 7://00111case 28://11100result 800;break;case 14://01110result 1000;break;case 13://01101case 26://11010case 11://01011case 22://10110result 800;break;case 19://10011case 21://10101case 25://11001result 600;break;case 15://01111case 30://11110result 10000;break;case 29://11101case 23://10111result 8000;break;case 27://11011result 6000;break;case 31://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::arrayState, 5v;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::arrayState, 5v;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::arrayState, 5v;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::arrayState, 5v;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;elsebeginX lastX - 5;endX lastX 5;if (endX BOARDSIZE)endX BOARDSIZE;if (lastY 5)beginY 0;elsebeginY 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(maxx2,14); i) {for (int j max(miny-2,0); j min(maxy2,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);minxmin(minx,i);maxxmax(maxx,i);minymin(miny,j);maxymax(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::pairuint8_t, uint8_tAIGetNextPos(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));minxmin(minx,y);maxxmax(maxx,y);minymin(miny,x);maxymax(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 (i0 j10)cout j ;else if (i0 j10)cout j ;else if (j0 i10)cout i ;else if (j0 i10)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-value0判断平局因为平局一定为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 (i0 j10)cout j ;else if (i0 j10)cout j ;else if (j0 i10)cout i ;else if (j0 i10)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-value0判断平局因为平局一定为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 (i0 j10)cout j ;else if (i0 j10)cout j ;else if (j0 i10)cout i ;else if (j0 i10)cout i ;else {color(5);std::cout 十 ;}}std::cout \n;}GameTree(4).Run(); //较为智能的模式可改为3、2不智能模式以及5超级智能模式但是特别慢 return 0;
}
