Проблемы с преобразованием алгоритма обрезки альфа-бета из C ++ в Ruby

Question

Таким образом, альфа-бета-обрезание кажется наиболее эффективным алгоритмом, кроме жесткого кодирования (для крестики-нолики).Однако у меня возникают проблемы при преобразовании алгоритма из примера C ++, приведенного в ссылке: http://www.webkinesia.com/games/gametree.php.

Игроки имеют либо 1, либо 0, поэтому выполнение 1-player переключит игрока.

WIN = 1
LOSS = -1
DRAW = 0
INFINITY = 100
def calculate_ai_next_move
  best_move = -1
  best_score = -INFINITY

  cur_player = COMPUTER
  self.remaining_moves.each do |move|
    self.make_move_with_index(move, cur_player)
    score = -self.alphabeta(-INFINITY,INFINITY, 1 - cur_player)
    self.undo_move(move)

    if score > best_score
      best_score = score
      best_move = move
    end
  end

  return best_move
end

def alphabeta(alpha, beta, player)
  best_score = -INFINITY
  if not self.has_available_moves?
    return WIN if self.has_this_player_won?(player) == player
    return LOSS if self.has_this_player_won?(1 - player) == 1 - player
    return DRAW
  else
    self.remaining_moves.each do |move|
      break if alpha > beta

      self.make_move_with_index(move, player)
      move_score = -alphabeta(-beta, -alpha, 1 - player)
      self.undo_move(move)

      if move_score > alpha
        alpha = move_score
        next_move = move
      end
      best_score = alpha
    end
  end
  return best_score
end

В настоящее время алгоритм играет ужасно.Сначала он выберет последний пробел, а затем после этого выберет первый (слева направо) доступный пробел.

Есть идеи, что с этим не так?

Кроме того, я занимался TDD, поэтому я знаю, что self.has_this_player_won ?, self.undo_move и self.remaining_moves верны.

Answer 1

Подсказка: где обновляется beta?

Полагаю, вам следует поменять местами alpha и beta на каждом уровне дерева.