爲2人遊戲的最佳策略

2玩家一個& B被打涉及多個遊戲ň
玩家A使第一招&雙方球員發揮交替。
在各移動玩家需要的數量n，選擇一個數量我使得2^I <Ñ和替換Ñ與K = N - 2^I當且僅當在1的個數的ķ二進制表示大於或等於1的數量在ñ
遊戲的二進制表示結束時沒有玩家可以使一動，即不存在這樣的我

n = 13 = b1101

唯一可能的I = 1

k = n - 2^i = 11 = b1011

同樣，只有可能的I = 2

k = n - 2^i = 7 = b111

由於玩家A不能作出任何更多的動作，播放器B贏

我推斷d在任何一步，我們只能選擇一個i，這樣在n的二進制表示中相應的位置就有一個0。

例如：如果n = 1010010，那麼我只能是{0,2,3,5}。

，但我不能移動任何further.A極大極小算法的心不是正好撞擊我，我將不勝感激任何help.Thanks提前

來源

2012-09-24 Leopard

看起來像一個「淨息差」的遊戲給我。你可以將規則編輯成項目列表嗎？ – wildplasser

http://math.stackexchange.com可能會做得更好 – Eric

感謝您的編輯。它更可讀。空白也有幫助。（但我似乎還沒有把握住它;-) – wildplasser

假設n是不是太大了，我們可以使用動態編程來解決這個問題。定義一個數組A [1：n]，其中A [i]表示玩家是否會贏得輸入i。讓我們用解釋：

A[i] = 1, if A wins on input i, 
    A[i] = 0, if A loses on input i.

現在可以計算自下而上如下：

A[1] = 0, A[2] = 1. 
For j=3:n { 
     Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
           (number of 1's in i >= number of 1's in j) 
     Otherwise Assign A[j] = 0 
}

來源

2012-09-25 00:07:02 krjampani

如果n變得太大，例如10^9的順序，那麼自頂向下的方法將工作而不是DP方法。 – Leopard

如果n在二進制表示中有多個1，則記憶化的自頂向下方法可能比DP快得多。否則，我猜測DP會更快。運行一些測試看看哪個更好，會很有趣。 – krjampani

爲2人遊戲的最佳策略

回答

相關問題