Я разрабатываю игру фианко (очень похожую на шашки) на Python и пытаюсь реализовать Negamax с алгоритмом обрезки альфа-бета, но на данный момент он не работает должным образом. Он не выполняет лучшие движения, когда должен, и я не могу понять, почему. Ниже вы можете найти алгоритм, а также очень простую функцию оценки. Функции undo и apply_move работают корректно, как и генерация ходов.
def negamax(self, board, depth, alpha, beta, color):
# Base case: if depth is 0 or the game has a winner, return evaluation
self.log.debug(f"Score:")
if depth == 0 or board.is_winner() is not None:
evaluation = color * board.evaluate() # Multiply by color to get perspective
return evaluation, None
best_score = -float("inf")
best_move = None
normal_moves, captures = board.get_valid_moves_and_captures(board.current_player)
moves = captures if captures else normal_moves
for move in moves:
self.log.debug(f"Valid moves: {moves}")
self.log.debug(f"Board before move:\n {board.board}")
board.apply_move(move)
self.log.debug(f"Board after move: {move} by color {color}\n {board.board}")
score = -self.negamax(board, depth - 1, -beta, -alpha, -color)[0]
self.log.debug(f"Evaluating move {move} for color {color}: Current best score = {best_score}, Alpha = {alpha}, Beta = {beta}")
board.undo() # Undo the move and switch player back
self.log.debug(f"Board after undo:\n {board.board}")
if score > best_score:
best_score = score
best_move = move
alpha = max(alpha, score)
if alpha >= beta:
break
return best_score, best_move
def evaluate(self):
white_score = 0
black_score = 0
winner = self.is_winner()
if winner == 1:
return 1500 # High positive score for white win
elif winner == 2:
return -1500 # High negative score for black win
# Calculate scores based on the number of stones
white_stones = np.sum(self.board == 1)
black_stones = np.sum(self.board == 2)
white_score += white_stones * 10 # Each white stone has a base value
black_score += black_stones * 10 # Each black stone has a base value
# Additional scoring based on positioning
for r in range(9):
for c in range(9):
if self.board[r, c] == 1: # White
white_score += self.position_score(r, c, 1)
elif self.board[r, c] == 2: # Black
black_score += self.position_score(r, c, 2)
# Final evaluation is white score minus black score
white_score += random.randint(-5, 5) # Add some randomness to the score
black_score += random.randint(-5, 5)
return white_score - black_score
def position_score(self, r, c, player):
"""Calculate score based on position. Closer to the opponent's back row is better."""
score = 0
if player == 1: # White
score += 8 - r # Bonus for being closer to row 8
else: # Black
score += r # Bonus for being closer to row 0
return score
Подробнее здесь: https://stackoverflow.com/questions/790 ... -in-python
