Я использую алгоритм минимакс для ИИ для игры в шашки.
Для лучшей производительности я использую альфа-бета отсечение.
Так как в шашках сложно предсказать, какая глубина поиска нужна в конкретной позиции, я хочу использовать итеративное углубление: поиск происходит сначала на глубину 1, затем 2, 3 и так далее.
Как я понял, смыслом итеративного углубления является то, что на при расчете на глубину n мы используем ранее уже выполненный расчет на глубину n-1, результаты которого сохраняются (в хеш-таблице/файле...)
Однако мне не совсем понятно, что конкретно мне нужно сохранять в этой хеш таблице? Я должен сохранять ВСЕ позиции, которые встречаются в процессе минимакса или только позиции на стартовых глубинах?
Сейчас моя программа просто последовательно проходит по всем глубинам, никак не используя результаты предыдущих менее глубоких вычислений.
class AI:
def get_best_move (self, board, time_limit):
self.analysed_positions = 0
self.best_move = None
self.calculation_process = True
calculation_process = threading.Thread(target=self.iterative_deepening_minimax, args=(board, ))
calculation_process.start()
calculation_process.join(time_limit)
self.calculation_process = False
return self.best_move
def iterative_deepening_minimax (self, board):
for depth in range(2, 30):
if self.calculation_process:
# Начинаем поиск на глубине depth, который возвращает лучший ход в этой позиции
self.best_move = self.minimax(board, depth, -INFINITY, INFINITY, board.whitesMove)[1]
else:
break
def minimax (self, board, depth, alpha, beta, maximizingPlayer):
if self.calculation_process == False:
return (0, None)
board.find_all_moves()
game_state = board.get_game_state()
if game_state != STATE_OK:
self.analysed_positions += 1
return (INFINITY + depth, None) if game_state == WHITE_WIN else (-INFINITY - depth, None)
if depth == 0:
self.analysed_positions += 1
eval = self.evaluate(board)
return (eval, None)
bestMove = None
if maximizingPlayer:
maxEval = -INFINITY
for move in board.moves:
next_pos = Board(board, search_all_moves=False)
next_pos.make_move(move)
next_pos.change_turn()
eval = self.minimax(next_pos, depth - 1, alpha, beta, False)[0]
if eval > maxEval:
maxEval = eval
bestMove = move
# Pruning
alpha = max(alpha, eval)
if beta <= alpha:
break
return (maxEval, bestMove)
else:
minEval = INFINITY
for move in board.moves:
next_pos = Board(board, search_all_moves=False)
next_pos.make_move(move)
next_pos.change_turn()
eval = self.minimax(next_pos, depth-1, alpha, beta, True)[0]
if eval < minEval:
minEval = eval
bestMove = move
# Pruning
beta = min(beta, eval)
if beta <= alpha:
break
return (minEval, bestMove)
# Возвращает статическую оценку позиции
def evaluate():
...