Alpha-beta pruning - ускорение минимакс-алгоритма

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

Как же так? Советую поглядывать на картинку, пока вы это читаете:

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

А в какой ситуации из этого следует то, что вы никогда не окажетесь в этой вершине при оптимальной игре? Это происходит тогда, когда у вашего противника выше по дереву есть варианты, которые хуже X. Ведь если они есть, зачем пускать вас туда, где вам будет лучше?

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

Судя по википедии, количество вершин в лучшем случае становится вместо N^d равным sqrt(N^d). Судя по данному рандому со stackexchange, в шахматах 4.8x10^44 легальных позиций. То есть можно предположить, что в правильном порядке "обойти дерево шахмат" можно было бы за примерно 10^22 операций, что звучит гораздо реалистичнее, чем 10^44. Может быть, нейросеть способна упорядочить вершины так удачно?

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

Раз и два - видео с примером

@knowledge_accumulator