我是博弈论的新手,只了解普通的 nim 游戏,您可以在无条件 的情况下从堆中移除石子,最后移除的玩家获胜。但是后来我在阅读时遇到了一个很好的问题 Game theory tutorial on Topcoder .要点如下:
You and a friend are playing a game in which you take turns removing stones from piles. Initially, every pile has at least as many stones as the pile to its left. This property must be maintained throughout the game. On each turn, you remove one or more stones from a single pile. You and your friend alternate turns until it is no longer possible to make a valid move. The last player to have made a move wins the game. Note that if you remove all the stones from a pile, it is still considered a pile. You are said to have made a "winning move" if after making that move, you can eventually win no matter what your friend does. You are given a int[] piles representing the number of stones in each pile from left to right. It is your turn to move. Find a winning move and return it as a String formatted as "TAKE s STONES FROM PILE k" (quotes for clarity only), where s and k (a 0-based index) are each integers with no leading zeros. If there are multiple winning moves, choose the one that minimizes s. If there is still a tie, choose the one that minimizes k. If no winning move is possible, return the String "YOU LOSE" (quotes for clarity only).
这里去石子有一个条件,需要保持整体的非递减顺序,这成为我想逻辑的障碍。我试着阅读 editorial为此,但不幸的是无法理解其背后的想法。谁能用更简单的术语解释解决方案?
最佳答案
这篇社论没有解释如何解决 Nim 的原始游戏,只是提供了维基百科页面的链接(可以在其中找到解决方案)。
这篇社论只是解释了如何将 Topcoder 问题映射到 Nim 的常规游戏中:
首先,可以将游戏转换成堆与原始堆之间存在差异的游戏(因此 3 6 6 示例变为 3 3 0)。
然后将堆的顺序颠倒(因此示例变为 0 3 3)。
然后这个新游戏中的一步变成了一个两步过程:从一堆中取出石头并将其添加到前一堆中(在示例中,获胜的一步从最后一个中取出 3 个并将它们添加到中间堆中,变成 0 6 0)。
然后,如果你只看奇数堆(#1、#3、#5 等),你就会得到 Nim 的常规游戏,并且可以对其应用记录的算法(所以 0 3 3 是与 Nim 位置 0 3 相同)。
因此给出的解释是:
关于c++ - Nim 变体游戏策略 - StoneGameStrategist - SRM 309,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47368492/