计算减法游戏的赢得策略

问题：
假设有100个宝石，两个玩家交替取出宝石。人们可以从1到15中的任何数字;但是，不能接受已经采取的任何号码。如果在比赛结束时，剩下k个棋子，但是1到k都是以前被占用的，可以拿k个棋子。拿到最后一块石头的人获胜。第一个玩家如何赢得比赛？计算减法游戏的赢得策略

我的想法
使用递归（或动态编程）。基本情况1，其中玩家1具有获胜策略。减少：n个石头离开，如果在线播放1采用M1的石头，他必须确保所有选项的球员有2（M2），他有一个成功的策略。因此问题被减少到（n - m1 - m2）。

跟进问：
如果一个使用DP，则填充表格的潜在数量较大（2^15），从左边的可用选项取决于历史，其中有2^15的可能性。
如何优化？

来源

2017-08-14 yangsuli

这是一个所谓的Nim游戏。可以用Sprague-Grundy定理和nimbers来解决。见：https://en.wikipedia.org/wiki/Nim#The_subtraction_game_S.281.2C_2.2C_._._..2C_k.29 – m69

2^15 = 32768，这似乎很小，所以似乎没有任何需要优化？（请注意，知道已完成拍摄的数字决定了游戏的状态，因此每个人只需要存储一个数字，即最终获胜者） –

@ m69我认为Nim游戏无记忆：您的选择可以不依赖于历史 – yangsuli

假设该组剩余数的可被表示为R，剩余的后您的选择可以由RH表示，并且剩余的最低数目可以是RL的最高数量，诀窍是使用您的第二到最后一个移动将数量提高至< 100-RH，但> 100-RH-RL。这迫使你的对手采取一个数字，将你的胜利范围。

殊荣，与你与你的第二个到最后一步创建总数的最终范围是：

N < 100-RH 
N > 100-RH-RL

通过观察我注意到，相对湿度可高达15和低为8. RL可以低至1并且高至13.从这个范围我评估了等式。

N < 100-[8:15]   => N < [92:85] 
N > 100-[8:15]-[1:13] => N > [92:85] - [1:13] => N > [91:72]

其他考虑可以缩小这个差距。 RL，例如，仅13中的边缘的情况总是导致对于玩家A损失，所以真正的范围是72和91之间有一个类似的问题与RH和它的低端，所以最终的范围并计算如下：

N < 100-[9:15]   => N < [91:85] 
N > 100-[9:15]-[1:12] => N > [91:85] - [1:12] => N > [90:73] 
[90:73] < N < [91:85]

然而，在此之前，可能性爆炸。记住，这是在选择倒数第二个数字之后，而不是之前。在这一点上，他们被迫选择一个可以让你赢的数字。

注意，90是不是一个有效的选择有赢，即使它可能存在。因此，它可以最大为89 N的真正范围：

[88:73] < N < [90:85]

它是，但是，可以计算出你使用的把你的对手在无糖的数量范围赢得局面。在这种情况你会发现自己在最低数量或次数最多的可能是你选择的，所以如果RHC是你可以选择的最高数和RLC是你可以选择最低的数字，然后

RHc = [9:15] 
RLc = [1:12]

有了这些信息，我就可以开始构建从游戏结束开始的相对算法。

N*p* - RHp - RLp < Np < N*p* - RHp, where p = iteration and *p* = iteration + 1 
RHp = [8+p:15] 
RLp = [1:13-p] 
p = -1 is your winning move 
p = 0 is your opponent's helpless move 
p = 1 is your set-up move 
Np is the sum of that round.

因此，求解算法为您设置了移动，P = 1，您可以：

N*p* - [9:15] - [1:12] < Np < N*p* - [9:15] 
100 <= N*p* <= 114

我还在工作了数学这一点，因此预计调整。如果您发现错误，请告诉我，我会适当调整。

来源

2017-08-14 21:57:55

下面是一个简单，蛮力Python代码：

# stoneCount: number of stones to start the game with 
# possibleMoves: which numbers of stones may be removed? (*sorted* list of integers) 
# return value: signals if winning can be forced by first player; 
#    if True, the winning move is attached 
def isWinningPosition(stoneCount, possibleMoves): 
    if stoneCount == 0: 
     return False 
    if len(possibleMoves) == 0: 
     raise ValueError("no moves left") 
    if stoneCount in possibleMoves or stoneCount < possibleMoves[0]: 
     return True,stoneCount 
    for move in possibleMoves: 
     if move > stoneCount: 
      break 
     remainingMoves = [m for m in possibleMoves if m != move] 
     winning = isWinningPosition(stoneCount - move, remainingMoves) 
     if winning == False: 
      return True,move 
    return False

对于给定的问题的大小此功能在小于20秒返回在Intel I7：

>>> isWinningPosition(100, range(1,16)) 
False

（因此，第一个在这种情况下不能强制赢球，无论他做什么动作，都会导致第二名球员获胜。）

当然，运行时间有很大的优化空间通货膨胀。在上面的实现中，很多情况都会被一次又一次地重新计算（例如，当第一次玩牌花费一块石头，第二玩家花费两块石头时，这将使第一玩家陷入与每个玩家所花费的宝石数量相同的情况相反）。所以第一个（主要）改进是记住已经计算好的情况。然后可以选择更有效的数据结构（例如，将可能的移动列表编码为位模式）。

来源

2017-08-15 10:38:04 coproc

计算减法游戏的赢得策略

回答

相关问题