三子棋（Minimax算法 + alpha-beta剪枝算法）
Winner() 函数用来检测当前棋局是否有玩家获胜，它的检测方式为：检查每一行、每一列、对角线是否有三个同样的棋子，如果有，则返回对应位置的字符（举个例子：如果对角线（0，0）（1，1）（2，2）有三个同样的棋子 ' # ' ，则返回字符 ' # '）；极小极大算法是一种用于决策过程的算法，它假设双方都是理性的，且都采取最优策略。你可以在程序中加入常量或打印出变量的数值，这样你可以清晰的看到变量
·
这个程序我用CLion编写的。
问题描述： 这个程序实现了一个简单的井字棋游戏，玩家可以与电脑进行对战。电脑使用 Minimax算法 并结合 Alpha-Beta剪枝 来选择最佳移动，确保在每一步都采取最优策略。
下面先上代码（在Visual Studio上要把 scanf() 替换成 scanf_s() ）：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROW 3
#define COL 3
// 提示用户菜单
void Prompt_users() {
printf("**************************\n");
printf("******** 1: start ********\n");
printf("******** 2: exit ********\n");
printf("**************************\n");
}
// 获取用户输入
int Users_enter() {
int t;
while (1) {
printf("You can enter 1 or 2 to start or exit: ");
scanf_s("%d", &t);
if (t == 1) {
return 1;
}
else if (t == 2) {
printf("Welcome to use again!\n");
return 0;
}
else {
printf("You must input 1 or 2!\n");
}
}
}
// 初始化棋盘
void Init_board(char board[ROW][COL]) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
board[i][j] = ' ';
}
}
}
// 打印棋盘
void Print_chessboard(char board[ROW][COL]) {
printf("|-----|-----|-----|\n");
for (int i = 0; i < ROW; i++) {
printf("| %c | %c | %c |\n", board[i][0], board[i][1], board[i][2]);
printf("|-----|-----|-----|\n");
}
}
// 检查是否有玩家获胜
char Winner(char board[ROW][COL]) {
// 检查行
for (int i = 0; i < ROW; i++) {
if (board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] != ' ') {
return board[i][0];
}
}
// 检查列
for (int j = 0; j < COL; j++) {
if (board[0][j] == board[1][j] && board[1][j] == board[2][j] && board[0][j] != ' ') {
return board[0][j];
}
}
// 检查对角线
if (board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != ' ') {
return board[0][0];
}
if (board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[0][2] != ' ') {
return board[0][2];
}
return ' '; // 没有获胜者
}
// 检查棋盘是否已满
int IsBoardFull(char board[ROW][COL]) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
return 0; // 棋盘未满
}
}
}
return 1; // 棋盘已满
}
// 获取用户输入的坐标并更新棋盘
void Coordinate_users(char board[ROW][COL]) {
int a, b;
while (1) {
printf("Please enter the coordinate (for example: 2 3): ");
scanf_s("%d%d", &a, &b);
if (a >= 0 && a < ROW && b >= 0 && b < COL && board[a][b] == ' ') {
board[a][b] = '*';
break;
}
else {
printf("The coordinate %d %d is invalid or already occupied! Please enter another coordinate.\n", a, b);
}
}
}
// Minimax 算法实现
int Minimax(char board[ROW][COL], int depth, int isMaximizing, int alpha, int beta) {
char result = Winner(board);
if (result == '#') {
return 10 - depth; // 电脑获胜
}
if (result == '*') {
return depth - 10; // 玩家获胜
}
if (IsBoardFull(board)) {
return 0; // 平局
}
if (isMaximizing) {
int bestScore = -1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '#';
int score = Minimax(board, depth + 1, 0, alpha, beta);
board[i][j] = ' ';
bestScore = (score > bestScore) ? score : bestScore;
alpha = (alpha > bestScore) ? alpha : bestScore;
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
else {
int bestScore = 1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '*';
int score = Minimax(board, depth + 1, 1, alpha, beta);
board[i][j] = ' ';
bestScore = (score < bestScore) ? score : bestScore;
beta = (beta < bestScore) ? beta : bestScore;
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
}
// 电脑使用 Minimax 算法选择最佳移动
void Coordinate_computer(char board[ROW][COL]) {
int bestScore = -1000;
int bestMove[2] = { -1, -1 };
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '#';
int score = Minimax(board, 0, 0, -1000, 1000);
board[i][j] = ' ';
if (score > bestScore) {
bestScore = score;
bestMove[0] = i;
bestMove[1] = j;
}
}
}
}
if (bestMove[0] != -1 && bestMove[1] != -1) {
printf("The computer will enter a coordinate: %d %d\n", bestMove[0], bestMove[1]);
board[bestMove[0]][bestMove[1]] = '#';
}
}
int main(void) {
char board[ROW][COL];
int UserEnter;
srand((unsigned int)time(NULL)); // 初始化随机数种子
Prompt_users();
UserEnter = Users_enter();
if (UserEnter) {
Init_board(board);
Print_chessboard(board);
while (1) {
// 用户移动
Coordinate_users(board);
Print_chessboard(board);
if (Winner(board) == '*') {
printf("User is the winner!\n");
break;
}
if (IsBoardFull(board)) {
printf("It's a tie!\n");
break;
}
// 电脑移动
Coordinate_computer(board);
Print_chessboard(board);
if (Winner(board) == '#') {
printf("Computer is the winner!\n");
break;
}
if (IsBoardFull(board)) {
printf("It's a tie!\n");
break;
}
}
}
return 0;
}
电脑的棋子表示为 ' # '，人的棋子表示为 ' * '。下面的运行结果为平局：
C:\Users\yourname\CLionProjects\cmake-build-debug\CLionProjects.exe
**************************
******** 1: start ********
******** 2: exit ********
**************************
You can enter 1 or 2 to start or exit:1
|-----|-----|-----|
| | | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
Please enter the coordinate (for example: 2 3):1 1
|-----|-----|-----|
| | | |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
The computer will enter a coordinate: 0 0
|-----|-----|-----|
| # | | |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
Please enter the coordinate (for example: 2 3):0 2
|-----|-----|-----|
| # | | * |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
The computer will enter a coordinate: 2 0
|-----|-----|-----|
| # | | * |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| # | | |
|-----|-----|-----|
Please enter the coordinate (for example: 2 3):1 0
|-----|-----|-----|
| # | | * |
|-----|-----|-----|
| * | * | |
|-----|-----|-----|
| # | | |
|-----|-----|-----|
The computer will enter a coordinate: 1 2
|-----|-----|-----|
| # | | * |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| # | | |
|-----|-----|-----|
Please enter the coordinate (for example: 2 3):2 1
|-----|-----|-----|
| # | | * |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| # | * | |
|-----|-----|-----|
The computer will enter a coordinate: 0 1
|-----|-----|-----|
| # | # | * |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| # | * | |
|-----|-----|-----|
Please enter the coordinate (for example: 2 3):2 2
|-----|-----|-----|
| # | # | * |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| # | * | * |
|-----|-----|-----|
It's a tie!
Process finished with exit code 0
以上代码能够实现人机对弈，人无法取胜。（是不是感觉很神奇？）
下面，我们先分析算法以外的部分
首先是 Prompt_users() 函数和 Users_enter() 函数及运行结果：
// 提示用户菜单
void Prompt_users() {
printf("**************************\n");
printf("******** 1: start ********\n");
printf("******** 2: exit ********\n");
printf("**************************\n");
}
// 获取用户输入
int Users_enter() {
int t;
while (1) {
printf("You can enter 1 or 2 to start or exit: ");
scanf_s("%d", &t);
if (t == 1) {
return 1;
}
else if (t == 2) {
printf("Welcome to use again!\n");
return 0;
}
else {
printf("You must input 1 or 2!\n");
}
}
}
Prompt_users() 函数用来打印菜单； Users_enter() 函数用来检测用户输入的数字，用户输入数字 1 即可开始游戏，输入数字 2 即可退出游戏（但在游戏过程中输入 2 是无效的）。
下面是 Init_board() 函数和 Print_chessboard() 函数：
// 初始化棋盘
void Init_board(char board[ROW][COL]) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
board[i][j] = ' ';
}
}
}
// 打印棋盘
void Print_chessboard(char board[ROW][COL]) {
printf("|-----|-----|-----|\n");
for (int i = 0; i < ROW; i++) {
printf("| %c | %c | %c |\n", board[i][0], board[i][1], board[i][2]);
printf("|-----|-----|-----|\n");
}
}Init_board() 函数用来初始化棋盘，它定义了一个二维数组用于表示棋子的坐标（棋盘左上角坐标为（0，0）；右下角坐标为（2，2））并将所有坐标全部初始化为空格。 Print_chessboard() 函数用来打印初始化的棋盘，结果如下：
下面是 Winner() 函数和 IsBoardFull() 函数：
// 检查是否有玩家获胜
char Winner(char board[ROW][COL]) {
// 检查行
for (int i = 0; i < ROW; i++) {
if (board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] != ' ') {
return board[i][0];
}
}
// 检查列
for (int j = 0; j < COL; j++) {
if (board[0][j] == board[1][j] && board[1][j] == board[2][j] && board[0][j] != ' ') {
return board[0][j];
}
}
// 检查对角线
if (board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != ' ') {
return board[0][0];
}
if (board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[0][2] != ' ') {
return board[0][2];
}
return ' '; // 没有获胜者
}
// 检查棋盘是否已满
int IsBoardFull(char board[ROW][COL]) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
return 0; // 棋盘未满
}
}
}
return 1; // 棋盘已满
}
Winner() 函数用来检测当前棋局是否有玩家获胜，它的检测方式为：检查每一行、每一列、对角线是否有三个同样的棋子，如果有，则返回对应位置的字符（举个例子：如果对角线（0，0）（1，1）（2，2）有三个同样的棋子 ' # ' ，则返回字符 ' # '）；如果没有，则返回空格。 IsBoardFull() 函数用来检测棋盘是否已满，通过遍历整个棋盘，如果没有空格，则返回 1 。
下面是 Coordinate_users() 函数：
// 获取用户输入的坐标并更新棋盘
void Coordinate_users(char board[ROW][COL]) {
int a, b;
while (1) {
printf("Please enter the coordinate (for example: 2 3): ");
scanf_s("%d%d", &a, &b);
if (a >= 0 && a < ROW && b >= 0 && b < COL && board[a][b] == ' ') {
board[a][b] = '*';
break;
}
else {
printf("The coordinate %d %d is invalid or already occupied! Please enter another coordinate.\n", a, b);
}
}
}Coordinate_users() 函数用来获取用户输入的坐标并更新棋盘。通过检测用户输入的坐标是否合规，如果是，则将该位置的空格替换成用户的棋子 ' * '，如果不合规，则提示用户重新输入，直到坐标合规。
最后的 main() 主函数是前面的函数调用，我就不讲了，大家可以稍作更改来改变终端打印的内容。
下面我们进入稍微烧脑的部分：Minimax 算法和 alpha-beta 剪枝算法。
下面是 Minimax 算法和 alpha-beta 剪枝算法的基本原理：
Alpha-beta剪枝算法是对极小极大算法（Minimax算法）的扩展。极小极大算法是一种用于决策过程的算法，它假设双方都是理性的，且都采取最优策略。然而，极小极大算法在搜索过程中可能会产生大量的节点，导致计算效率低下。为了解决这个问题，Alpha-beta剪枝算法引入了剪枝技术，以减少搜索树中的节点数。
该算法使用两个值：Alpha和Beta。Alpha值表示当前节点的最好结果（对于最大化玩家而言），而Beta值表示当前节点的最差结果（对于最小化玩家而言）。在搜索过程中，如果某个节点的最好结果已经小于等于Alpha值，或者最差结果已经大于等于Beta值，那么这个节点的子树就可以被剪掉，因为这些子树不可能对最终结果产生影响。
上面这两段文字是不是看得云里雾里的？下面我们来深入浅出地解释该算法：
首先是 Minimax 算法：
想象一下你和朋友在下棋，你们都想赢。Minimax 算法的核心思想就是假设对手会采取最优策略来对抗你。
你的回合：你会选择对自己最有利的走法（即最大化自己的利益）
对手的回合：对手会选择对你最不利的走法（即最小化你的利益）
这个过程可以看作是一棵树，每一层代表一个回合，交替进行“最大化”和“最小化”选择。最终，你会选择一个在当前状态下对自己最有利的走法。
其次是 alpha-beta 算法：
现在，假设你在下棋时发现某些走法明显不如其他走法好，你就不需要再深入考虑这些走法了。这就是 alpha-beta 剪枝的核心思想。
alpha：表示当前你找到的最好的走法（最大值）
beta：表示当前对手找到的最好的走法（最大值）
在搜索过程中，如果发现某个走法比已知的最差选择还要差，就可以直接剪掉这个分支，不再继续搜索。这样可以大大减少需要评估的节点数量，提高效率。
我们再用一个比喻来解释一下这两个算法：
假设你在一个迷宫中寻找宝藏，而你的对手是这个迷宫的设计者。现在每个路口都有两个选择：
Minimax 算法：你到达每一个路口都会评估，并选择最有可能找到宝藏的那条路；而你的对手在每个路口都会引导你进入死胡同。
alpha-beta 算法：当你到达某一个路口时，你发现某条路径的评估分数明显低于其余路径，那么就直接舍弃这条路，不再浪费时间和资源。
好，通过以上解释，现在你是不是对 Minimax 算法和 alpha-beta 算法有了一个更好的理解？下面我们再通过一个例子来进一步解释：
假设存在 T ，T 有 3 个分支，分别为 A 、B 、C ；
A 有 3 个分支：A1 、 A2 、 A3；
B 有 3 个分支：B1 、 B2 、B3；
C 有 3 个分支：C1 、C2 、C3；
现在，每个分支的评分为：
A1：3分，A2：2分，A3：1分；
B1：0分，B2：-1分，B3：-2分；
C1：1分，C2：0分，C3：0分。
下面是我手画的一张图（对应上面的分支结构，只是图片更直观）：
首先，我们先假设这是一个 Minimax 问题。在图片中，T(Max) 意思是 T 要从 A、B、C 中选择评分最高的那个；A(Min) 的意思是 A 要从 A1、A2、A3 中选择评分最低的那个。
现在，我们初始化 alpha 和 beta 的值：
alpha：负无穷（表示 Max 节点的下限）；
beta：正无穷（表示 Min 节点的上限）。
下面，你可以想象 T --> A 、T --> B、 T --> C 三个过程是电脑下棋，A --> A、1A --> A2、A --> A3 是人下棋，B、C亦如此。那么，从电脑角度去看，T 要从 A、B、C 中选择评分最高的一种走法，而 A 要从 A1、A2、A3 中选择评分最低的走法。因为从电脑角度看，A1、A2、A3 中评分最低的走法对电脑最不利（即假设人绝顶聪明），下面，我们来遍历这些走法：
初始化：alpha = -∞，beta = +∞
搜索 A：
A1 的值为 3
更新 beta = min(beta, 3) = 3
更新 alpha = max(alpha, 3) = 3
A2 的值为 2
更新 beta = min(beta, 2) = 2
更新 alpha = max(alpha, 2) = 3
A3 的值为 1
更新 beta = min(beta, 1) = 1
更新 alpha = max(alpha, 1) = 3
A 分支的最终值为 1 （Min 节点选择最小值）
搜索 B
B1 的值为 0
更新 beta = min(beta, 0) = 0
更新 alpha = max(alpha, 0) = 3
B2 的值为 -1
更新 beta = min(beta, -1) = -1
更新 alpha = max(alpha, -1) = 3
B3 的值为 -2
更新 beta = min(beta, -2) = -2
更新 alpha = max(alpha, -2) = 3
B 分支的最终值为 -2 （Min 节点选择最小值）
搜索 C
C1 的值为 1
更新 beta = min(beta, 1) = 1
更新 alpha = max(alpha, 1) = 3
C2 的值为 0
更新 beta = min(beta, 0) = 0
更新 alpha = max(alpha, 0) = 3
C3 的值为 0
更新 beta = min(beta, 0) = 0
更新 alpha = max(alpha, 0) = 3
C 分支的最终值为 0 （Min 节点选择最小值）
经过搜索，T 的最终值是 1（Max 节点选择最大值）好，现在你应该了解 Minimax 算法了。但上面并没有体现出剪枝。别急，看下面：
假设现在分支有了变化，如下图：
现在我们给B1、B2、B3 均添加分支。下面我们来探讨这个复杂的过程：
初始化 alpha = -∞
搜索 A：
初始化 beta = +∞
A1 的值为 3
更新 beta = min(beta, 3) = 3
更新 alpha = max(alpha, 3) = 3
A2 的值为 2
更新 beta = min(beta, 2) = 2
更新 alpha = max(alpha, 2) = 3
A3 的值为 1
更新 beta = min(beta, 1) = 1
更新 alpha = max(alpha, 1) = 3
A 分支的最终值为 1 （Min 节点选择最小值）
搜索 B
初始化 beta = +∞
搜索 B1
初始化：alpha = -∞
B11 的值是 0
更新 alpha = max(alpha, 0) = 0
更新 beta = min(beta, alpha) = 0
B12 的值是 -1
更新 alpha = max(alpha, -1) = 0
更新 beta = min(beta, alpha) = 0
B13 的值是 2
更新 alpha = max(alpha, 2) = 2
更新 beta = min(beta, alpha) = 0
B1 分支的最大值是 2（Max 节点选择最大值）
搜索 B2
初始化：alpha = -∞
B21 的值是 3
更新 alpha = max(alpha, 3) = 3
更新 beta = min(beta, alpha) = 3
不再遍历 B22 和 B23，即剪枝
B2 分支的最大值是 3（Max 节点选择最大值）
搜索 B3
初始化：alpha = -∞
B31 的值是 -2
更新 alpha = max(alpha, -2) = -2
更新 beta = min(beta, alpha) = -2
B32 的值是 1
更新 alpha = max(alpha, 1) = 1
更新 beta = min(beta, alpha) = -2
B33 的值是 3
更新 alpha = max(alpha, 3) = 3
更新 beta = min(beta, alpha) = -2
B3 分支的最大值是 3（Max 节点选择最大值）
B 分支的最小值是 2（Min 节点选择最小值）
搜索 C
初始化 beta = +∞
C1 的值为 0
更新 beta = min(beta, 0) = 0
更新 alpha = max(alpha, 0) = 3
C2 的值为 0
更新 beta = min(beta, -3) = -3
更新 alpha = max(alpha, -3) = 3
C3 的值为 0
更新 beta = min(beta, 4) = -3
更新 alpha = max(alpha, 4) = 4
C 分支的最终值为 -3 （Min 节点选择最小值）
经过搜索，T 的最终值是 -3（Max 节点选择最大值）
我们看到，算法在遍历 B2 中的分支B21、B22、B23 时进行了剪枝，将B22、B23 两个分支全部剪掉。为什么？因为 B1、B2、B3 选的都是最大值，当检测到 B21 的值大于 B1 中所有数值时，即便 B22、B23 的值多大多小，B2 的值一定不会小于 B21。因此检测B22、B23 将不存在任何意义，那么就剪掉，避免浪费时间和资源。
经过以上描述，你应该对 Minimax 算法和 alpha-beta 算法有了一定的了解。下面我们分析一下程序中的算法部分：
// Minimax 算法实现
int Minimax(char board[ROW][COL], int depth, int isMaximizing, int alpha, int beta) {
char result = Winner(board);
if (result == '#') {
return 10 - depth; // 电脑获胜
}
if (result == '*') {
return depth - 10; // 玩家获胜
}
if (IsBoardFull(board)) {
return 0; // 平局
}
if (isMaximizing) {
int bestScore = -1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '#';
int score = Minimax(board, depth + 1, 0, alpha, beta);
//printf("The computer:\n");
//printf("depth: %d\n",depth);
//Print_chessboard(board);
board[i][j] = ' ';
bestScore = (score > bestScore) ? score : bestScore;
// printf("bestScore: %d\n",bestScore);
alpha = (alpha > bestScore) ? alpha : bestScore;
//printf("alpha: %d\nbeta: %d\n",alpha,beta);
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
else {
int bestScore = 1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '*';
int score = Minimax(board, depth + 1, 1, alpha, beta);
//printf("The user:\n");
//printf("depth: %d\n",depth);
//Print_chessboard(board);
board[i][j] = ' ';
bestScore = (score < bestScore) ? score : bestScore;
//printf("bestScore: %d\n",bestScore);
beta = (beta < bestScore) ? beta : bestScore;
//printf("alpha: %d\nbeta: %d\n",alpha,beta);
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
}
// 电脑使用 Minimax 算法选择最佳移动
void Coordinate_computer(char board[ROW][COL]) {
int bestScore = -1000;
int bestMove[2] = { -1, -1 };
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '#';
int score = Minimax(board, 0, 0, -1000, 1000);
board[i][j] = ' ';
if (score > bestScore) {
bestScore = score;
bestMove[0] = i;
bestMove[1] = j;
}
}
}
}
if (bestMove[0] != -1 && bestMove[1] != -1) {
printf("The computer will enter a coordinate: %d %d\n", bestMove[0], bestMove[1]);
board[bestMove[0]][bestMove[1]] = '#';
}
}
这里面涉及到了一个递归函数，第一次看，你可能有点乱，我们简单地模拟一下这个递归函数：
我们来模拟一下递归过程：
假设我与电脑对弈，我是先手并将棋子下在了（1，1）。
下面是递推过程：
此时，程序调用函数 Coordinate_computer()：
遍历棋盘上的空位，并将空位设置成电脑棋子 ' # '
|-----|-----|-----|
| # | | |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
调用函数 Minimax(board, 0, 0, -1000, 1000)，其中参数 isMaximizing = 0。
检查发现没有获胜方，继续遍历并将下一个空位设置成玩家棋子 ' * '
|-----|-----|-----|
| # | * | |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
调用函数 Minimax(board, 1, 1, -1000, 1000)，其中参数 isMaximizing = 1。
检查发现没有获胜方，继续遍历并将下一个空位设置成电脑棋子 ' # '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
调用函数 Minimax(board, 2, 0, -1000, 1000)，其中参数 isMaximizing = 0。
检查发现没有获胜方，继续遍历并将下一个空位设置成玩家棋子 ' * '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | |
|-----|-----|-----|
| | | |
|-----|-----|-----|
调用函数 Minimax(board, 3, 1, -1000, 1000)，其中参数 isMaximizing = 1。
检查发现没有获胜方，继续遍历并将下一个空位设置成电脑棋子 ' # '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| | | |
|-----|-----|-----|
调用函数 Minimax(board, 4, 0, -1000, 1000)，其中参数 isMaximizing = 0。
检查发现没有获胜方，继续遍历并将下一个空位设置成玩家棋子 ' * '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | | |
|-----|-----|-----|
调用函数 Minimax(board, 5, 1, -1000, 1000)，其中参数 isMaximizing = 1。
检查发现没有获胜方，继续遍历并将下一个空位设置成电脑棋子 ' # '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | # | |
|-----|-----|-----|
调用函数 Minimax(board, 6, 0, -1000, 1000)，其中参数 isMaximizing = 0。
检查发现没有获胜方，继续遍历并将下一个空位设置成玩家棋子 ' * '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | # | * |
|-----|-----|-----|
再次调用 Minimax() 函数，发现双方平局，返回 0 。
下面是回归过程：
将结果 0 返回到 Minimax(board, 6, 0, -1000, 1000)，赋值给score
此时深度 depth = 6
将棋盘最后一个棋子清除：
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | # | |
|-----|-----|-----|
经过比较，bestScore = 0; alpha = -1000; beta = 0
因为这一层循环已经遍历到最后，直接返回 bestScore
将 bestScore = 0 返回到 Minimax(board, 5, 1, -1000, 1000)，赋值给 score
此时深度 depth = 5
将棋盘倒数第二个棋子清除：
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | | |
|-----|-----|-----|
经过比较，bestScore = 0; alpha = 0; beta = 1000
因为这一层循环并未结束，还差最后一个位置没有遍历。先把该位置设置成电脑棋子 ' # '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| * | | # |
|-----|-----|-----|
调用函数 Minimax(board, 6, 1, -1000, 1000)，注意这里 isMaximizing = 1
发现电脑获胜。因为此时深度 depth = 6，返回 10 - depth = 4
将 4 返回到函数 Minimax(board, 6, 1, -1000, 1000)，并赋值给 score
清除最后一个位置的棋子
经过比较， bestScore = 4; alpha = 4; beta = 1000
这一层循环已经到达最后，直接返回 bestScore
将 bestScore = 4 返回到函数 Minimax(board, 4, 0, -1000, 1000)，并赋值给 score
此时深度 depth = 4
将棋盘倒数第三个棋子清除：
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| | | |
|-----|-----|-----|
经过比较，bestScore = 4; alpha = -1000; beta = 4
因为这层循环没有结束，倒数第二个位置和倒数第一个位置没有遍历，先遍历倒数第二个位置，并将该位置设置成玩家棋子 ' * '
|-----|-----|-----|
| # | * | # |
|-----|-----|-----|
| * | * | # |
|-----|-----|-----|
| | * | |
|-----|-----|-----|
调用函数 Minimax(board, 5, 0, -1000, 1000)，发现玩家获胜
注意此时 depth = 5，返回 depth - 10 = -5
将 -5 返回到函数 Minimax(board, 5, 0, -1000, 1000)
经过比较，bestScore = -5; alpha = -1000; beta = -5
你可以仿照我的方法，多推演几步，你就能理解这个递归了，同时还能对 Minimax 算法和 alpha-beta 剪枝算法有更深的了解。注意每次一定要看看循环有没有结束，要注意变量的变化。
你可以在程序中加入常量或打印出变量的数值，这样你可以清晰的看到变量在递归过程中的变化，比如下面：代码是 Minimax 算法部分，在适当的位置打印变量的值和棋盘情况。
// Minimax 算法实现
int Minimax(char board[ROW][COL], int depth, int isMaximizing, int alpha, int beta) {
char result = Winner(board);
if (result == '#') {
return 10 - depth; // 电脑获胜
}
if (result == '*') {
return depth - 10; // 玩家获胜
}
if (IsBoardFull(board)) {
return 0; // 平局
}
if (isMaximizing) {
int bestScore = -1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '#';
int score = Minimax(board, depth + 1, 0, alpha, beta);
printf("The computer:\n");
printf("depth: %d\n",depth);
Print_chessboard(board);
board[i][j] = ' ';
bestScore = (score > bestScore) ? score : bestScore;
printf("bestScore: %d\n",bestScore);
alpha = (alpha > bestScore) ? alpha : bestScore;
printf("alpha: %d\nbeta: %d\n",alpha,beta);
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
else {
int bestScore = 1000;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (board[i][j] == ' ') {
board[i][j] = '*';
int score = Minimax(board, depth + 1, 1, alpha, beta);
printf("The user:\n");
printf("depth: %d\n",depth);
Print_chessboard(board);
board[i][j] = ' ';
bestScore = (score < bestScore) ? score : bestScore;
printf("bestScore: %d\n",bestScore);
beta = (beta < bestScore) ? beta : bestScore;
printf("alpha: %d\nbeta: %d\n",alpha,beta);
if (beta <= alpha) {
break; // Alpha-Beta 剪枝
}
}
}
}
return bestScore;
}
}
分享最新的 NVIDIA AI Software 资源以及活动/会议信息，精选收录AI相关技术内容，欢迎大家加入社区并参与讨论。
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)