Math
Дерево игры и альфа-бета
Дерево игры, в котором каждый блок высотой со своё значение: MAX-вершина ровно с самый высокий из детей, MIN-вершина — с самый низкий. Минимакс смотрит каждый лист; альфа-бета пропускает то, что не может изменить ответ, и сколько пропустит — зависит от порядка ходов.
Что происходит
Каждый блок высотой со своё значение, поэтому правило видно раньше, чем названо: MAX-вершина ровно с самый высокий из детей, MIN-вершина — с самый низкий, а корень — цена игры. Минимакс читает все b^d листьев. Альфа-бета читает их по порядку и перестаёт смотреть на вершину в тот миг, когда уже виденный сосед делает остальное неважным — ветви, куда она не вошла, остаются тёмными. Ответ от этого не меняется никогда, меняется только счёт, и счёт зависит от ПОРЯДКА ходов, а не от дерева: с лучшим ходом первым в каждой вершине нужен ровно минимум Кнута — Мура, около корня из b^d; с худшим ходом первым она видит каждый лист — но только до глубины 3, потому что с глубины 4 альфа, поднятая корнем, достаёт вниз и режет даже это. На что смотреть: тёмные ветви, золотой путь главной вариации и три столбика сзади — минимакс, этот поиск, минимум.
Уравнения модуля
Уравнения узел MAX: v = max по потомкам; узел MIN: v = min по потомкам; минимакс читает все b^d листьев альфа-бета: отбросить остальных потомков узла, как только альфа >= бета - ответ тот же, а число просмотренных узлов другое идеальный порядок: N_min = 2·b^(d/2) − 1 при чётном d, b^((d+1)/2) + b^((d−1)/2) − 1 при нечётном d (Кнут - Мур, 1975) наихудший порядок в каждом узле: N = b^d при d <= 3; начиная с d = 4 альфа корня достигает третьего уровня и всё равно отсекает порядок s из [−1, 1]: потомки узла сортируются по точному значению, когда его собственная хеш-монета ниже |s| - сначала лучшие при s > 0, сначала худшие при s < 0
