我正在使用带有alpha-beta修剪的minimax算法,用Python创建一个国际象棋引擎。然而,目前速度非常慢,我发现在minimax中执行deepcopy每次迭代的速度与我所有其他函数的速度之和一样慢
有没有办法绕过deepcopy,或者让它更快?下面是我今天的minimax函数。它只能想向前移动3-4步左右,这不是一个很好的引擎。。。任何关于加速算法的建议都将不胜感激
def minimax(board, depth, alpha, beta, maximizing_player):
board.is_human_turn = not maximizing_player
children = board.get_all_possible_moves()
if depth == 0 or board.is_draw or board.is_check_mate:
return None, evaluate(board)
best_move = random.choice(children)
if maximizing_player:
max_eval = -math.inf
for child in children:
board_copy = copy.deepcopy(board)
board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
if current_eval > max_eval:
max_eval = current_eval
best_move = child
alpha = max(alpha, current_eval)
if beta <= alpha:
break
return best_move, max_eval
else:
min_eval = math.inf
for child in children:
board_copy = copy.deepcopy(board)
board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
if current_eval < min_eval:
min_eval = current_eval
best_move = child
beta = min(beta, current_eval)
if beta <= alpha:
break
return best_move, min_eval
关于如何优化程序的一些想法(无特定顺序):
1)在
minimax
函数中首先进行检查if depth == 0 or board.is_draw or board.is_check_mate
。现在调用board.get_all_possible_moves()
,这可能是多余的(例如在depth == 0
的情况下)2)我不知道
get_all_possible_moves()
方法是如何实现的,并且假设它不进行任何排序。一个很好的做法是为minimax算法排序移动,以便从最好的移动到最坏的移动(在这种情况下,您可能会修剪更多节点并加快程序的速度)3)
for child in children
循环中的child
变量是二维矩阵。我还猜想board
也是一个多维数组。多维数组可能比一维数组慢,因为它们的内存布局(例如,如果按列遍历它们)。如果可能,请使用一维数组(例如,可以将二维数组表示为一维数组的“串联”)4)使用生成器进行延迟评估。例如,您可以将
get_all_possible_moves()
转换为生成器并在其上迭代,而无需创建列表和消耗额外内存。如果alpha/beta修剪条件提前触发,则不需要扩展该位置中的所有子项列表5)通过制作和取消制作当前移动避免深入复制线路板。在这种情况下,您不创建电路板的副本,而是重用原始电路板,这可能会更快:
current_move_info = ... # collect and store info necessary to make/unmake the current move
board.move(current_move_info)
current_eval = minimax(board, ...)[1]
board.unmake_move(current_move_info) # restore the board position by undoing the last move
6)增加更多经典的优化棋盘引擎功能,如迭代深化、主变分搜索、换位表、比特板等
相关问题 更多 >
编程相关推荐