我正在尝试找到使用 Minimax 树并行实现 Tic tac toe 游戏的源代码，无论是在 Java 中使用 Fork/Join 还是在 C/C++ 中使用 pthread。我可以找到很多游戏的串行版本，但没有找到并行版本。
我看到这个问题： 使用 minimax 进行 tic-tac-toe 游戏可以使用多少个线程？ 作者：@good_evening
但我找不到任何源代码。 如有任何帮助，我们将不胜感激。
我快速搜索没有找到。
这是一个并行极小极大国际象棋程序。 这可能更有启发性，因为它是一个更“实用”的例子。
这是一个 C++ 实现：
游戏主文件（main.cpp）：
// File: main.cpp
#include <iostream>
#include <vector>
#include <thread>
#include <limits>
#include "Board.h"
#include "Minimax.h"
int main() {
Board board;
char currentPlayer = Board::PLAYER_O; // Human plays 'O', AI plays 'X'
while (true) {
board.printBoard();
if (board.checkWin(Board::PLAYER_X)) {
std::cout << "AI wins!" << std::endl;
break;
} else if (board.checkWin(Board::PLAYER_O)) {
std::cout << "You win!" << std::endl;
break;
} else if (board.isFull()) {
std::cout << "It's a draw!" << std::endl;
break;
}
if (currentPlayer == Board::PLAYER_O) {
// Human's turn
int x, y;
std::cout << "Enter your move (row[0-2] and column[0-2]): ";
std::cin >> x >> y;
if (x < 0 || x > 2 || y < 0 || y > 2 || !board.makeMove(x, y, Board::PLAYER_O)) {
std::cout << "Invalid move! Try again." << std::endl;
continue;
}
currentPlayer = Board::PLAYER_X;
} else {
// AI's turn
std::cout << "AI is thinking..." << std::endl;
std::vector<std::pair<int, int>> moves = board.getAvailableMoves();
int bestScore = std::numeric_limits<int>::min();
std::pair<int, int> bestMove;
std::vector<std::thread> threads;
std::vector<int> scores(moves.size());
for (size_t i = 0; i < moves.size(); ++i) {
threads.emplace_back([&, i]() {
Board newBoard = board;
newBoard.makeMove(moves[i].first, moves[i].second, Board::PLAYER_X);
scores[i] = minimax(newBoard, false, Board::PLAYER_X, Board::PLAYER_O);
});
}
for (auto& thread : threads) {
thread.join();
}
for (size_t i = 0; i < scores.size(); ++i) {
if (scores[i] > bestScore) {
bestScore = scores[i];
bestMove = moves[i];
}
}
board.makeMove(bestMove.first, bestMove.second, Board::PLAYER_X);
std::cout << "AI played: " << bestMove.first << "," << bestMove.second << std::endl;
currentPlayer = Board::PLAYER_O;
}
}
board.printBoard();
return 0;
}
现在让我们开发board.h
// File: Board.h
#ifndef BOARD_H
#define BOARD_H
#include <vector>
class Board {
public:
Board();
void printBoard();
bool makeMove(int x, int y, char player);
void undoMove(int x, int y);
bool checkWin(char player);
bool isFull();
std::vector<std::pair<int, int>> getAvailableMoves();
char getCell(int x, int y);
static const char EMPTY = ' ';
static const char PLAYER_X = 'X'; // AI
static const char PLAYER_O = 'O'; // Human
private:
char board[3][3];
};
#endif
和 board.cpp 将是
// File: Board.cpp
#include "Board.h"
#include <iostream>
Board::Board() {
// Initialize the board with empty cells
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
board[i][j] = EMPTY;
}
void Board::printBoard() {
std::cout << "Board:" << std::endl;
for (int i = 0; i < 3; ++i) {
for(int j=0; j<3; ++j) {
std::cout << board[i][j];
if(j < 2) std::cout << "|";
}
std::cout << std::endl;
if(i < 2) std::cout << "-----" << std::endl;
}
}
bool Board::makeMove(int x, int y, char player) {
if (board[x][y] == EMPTY) {
board[x][y] = player;
return true;
}
return false;
}
void Board::undoMove(int x, int y) {
board[x][y] = EMPTY;
}
bool Board::checkWin(char player) {
// Check rows, columns, and diagonals
for(int i=0; i<3; ++i) {
if(board[i][0]==player && board[i][1]==player && board[i][2]==player)
return true;
if(board[0][i]==player && board[1][i]==player && board[2][i]==player)
return true;
}
if(board[0][0]==player && board[1][1]==player && board[2][2]==player)
return true;
if(board[0][2]==player && board[1][1]==player && board[2][0]==player)
return true;
return false;
}
bool Board::isFull() {
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(board[i][j]==EMPTY)
return false;
return true;
}
std::vector<std::pair<int, int>> Board::getAvailableMoves() {
std::vector<std::pair<int, int>> moves;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(board[i][j]==EMPTY)
moves.emplace_back(i, j);
return moves;
}
char Board::getCell(int x, int y) {
return board[x][y];
}
Minimax 算法（Minimax.h 和 Minimax.cpp）：
最小最大.h：
// File: Minimax.h
#ifndef MINIMAX_H
#define MINIMAX_H
#include "Board.h"
int minimax(Board& board, bool isMaximizing, char aiPlayer, char humanPlayer);
#endif
最小最大.cpp：
// File: Minimax.cpp
#include "Minimax.h"
#include <vector>
#include <limits>
int minimax(Board& board, bool isMaximizing, char aiPlayer, char humanPlayer) {
if (board.checkWin(aiPlayer))
return 10;
else if (board.checkWin(humanPlayer))
return -10;
else if (board.isFull())
return 0;
std::vector<std::pair<int, int>> moves = board.getAvailableMoves();
int bestScore = isMaximizing ? std::numeric_limits<int>::min() : std::numeric_limits<int>::max();
for (auto move : moves) {
board.makeMove(move.first, move.second, isMaximizing ? aiPlayer : humanPlayer);
int score = minimax(board, !isMaximizing, aiPlayer, humanPlayer);
board.undoMove(move.first, move.second);
if (isMaximizing)
bestScore = std::max(bestScore, score);
else
bestScore = std::min(bestScore, score);
}
return bestScore;
}
编译命令：
g++ -std=c++11 main.cpp Board.cpp Minimax.cpp -o TicTacToe -pthread
-pthread 标志对于线程支持是必需的。
运行游戏：
./TicTacToe