你的板子有多大?
如果您的棋盘相当小,那么您可以使用动态规划精确地解决游戏。在 Python 中:
n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))
def moves(board):
return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]
@memoize
def wins(board):
if not board: return True
return any(not wins(move) for move in moves(board))
函数 wins(board) 计算棋盘是否为获胜位置。棋盘表示是一组元组 (x,y),指示棋子 (x,y) 是否仍在棋盘上。函数 move 计算一次可到达的板的列表。
wins 函数背后的逻辑是这样工作的。如果棋盘在我们移动时是空的,那么其他玩家一定吃掉了最后一块,所以我们赢了。如果棋盘不是空的,那么如果有any
移动我们可以赢,我们可以这样做,结果位置是一个失败的位置(即不获胜 ie not wins(move)
),因为这样我们让另一个玩家进入了一个失败的位置。
您还需要缓存结果的 memoize 辅助函数:
def memoize(f):
cache = dict()
def memof(x):
try: return cache[x]
except:
cache[x] = f(x)
return cache[x]
return memof
通过缓存,我们只计算给定位置的获胜者一次,即使该位置可以通过多种方式到达。例如,如果第一个玩家在第一个动作中吃掉所有剩余的巧克力排,则可以获得单排巧克力的位置,但也可以通过许多其他系列的动作来获得。一次又一次地计算谁在单排板上获胜是很浪费的,所以我们缓存了结果。这将渐近性能从 提高O((n*m)^(n+m))
到O((n+m)!/(n!m!))
,虽然对于大型电路板来说仍然很慢,但这是一个巨大的改进。
为了方便,这里有一个调试打印功能:
def show(board):
for x in range(n):
print '|' + ''.join('x ' if (x,y) in board else ' ' for y in range(m))
这段代码仍然相当慢,因为代码没有以任何方式优化(这是 Python ......)。如果你用 C 或 Java 高效地编写它,你可能可以将性能提高 100 倍以上。您应该能够轻松处理 10x10 板,并且您可能最多可以处理 15x15 板。您还应该使用不同的板表示,例如位板。如果您使用多个处理器,也许您甚至可以将其加速 1000 倍。
这是从极小极大的推导
我们将从极小极大开始:
def minimax(board, depth):
if depth > maxdepth: return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -minimax(move, depth-1))
return alpha
我们可以删除深度检查来进行完整搜索:
def minimax(board):
if game_ended(board): return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -minimax(move))
return alpha
由于游戏结束,启发式将返回 -1 或 1,具体取决于哪个玩家获胜。如果我们将 -1 表示为假,将 1 表示为真,则max(a,b)
变为a or b
,然后-a
变为not a
:
def minimax(board):
if game_ended(board): return heuristic(board)
else:
alpha = False
for move in moves(board):
alpha = alpha or not minimax(move)
return alpha
你可以看到这相当于:
def minimax(board):
if not board: return True
return any([not minimax(move) for move in moves(board)])
如果我们从带有 alpha-beta 剪枝的 minimax 开始:
def alphabeta(board, alpha, beta):
if game_ended(board): return heuristic(board)
else:
for move in moves(board):
alpha = max(alpha, -alphabeta(move, -beta, -alpha))
if alpha >= beta: break
return alpha
// start the search:
alphabeta(initial_board, -1, 1)
搜索从 alpha = -1 和 beta = 1 开始。一旦 alpha 变为 1,循环就会中断。所以我们可以假设在递归调用中 alpha 保持 -1 而 beta 保持 1。所以代码等价于:
def alphabeta(board, alpha, beta):
if game_ended(board): return heuristic(board)
else:
for move in moves(board):
alpha = max(alpha, -alphabeta(move, -1, 1))
if alpha == 1: break
return alpha
// start the search:
alphabeta(initial_board, -1, 1)
所以我们可以简单地删除参数,因为它们总是作为相同的值传入:
def alphabeta(board):
if game_ended(board): return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -alphabeta(move))
if alpha == 1: break
return alpha
// start the search:
alphabeta(initial_board)
我们可以再次从 -1 和 1 切换到布尔值:
def alphabeta(board):
if game_ended(board): return heuristic(board)
else:
alpha = False
for move in moves(board):
alpha = alpha or not alphabeta(move))
if alpha: break
return alpha
所以你可以看到这等同于使用 any 和生成器,一旦找到 True 值就停止迭代,而不是总是计算整个子列表:
def alphabeta(board):
if not board: return True
return any(not alphabeta(move) for move in moves(board))
请注意,这里我们有any(not alphabeta(move) for move in moves(board))
而不是any([not minimax(move) for move in moves(board)])
. 这加快了对合理尺寸电路板的搜索速度大约 10 倍。不是因为第一种形式更快,而是因为它允许我们在找到一个为 True 的值后立即跳过整个其余的循环,包括递归调用。
所以你有了它,wins 函数只是变相的字母搜索。我们用于获胜的下一个技巧是记住它。在游戏编程中,这将被称为“转置表”。因此,wins 函数正在使用转置表进行字母搜索。当然,直接写下这个算法而不是通过这个推导更简单;)