你正試圖決定誰會贏得一場比賽，並假設有最佳選擇。這個想法是有x個空格，_ _ _ _ _ _ _。球員一個去並且連續兩個點。然後球員二去並且做相同。第一個不能參加WINS的玩家。因此，考慮到板之前，這是一個方法可行：無論如何做這個不是蠻力的謎題（以及你如何蠻力）？
P1：XX _ _ _ _ _
P2：XX _ XX _
P1：XX _ XXXX
所以玩家2勝。您將得到一個數組，其中0表示可用空間，1表示標記點。該陣列可能有一些點已經標記。
我能想到做到這一點的唯一方法是檢查每一個動作，併爲每一個動作檢查是否每一個可能的舉動後結果在勝利。我甚至無法完全弄清楚我會如何做到這一點，但我希望有更好的方法。有任何想法嗎？
你應該像這樣反向工作。
給出所有可能的遊戲狀態，通過並決定哪個是玩家1（W）的勝利，哪個是玩家2（L）的勝利。最初，你只知道沒人能玩的州的答案。在這種情況下，答案是
W如果沒有兩個連續的點，並採取點的總數是4kL如果沒有兩個連續的點，並採取點的總數爲4k+2現在向後工作。如果玩家1可以移動到W的任何棋盤位置，請將其標記爲W，並且如果玩家2有任何棋盤位置可以移動到L，則將其標記爲L。再次，這不會立即標記所有的位置，但迭代這將是。迭代部分是
W如果有4k+2點和連續的兩個景點其中，填充時，產生位置標記WL如果有4k點和連續的兩個景點其中，在填充時，給位置標記L例：考慮板_ _ _ _ _ _。向後工作
球員兩個最終狀態評估中移動：
X X X X X X (L - terminal)
球員一動：
X X _ X X _ (W - terminal)
_ X X _ X X (W - terminal)
_ X X X X _ (W - terminal)
X X X X _ _ (L - must move to X X X X X X)
_ _ X X X X (L - must move to X X X X X X)
球員兩個移動：
X X _ _ _ _ (L - can move to X X X X _ _)
_ X X _ _ _ (W - must move to _ X X _ X X or _ X X X X _)
_ _ X X _ _ (L - can move to X X X X _ _)
_ _ _ X X _ (W - must move to X X _ X X _ or _ X X X X _)
_ _ _ _ X X (L - can move to X X _ _ X X)
球員一到移動：
_ _ _ _ _ _ (W - can move to _ X X _ _ _)
，使每個位置會W或L來評估您可以遞歸程序這一點。讓每個棋盤位置P由長度爲n的二元向量表示，其中1表示被拍攝的點並且0表示開放點。下面是僞代碼爲doesPlayerOneWin：
// STORE NUMBER OF ONES
int m = 0;
for (int i=0; i<n; ++i)
m += P[i];
// LOOK FOR LEGAL MOVES
bool canMove = false;
for (int i=0; i<n-1; ++i)
int[] newP = P;
if (P[i]+P[i+1] == 0) {
canMove = true;
newP[i] = 1;
newP[i+1] = 1;
// PLAYER ONE CAN MOVE TO WIN
if (m % 4 == 0 && doesPlayerOneWin(newP))
return true;
// PLAYER TWO CAN MOVE TO WIN
if (m % 4 == 2 && !doesPlayerOneWin(newP))
return false;
}
}
// IF NO LEGAL MOVES, PLAYER TO MOVE WINS
if (!canMove && m % 4 == 0)
return true;
else if (!canMove && m % 4 == 2)
return false;
// OTHERWISE IF LOOP RUNS, PLAYER TO MOVE LOSES
if (m % 4 == 0)
return false;
else
return true;
Assuming optimal choices實際上是一個最佳startegy。
「選擇」移動給玩家的常用方式是使用min-max algorithm。 [它實際上是deep blue贏得卡斯帕羅夫使用的算法]。最小 - 最大「選擇」每個球員的最優移動，以便選擇它將產生的移動。
min-max算法通常是啓發式的，然後給出每個遊戲狀態的評估，但是 - 對於您的情況，因爲您正在尋找最佳移動和蠻力解決方案，所以您需要使用min-max每次迭代直到比賽結果爲贏家/輸家，這是董事會唯一的評估。
使用此方法，您可以確定哪個玩家將使用起始狀態的值獲勝 - 它會指示您認爲是「我」的玩家是贏家還是輸家。
請注意，對於這種特定情況，僅在評估板根據其最終狀態進行評估時，最小最大值衰減到與@PenOne解決方案非常相似的值。
有一個理論可以解決這樣的遊戲。
你的遊戲是一個公正的遊戲 - 兩個玩家在每個位置都有相同的動作。國際象棋不公正，因爲白色只能控制白色數字。當一名球員沒有移動時，比賽結束，然後他輸了。假設每場比賽都在有限的時間內結束。
您可以根據PengOne的建議L和W來分析職位並標註職位。失敗職位是指所有可能的舉動都會導致勝出的職位，而勝出的職位是至少有一次移動的職位失去了地位。遞歸的，但定義明確的標籤。當玩家沒有移動時，所有連續位置都獲勝（a vacuous truth），所以這被標記爲失敗位置。
你可以計算更多的信息，這將有助於你。調用mex（A）不是A中最小的非負整數。例如，mex（{0,1,5}）= 2和mex（{1,2,3}）= 0。現在，您可以在每個位置貼上所有可以移動到的標籤的位置。這也是一個遞歸的，明確的標籤。如果某個職位的價值爲0，則該職位正在流失。在這種分類下，一個標記爲0的位置正在丟失，但是您擁有數字爲1,2的獲勝位置的細粒度分類。...
這些數字允許您計算兩個遊戲總和的值。你可以添加兩個遊戲，通過獨立播放。在移動過程中，您可以在第一場比賽或第二場比賽中進行比賽。您的遊戲___X__X__中的一個位置實際上是三場比賽的總和___,__,__。
Sprague-Grundy定理。價值爲a_1，a_2，...，a_N的N個遊戲的總和值爲a_1 xor a_2 xor ... a_N。因此，N個遊戲的總和如果它們的值異或爲0，則它將丟失。
您的初始位置是由X分隔的K個獨立遊戲的總和。您需要找到每個空白條的Sprague-Grundy值，並將它們加以異或，如果結果爲0，則返回。我想如果您嘗試計算其中前50個值，您可能會得到一個如何計算這些值的提示。
由於我不喜歡使用本網站作爲工作的替代品，我在這裏停留。希望你能完成，如果你卡住了，提出問題。
值得一提的是，這裏有一個用Python編寫的暴力破解器。有趣！你甚至可以用N> 2來運行它，以便每回合放下更多的棋子。請注意，失敗的玩家只是玩最左邊的有效動作。
一，輸出。我以不同的棋盤尺寸（從這裏的2到16）開始了比賽。
Size = 2
..
11
Player 1 Wins!
Size = 3
...
11.
Player 1 Wins!
Size = 4
....
.11.
Player 1 Wins!
Size = 5
.....
11...
1122.
Player 2 Wins!
Size = 6
......
..11..
2211..
221111
Player 1 Wins!
Size = 7
.......
11.....
1122...
112211.
Player 1 Wins!
Size = 8
........
.11.....
.1122...
.112211.
Player 1 Wins!
Size = 9
.........
11.......
1122.....
112211...
11221122.
Player 2 Wins!
Size = 10
..........
....11....
22..11....
22..1111..
22221111..
2222111111
Player 1 Wins!
Size = 11
...........
11.........
1122.......
112211.....
11221122...
1122112211.
Player 1 Wins!
Size = 12
............
.11.........
.1122.......
.112211.....
.11221122...
.1122112211.
Player 1 Wins!
Size = 13
.............
...11........
22.11........
22.11.11.....
22.11.1122...
22.11.112211.
Player 1 Wins!
Size = 14
..............
......11......
22....11......
22....1111....
2222..1111....
2222..111111..
222222111111..
22222211111111
Player 1 Wins!
Size = 15
...............
11.............
11...22........
1111.22........
1111.22.22.....
1111.22.2211...
1111.22.221122.
Player 2 Wins!
Size = 16
................
.....11.........
22...11.........
2211.11.........
2211.1122.......
2211.112211.....
2211.11221122...
2211.1122112211.
Player 1 Wins!
下面的代碼：
N = 2 # number of pieces placed per turn
CACHE = {}
def compute_moves(board):
gaps = [0] * len(board)
previous = 0
for i in range(len(board) - 1, -1, -1):
if board[i]:
previous = 0
gaps[i] = 0
else:
previous += 1
gaps[i] = previous
return [i for i, gap in enumerate(gaps) if gap >= N]
def do_move(board, index, player):
for i in range(N):
board[index + i] = player
def undo_move(board, index):
for i in range(N):
board[index + i] = 0
def search(board):
key = tuple(board)
if key in CACHE:
return CACHE[key]
moves = compute_moves(board)
for move in moves:
do_move(board, move, 1)
a, _ = search(board)
undo_move(board, move)
if not a:
result = (True, move)
break
else:
result = (False, moves[0] if moves else None)
CACHE[key] = result
return result
def play(board):
player = 0
while True:
print ''.join(str(x or '.') for x in board)
_, index = search(board)
if index is None:
break
do_move(board, index, player + 1)
player = int(not player)
print 'Player %d Wins!' % (int(not player) + 1)
for size in range(2, 17):
print 'Size = %d' % size
board = [0] * size
play(board)
print
你會如何慶祝，如果一個特定的狀態是贏或輸？另外，什麼是K？ – user1248092 2012-03-14 18:05:22
@ user1248092看到我上面的僞代碼。數字「k」是任何整數。關鍵在於拍攝點的數量總是偶數，因此對於某些非負整數「k」，其形式爲「4k」或「4k + 2」（例如，如果拍攝的點數是「14」那麼'k = 3'因爲'14 = 4 * 3 + 2'）。 – PengOne 2012-03-14 18:15:58
我剛剛在板子上運行你的代碼[0,0,0,0]，它說錯誤。 P1應該贏。 – user1248092 2012-03-14 18:27:50