The Nim 21 Game represents a modified version of the well-known Nim game, a mathematical game often employed to demonstrate principles of combinatorial game theory. In traditional Nim games, the player who takes the last object emerges victorious; however, alternative versions require players to avoid selecting the final object. In the Nim 21 game, participants commence with a total of 21 items and are allowed to remove one, two, or three items per turn. The player forced to subtract the last item ultimately faces defeat, emphasizing the importance of strategic decision-making.
The objective is to maneuver the opponent into a disadvantageous position, forcing them to eliminate the final player. This encourages the development of strategic thinking skills that are transferable to digital formats as well.
Game Strategy:
The Nim 21 game stands out due to its inherent mathematical strategy, making it quite intriguing. The key to winning involves ensuring that the opponent is left with a multiple of 4 remaining items. This strategic move guarantees that regardless of the opponent's choice of 1, 2, or 3 items, the player will always force them to confront a multiple of 4 in the subsequent round. The ultimate goal is to manipulate the game in such a way that the opponent is left with exactly 4 items on their turn, paving the way for a definite victory for the player who starts the game. Once both players are aware of this optimal strategy, the game becomes completely predictable or deterministic in nature.
The Nim 21 game demonstrates fundamental concepts in game theory such as winning tactics and best possible actions. It is important to highlight that developers employed iterations and if-else statements to manage data flow. This serves as a prime illustration of translating a straightforward logical approach into code, making it accessible even to novice programmers by illustrating its inner workings and the cohesion of its components.
Approach-1: Basic Brute force approach
The Fundamental Brute Force strategy offers a simple technique for engaging in the Nim 21 game, making it ideal for novices. This technique involves players selecting random moves without strategic foresight, choosing to remove 1, 2, or 3 items within the permissible limits. The absence of a clear strategy leads to unpredictable game outcomes, often yielding subpar results due to overlooking the impact of a player's decisions on the opponent's moves.
This method serves as an excellent educational activity, necessitating fundamental programming principles like loops, conditionals, and input management. The process continues until it compels a player to select the final item, resulting in their loss. The benefit of this method is that it allows individuals to practice coding without needing to fully grasp that particular domain beforehand.
Program:
Let's consider a scenario to demonstrate the Nim 21 game in C++ employing a fundamental Brute Force strategy.
#include <iostream>
#include <cstdlib> // For rand() and srand()
#include <ctime> // For time()
using namespace std;
// Function to get the player's move with input validation
int getPlayerMove() {
int playerMove;
while (true) {
cout << "Your turn! Please enter 1, 2, or 3 to reduce the total: ";
cin >> playerMove;
// Check if the input is valid
if (playerMove >= 1 && playerMove <= 3) {
cout << "You chose to reduce the total by " << playerMove << ".\n";
break; // Valid move, exit the loop
} else {
cout << "Invalid move. Remember, you can only remove 1, 2, or 3 items.\n";
}
}
return playerMove;
}
// Function to generate the computer's move randomly
int getComputerMove() {
int computerMove = (rand() % 3) + 1; // Generates a random move (1, 2, or 3)
cout << "Computer's turn! It decides to reduce the total by " << computerMove << ".\n";
return computerMove;
}
// Function to display the current game status
void displayStatus(int total) {
cout << "Current total remaining: " << total << "\n";
if (total > 1) {
cout << "The game continues! Try not to leave yourself in a losing position.\n\n";
} else if (total == 1) {
cout << "Warning: Only 1 item left! Whoever has to take it will lose.\n\n";
}
}
int main() {
srand(static_cast<unsigned int>(time(0))); // Seed random number generator
int total = 21; // Starting total
cout << "Welcome to the Nim 21 Game! \n";
cout << "The rules are simple:\n";
cout << "1. We start with 21 items. Each turn, you can remove 1, 2, or 3 items from the total.\n";
cout << "2. The player who is forced to take the last item loses the game.\n";
cout << "3. Take turns with the computer until only one item remains.\n";
cout << "Let's begin! The starting total is " << total << ".\n";
// Game loop
while (total > 1) {
// Player's turn
displayStatus(total); // Display the current status before the player moves
int playerMove = getPlayerMove();
total -= playerMove;
cout << "You reduced the total to " << total << " by removing " << playerMove << " items.\n";
// Check if the player lost
if (total <= 0) { // If total becomes zero, player loses
cout << "\nOops! You've taken the last item.\n";
cout << "You lose! Better luck next time.\n";
break;
}
// Computer's turn
cout << "\nNow it's the computer's turn to play...\n";
displayStatus(total); // Display the status before the computer moves
int computerMove = getComputerMove();
total -= computerMove;
cout << "The computer reduced the total to " << total << " by removing " << computerMove << " items.\n";
// Check if the computer lost
if (total <= 0) { // If total becomes zero, computer loses
cout << "\nThe computer was forced to take the last item.\n";
cout << "Congratulations! You win the game!\n";
break;
}
}
// Game ends if total reaches exactly 1
if (total == 1) {
cout << "Only 1 item left! The next player to move loses.\n";
// If it's the player's turn, they lose
if (total % 2 == 1) {
cout << "\nThe computer wins this time. Try again for a better strategy next time!\n";
} else {
cout << "\nFantastic job! You've outplayed the computer and won the game!\n";
}
}
cout << "Thank you for playing!\n";
return 0;
}
Output:
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:
Explanation:
- Setup and Introduction: When the game starts, it has a welcome message explaining rules. The player and computer remove 1, 2, or 3 items each turn, and the person to take the last item loses. Rand and srand functions were used to initialize the random number generator by the current time to get different computer moves for our MCTS search.
- Game Loop: The turns are handled by the main loop while (total > 1). On each loop iteration: Player's Turn: We have a function called displayStatus that is used to show the current total. The getPlayerMove function provides the player's move in form (1, 2, or 3). It is checked to ensure that the input is valid; if not, it must be set back and retrieved again. If an invalid input is input, an error message is printed, and the player asks again. It is subtracted from the total once we confirm the player's move. Loss Check: After that, the code checks that the total is zero or less after every turn. Once the player gets the last item, a disclosure message indicates that he lost, and the game is over. Computer's Turn: The getComputerMove generates a random value between 1 and 3 to be used as a computer's move, which makes the game simple and unpredictable. After the move, the whole thing is made up again to see if the computer loses. End Condition: If the total is exactly 1, a message is given in case the total after the next move will determine the game. A message is displayed based on whose turn it is and tells the player or computer who is the winning player.
- Player's Turn: We have a function called displayStatus that is used to show the current total. The getPlayerMove function provides the player's move in form (1, 2, or 3). It is checked to ensure that the input is valid; if not, it must be set back and retrieved again. If an invalid input is input, an error message is printed, and the player asks again. It is subtracted from the total once we confirm the player's move.
- Loss Check: After that, the code checks that the total is zero or less after every turn. Once the player gets the last item, a disclosure message indicates that he lost, and the game is over.
- Computer's Turn: The getComputerMove generates a random value between 1 and 3 to be used as a computer's move, which makes the game simple and unpredictable. After the move, the whole thing is made up again to see if the computer loses.
- End Condition: If the total is exactly 1, a message is given in case the total after the next move will determine the game. A message is displayed based on whose turn it is and tells the player or computer who is the winning player.
This script covers fundamental concepts in control flow, validating input, and displaying messages, resulting in an interactive game that is approachable for novices to grasp and engage with.
Complexity Analysis:
Time Complexity
- Main Game Loop:
The primary while loop continues to iterate until the sum (initially 21) becomes 1 or less. Every player can take away 1, 2, or 3 items during their turn, resulting in a maximum of 21 iterations (assuming only one item is removed per turn in the worst-case scenario).
However, each object eliminated by a player permits the removal of a maximum of 3 objects. This reduction significantly decreases the anticipated number of rounds to an average of 7-10 moves. Consequently, the time complexity of the game loop is O(n), where n represents the total number of the initial objects (21).
- Player and Computer Moves:
In every scenario, the computer generates a random number (for the computer's action) or verifies the input (for the player's action). O(1): these tasks are executed in constant time.
Each failure assessment and the showState method are considered constant time operations, and the entire process remains constant time.
Overall, when continuously determining the number of items to include at each iteration, it becomes evident that this straightforward method consumes a total of O(n) time, where n represents the initial quantity of items.
Space Complexity
- Variables:
The code optimizes space complexity to O(1) through the utilization of a fixed set of integer variables (total, playerMove, computerMove).
- Invocations of Functions:
The functions getComputerMove and getPlayerMove are duplicated and simply need O(1) space as they do not rely on any extra data structures.
As there are no additional data structures for storage, the space complexity remains at O(1).
Approach-2: Optimal Strategy (Multiples of 4)
The game strategist devised a successful approach to the endgame in Nim 21, pinpointing multiples of 4 as pivotal. This tactic revolves around the principle that the optimal strategy is consistently ensuring the opponent faces a sum that is divisible by 4 after every turn. By maneuvering towards a scenario where the total amount diminishes to a multiple of 4, it forces the adversary to select 1, 2, or 3 objects. Ultimately, this strategic maneuvering sets the stage for their imminent defeat.
By consistently applying this approach during the game, we ensure that the player avoids selecting the final item, placing the opponent in a position where they are compelled to make the last move to try to catch up. Adhering to this strategy assures victory for the player who comprehends and adheres to it. This method, while straightforward, is highly effective and guarantees a win whenever we have the initial turn.
Program:
Let's consider a scenario to demonstrate the Nim 21 game in C++ using the most efficient method.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// Function to display the current status of the game
void displayStatus(int total) {
cout << "Current total: " << total << " items left." << endl;
}
// Function to get the player's move
int getPlayerMove(int total) {
int move;
while (true) {
cout << "Your turn! How many items would you like to take? (1, 2, or 3): ";
cin >> move;
if (move >= 1 && move <= 3 && move <= total) {
return move;
} else {
cout << "Invalid move. Please choose between 1, 2, or 3 items, and not more than the remaining items." << endl;
}
}
}
// Function to get the computer's move using the optimal strategy (multiples of 4)
int getComputerMove(int total) {
int move = total % 4;
cout << "Computer's turn..." << endl;
if (move == 0) {
// If the total is already a multiple of 4, the computer plays randomly
move = (rand() % 3) + 1;
cout << "The computer randomly decides to take " << move << " item(s)." << endl;
} else {
// If the total is not a multiple of 4, the computer makes the move that leaves a multiple of 4
move = move;
cout << "The computer decides to take " << move << " item(s) to leave you with " << total - move << " items." << endl;
}
return move;
}
int main() {
srand(time(0)); // Initialize random seed for randomness in computer's move
int total = 21; // The starting number of items
int playerMove, computerMove;
cout << "Welcome to the Nim 21 Game!" << endl;
cout << "The objective of the game is to avoid being the player who takes the last item." << endl;
cout << "You can take 1, 2, or 3 items on your turn." << endl;
cout << "The game starts with 21 items, and you will play against the computer." << endl;
cout << "Good luck!" << endl;
// Main game loop
while (total > 1) {
displayStatus(total);
// Player's turn
playerMove = getPlayerMove(total);
total -= playerMove;
cout << "You took " << playerMove << " item(s). " << total << " item(s) remaining." << endl;
if (total == 1) {
cout << "You left 1 item remaining. The computer will have to take the last item and lose!" << endl;
break;
}
// Computer's turn
computerMove = getComputerMove(total);
total -= computerMove;
cout << "The computer took " << computerMove << " item(s). " << total << " item(s) remaining." << endl;
if (total == 1) {
cout << "The computer left 1 item remaining. You will have to take the last item and lose!" << endl;
break;
}
}
// Determine the winner
if (total == 1) {
if (total % 2 == 0) {
cout << "Congratulations! You win!" << endl;
} else {
cout << "Sorry! You lose. Better luck next time!" << endl;
}
}
return 0;
}
Output:
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):
Explanation:
- Initial Setup: On day one of the game, 21 items are available. After that, the player and the computer take turns removing one, two, or three items. When using the modulo operation (total % 4), the computer always leaves the opponent with a multiple of 4 items.
- Displaying the Status: It shows the player's current number of items left after each move with the displayStatus function.
- Player's Move: The getPlayerMove function asks the player which item to take ( 1, 2, or 3 ). The move only allows the move if the input is valid (i.e., no more items are moving than exist).
- Computer's Move: The getComputerMove function implements the optimal strategy. In the computer move, if the total is already a multiple of 4, the computer makes a random move; otherwise, the computer calculates the move that leaves a multiple of 4 items for the player. It ensures that if the computer plays optimally, it won't lose.
- Game Loop: There is a loop until the total reaches 1. The program will check after each move whether the game has ended, i.e., if the next player will be forced to complete the game with the last item to lose.
- End Conditions: The game ends if there is only one item left. The winner is announced depending on who is responsible for the last item taken.
Complexity Analysis:
Time Complexity:
- Player Move: This particular function encompasses a basic validation process to ensure that the player's move is valid (consisting of 1, 2, or 3 items). The validation loop iterates only once per turn as it terminates once a valid input is provided. Consequently, the time complexity of the getPlayerMove function remains O(1).
- Computer Move: In contrast, the getComputerMove function computes the optimal move using a modulo operation (total % 4). This operation is considered constant time, denoted as O(1). The computer simply verifies if the total is a multiple of four and then proceeds to play randomly or based on a predefined strategy, still maintaining a time complexity of O(1).
Space Complexity:
- Variable Space: The minimum space usage of the program is single O(1) integer variables (total, playerMove, computerMove) used in the program.
- Input Storage: The player's move takes only O(1) space on a single integer variable.
- Function Call Stack: Because the game operates in an iterative loop, all memory required by the game is for the main loop, and non-iterative recursions or function calls do not increase the recursion depth or function call stack. It means that we have an O(1) space complexity from function calls. It is O(1) dominated by the variables and their fixed size.
