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
