Комп'ютерне ґо — напрямок штучного інтелекту зі створення комп'ютерних програм, що грають у ґо.
Гра ґо є плідною темою досліджень зі штучного інтелекту протягом десятиліть, кульмінацією чого став 2017 рік, коли AlphaGo Master виграла три з трьох ігор проти , який на той час неперервно утримував світовий рейтинг № 1 протягом двох років.
Перешкоди на шляху програм Протягом довгого часу вважалося, що комп'ютерне ґо має суттєві відмінності в порівнянні з комп'ютерними шахами, оскільки методи, засновані на швидкому пошуку в порівнянні з людським досвідом, об'єднані з відносно низьким знанням предметної галузі не будуть ефективними для ґо. Тому значні зусилля в галузі комп'ютерного ґо витрачено на об'єднання експертних знань з локальним пошуком для знаходження відповіді на питання тактичної природи гри. Результатом цих зусиль стали програми, здатні знаходити хороші рішення в деяких локальних ситуаціях, але явно слабкі щодо повного аналізу гри. Крім того, збільшення потужності обладнання мало додавало для цих програм у плані сили гри, що робило у цілому повільним розвиток цієї галузі. Тому вважалося, що програму, яка добре грає в ґо, можна буде створити тільки в далекому майбутньому і тільки за допомогою накопичених на той час знань у галузі штучного інтелекту. Навіть написання програми, здатної визначити переможця в закінченій грі, сприймалося як нетривіальне завдання.
2006 року з'явилися програми, засновані на пошуку Монте-Карло. Сила гри штучного інтелекту покращилася, але розрив з рівнем гри професійних гравців в ґо залишався, і причому значний.
Однак у 2015 році комп'ютерна програма (AlphaGo, компанія DeepMind) вперше виграла у професіонала (, 2 професійний дан) рівний матч (з рахунком 5-0).
У березні 2016 року AlphaGo перемогла професіонала Лі Седоля у перших трьох партіях з п'яти ігор. Це був перший випадок, коли професіонал 9 дану, один з найсильніших гравців світу, грав з комп'ютером без гандикапу. У четвертій грі Лі зміг здобути перемогу, але п'яту партію виграв комп'ютер, таким чином матч закінчився з рахунком 4:1. (див. докладно： Матч AlphaGo — Лі Седоль)
У травні 2017 року на саміті «Future of Go Summit» зіграно міні-матч із 3 партій між AlphaGo і одним з найсильніших гравців у світі, лідером світового рейтингу Ело , де всі партії виграла програма. На цьому ж форумі AlphaGo обіграла команду з 5 професіоналів максимального 9 дану ( (№ 3 в рейтингу найсильніших гравців, рейтинг перед матчем 3571 пункт), (№ 8, 3513)), (№ 10, 3509), (№ 11, 3508), (№ 18, 3474)).
Занадто велика дошка Велика дошка (19x19, 361 перетин) часто відзначається як основна перешкода на шляху створення сильних ґо-програм. Проблема великої дошки в тому, що вона перешкоджає глибокому пошуку методом альфа-бета-відсікання.
Поки що найбільшою дошкою, на якій донині здійснено повний перебір позицій є дошка 6x7.
Велика кількість допустимих ходів Продовжуючи порівняння з шахами, слід зазначити, що ходи в ґо майже не обмежені правилами. У той час як перший хід у шахах можна здійснити двадцятьма способами, перший хід у ґо має 55 варіантів, з урахуванням симетрії дошки. Після декількох перших ходів у різних кутах дошки симетрія ігрової ситуації втрачається і кількість можливих ходів зростає, досягаючи кількості вільних пунктів на дошці.
Відсутність «точної» дебютної теорії Початкова стадія партії в ґо — фусекі — підпорядковується певним загальним принципам розвитку конфігурацій каменів, але для неї характерна значно більша різноманітність ходів, ніж у шахах. Новинки можуть зустрічатися не на 20-му ходу, а вже на третьому або четвертому, і грамотна гра в дебюті неможлива без осмислення стратегічних перспектив конструкцій, що виникають на дошці. Дзьосекі (типові схеми розіграшу позиції на обмеженій частині дошки, зокрема, у кутах), які в певному сенсі можна вважати аналогом розроблених шахових дебютів, не допускають механічного застосування і не дають гарантованого результату, оскільки ефект від їх використання залежить від загальної позиції на всій дошці, так що навіть вибір відповідного для цієї позиції дзьосекі в конкретному куті є складним інтелектуальним завданням.
Ко-боротьба Правило ко часто спричинює різку зміну характеру боротьби, наслідки якої важко оцінити навіть досвідченому гравцеві. Фактично треба щоразу порівнювати наслідки від «невідповіді» на ко-загрозу (як свою, так і противника) з ціною програшу ко-боротьби. Людині доводиться спиратися на свій досвід і інтуїцію, тоді як для комп'ютера ці поняття важко формалізуються.
Адитивна природа гри У шахах, як і в багатьох інших іграх, протягом партії фігур на дошці стає менше, що спрощує перебір ходів. У ґо кожен наступний хід, навпаки, додає на дошку один камінь (хоча можливі й зняття), створюючи додаткові ігрові моменти.
Шахова техніка незастосовна в ґо Комп'ютерні ґо-програми довгий час були значно слабшими, ніж шахові програми. Підходи, застосовувані в шахових програмах, вивявилися посередніми в комп'ютерному ґо.
Шахові правила легко формалізуються, їх можна подати в зручній для машини формі, яка дозволить їй грати на високому рівні.
Але прості позиційні правила, що застосовуються в шахах, не будуть ефективними в ґо. Для визначення цінності каменя потрібен складний аналіз, хоча б для визначення того, чи жива група, якій він належить, наскільки значний вплив групи і які небезпеки їй загрожують.
Функція оцінки Ще одна проблема полягає у створенні хорошої оцінювальної функції для ґо. На кожному ходу може існувати кілька хороших ходів і щоб вибрати кращий хід, комп'ютер має оцінити різні можливі результати. Це стає складним завданням у ґо. Наприклад, може з'явитися можливість захопити камені противника завдяки зміцненню його групи в іншому місці. Рішення про те, чи є такий обмін вигідним, може бути занадто складним навіть для гравця-людини. Також може виявитися, що хід в іншій частині дошки і побудова там форми можуть виявитися важливішими.
Комбінаторна складність Іноді згадується, що деякі складні комбінаторні задачі (фактично будь-яка NP-повна задача) можна перетворити стосовно ґо; однак те ж істинне і для інших настільних ігор, подібних до шахів, узагальненим для дошки довільної розмірності. NP-повні задачі люди не можуть розв'язувати швидше від комп'ютерів: сумнівно, що людина в змозі, наприклад, розв'язати задачу комівояжера за час, порівнянний з тим, за який її розв'язує комп'ютер. Отже, можливість застосувати методи розв'язування NP-повних задач до комп'ютерного ґо не дозволяє пояснити переваги людини над комп'ютером у цій грі.
Завершення гри Враховуючи, що завершальна стадія гри ґо (йосе) містить менше можливих ходів, ніж початок або середина, можна було б припустити, що комп'ютеру буде значно легше грати цю частину гри. Але й тут виникають проблеми:
Закінчення партії в ґо — найбільш «математична» частина партії; в ній майже кожному ходу можна дати оцінку з точки зору кількості принесених ним очок. Проте, і ця стадія виявляється складною для комп'ютера — багато в чому через ко-боротьбу, що несподівано виникає у варіантах тактики, а також внаслідок труднощів, пов'язаних із чисельною оцінкою поняття ініціативи. На відміну від шахів, у ґо до кінця гри дошка не звільняється від фігур, а тісно заповнюється каменями, що унеможливлює створення глобальних баз даних для закінчень. Йосе може потягти за собою розгляд таких аспектів ґо, як «життя і смерть», які є NP-повними. Кожна з ділянок, що розглядається в йосе, може зачіпати інші ділянки, або спричинити зміни в загальній картині гри. Це призводить до таких непростих навіть для людини ситуацій, як потрійне ко, чотирикратне ко тощо.
Таким чином, дуже складно запрограмувати ефективний алгоритм навіть для гри завершальної стадії ґо, не кажучи про всю партіюСм. Computer Go Programming pages at Sensei's Library.
Чому люди грали в ґо краще від комп'ютера Люди відчувають, що грають в ґо краще, ніж комп'ютери, тому що порівнюють їх з людьми. «Можливо це не комп'ютери грають в ґо погано, а люди грають в нього занадто добре»Raiko, Tapani: «The Go-Playing Program Called Go81» section 1.2. Ґо, в порівнянні з іншими іграми з повною інформацією, має особливості, які роблять її особливо легкою для людей. Камені не рухаються, як фігури в шахах, не змінюють кольору, як у реверсі. Ці особливості дозволяють людям прораховувати довгі ланцюжки ходів, що складно для машини.
Однак у тих рідкісних випадках, коли камені неодноразово захоплюються і переграються на тих самих пунктах, у людей виникають проблеми, тоді як вони легкі для комп'ютерів.
Тактичний пошук Один дуже важливий розділ гри ґо, пов'язаний з визначенням того, які групи каменів здатні вижити, а які можна захопити, відомий як «життя і смерть». Найпрямішою стратегією для визначення життя та смерті є побудова дерева пошуку ходів, які впливають на розглянуту групу та визначення статусу групи в кінцевих вершинах цього дерева.
Однак у межах часових обмежень і обмежень обсягу оперативної пам'яті неможливо визначити з повною точністю, які ходи зачіпають певну групу. Нерідкі, наприклад, ситуації, коли життя однієї групи можна забезпечити тільки за рахунок полону іншої. Це означає, що для розв'язання поставленої задачі слід застосувати деякі евристики для визначення ходів, які потребують розгляду. Як результат у програм, що грають у ґо простежується залежність між часовими витратами на обдумування і якістю визначення життєздатності груп.
Проблема подання Існує проблема подання позиції в ґо для програм. Якщо в процесі обдумування ходу відбувається інтенсивний пошук ходу, то подання потребує малого обсягу даних, які можна було б легко скопіювати і знищити. Якщо інформація про позицію буде містити сильно-структуровані дані, то їх буде важко копіювати і це призведе до уповільнення процесу пошуку.
Найпростіший спосіб подання-завести одно- або двомірний масив, у якому буде міститися інформація про те, камені якого кольору стоять на кожній позиції поля і можливість ходу на порожні позиції.
Більшість програм, однак, використовують для подання позиції сирішу інформацію про дошку. Це може бути інформація про те, як з'єднані камені в кожному рядку і як рядки асоціюються між собою, інформація про групи каменів, які ризикують бути захопленими і які живі. І хоча цю інформацію можна добути з прямого подання, буде значно швидше змінювати її на кожному ході і передавати в готовому вигляді. Такі додаткові зміни вимагають запам'ятовування більших обсягів даних і можуть знизити швидкість копіювання, тому проблема подання ігрової ситуації також гостро стоїть перед творцями ґо-програм.
Альтернативою може бути зберігання тільки однієї копії дошки, а під час ходу запам'ятовування зроблених змін. Це дозволяє скоротити витрати пам'яті і швидкість копіювання і позбавляє від повторного копіювання зайвих даних. Але слід урахувати, що така форма подання може вимагати інших підходів до її інтерпретації, ніж зберігання повної інформації про дошку.
Використання подань, відмінних від прямого, стикається в ґо зі ще одним підводним каменем, пов'язаним із самою структурою гри. Позиція в ґо складається з одиничних каменів, що утворюють змінювані структури (групи і набори груп). З точки зору стратегії і тактики гри, кориснішими є варіанти подання, які містять у явному вигляді інформацію про структури і стани. Але така інформація може істотно змінюватися буквально на кожному ході (наприклад, єдиний хід, що створює з'єднання між двома групами, які мають по одному оку, фактично перетворює ці дві групи, що перебувають під загрозою, на одну, гарантовано живу, що має відбитися в поданні як об'єднання цих груп). Задача адекватної зміни складного подання в подібних випадках є вельми нетривіальною.
Системний дизайн
Нові підходи до проблем Історично основним підходом до проблеми комп'ютерного ґо був «старий добрий ШІ». Пізніше як альтернативу такому підходу стали розглядати нейронні мережі. Однією з програм, що використовують алгоритм нейронних мереж для гри в ґо є WinHonte.