Я создаю соединение четырех ИИ. У меня проблемы с оптимизацией сокращения альфа-бета. В Википедии говорится, что сортировка узлов таким образом, что мы сначала пробуем наиболее вероятные (то есть те, которые с наибольшей вероятностью вызовут отсечку альфа/бета), повысит производительность без изменения результатов. Вот мой код без сортировки. Кажется, это работает нормально.
def minimax_i(board, start_depth):
"""Return the highest valued move by minimaxing."""
best_value = -100000
best_move = None
alpha = -100000
beta = 100000
moves = board.get_valid_moves()
for move in moves:
value = minimax_r(board.make_move(move), board.nextplayer, alpha, beta, start_depth)
if value > best_value:
best_value = value
best_move = move
if alpha >= beta:
break
return best_move
def minimax_r(board, player, alpha, beta, depth):
result = board.winner()
if result != -1: # If game is finished
if result == 0:
return 0
if result == player:
return 1000 + depth
return -(1000 + depth)
if depth <= 0:
return heuristic(board, player)
moves = board.get_valid_moves()
if board.nextplayer == player: # Maximizing
best_value = -100000
for move in moves:
score = minimax_r(board.make_move(move), player, alpha, beta, depth-1)
best_value = max(best_value, score)
alpha = max(alpha, best_value)
if alpha >= beta:
break
return best_value
else: # Minimizing
best_value = 100000
for move in moves:
score = minimax_r(board.make_move(move), player, alpha, beta, depth-1)
best_value = min(best_value, score)
beta = min(beta, best_value)
if alpha >= beta:
break
return best_value
Изменение moves = board.get_valid_moves() на moves = sorted(board.get_valid_moves(), key = lambda x: abs(board.lastmove[0]-x)) должно заставить его сначала проверять ходы, которые граничат с последним ходом, наивная, но, надеюсь, полезная эвристика упорядочения. Проблема в том, что он изменяет результаты поиска.
Единственное, о чем я могу думать, это то, что я должен распространять изменения в альфа- и бета-версии, которые происходят в дочерних узлах, на родительские узлы. Любые идеи?
