C++ 21 点游戏

Nim 21 游戏 是 Nim 的一个变体，Nim 是经典的数学游戏，用于例证组合博弈论原理。在 Nim 游戏中，赢得者拿走最后一个物品；其他变体则要求玩家从集合中拿走物品，目标是永远不拿走最后一个。在 Nim 21 游戏中，玩家以 21 个物品开始，在每一轮中，可以拿走一个、两个或三个物品。因为会迫使输家拿走最后一个物品，所以需要策略性思考。

目标是将对方置于不利位置，使其被迫拿走最后一个物品。它有助于理解逻辑策略，这些策略也可以应用于计算机化形式。

游戏策略

Nim 21 游戏有趣之处在于其数学策略是固有的。获胜策略是让对手处于一个剩下物品数量仍是 4 的倍数的位置。这将保证，无论对手拿走 1、2 或 3 个物品中的哪一个，玩家都将迫使对手在下一轮离开 4 的倍数。关键在于，当对手轮到他们时，他们会留下正好 4 个物品；这是对先手的玩家来说不可避免的胜利之路。当双方都知道最优策略时，游戏是确定性的。

Nim 21 游戏展示了博弈论的基本主题：获胜策略和最优走法。应注意的是，它们利用了循环和条件语句，并能够处理输入输出。这是一个很好的例子，说明如何将简单的逻辑策略以代码形式编写，也适合编程初学者，因为任何人都可以理解它的工作原理以及每个部分如何组合在一起。

方法一：基本暴力破解方法

基本暴力破解方法是玩 Nim 21 游戏的直接方式，适合初学者。在此方法中，玩家进行随机走法（忘记策略规划），在允许范围内拿走 1、2 或 3 个物品。由于缺乏策略，这种游戏结果不可预测，并且当我们不考虑玩家的选择如何影响对手的走法时，通常会导致次优结果。

这种方法是一个很好的学习练习，需要基本的编程概念，如循环、条件语句和输入处理。它一直进行，直到迫使一名玩家拿走最后一个物品并输掉。这种方法的优点在于我们可以学习编码，而无需先掌握该特定领域。

程序

让我们以一个例子来说明如何使用基本暴力破解方法在 C++ 中实现 Nim 21 游戏。

输出

 
Welcome to the Nim 21 Game! 
The rules are simple:
1. We start with 21 items. Each turn, you can remove 1, 2, or 3 items from the total.
2. The player who is forced to take the last item loses the game.
3. Take turns with the computer until only one item remains.
Let's begin! The starting total is 21.
Current total remaining: 21
The game continues! Try not to leave yourself in a losing position.

Your turn! Please enter 1, 2, or 3 to reduce the total: 2
You chose to reduce the total by 2.
You reduced the total to 19 by removing 2 items.

Now it's the computer's turn to play...
Current total remaining: 19
The game continues! Try not to leave yourself in a losing position.

Computer's turn! It decides to reduce the total by 1.
The computer reduced the total to 18 by removing 1 items.
Current total remaining: 18
The game continues! Try not to leave yourself in a losing position.

Your turn! Please enter 1, 2, or 3 to reduce the total: 2
You chose to reduce the total by 2.
You reduced the total to 16 by removing 2 items.

Now it's the computer's turn to play...
Current total remaining: 16
The game continues! Try not to leave yourself in a losing position.

Computer's turn! It decides to reduce the total by 1.
The computer reduced the total to 15 by removing 1 items.
Current total remaining: 15
The game continues! Try not to leave yourself in a losing position.

Your turn! Please enter 1, 2, or 3 to reduce the total:   

说明

1. 设置和介绍：游戏开始时，会有一个欢迎消息解释规则。玩家和计算机轮流拿走 1、2 或 3 个物品，拿走最后一个物品的人输。Rand() 和 srand() 函数用于通过当前时间初始化随机数生成器，为我们的 MCTS 搜索获取不同的计算机走法。
2. 游戏循环：回合由主循环 while (total > 1) 处理。在每次循环迭代中
   
   • 玩家回合：我们有一个名为 displayStatus 的函数，用于显示当前总数。getPlayerMove 函数以 (1, 2, 或 3) 的形式提供玩家的走法。它会被检查以确保输入有效；如果无效，则必须重置并重新获取。如果输入无效，则会打印错误消息，并再次提示玩家输入。一旦确认玩家的走法，就会将其从总数中减去。
   • 输赢检查：之后，代码会在每个回合后检查总数是否为零或更少。一旦玩家拿走最后一个物品，一个提示消息会表明他输了，游戏结束。
   • 计算机回合：getComputerMove 生成一个介于 1 和 3 之间的随机值作为计算机的走法，这使得游戏简单且不可预测。走法完成后，会再次检查是否计算机输。
   • 结束条件：如果总数恰好是 1，则会显示一条消息，说明下一个走法将决定游戏。消息会根据当前是谁的回合显示，并告知玩家或计算机谁是获胜者。

此代码提供了控制结构、输入验证和输出消息的基础知识，创建了一个易于初学者理解和遵循的交互式游戏。

复杂度分析

