О случайности и алгоритме minmax с альфа-бета-обрезкой

Будет ли случайный выбор дочернего узла в алгоритме альфа-бета иметь больше шансов получить отсечение, чем выбор их по порядку?

Вот псевдокод с моим дополнением, отмеченным ***.

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     arrange childs of node randomly ***
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off*)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off*)
         return v

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

Можно ли доказать, что это быстрее (или медленнее)?


person shinzou    schedule 30.04.2016    source источник


Ответы (1)


Будет ли случайный выбор дочернего узла в алгоритме альфа-бета иметь больше шансов получить отсечение, чем выбор их по порядку?

Это зависит. В каком порядке находятся дети, если они не рандомизированы явно?

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

Конечно, если бы мы уже знали, какой ход наилучший, нам не нужно было бы его искать.

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

person 500 - Internal Server Error    schedule 30.04.2016
comment
Это действительно странно, но случайный выбор был на самом деле быстрее, чем сортировка ходов по счету и запоминание их порядка для следующего поиска ... это игра с четырьмя соединениями с размером доски 8 * 8 и глубиной 6, так что это не очень мало. - person shinzou; 30.04.2016
comment
Стратегия с упорядочиванием ходов по предыдущему счету может работать лучше в таких играх, как шахматы, которые по своей природе менее хаотичны, чем в играх типа «соедини четыре» или «реверси». Для игр последнего типа оценка ранее оцененной позиции имеет тенденцию изменяться сильнее. - person 500 - Internal Server Error; 30.04.2016