[数据结构与算法]C++五子棋AI

运用了极小极大算法，α-β剪枝。运算速度还是很慢，目前最多搜索3层（不加根节点），有待优化。

#pragma once
#include<iostream>
#include<vector>
#include<array>
#include<fstream>
class GameTree
{
private:
	class Node
	{
	public:
		static const unsigned short SIZE = 15;
		enum State { SPACE, BLACK, WHITE };
		int value;//叶节点表示估价函数的结果，MAX节点表示α值，MIN节点表示β值
		unsigned short depth;//深度
		uint8_t lastX, lastY;//上一次落子的xy坐标
		Node* father;//父亲节点
		std::vector<Node*> children;//子节点
		State board[SIZE][SIZE];//棋盘
		Node() :father(nullptr), depth(0), value(INT32_MAX),lastX(SIZE),lastY(SIZE)
		{
			memset(board, 0, sizeof(board));
		}
		Node(Node* nf, uint8_t x, uint8_t y) :father(nf), lastX(x), lastY(y), depth(nf->depth + 1),value(0)
		{
			father->children.push_back(this);
			memcpy_s(board, sizeof(board), father->board, sizeof(father->board));
			if (IsMaxNode())
			{
				board[x][y] = BLACK;
			}
			else
			{
				board[x][y] = WHITE;
			}
		}
		Node(int _depth, uint8_t x, uint8_t y):father(nullptr),depth(_depth),lastX(x),lastY(y),value(0)
		{
			memset(board, 0, sizeof(board));
			if (IsMaxNode())
			{
				board[x][y] = BLACK;
			}
			else
			{
				board[x][y] = WHITE;
			}
		}
		void Search(unsigned short _depth)
		{
			value = Evaluate();//先对当前棋局估价，排除已经决出胜负的棋局。一定把这一句放在下一句前面，保证叶节点也被估价。
			if (_depth == 0 || value == INT_MAX || value == INT_MIN)
				return;
			if (IsMaxNode())
				value = INT_MIN;
			else
				value = INT_MAX;
			for (uint8_t i = 0; i < SIZE; i++)
			{
				for (uint8_t j = 0; j < SIZE; j++)
				{
					if (!board[i][j])
					{
						Node* node = nullptr;
						for (Node* child : children)
						{
							if (child->lastX == i && child->lastY == j)//已经被搜索过
							{
								node = child;
								break;
							}
						}
						if (!node)//还没有搜索过，有两种情况，要么是开局第一次搜索，要么是用户选择了被剪枝的
							node = new Node(this, i, j);
						node->Search(_depth - 1);
						//α - β 剪枝
						if (IsMaxNode())
						{
							if (node->value > this->value)
							{
								this->value = node->value;
								if (father && value >= father->value && this != father->children.front())
								{
									return;//剪枝
								}
							}
						}
						else//MIN节点
						{
							if (node->value < this->value)
							{
								this->value = node->value;
								if (father && value <= father->value && this != father->children.front())
								{
									return;//剪枝
								}
							}
						}
					}
				}
			}
			if (children.empty())//此时一定是平局，因为此时棋盘已经被填满，而一方胜利的情况已经被排除
			{
				value = 0;
			}
		}
		bool IsMaxNode()const//默认计算机后手
		{
			return depth & 1u;//相当于depth%2
		}
		int Evaluate()const//估价函数
		{
			int result = 0;
			static auto EvaluateSome = [](const std::array<State, 5>& v)//假定自己是白方
			{
				//判断颜色并记录棋子个数
				State lastColor = SPACE;
				uint8_t count = 0;
				for (State i : v)
				{
					if (i != SPACE)
					{
						++count;
						if (i != lastColor)
						{
							if (lastColor == SPACE)//遇到的第一个棋子
							{
								lastColor = i;
							}
							else//有不同颜色的棋子
							{
								return 0;
							}
						}
					}
				}
				if (!count)//没有棋子
					return 0;
				if (count == 5)
				{
					return lastColor == WHITE ? INT_MAX : INT_MIN;//一定不要认为-INT_MAX就是INT_MIN！
				}
				const int result = static_cast<int>(std::pow(10, count - 1));
				return lastColor == WHITE ? result : static_cast<int>(-1.1 * result);//对手返回负值，我方返回正值，乘以1.1后优先防守
			};
			for (uint8_t i = 0; i < 15; i++)//分别从四个方向判断
			{
				for (uint8_t j = 0; j < 15; j++)
				{
					if (j + 4 < 15)
					{
						std::array<State, 5>v;
						for (uint8_t k = 0; k < 5; k++)
							v[k] = board[i][j + k];
						const int t = EvaluateSome(v);
						if (t == INT_MAX || t == INT_MIN)//决出胜负直接返回
							return t;
						result += t;
					}
					if (i + 4 < 15)
					{
						std::array<State, 5>v;
						for (uint8_t k = 0; k < 5; k++)
							v[k] = board[i + k][j];
						const int t = EvaluateSome(v);
						if (t == INT_MAX || t == INT_MIN)//决出胜负直接返回
							return t;
						result += t;
					}
					if (i + 4 < 15 && j + 4 < 15)
					{
						std::array<State, 5>v;
						for (uint8_t k = 0; k < 5; k++)
							v[k] = board[i + k][j + k];
						const int t = EvaluateSome(v);
						if (t == INT_MAX || t == INT_MIN)//决出胜负直接返回
							return t;
						result += t;
					}
					if (i + 4 < 15 && j - 4 >= 0)
					{
						std::array<State, 5>v;
						for (uint8_t k = 0; k < 5; k++)
							v[k] = board[i + k][j - k];
						const int t = EvaluateSome(v);
						if (t == INT_MAX || t == INT_MIN)//决出胜负直接返回
							return t;
						result += t;
					}
				}
			}
			return result;
		}
		void DeleteAllButThis()
		{
			for (Node* n : father->children)
			{
				if (n != this)
					delete n;
			}
			free(father);//避免调用析构函数
			father = nullptr;
		}
		bool IsFull()const
		{
			for (int i = 0; i < SIZE; i++)
			{
				for (int j = 0; j < SIZE; j++)
				{
					if (board[i][j] == SPACE)
						return false;
				}
			}
			return true;
		}
		~Node()
		{
			for (Node* n : children)
			{
				delete n;
			}
		}
	};
	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);
		for (Node* node : root->children)//选择分值最大的
		{
			if (node->value == root->value)
			{
				node->DeleteAllButThis();
				root = node;
				break;
			}
		}
		return std::make_pair(root->lastX, root->lastY);
	}
	void Run()
	{
		while (1)
		{
			int x, y;
			do
			{
				std::cout << "输入x,y坐标";
				std::cin >> x >> y;
			} while (x < 0 || y < 0 || x >= 15 || y >= 15 || (root && root->board[x][y] != Node::SPACE));
			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 < Node::SIZE; i++)
			{
				for (int j = 0; j < Node::SIZE; j++)
				{
					if (root->board[i][j] == Node::SPACE)
						std::cout << "十 ";
					else if (root->board[i][j] == Node::BLACK)
						std::cout << "黑 ";
					else
						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 < Node::SIZE; i++)
			{
				for (int j = 0; j < Node::SIZE; j++)
				{
					if (root->board[i][j] == Node::SPACE)
						std::cout << "十 ";
					else if (root->board[i][j] == Node::BLACK)
						std::cout << "黑 ";
					else
						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;
	}
};