Альфа-бета-відсікання в шахових рушіях

Пояснення

Альфа-бета-відсікання прискорює пошук, який виконує , програма для порівняння ходів і відповідей. Пошук можна уявити як дерево: кожен вузол є позицією, а кожна гілка легальним ходом. Без відсікання програма переглядала б багато продовжень, які зрештою виявляться неважливими.

Під час пошуку метод підтримує дві межі. Альфа є найкращим результатом, який одна сторона вже може гарантувати на поточному шляху. Бета є межею, створеною альтернативою, уже доступною супернику. Щойно продовження стає настільки поганим, що раціональний гравець ніколи його не обере, подальший пошук у ньому не може змінити рішення у вищому вузлі.

Гілку зупиняють через логічну межу в дереві, а не лише тому, що хід здається непривабливим. За тієї самої глибини й тих самих оцінок на межі пошуку альфа-бета повертає той самий вибір, що й повний пошук, який припускає найкращі відповіді обох сторін.

Економія сильно залежить від порядку ходів. Раннє випробування сильних ходів швидше встановлює корисні межі й дозволяє зупинити більше гілок без глибшого перегляду. , яка надає позиції числову оцінку, дає значення в точках, де скінченний пошук завершується.

Використання й контекст

Альфа й бета не є двома постійними оцінками дошки. Це змінні межі, які алгоритм підтримує під час дослідження лінії.

Поширені непорозуміння

Відсікання та довільне відкидання

Альфа-бета пропускає гілку лише після доведення, що за поточних меж вона не може змінити вибір.

Більше відсікань автоматично означає більшу силу

Сила також залежить від упорядкування ходів, якості оцінювання, глибини пошуку та багатьох інших методів рушія.

Джерела

1.An analysis of alpha-beta pruning, Artificial Intelligence / Elsevier
2.Alpha-Beta, Chess Programming Wiki
3.search.cpp, Stockfish