計算減法遊戲的贏得策略

問題：
假設有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

計算減法遊戲的贏得策略

回答

相關問題