Програма за 72 години сама себе навчила грати в шахи

Студент з Імперського коледжу в Лондоні створив шахову комп'ютерну програму Giraffe, яка повністю побудована на принципах машинного навчання і не використовує вручну налаштовані інструменти для аналізу партії. Giraffe навчалася в ході гри з самим собою і за рекордні 72 години досягла рівня, що відповідає двом верхнім відсоткам рейтингу за версією Міжнародної шахової асоціації. Препринт магістерської дисертації з описом програми викладено на .Автор використовував два підходи, що принципово відрізняли Giraffe від аналогічних шахових програм. По-перше, для оцінки позиції на дошці алгоритм автоматично відбирав найбільш значущі ознаки в ході ігор з самим собою (приклад машинного навчання з підкріпленням). При цьому програма не мала доступу до попередньо закладених рекомендацій, відомих, наприклад, із залучення шахових експертів до розробки або попереднього аналізу великої кількості партій. По-друге, в Giraffe використовувався якісно новий підхід до аналізу дерева рішень. Так як в ході типової шахової партії може виникнути величезне число допустимих варіантів ходу, для того, щоб проаналізувати їх всі, необхідні обчислювальні потужності, доступні тільки на суперкомп'ютерах. Для того, щоб знизити обсяг обчислень, алгоритм на кожному ході аналізує лише частину дерева рішень. Традиційно в шахових програмах застосовується метод, заснований на максимальній довжині гілок. Наприклад, на кожному ході алгоритм проаналізує всі доступні гілки не далі, ніж на 10 ходів. У Giraffe автор замість довжини гілки використовував значення ймовірності того, що дана гілка призведе до найбільш довгого ланцюжку ходів. Таким чином, аналізувалися тільки ті гілки, в яких ця ймовірність була вище певного порогу. За таким методом існує наступне пояснення: пошук найкращого ходу заснований на тому припущенні, що противник також обере найкращий хід. Таким чином, партія буде розвиватися настільки довго, наскільки це можливо. При цьому деякі ситуації на дошці (наприклад, шах або розмін цінних фігур) вимагають обов'язкових відповідних ходів, таким чином обмежуючи число можливих продовжень. Якщо, наприклад, в даній партії відбувається розмін ферзей, алгоритм, заснований на глибині гілки, буде аналізувати в тому числі і всі доступні гілки, де ферзя все-таки не взяли, просто тому, що всі ці гілки виявляться коротшими порогової величини. При цьому алгоритм на основі ймовірностей навпаки, - буде рухатися в бік найбільш довгої гілки з найменшим числом розвилок.


У підсумку Giraffe протягом 72 годин навчався в ході гри з самим собою, а його остаточна сила перевірялася на спеціальному наборі з 15000 позицій, в якій всі доступні ходи проранжовані від 0 до 10, де 10 відповідає кращому ходу. З дев'яти популярних алгоритмів для настільних комп'ютерів і невеликих серверів Giraffe посів друге місце за ефективністю, виявивши 9641 «правильний» хід з 15000. Перше місце посіла програма Stockfish 5, яка знайшла 10505 найкращих рішень. Автор зазначає, що основною метою в розробці Giraffe було створення програми, яка б мала можливість навчатися незалежно від «ручних» налаштувань або участі експертів-шахістів. Передбачається, що Giraffe проявить таку ж вражаючу ефективність і в інших настільних іграх, оскільки він використовує дуже узагальнений підхід до навчання. Шахові комп'ютери розроблялися з середини XX століття, проте лише в 1990-х роках вони досягли рівня гросмейстерів. У 1997 році суперкомп'ютер Deep Blue в шести партіях обіграв чинного чемпіона світу Гаррі Каспарова. Відтоді шахові комп'ютери ставали тільки сильнішими, і на сьогоднішній день гравці-люди не можуть змагатися з топовими програмами. Проте, існують класичні настільні ігри, в яких людина досі обігрує навіть найпотужніші суперкомп'ютери. Найбільш відомим прикладом є го - гра, що з'явилася в Китаї кілька тисяч років тому.


COM_SPPAGEBUILDER_NO_ITEMS_FOUND