Евристика нульового ходу
Евристика нульового ходу — метод збільшення швидкості алгоритму відсічення альфа-бета в комп'ютерних шахах.
Відсічення альфа-бета прискорює виконання алгоритму мінімакс, розпізнаючи точки відсічки. Це точки в ігровому дереві, де поточна позиція така добра для сторони, яка зараз ходить, що найкращий шлях для протилежної сторони — уникнути ходу. Так як такі позиції, можливо, не були результатом найкращої гри, їх та всі гілки ігрового дерева, які ідуть від них, можна проігнорувати. Чим скоріше програма робить відсічку, тим скоріше працює система пошуку. Евристика нульового ходу спроєктована, щоб зменшити час пошуку.
Ідея евристики нульового ходу базується на факті, що найкращі ходи в шахах покращують позицію для того, хто їх зробив. Так, якщо гравець втратить право ходу (що недопустимо в шахах) і все ще має позицію, достатню для відсічки, тоді програма майже неодмінно зробить відсічку, якщо цей гравець вже походив.
Ця стаття не містить посилань на джерела. (вересень 2015) |