Будет ли случайный выбор дочернего узла в алгоритме альфа-бета иметь больше шансов получить отсечение, чем выбор их по порядку?
Вот псевдокод с моим дополнением, отмеченным ***.
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
Я провел небольшую выборку с этим в игре с подключением четыре, и кажется, что она работает немного быстрее, но когда я на самом деле подсчитываю отсечки со случайностью и без нее, оказывается больше отсечек без случайности. Это немного странно.
Можно ли доказать, что это быстрее (или медленнее)?