Альфа-бета отсечение

Question

Я понимаю основы этого поиска, однако часть обрезки бета смущает меня, когда бета <= значение альфа-бета, я могу либо вернуть бета, разорвать или продолжить цикл. </p>

• бета возврата не работает должным образом, она возвращает неверное движение игроков для другого состояния доски (далее в дерево поиска)

• Кажется, что перерыв работает правильно, он очень быстрый, но кажется слишком СКОРОСТНЫМ

• продолжить намного медленнее, чем перерыв, но кажется, что это более правильно ... Я предполагаю, что это правильный путь, но псевдокод в Google все использует 'перерыв', но поскольку это псевдокод, я не уверен они имеют в виду «перерыв»

Answer 1

Просто для удовольствия, я собираюсь догадаться, что вы говорите о минимаксе с отсечкой альфа-беты, где

АЛЬФА-БЕТА - это метод для уменьшение количества исследуемых узлов в минимаксной стратегии. Для узлов он исследует это вычисляет, в дополнение на счет, альфа-значение и бета-значение.

Вот страница , которая описывает этот метод, а также предоставляет ссылку на программу C , которая реализует этот метод. Надеюсь, что что-то здесь поможет вам в вашей проблеме, если я полностью не согласен с моим предположением, пожалуйста, дайте больше деталей в вашем вопросе.

    function MINIMAX(N) is
    begin
       if N is a leaf then
           return the estimated score of this leaf
       else
           Let N1, N2, .., Nm be the successors of N;
           if N is a Min node then
              return min{MINIMAX(N1), .., MINIMAX(Nm)}
           else
              return max{MINIMAX(N1), .., MINIMAX(Nm)}
      end MINIMAX;

Answer 2

Бета-отсечки происходят, когда ветка, которую вы ищете в данный момент, лучше для вашего оппонента, чем та, которую вы уже искали. Однажды мне объяснили следующее:

предположим, что вы сражаетесь со своим врагом, и вы рассматриваете несколько вариантов.

После полного поиска наилучшего возможного результата по вашему первому выбору (нанесения удара) вы решаете, что в результате ваш оппонент в конечном итоге ткнет вас в глаз. Мы назовем эту бета-версию ... лучшим, что может сделать ваш противник. Очевидно, вы хотели бы найти результат, который будет лучше.

Теперь мы рассмотрим ваш следующий вариант (с позором убегать). Изучая оппонента первым возможным ответом, мы обнаруживаем, что наилучший возможный результат - это выстрел в спину из ружья. Это где бета-отсечение срабатывает ... мы прекращаем поиск остальных ходов ваших оппонентов и возвращаем бета-версию, потому что нам действительно все равно, если вы найдете в поиске других его ответов, он также может убить вас ... вы бы уже выбрать тыкать в глаза от предыдущего варианта.

Теперь, в частности, это означает, что ваша программа должна возвращать бета-версию ... если она не работает, вы должны сравнить ее с алгоритмом поиска альфа-бета в другом месте .