C++ 五子棋 AI 实现：极大极小算法和 Alpha-Beta 剪枝

编写五子棋 AI 可以使用极大极小算法 (MinMax Algorithm) 和 Alpha-Beta 剪枝 (Alpha-Beta Pruning) 来优化算法效率。以下是一个简单的示例代码：\n\ncpp\n#include \"iostream\"\n#include \"vector\"\n#include \"climits\"\n\nconst int SIZE = 15; // 棋盘大小\n\nenum class Player {\n NONE, \n BLACK, \n WHITE\n};\n\nstruct Move {\n int row; \n int col; \n};\n\n// 判断棋盘上某位置是否合法\nbool isValidMove(int row, int col) {\n return row >= 0 && row < SIZE && col >= 0 && col < SIZE; \n}\n\n// 判断游戏是否结束\nbool isGameOver(const std::vector<std::vector<Player>>& board, Player& winner) {\n int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}}; // 四个方向：横、竖、斜、反斜\n\n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n continue; \n }\n\n Player currPlayer = board[row][col]; \n\n for (const auto& direction : directions) {\n int dx = direction[0]; \n int dy = direction[1]; \n int count = 1; \n\n for (int i = 1; i < 5; ++i) {\n int newRow = row + dx * i; \n int newCol = col + dy * i; \n\n if (isValidMove(newRow, newCol) && board[newRow][newCol] == currPlayer) {\n ++count; \n } else {\n break; \n } \n } \n\n if (count == 5) {\n winner = currPlayer; \n return true; \n } \n } \n } \n } \n\n return false; \n}\n\n// 评估当前局面分数\nint evaluate(const std::vector<std::vector<Player>>& board) {\n int score = 0; \n\n int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}}; \n\n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n continue; \n } \n\n Player currPlayer = board[row][col]; \n\n for (const auto& direction : directions) {\n int dx = direction[0]; \n int dy = direction[1]; \n int count = 1; \n int emptyCount = 0; \n\n for (int i = 1; i < 5; ++i) {\n int newRow = row + dx * i; \n int newCol = col + dy * i; \n\n if (isValidMove(newRow, newCol) && board[newRow][newCol] == currPlayer) {\n ++count; \n } else if (isValidMove(newRow, newCol) && board[newRow][newCol] == Player::NONE) {\n ++emptyCount; \n } else {\n break; \n } \n } \n\n score += (count * count * count * count) * (currPlayer == Player::BLACK ? 1 : -1); \n score += (emptyCount * emptyCount * emptyCount * emptyCount) * (currPlayer == Player::BLACK ? 1 : -1); \n } \n } \n } \n\n return score; \n}\n\n// 极大极小算法\nint minimax(std::vector<std::vector<Player>> board, int depth, bool isMaximizingPlayer) {\n Player winner = Player::NONE; \n if (isGameOver(board, winner)) {\n if (winner == Player::BLACK) {\n return INT_MAX; \n } else if (winner == Player::WHITE) {\n return INT_MIN; \n } else {\n return 0; \n } \n } \n\n if (depth == 0) {\n return evaluate(board); \n } \n\n if (isMaximizingPlayer) {\n int maxEval = INT_MIN; \n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n board[row][col] = Player::BLACK; \n int eval = minimax(board, depth - 1, false); \n board[row][col] = Player::NONE; \n maxEval = std::max(maxEval, eval); \n } \n } \n } \n return maxEval; \n } else {\n int minEval = INT_MAX; \n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n board[row][col] = Player::WHITE; \n int eval = minimax(board, depth - 1, true); \n board[row][col] = Player::NONE; \n minEval = std::min(minEval, eval); \n } \n } \n } \n return minEval; \n } \n}\n\n// Alpha-Beta 剪枝\nint alphabeta(std::vector<std::vector<Player>> board, int depth, int alpha, int beta, bool isMaximizingPlayer) {\n Player winner = Player::NONE; \n if (isGameOver(board, winner)) {\n if (winner == Player::BLACK) {\n return INT_MAX; \n } else if (winner == Player::WHITE) {\n return INT_MIN; \n } else {\n return 0; \n } \n } \n\n if (depth == 0) {\n return evaluate(board); \n } \n\n if (isMaximizingPlayer) {\n int maxEval = INT_MIN; \n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n board[row][col] = Player::BLACK; \n int eval = alphabeta(board, depth - 1, alpha, beta, false); \n board[row][col] = Player::NONE; \n maxEval = std::max(maxEval, eval); \n alpha = std::max(alpha, eval); \n if (beta <= alpha) {\n break; \n } \n } \n } \n } \n return maxEval; \n } else {\n int minEval = INT_MAX; \n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n board[row][col] = Player::WHITE; \n int eval = alphabeta(board, depth - 1, alpha, beta, true); \n board[row][col] = Player::NONE; \n minEval = std::min(minEval, eval); \n beta = std::min(beta, eval); \n if (beta <= alpha) {\n break; \n } \n } \n } \n } \n return minEval; \n } \n}\n\n// 获取AI的下一步落子位置\nMove getNextMove(const std::vector<std::vector<Player>>& board, int depth, bool useAlphaBeta) {\n Move bestMove; \n int bestScore = INT_MIN; \n\n Player currPlayer = Player::BLACK; // AI执黑棋\n\n if (!useAlphaBeta) {\n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n std::vector<std::vector<Player>> newBoard = board; \n newBoard[row][col] = currPlayer; \n int score = minimax(newBoard, depth, false); \n if (score > bestScore) {\n bestScore = score; \n bestMove.row = row; \n bestMove.col = col; \n } \n } \n } \n } \n } else {\n int alpha = INT_MIN; \n int beta = INT_MAX; \n\n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n if (board[row][col] == Player::NONE) {\n std::vector<std::vector<Player>> newBoard = board; \n newBoard[row][col] = currPlayer; \n int score = alphabeta(newBoard, depth, alpha, beta, false); \n if (score > bestScore) {\n bestScore = score; \n bestMove.row = row; \n bestMove.col = col; \n } \n alpha = std::max(alpha, score); \n } \n } \n } \n } \n\n return bestMove; \n}\n\nint main() {\n std::vector<std::vector<Player>> board(SIZE, std::vector<Player>(SIZE, Player::NONE)); \n\n // AI执黑棋，玩家执白棋\n Player currPlayer = Player::BLACK; \n Player winner = Player::NONE; \n\n while (!isGameOver(board, winner)) {\n // 玩家输入下一步落子位置\n int row, col; \n std::cin >> row >> col; \n if (isValidMove(row, col) && board[row][col] == Player::NONE) {\n board[row][col] = Player::WHITE; \n } else {\n std::cout << \"Invalid move. Please try again.\" << std::endl; \n continue; \n } \n\n // AI计算下一步落子位置\n Move nextMove = getNextMove(board, 4, true); \n board[nextMove.row][nextMove.col] = Player::BLACK; \n\n // 打印棋盘\n for (int row = 0; row < SIZE; ++row) {\n for (int col = 0; col < SIZE; ++col) {\n switch (board[row][col]) {\n case Player::NONE: \n std::cout << \".\"; \n break; \n case Player::BLACK: \n std::cout << \"X\"; \n break; \n case Player::WHITE: \n std::cout << \"O\"; \n break; \n } \n } \n std::cout << std::endl; \n } \n } \n\n if (winner == Player::BLACK) {\n std::cout << \"AI wins!\" << std::endl; \n } else if (winner == Player::WHITE) {\n std::cout << \"Player wins!\" << std::endl; \n } else {\n std::cout << \"It's a draw!\" << std::endl; \n } \n\n return 0; \n}\n\n\n这个示例代码实现了一个简单的五子棋 AI，通过极大极小算法和 Alpha-Beta 剪枝来搜索最优解。其中，isValidMove 函数用于判断落子位置是否合法，isGameOver 函数用于判断游戏是否结束，evaluate 函数用于评估当前局面分数，minimax 函数用于执行极大极小算法，alphabeta 函数用于执行 Alpha-Beta 剪枝，getNextMove 函数用于获取 AI 的下一步落子位置。\n\n在 main 函数中，先由玩家输入下一步落子位置，然后 AI 计算下一步落子位置，并将落子位置打印到控制台。\n\n需要注意的是，这只是一个简单的示例，实际的五子棋 AI 可能需要更复杂的算法和策略来提高性能和游戏水平。