时间复杂度

1. 主游戏循环

现在，主 while 循环会一直运行，直到总数（从 21 开始）小于或等于 1。每个玩家每回合拿走 1、2 或 3 个物品，因此我们最多有 21 次迭代（最坏情况是每回合只拿走一个物品）。

然而，玩家拿走的每个物品允许最多拿走 3 个物品。这使得预期的迭代次数减少到大约 7-10 次，平均而言。在这种情况下，游戏循环的时间复杂度为 O(n)，其中 n 是初始总数（21）。

2. 玩家和计算机走法

在每种情况下，计算机都会取一个随机数（对于计算机的走法）或验证输入（对于玩家的走法）。O(1)：这些操作是常数时间。

每次输赢检查和 displayStatus 函数都是 O(1) 操作，整个过程都是 O(1)。

总体而言，如果我们持续计算每一步可以拿走多少物品，我们会发现这种暴力破解方法总的时间复杂度为 O(n)，其中 n 是物品的初始总数。

空间复杂度

1. 变量

代码使用固定数量的整数 变量（total、playerMove、computerMove），空间复杂度为 O(1)。

2. 函数调用

getComputerMove 和 getPlayerMove 函数会被重复调用，并且只需要 O(1) 空间，因为它们不需要任何额外的数据结构。

由于没有额外用于存储的 数据结构，空间复杂度为 O(1)。

方法二：最优策略（4 的倍数）

游戏理论上为玩 Nim 21 确立了获胜阶段，并且 4 的倍数是明确的。这种策略包括知道我们的获胜策略始终是在每次走法结束时给对手留下一个 4 的倍数。达到一个总数减少到 4 的倍数，这意味着对手必须拿走 1、2 或 3 个物品。他们最终会陷入一个失败的位置只是时间问题。

为此，我们在整个游戏中保持此策略，以便玩家永远不会拿走最后一个物品，而是将对手置于一个被迫走法的境地，他们将不得不拿走最后一个物品以赶上。此策略保证了理解并遵循此策略的玩家将获胜。这是一种简单但非常好的技术，如果我们先手，它将始终确保我们获胜。

程序

让我们以一个例子来说明如何使用最优策略在 C++ 中实现 Nim 21 游戏。

输出

 
Welcome to the Nim 21 Game!
The objective of the game is to avoid being the player who takes the last item.
You can take 1, 2, or 3 items on your turn.
The game starts with 21 items, and you will play against the computer.
Good luck!
Current total: 21 items left.
Your turn! How many items would you like to take? (1, 2, or 3): 1
You took 1 item(s). 20 item(s) remaining.
Computer's turn...
The computer randomly decides to take 1 item(s).
The computer took 1 item(s). 19 item(s) remaining.
Current total: 19 items left.
Your turn! How many items would you like to take? (1, 2, or 3):    

说明

1. 初始设置
   游戏开始时，有 21 个物品可用。之后，玩家和计算机轮流拿走一个、两个或三个物品。
   当使用模运算（total % 4）时，计算机总是给对手留下 4 的倍数的物品。
2. 显示状态
   它使用 displayStatus 函数显示每次走法后玩家剩余的物品数量。
3. 玩家走法
   getPlayerMove 函数询问玩家要拿走哪个物品（1、2 或 3）。该走法只有在输入有效时才允许（即，拿走的物品数量不超过剩余物品数量）。
4. 计算机走法
   getComputerMove 函数实现了最优策略。在计算机走法中，如果总数已经是 4 的倍数，则计算机进行随机走法；否则，计算机计算留下 4 的倍数物品给玩家的走法。它确保如果计算机采取最优策略，它就不会输。
5. 游戏循环
   有一个循环，直到总数达到 1。程序会在每次走法后检查游戏是否结束，即下一个玩家是否将被迫用最后一个物品完成游戏并输掉。
6. 结束条件
   如果只剩下一个物品，游戏就结束了。根据谁拿走了最后一个物品来宣布获胜者。

复杂度分析

时间复杂度

1. 玩家走法
   此函数包含一个简单的验证循环，以确保玩家已正确走法（1、2 或 3 个物品）。循环每回合只运行一次，因为一旦玩家输入了有效输入，它就会退出。因此，getPlayerMove() 函数的时间复杂度为 O(1)。
2. 计算机走法
   getComputerMove() 函数通过模运算（total % 4）简单地计算最优走法。这是一个常数时间操作，即 O(1)。计算机只是检查总数是否已经是 4 的倍数，然后随机或根据策略走法，但它仍然是 O(1)。

空间复杂度

1. 变量空间
   程序最小的空间使用是程序中使用的 O(1) 个整数变量（total、playerMove、computerMove）。
2. 输入存储
   玩家的走法仅使用一个 O(1) 的整数变量。
3. 函数调用堆栈
   由于游戏以迭代循环的形式运行，游戏所需的所有内存都用于主循环，非迭代递归或 函数调用不会增加 递归深度或函数调用堆栈。这意味着我们从函数调用中获得的 O(1) 空间复杂度。
   由变量及其固定大小决定，其复杂度为 O(1)。