我们强烈建议将下面的文章作为本文的先决条件。
在这篇文章中，我们将讨论尼姆的游戏。尼姆的游戏由以下规则描述-
“ 给定若干堆，其中每一堆包含一定数量的石头/硬币。在每一回合中，玩家只能选择一堆，并从该堆中移除任意数量的石头（至少一块）。不能移动的玩家将被视为输掉比赛（即，拿走最后一块石头的玩家为赢家）。 ”
例如，考虑有两个玩家—— A. 和 B ，最初有三堆硬币 3, 4, 5 如下图所示。我们假设第一步是由 A. .请参阅下图，以清楚了解整个游戏。
A赢了比赛（注：A迈出了第一步）
他也是 A. 在这个游戏中有很强的专业知识吗？或者他/她在这方面有些优势 B 先开始？
现在让我们再次玩，使用与上面相同的桩配置，但这一次 B 先开始，而不是 A. .
B赢了比赛（注：B迈出了第一步）
B 综上所述，必须明确的是，比赛取决于一个重要因素——谁先开始比赛？
那么先发球员每次都会赢吗？ 让我们再次玩这个游戏，从 A. ，这一次使用了不同的桩初始配置。这堆硬币最初有1、4、5枚硬币。
将 A. 又赢了，因为他先开始了？让我们看看。 
A迈出了第一步，但输掉了比赛。
因此，结果是明确的。 A. 他输了。但是怎么做呢？我们知道这场比赛很大程度上取决于哪个球员先开始。因此，一定还有另一个因素主导着这个简单而有趣的游戏的结果。该因素是堆/桩的初始配置。这一次的初始配置与前一次不同。
所以，我们可以得出结论，这个游戏取决于两个因素-
- 先开始的球员。
- 桩/堆的初始配置。
事实上，我们甚至可以在玩游戏之前预测游戏的赢家！
尼姆·苏姆： 在游戏的任何一点上，每堆硬币/石头数量的累积XOR值在该点被称为Nim Sum。 “如果两者都有 A. 和 B 如果游戏开始时的Nim和不为零，那么先开始的玩家一定会赢。否则，如果Nim和的计算结果为零，则player A. 肯定会输。”
有关上述定理的证明，请参见- https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula
最佳策略：
- 理解最佳策略所需的关于位异或的两个推论：
- 如果“n”个数的异或和已经为零，则不可能通过对一个数进行一次缩减使异或和为零。
- 如果n个数的异或和不为零，那么至少有一种方法，如果你减少一个数，那么异或和为零。
最初可能存在两种情况。
案例1：初始Nim和为零 正如我们所知，在这种情况下，如果发挥最佳 B 胜利，这意味着 B 总是希望Nim和为零 A. 轮到你了。 所以，由于Nim和最初为零，无论项数是多少 A. 移除新的Nim和将不为零（如上所述）。还有 B 我更喜欢尼姆零和 A. 轮到他时，他会做出一个动作，使Nim和再次为零（如上所述，这总是可能的）。 游戏将运行，只要有项目在任何一堆和在各自的回合 A. 会使尼姆和非零 B 会使它再次为零，最终将不再有元素留下 B 选择最后一位赢得比赛。
从上面的解释可以明显看出，每个玩家的最佳策略是在每一轮中让对手的Nim和为零，如果已经为零，这是不可能的。
案例2：初始Nim和非零 现在选择最佳方法 A. 将使Nim和现在为零（这是可能的，因为初始Nim和是非零的，如上所述）。现在，在 B 不管是什么数字，nim和已经是零了 B 如果选择，nim和将是非零和 A. 可以选择一个数字使nim和再次为零。只要有任何一堆可用的物品，这将继续下去。 和 A. 将是选择最后一项的人。
因此，正如在上述案例中所讨论的，现在应该很明显，对于任何玩家来说，最佳策略是使nim和为零，如果它是非零的，那么如果它已经为零，那么无论玩家现在做出什么动作，它都可以被反击。
让我们在上面的游戏中应用上述定理。在第一场比赛中 A. 首先开始，游戏开始时的Nim和是，3xor 4xor 5=2，这是一个非零值，因此 A. 赢了而在第二个游戏中，当桩的初始配置为1、4、5和5时 A. 先开始，然后 A. 注定要输，因为游戏开始时的Nim总和是1或4或5=0。
实施：
在下面的程序中，我们在计算机和人类（用户）之间玩Nim游戏 下面的程序使用两个函数 KnowWinnerBeforReplaying（）： ：播放前告知结果。 playGame（）： 全场比赛，最后宣布胜利者。函数playGame（）不接受人类（用户）的输入，而是使用rand（）函数随机拾取一堆石头，并从拾取的石头中随机移除任意数量的石头。
通过删除rand（）函数并插入cin或scanf（）函数，可以修改以下程序以获取用户的输入。
C++
/* A C++ program to implement Game of Nim. The program assumes that both players are playing optimally */ #include <iostream> #include <math.h> using namespace std; #define COMPUTER 1 #define HUMAN 2 /* A Structure to hold the two parameters of a move A move has two parameters- 1) pile_index = The index of pile from which stone is going to be removed 2) stones_removed = Number of stones removed from the pile indexed = pile_index */ struct move { int pile_index; int stones_removed; }; /* piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n -> Number of piles The piles[] are having 0-based indexing*/ // A C function to output the current game state. void showPiles ( int piles[], int n) { int i; cout << "Current Game Status -> " ; for (i=0; i<n; i++) cout << " " << piles[i]; cout << "" ; return ; } // A C function that returns True if game has ended and // False if game is not yet over bool gameOver( int piles[], int n) { int i; for (i=0; i<n; i++) if (piles[i]!=0) return ( false ); return ( true ); } // A C function to declare the winner of the game void declareWinner( int whoseTurn) { if (whoseTurn == COMPUTER) cout << "HUMAN won" ; else cout << "COMPUTER won" ; return ; } // A C function to calculate the Nim-Sum at any point // of the game. int calculateNimSum( int piles[], int n) { int i, nimsum = piles[0]; for (i=1; i<n; i++) nimsum = nimsum ^ piles[i]; return (nimsum); } // A C function to make moves of the Nim Game void makeMove( int piles[], int n, struct move * moves) { int i, nim_sum = calculateNimSum(piles, n); // The player having the current turn is on a winning // position. So he/she/it play optimally and tries to make // Nim-Sum as 0 if (nim_sum != 0) { for (i=0; i<n; i++) { // If this is not an illegal move // then make this move. if ((piles[i] ^ nim_sum) < piles[i]) { (*moves).pile_index = i; (*moves).stones_removed = piles[i]-(piles[i]^nim_sum); piles[i] = (piles[i] ^ nim_sum); break ; } } } // The player having the current turn is on losing // position, so he/she/it can only wait for the opponent // to make a mistake(which doesn't happen in this program // as both players are playing optimally). He randomly // choose a non-empty pile and randomly removes few stones // from it. If the opponent doesn't make a mistake,then it // doesn't matter which pile this player chooses, as he is // destined to lose this game. // If you want to input yourself then remove the rand() // functions and modify the code to take inputs. // But remember, you still won't be able to change your // fate/prediction. else { // Create an array to hold indices of non-empty piles int non_zero_indices[n], count; for (i=0, count=0; i<n; i++) if (piles[i] > 0) non_zero_indices [count++] = i; (*moves).pile_index = ( rand () % (count)); (*moves).stones_removed = 1 + ( rand () % (piles[(*moves).pile_index])); piles[(*moves).pile_index] = piles[(*moves).pile_index] - (*moves).stones_removed; if (piles[(*moves).pile_index] < 0) piles[(*moves).pile_index]=0; } return ; } // A C function to play the Game of Nim void playGame( int piles[], int n, int whoseTurn) { cout << "GAME STARTS" ; struct move moves; while (gameOver (piles, n) == false ) { showPiles(piles, n); makeMove(piles, n, &moves); if (whoseTurn == COMPUTER) { cout << "COMPUTER removes" << moves.stones_removed << "stones from pile at index " << moves.pile_index << endl; whoseTurn = HUMAN; } else { cout << "HUMAN removes" << moves.stones_removed << "stones from pile at index " << moves.pile_index << endl; whoseTurn = COMPUTER; } } showPiles(piles, n); declareWinner(whoseTurn); return ; } void knowWinnerBeforePlaying( int piles[], int n, int whoseTurn) { cout << "Prediction before playing the game -> " ; if (calculateNimSum(piles, n) !=0) { if (whoseTurn == COMPUTER) cout << "COMPUTER will win" ; else cout << "HUMAN will win" ; } else { if (whoseTurn == COMPUTER) cout << "HUMAN will win" ; else cout << "COMPUTER will win" ; } return ; } // Driver program to test above functions int main() { // Test Case 1 int piles[] = {3, 4, 5}; int n = sizeof (piles)/ sizeof (piles[0]); // We will predict the results before playing // The COMPUTER starts first knowWinnerBeforePlaying(piles, n, COMPUTER); // Let us play the game with COMPUTER starting first // and check whether our prediction was right or not playGame(piles, n, COMPUTER); /* Test Case 2 int piles[] = {3, 4, 7}; int n = sizeof(piles)/sizeof(piles[0]); // We will predict the results before playing // The HUMAN(You) starts first knowWinnerBeforePlaying (piles, n, COMPUTER); // Let us play the game with COMPUTER starting first // and check whether our prediction was right or not playGame (piles, n, HUMAN); */ return (0); } // This code is contributed by shivanisinghss2110 |
C
/* A C program to implement Game of Nim. The program assumes that both players are playing optimally */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define COMPUTER 1 #define HUMAN 2 /* A Structure to hold the two parameters of a move A move has two parameters- 1) pile_index = The index of pile from which stone is going to be removed 2) stones_removed = Number of stones removed from the pile indexed = pile_index */ struct move { int pile_index; int stones_removed; }; /* piles[] -> Array having the initial count of stones/coins in each piles before the game has started. n -> Number of piles The piles[] are having 0-based indexing*/ // A C function to output the current game state. void showPiles ( int piles[], int n) { int i; printf ( "Current Game Status -> " ); for (i=0; i<n; i++) printf ( "%d " , piles[i]); printf ( "" ); return ; } // A C function that returns True if game has ended and // False if game is not yet over bool gameOver( int piles[], int n) { int i; for (i=0; i<n; i++) if (piles[i]!=0) return ( false ); return ( true ); } // A C function to declare the winner of the game void declareWinner( int whoseTurn) { if (whoseTurn == COMPUTER) printf ( "HUMAN won" ); else printf ( "COMPUTER won" ); return ; } // A C function to calculate the Nim-Sum at any point // of the game. int calculateNimSum( int piles[], int n) { int i, nimsum = piles[0]; for (i=1; i<n; i++) nimsum = nimsum ^ piles[i]; return (nimsum); } // A C function to make moves of the Nim Game void makeMove( int piles[], int n, struct move * moves) { int i, nim_sum = calculateNimSum(piles, n); // The player having the current turn is on a winning // position. So he/she/it play optimally and tries to make // Nim-Sum as 0 if (nim_sum != 0) { for (i=0; i<n; i++) { // If this is not an illegal move // then make this move. if ((piles[i] ^ nim_sum) < piles[i]) { (*moves).pile_index = i; (*moves).stones_removed = piles[i]-(piles[i]^nim_sum); piles[i] = (piles[i] ^ nim_sum); break ; } } } // The player having the current turn is on losing // position, so he/she/it can only wait for the opponent // to make a mistake(which doesn't happen in this program // as both players are playing optimally). He randomly // choose a non-empty pile and randomly removes few stones // from it. If the opponent doesn't make a mistake,then it // doesn't matter which pile this player chooses, as he is // destined to lose this game. // If you want to input yourself then remove the rand() // functions and modify the code to take inputs. // But remember, you still won't be able to change your // fate/prediction. else { // Create an array to hold indices of non-empty piles int non_zero_indices[n], count; for (i=0, count=0; i<n; i++) if (piles[i] > 0) non_zero_indices [count++] = i; (*moves).pile_index = ( rand () % (count)); (*moves).stones_removed = 1 + ( rand () % (piles[(*moves).pile_index])); piles[(*moves).pile_index] = piles[(*moves).pile_index] - (*moves).stones_removed; if (piles[(*moves).pile_index] < 0) piles[(*moves).pile_index]=0; } return ; } // A C function to play the Game of Nim void playGame( int piles[], int n, int whoseTurn) { printf ( "GAME STARTS" ); struct move moves; while (gameOver (piles, n) == false ) { showPiles(piles, n); makeMove(piles, n, &moves); if (whoseTurn == COMPUTER) { printf ( "COMPUTER removes %d stones from pile " "at index %d" , moves.stones_removed, moves.pile_index); whoseTurn = HUMAN; } else { printf ( "HUMAN removes %d stones from pile at " "index %d" , moves.stones_removed, moves.pile_index); whoseTurn = COMPUTER; } } showPiles(piles, n); declareWinner(whoseTurn); return ; } void knowWinnerBeforePlaying( int piles[], int n, int whoseTurn) { printf ( "Prediction before playing the game -> " ); if (calculateNimSum(piles, n) !=0) { if (whoseTurn == COMPUTER) printf ( "COMPUTER will win" ); else printf ( "HUMAN will win" ); } else { if (whoseTurn == COMPUTER) printf ( "HUMAN will win" ); else printf ( "COMPUTER will win" ); } return ; } // Driver program to test above functions int main() { // Test Case 1 int piles[] = {3, 4, 5}; int n = sizeof (piles)/ sizeof (piles[0]); // We will predict the results before playing // The COMPUTER starts first knowWinnerBeforePlaying(piles, n, COMPUTER); // Let us play the game with COMPUTER starting first // and check whether our prediction was right or not playGame(piles, n, COMPUTER); /* Test Case 2 int piles[] = {3, 4, 7}; int n = sizeof(piles)/sizeof(piles[0]); // We will predict the results before playing // The HUMAN(You) starts first knowWinnerBeforePlaying (piles, n, COMPUTER); // Let us play the game with COMPUTER starting first // and check whether our prediction was right or not playGame (piles, n, HUMAN); */ return (0); } |
Prediction before playing the game -> COMPUTER will win GAME STARTS Current Game Status -> 3 4 5 COMPUTER removes 2 stones from pile at index 0 Current Game Status -> 1 4 5 HUMAN removes 3 stones from pile at index 1 Current Game Status -> 1 1 5 COMPUTER removes 5 stones from pile at index 2 Current Game Status -> 1 1 0 HUMAN removes 1 stones from pile at index 1 Current Game Status -> 1 0 0 COMPUTER removes 1 stones from pile at index 0 Current Game Status -> 0 0 0 COMPUTER won
参考资料： https://en.wikipedia.org/wiki/Nim
本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并且想贡献自己的力量，你也可以写一篇文章，并将文章邮寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
