问分支因子和深度

EN

答:就深度而言，想象一下最长的游戏会是什么样子。这是一个游戏，由两名球员组成，每个回合只有1场比赛。由于有n个匹配，这样的游戏将轮流进行:树有n个深度。

B:只有2个*N状态，每个状态都可以从3个较高的火柴计数状态访问。由于匹配的数量必然会随着游戏的进行而减少，所以可能的状态图是DAG (有向无圈图)。因此，可以用动态规划方法来分析这个游戏。最后，您将看到最优移动仅取决于N mod 4，剩余匹配数为N。

编辑:证明的想法N mod 4：每个职位要么是一个输赢的立场或一个胜利的立场。失去位置是一种情况，无论你玩什么，如果你的对手发挥得最好，你就会输。同样地，一个胜利的位置是一种情况，如果你发挥正确的移动，对手不可能赢。N=1是一个失败的位置(根据游戏的定义)。因此，N=2,3,4是获胜的位置，因为通过移除正确的匹配量，您将对手置于一个失败的位置。N=5是一个失败的位置，因为不管你删除了多少个匹配项，你都会把对手放在一个获胜的位置。N=6,7,8是赢家.你知道这个主意。

现在，这只是一个正式的证明:假设一个位置N是一个丢失的位置当且仅当N mod 4 = 1。如果在某些整数k上这样做是正确的，那么您可以证明k+1是正确的。正如我们前面所展示的那样，这对于k = 4来说是正确的。通过递归，对任何N都是正确的。

游戏的状态在任何时候都可以用谁的回合和每个玩家举行的比赛次数来描述。在n个移动之后，有3^n可能的历史，但是对于大的n，许多小于3^n的可能状态，所以您可以节省时间，例如，通过识别您即将遇到一个您已经遇到的状态并计算出以前的值。

也请参阅https://en.wikipedia.org/wiki/Nim --如果这是Nim，或者是各种Nim，那么已经为它制定了有效的策略。