C++基于EasyX的AI五子棋源码+项目说明+代码注释+exe可执行程序(课程作业).zip

#include "chessai.h" #include<iostream> #include<string> #include<memory.h> #include<graphics.h> #include<set> #include<deque> #include<vector> #include<windows.h> using namespace std; //全局变量 int tuple6type[4][4][4][4][4][4]{};//棋型辨识数组,0无子,1黑子,2白子,3边界 /*工具函数*/ int evaluate(int board[15][15], int(&stat)[17])//stat返回某棋面中17种棋型数量;局面输赢可以通过函数返回值返回 { int A[17][17];//包括边界的虚拟大棋盘,board[i][j]=A[i-1][j-1],3表示边界 for (int i = 0; i < 17; ++i)A[i][0] = 3; for (int i = 0; i < 17; ++i)A[i][16] = 3; for (int j = 0; j < 17; ++j)A[0][j] = 3; for (int j = 0; j < 17; ++j)A[16][j] = 3; for (int i = 0; i < 15; ++i) for (int j = 0; j < 15; ++j) A[i + 1][j + 1] = board[i][j]; //判断横向棋型 for (int i = 1; i <= 15; ++i) { for (int j = 0; j < 12; ++j) { int type = tuple6type[A[i][j]][A[i][j + 1]][A[i][j + 2]][A[i][j + 3]][A[i][j + 4]][A[i][j + 5]]; stat[type]++; } } //判断竖向棋型 for (int j = 1; j <= 15; ++j) { for (int i = 0; i < 12; ++i) { int type = tuple6type[A[i][j]][A[i + 1][j]][A[i + 2][j]][A[i + 3][j]][A[i + 4][j]][A[i + 5][j]]; stat[type]++; } } //判断左上至右下棋型 for (int i = 0; i < 12; ++i) { for (int j = 0; j < 12; ++j) { int type = tuple6type[A[i][j]][A[i + 1][j + 1]][A[i + 2][j + 2]][A[i + 3][j + 3]][A[i + 4][j + 4]][A[i + 5][j + 5]]; stat[type]++; } } //判断右上至左下棋型 for (int i = 0; i < 12; ++i) { for (int j = 5; j < 17; ++j) { int type = tuple6type[A[i][j]][A[i + 1][j - 1]][A[i + 2][j - 2]][A[i + 3][j - 3]][A[i + 4][j - 4]][A[i + 5][j - 5]]; stat[type]++; } } //若出现连五可以直接判断输赢 //白赢 if (stat[WIN] > 0) return R_WHITE; //黑赢 else if (stat[LOSE] > 0) return R_BLACK; else return R_DRAW; } /*Node类函数实现*/ Node::Node()//无参构造函数 { father = nullptr; children.clear(); value = INT_MIN; depth = cntX = cntY = 0; memset(board, C_NONE, sizeof(board)); } Node::Node(Node* node, int opeX, int opeY)//利用父结点构造子结点 { depth = node->depth + 1; value = is_max_node() ? INT32_MIN : INT32_MAX; father = node; children.clear(); cntX = opeX; cntY = opeY; memcpy(board, node->board, sizeof(board)); board[cntX][cntY] = (depth % 2 == 0) ? C_BLACK : C_WHITE; } bool Node::is_max_node()//判断当前结点是否为MAX结点 { if (depth % 2 == 0) return true; else return false; } int Node::get_score()//返回某棋面得分 { //各棋型对应权重 int weight[17]= { 0,1000000,-10000000,50000,-100000,400,-100000,400,-8000,20,-50,20,-50,1,-3,1,-3 }; int stat[17];//统计17种棋型的个数 memset(stat, 0, sizeof(stat)); evaluate(board, stat); int score = 0; for (int i = 0; i < 17; ++i) score += stat[i] * weight[i];//初步计分 return score; } /*GameTree类函数实现*/ GameTree::GameTree(int maxDepth, int radius, int(&board)[15][15])//构造函数 { this->maxDepth = maxDepth; this->radius=radius; root = new(nothrow)Node; if (root == NULL) exit(EXIT_FAILURE); memcpy(this->root->board, board, sizeof(board)); } vector<pair<int, int>> GameTree::get_search_nodes(Node* node) //返回当前棋局的待扩展点坐标集合 { bool hasChess = false; bool newBoard[15][15]; memset(newBoard, false, sizeof(newBoard)); for (int i = 0; i < 15; i++) { for (int j = 0; j < 15; j++) { if (node->board[i][j] == C_NONE) continue; //只选择棋盘内距每个有棋子位置radius范围为内的位置作为下一步的候选位置（进行扩展） hasChess = true; int x1 = max(0, i - radius);//扩展左边界 int x2 = min(14, i + radius);//扩展右边界 int y1 = max(0, j - radius);//扩展上边界 int y2 = min(14, j + radius);//扩展下边界 for (int x = x1; x <= x2; x++) for (int y = y1; y <= y2; y++) if (node->board[x][y] == 0) newBoard[x][y] = true; /*for (int i = 0; i < 15; i++) { for (int j = 0; j < 15; j++) cout << newBoard[i][j] << " "; cout << endl; }*/ } } vector<pair<int, int>> mask; if (!hasChess) //棋盘上没有棋子时下在中间位置，事实上人类先手不需要考虑这个 { mask.emplace_back(pair<int, int>(7, 7)); } else { for (int i = 0; i < 15; i++) for (int j = 0; j < 15; j++) if (newBoard[i][j]) mask.emplace_back(pair<int, int>(i, j)); } return mask; } int GameTree::expand_children_nodes(Node* node) //扩展node结点，生成node结点的所有子结点 { vector<pair<int, int>> mask = get_search_nodes(node); for (auto pos : mask) { //cout << pos.first << " " << pos.second << endl; Node* n = new Node(node, pos.first, pos.second); if (n == NULL)exit(EXIT_FAILURE); node->children.insert(n); openTable.push_front(n); } return int(mask.size());//返回node结点的子结点数量 } bool GameTree::is_alpha_beta_cut(Node* node) //判断当前结点是否能进行ab剪枝 { if (node == nullptr || node->father == nullptr) return false; if (node->is_max_node() && node->value > node->father->value) return true; if (!node->is_max_node() && node->value < node->father->value) return true; return is_alpha_beta_cut(node->father); } void GameTree::update_value_from_node(Node* node) //更新非叶子结点的估值 { if (node == nullptr) return; if (node->children.empty()) //叶子结点估值已经通过evaluate函数更新 { update_value_from_node(node->father); return; } if (node->is_max_node()) //该结点为max结点 { int cntValue = INT32_MIN; for (Node* n : node->children) if (n->value != INT32_MAX) cntValue = max(cntValue, n->value); if (cntValue > node->value) { node->value = cntValue; update_value_from_node(node->father); } } else //该结点为min结点 { int cntValue = INT32_MAX; for (Node* n : node->children) if (n->value != INT32_MIN) cntValue = min(cntValue, n->value); if (cntValue < node->value) { node->value = cntValue; update_value_from_node(node->father); } } } void GameTree::set_next_pos()//设置下一步的最佳位置 { best = *root->children.begin(); for (Node* p : root->children) if (p->value > best->value) best = p; } void GameTree::game_tree()//控制整个博弈搜索过程的核心函数 { /*计时相关变量*/ double time = 0; double counts = 0; LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; /*开始搜索并计时*/ QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime);//开始计时 openTable.push_back(root);//将根结点放入open表中 while (!openTable.empty()) { Node* node = openTable.front(); openTable.pop_front(); //closedTable.push_back(node); if (is_alpha_beta_cut(node->father))//若父结点被剪枝，则该结点不进行扩展 continue; if (node->depth < maxDepth) { int numExpand = expand_children_nodes(node); if (numExpand != 0) continue; } //若为叶子结点则开始对棋面评分 node->value = node->get_score() + (node->cntX) * (14 - node->cntX) + (node->cntY) * (14