動態編程：棋盤

白車隊從標準的8乘8棋盤的左上角開始。兩名選手輪流將車向右或垂直向下水平移動，儘可能多的方格。固定移動不允許，玩家1先走。獲勝者是將車放在右下角廣場上的選手。說誰會贏，並描述贏球策略。動態編程：棋盤

我有上述聲明的問題，我很感興趣看到別人會如何解決這個問題。我知道有辦法計算出車的不同路徑。我嘗試着用手去解決問題，並且總是好像球員2一直贏得勝利，但我可能會簡單地想到它。以動態編程方式接近它似乎是一個好方法。無論如何，任何人都有任何見解，算法或類似的方法來解決這個問題！

來源

2013-02-27 NuNu

解釋「固定動作是不允許的」。 – RBarryYoung 2013-02-27 04:17:22

@RBarryYoung在你不能傳遞輪到你（你不能說你的舉動是保持當前的現貨您的，因爲它會導致僵持）。你必須做出向右移動或向下 – NuNu 2013-02-27 04:27:46

你試過玩這個遊戲？你可能能夠推理出一個勝利的策略，而不是訴諸於使用電腦。 – 2013-02-27 12:29:10

enter image description here

H8是一個勝利者框，以便高於一切，離開的是失敗者框。

一切權利和以下G7（G8和H7）是一個失敗者的盒子，所以它是一個勝利者的盒子。

G7是一個勝利者的盒子，所以上面和左邊的一切都是輸家。

等等......

啓動遊戲

球員一個只選擇去一個失敗者框，以便玩家倆永贏。

所有玩家要做的每一件事都是每次輪到他時移動到w箱子。

來源

2013-02-27 04:38:21 jurgenreza

。它使它對描述有幫助 – NuNu 2013-02-27 04:53:00

@NuNu我的榮幸。 – jurgenreza 2013-02-27 04:54:33

玩家二總是贏得任何尺寸的棋盤。通過電路板的大小進行歸納證明。

n = 1的情況可以忽略，所以從n = 2開始;很明顯，玩家2在2x2板上獲勝。

假設玩家2總是在n或更小的棋盤上獲勝。在大小爲n + 1的棋盤上，玩家1移動到左欄或頂欄的位置。玩家2然後移動到對角線上的位置（這就是你需要的所有策略），然後在n或更小的棋盤上的起始位置。

QED

來源

2013-02-27 04:49:16 Glenn

甲獲勝位置具有以下性質：

所有終端位置獲勝。在這種情況下，位置（8,8）是獲勝位置
所有可以達到目標位置的位置都是獲勝位置。 I.e.最後的行或列中所有的位置都在賺錢的倉位
如果我們能那麼我們是在一個成功的位置移動到一個失敗的位置，因爲未來的球員無法贏得比賽
如果我們只能夠移動到一個獲勝的位置，那麼我們處於失敗的位置

考慮到這一點，我們可以創建一個算法，可以告訴我們，如果當前位置是勝利的位置還是失敗的位置。使用表（dpTable）來存儲以前計算的結果將避免重複計算。

boolean isWinning(int x, int y) { 
    if (dpTable[x][y] != null) 
     return dpTable[x][y]; 

    // From the last row or the last column we can always win the game 
    if (x == n || y == n) 
     return true; 

    for (int i = 1; x + i <= n; i++) { 
     // Moving right 
     if (x + i <= n && !isWinning(x+i, y) { 
      dpTable[x][y] = true; 
      return true; 
     } 

     // Moving down 
     if (y + i <= n && !isWinning(x, y+i) { 
      dpTable[x][y] = true; 
      return true; 
     } 
    } 

    dpTable[x][y] = false; 
    return false; 
}

從位置在開始（X，Y），你可以通過玩優化和false贏得比賽時，有沒有辦法讓你開始在（X，Y），贏得了isWinning(x, y)函數返回true。

來源

2013-02-27 12:18:48

我認爲這是值得大家注意的，所描述的遊戲實際上是一個Nim遊戲兩樁7枚硬幣每。 Nim遊戲的勝者可以通過在每一堆中硬幣的數量來確定。他們稱之爲Nim-sum，它給出了Sprague-Grundy函數的值。只要Nim-sum是肯定的，這個位置就是勝利。所以考慮你的遊戲：7^7 = 0，這是一個失敗的位置。每一個對角位置失去，因爲無論什麼x是，x^x始終爲0
的好處是，使用這種技術，你可以在4-在3維和任意大的發揮空間（贏得）這個遊戲，以及，5維等。

來源

2013-02-27 12:37:25

動態編程：棋盤

回答

相關問題