分支因子和深度
Branching Factor and Depth
Question
A simple two-player game involves a pile of N matchsticks and two
players who have alternating turns. In each turn, a player removes 1,
2 or 3 matchsticks from the pile. The player who removes the last
matchstick loses the game.
A) What are the branching factor and depth of the game tree (give a general solution expressed in terms of N)? How large is the search
space?
B) How many unique states are there in the game? For large N what could be done to make the search more efficient?
回答
A) 我说过分支因子是 3 但我证明了这一点是因为玩家最多只能删除 3 个匹配项，这意味着我们的树通常有三个 children。第二部分关于深度，我不确定。
B) N x 2 其中 N 是剩余的匹配数。我不确定我们如何才能使搜索更有效率？也许引入 Alpha-beta 修剪？
任何时刻的比赛状态都可以用轮到谁和每个选手的比赛次数来描述。在 n 次移动之后，有 3^n 种可能的历史记录，但是对于大 n，可能的状态少于 3^n 种，因此您可以节省时间，例如，认识到您即将遇到您已经遇到的状态并且计算出之前的值。
另请参阅 https://en.wikipedia.org/wiki/Nim - 如果这是 Nim，或 Nim 的变体，则已经为它制定了有效的策略。
一个：
对于深度，想象一下最长的游戏会是什么样子。这是由两名玩家组成的游戏，每回合只移除 1 场比赛。由于有 n 场比赛，这样的比赛将进行 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.
都是正确的
Question
A simple two-player game involves a pile of N matchsticks and two players who have alternating turns. In each turn, a player removes 1, 2 or 3 matchsticks from the pile. The player who removes the last matchstick loses the game.
A) What are the branching factor and depth of the game tree (give a general solution expressed in terms of N)? How large is the search space?
B) How many unique states are there in the game? For large N what could be done to make the search more efficient?
回答
A) 我说过分支因子是 3 但我证明了这一点是因为玩家最多只能删除 3 个匹配项，这意味着我们的树通常有三个 children。第二部分关于深度，我不确定。
B) N x 2 其中 N 是剩余的匹配数。我不确定我们如何才能使搜索更有效率？也许引入 Alpha-beta 修剪？
任何时刻的比赛状态都可以用轮到谁和每个选手的比赛次数来描述。在 n 次移动之后，有 3^n 种可能的历史记录，但是对于大 n，可能的状态少于 3^n 种，因此您可以节省时间，例如，认识到您即将遇到您已经遇到的状态并且计算出之前的值。
另请参阅 https://en.wikipedia.org/wiki/Nim - 如果这是 Nim，或 Nim 的变体，则已经为它制定了有效的策略。
一个： 对于深度，想象一下最长的游戏会是什么样子。这是由两名玩家组成的游戏，每回合只移除 1 场比赛。由于有 n 场比赛，这样的比赛将进行 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.