蒙特卡洛搜索算法

蒙特卡洛算法浅析

preface: 参考链接：面向初学者的蒙特卡洛树搜索MCTS详解及其实现_mcts算法-CSDN博客 |

正文

 具体概念就不说了，具体可见上面的链接前面一部分。根据deepseek生成的井字棋算法来看，蒙特卡洛算法就是通过模拟，计算胜率，其核心在于模拟时落子的选择。（这里deepseek就是搞了个完全随机，显然在五子棋等就不可行了，其选择落子需要其他设计，当然我目前不会）

//这里仅取了必要部分
// 随机模拟游戏
int simulateRandomGame(int player) {
    int currentPlayer = player;
    while (1) {
        // 随机选择一个空位
        int x, y;
        do {
            x = rand() % BOARD_SIZE;
            y = rand() % BOARD_SIZE;
        } while (board[x][y] != EMPTY);

        // 下子
        board[x][y] = currentPlayer;

        // 检查是否获胜
        if (checkWin(currentPlayer)) {
            return currentPlayer;
        }

        // 检查是否平局
        if (isBoardFull()) {
            return 0; // 平局
        }

        // 切换玩家
        currentPlayer = (currentPlayer == PLAYER) ? AI : PLAYER;
    }
}

// 蒙特卡洛算法选择最佳走法
void monteCarloMove() {
    int bestMoveX = -1, bestMoveY = -1;
    int bestWinRate = -1;

    // 遍历所有空位
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (board[i][j] == EMPTY) { //凡是有空位的落点，均进行 模拟
                int wins = 0; //记录这一个落点win的次数

                // 模拟 SIMULATIONS 次
                for (int k = 0; k < SIMULATIONS; k++) {
                    // 保存当前棋盘状态
                    int tempBoard[BOARD_SIZE][BOARD_SIZE];
                    for (int x = 0; x < BOARD_SIZE; x++) {
                        for (int y = 0; y < BOARD_SIZE; y++) {
                            tempBoard[x][y] = board[x][y];
                        }
                    } // 储存board

                    // 下子并模拟游戏
                    board[i][j] = AI;
                    int result = simulateRandomGame(AI); //模拟
                    if (result == AI) wins++;

                    // 恢复棋盘状态
                    for (int x = 0; x < BOARD_SIZE; x++) {
                        for (int y = 0; y < BOARD_SIZE; y++) {
                            board[x][y] = tempBoard[x][y];
                        }
                    }
                }

                // 计算胜率
                int winRate = wins * 100 / SIMULATIONS;
                if (winRate > bestWinRate) {  //将这个落点的胜率和前面模拟的落点的胜率对比
                    bestWinRate = winRate;
                    bestMoveX = i;
                    bestMoveY = j;
                }
            }
        }
    }

    // 执行最佳走法
    if (bestMoveX != -1 && bestMoveY != -1) {
        board[bestMoveX][bestMoveY] = AI;
    }
}

// 主函数
int main() {
        if (currentPlayer == PLAYER) {
        } else {
            // AI回合
            printf("AI正在思考...\n");
            monteCarloMove();
        }