Комп'ютерне ґо

Велика дошка (19x19, 361 перетин) часто відзначається як основна перешкода на шляху створення сильних ґо-програм. Проблема великої дошки в тому, що вона перешкоджає глибокому пошуку методом альфа-бета-відсікання.

Поки що найбільшою дошкою, на якій донині здійснено повний перебір позицій є дошка 6x7[12].

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

Початкова стадія партії в ґо — фусекі — підпорядковується певним загальним принципам розвитку конфігурацій каменів, але для неї характерна значно більша різноманітність ходів, ніж у шахах. Новинки можуть зустрічатися не на 20-му ходу, а вже на третьому або четвертому, і грамотна гра в дебюті неможлива без осмислення стратегічних перспектив конструкцій, що виникають на дошці. Дзьосекі (типові схеми розіграшу позиції на обмеженій частині дошки, зокрема, у кутах), які в певному сенсі можна вважати аналогом розроблених шахових дебютів, не допускають механічного застосування і не дають гарантованого результату, оскільки ефект від їх використання залежить від загальної позиції на всій дошці, так що навіть вибір відповідного для цієї позиції дзьосекі в конкретному куті є складним інтелектуальним завданням.

Правило ко часто спричинює різку зміну характеру боротьби, наслідки якої важко оцінити навіть досвідченому гравцеві. Фактично треба щоразу порівнювати наслідки від «невідповіді» на ко-загрозу (як свою, так і противника) з ціною програшу ко-боротьби. Людині доводиться спиратися на свій досвід і інтуїцію, тоді як для комп'ютера ці поняття важко формалізуються.

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

Комп'ютерні ґо-програми довгий час були значно слабшми, ніж шахові програми. Підходи, застосовувані в шахових програмах, вивявилися посередніми в комп'ютерному ґо.

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

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

Ще одна проблема полягає у створенні хорошої оцінювальної функції для ґо. На кожному ходу може існувати кілька хороших ходів і щоб вибрати кращий хід, комп'ютер має оцінити різні можливі результати. Це стає складним завданням у ґо. Наприклад, може з'явитися можливість захопити камені противника завдяки зміцненню його групи в іншому місці. Рішення про те, чи є такий обмін вигідним, може бути занадто складним навіть для гравця-людини. Також може виявитися, що хід в іншій частині дошки і побудова там форми можуть виявитися важливішими.

Іноді згадується, що деякі складні комбінаторні задачі (фактично будь-яка NP-повна задача) можна перетворити стосовно ґо; однак те ж істинне і для інших настільних ігор, подібних до шахів, узагальненим для дошки довільної розмірності. NP-повні задачі люди не можуть розв'язувати швидше від комп'ютерів: сумнівно, що людина в змозі, наприклад, розв'язати задачу комівояжера за час, порівнянний з тим, за який її розв'язує комп'ютер. Отже, можливість застосувати методи розв'язування NP-повних задач до комп'ютерного ґо не дозволяє пояснити переваги людини над комп'ютером у цій грі.

Враховуючи, що завершальна стадія гри ґо (йосе) містить менше можливих ходів, ніж початок або середина, можна було б припустити, що комп'ютеру буде значно легше грати цю частину гри. Але й тут виникають проблеми:

• Закінчення партії в ґо — найбільш «математична» частина партії; в ній майже кожному ходу можна дати оцінку з точки зору кількості принесених ним очок. Проте, і ця стадія виявляється складною для комп'ютера — багато в чому через ко-боротьбу, що несподівано виникає у варіантах тактики, а також внаслідок труднощів, пов'язаних із чисельною оцінкою поняття ініціативи. На відміну від шахів, у ґо до кінця гри дошка не звільняється від фігур, а тісно заповнюється каменями, що унеможливлює створення глобальних баз даних для закінчень.
• Йосе може потягти за собою розгляд таких аспектів ґо, як «життя і смерть», які є NP-повними.
• Кожна з ділянок, що розглядається в йосе, може зачіпати інші ділянки, або спричинити зміни в загальній картині гри. Це призводить до таких непростих навіть для людини ситуацій, як потрійне ко, чотирикратне ко тощо.

Таким чином, дуже складно запрограмувати ефективний алгоритм навіть для гри завершальної стадії ґо, не кажучи про всю партію[13].

Люди відчувають, що грають в ґо краще, ніж комп'ютери, тому що порівнюють їх з людьми. «Можливо це не комп'ютери грають в ґо погано, а люди грають в нього занадто добре»[14]. Ґо, в порівнянні з іншими іграми з повною інформацією, має особливості, які роблять її особливо легкою для людей. Камені не рухаються, як фігури в шахах, не змінюють кольору, як у реверсі. Ці особливості дозволяють людям прораховувати довгі ланцюжки ходів, що складно для машини.

Однак у тих рідкісних випадках, коли камені неодноразово захоплюються і переграються на тих самих пунктах, у людей виникають проблеми, тоді як вони легкі для комп'ютерів.

Історично основним підходом до проблеми комп'ютерного ґо був «старий добрий ШІ». Пізніше як альтернативу такому підходу стали розглядати нейронні мережі. Однією з програм, що використовують алгоритм нейронних мереж для гри в ґо є WinHonte[15].

Результати цих розробок в галузі комп'ютерного ґо використовують у інших галузях: когнітивістика, розпізнавання образів і машинне навчання[16]. Теорія ігор, розділ прикладної математики, теж застосовується до комп'ютерного ґо[16].

Єдине, що повинна зробити програма внаслідок обмірковування ходу — вказати місце, куди слід помістити наступний камінь. Однак навіть таке просте рішення важко прийняти через неоднозначність позицій, до яких може привести ця постановка. Для вирішення цієї проблеми пристосовано різні архітектури. Найпопулярніші засновані на використанні дерева пошуку, застосування методів Монте-Карло, створення експертних систем і використанні машинного навчання. Деякі програми використовують тільки щось одне з перерахованого; більшість об'єднують кілька підходів.

Одна з традиційних технік у галузі ШІ для створення програм, які грають в ігри, використовує мінімаксне дерево пошуку. Для цього розглядають усі гіпотетично можливі послідовності ходів до певної глибини, а потім використовують оцінювальну функцію, щоб оцінити цінність ходу, з якого починалася кожна послідовність. Хід, який призводить до найкращого результату повторюється на дошці і далі така ж процедура проводиться для кожного ходу комп'ютерного гравця. Способи, засновані на використанні дерева пошуку, давали хороші результати стосовно шахів, проте, вони були менш успішними в застосуванні до ґо.

Частково причина в тому, що важко створити ефективну оцінювальну функцію і частково через велику кількість можливих ходів, яка приводить до великого коефіцієнта розгалуження. Це робить техніку дерева пошуку занадто ресурсомісткою. Тому програми, які інтенсивно використовують дерева пошуку, можуть добре грати тільки на маленькій дошці 9x9, але не на великій 19x19.

Існують методи, здатні поліпшити роботу дерев пошуку як щодо швидкості, так і щодо пам'яті. Метод альфа-бета-відсікання, пошуку основних відхилень, MDT-f можуть зменшити коефіцієнт розгалуження практично без втрати сили гри. Аналогічно, таблиця перестановок дозволяє зменшити кількість повторних обчислень, особливо коли вона використовується спільно з методом ітеративного заглиблення. Для швидкого доступу до даних, розташованих у таблиці перестановок, доводиться використовувати гешування. Гешування Зобріста часто зустрічається в програмах, що грають у ґо, оскільки забезпечує малу кількість колізій і дозволяє оперативно оновлювати інформацію про кожен хід з використанням лише двох операцій XOR замість повного обчислення.

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

Результати комп'ютерних змагань показують, що методи відповідності зразка для вибору ланцюжка кроків, об'єднані з швидким обмеженим тактичним пошуком (пояснений вище), достатні, щоб скласти конкурентоспроможну програму. Наприклад, GNU Go конкурентоспроможна, але вона не використовує пошук по всій дошці.

Новачки часто навчаються, переглядаючи записи старих партій майстрів гри. Є сильна гіпотеза, що накопичення знань — ключ до створення сильного ШІ. Наприклад, Тім Кінгер (Tim Kinger) і Девід Мічнер (David Mechner) кажуть: «ми віримо, що, тільки використовуючи інструменти накопичення і підтримки знань в галузі ґо, можна створити значно сильніші програми, ніж є зараз.» Вони пропонують два шляхи: розгляд загальних форм та їх використання, або розгляд місцевих протистоянь. «…Програмам для гри в ґо все ще бракує як якості, так і кількості знань.»[17]

Після реалізації, використання досвідних знань показало себе дуже ефективним. Сотні керівних принципів і емпіричних правил для сильної гри сформулювали і аматори високого рівня і професіонали. Завдання програміста полягає в тому, щоб узяти ці евристики, формалізувати їх у машинному коді, і використовувати порівняння зі зразком (pattern matching) і розпізнавання образів (pattern recognition) для виявлення того, коли їх варто застосовувати. Також варто розробити систему для виявлення кращого рішення в разі, коли застосовні відразу кілька принципів.

Більшість відносно успішних результатів отримані на основі навичок гри в ґо програмістів, які й написали програми, і їхніми особистими здогадками з приводу гри майстрів, а не на основі формальних математичних розрахунків; вони намагаються змусити комп'ютер наслідувати ті способи, якими вони самі грають у ґо. «Більшість конкурентоспроможних програм потребувало 5-15 років людських зусиль і містить 50-100 модулів, що мають справу з різними аспектами гри.»[18]

Цей метод до недавнього часу був найуспішнішою технікою у розробці конкурентоспроможних програм гри в ґо на повнорозмірному полі. Прикладами програм, які поклалися більшою мірою на досвід, є Handtalk (пізніше відомий як Goemate), The Many Faces of Go, Go Intellect і Go++, кожну з яких у певний момент вважали найкращою програмою ґо в світі.

Однак додавання експертних знань іноді послаблює програму, тому що просто поверхневе орієнтування в ситуації може привести до помилок. «Кращі програми зазвичай роблять хороші ходи рівня майстра, однак, як знають усі гравці, один поганий хід може зруйнувати хорошу гру.»[18]

Однією з головних альтернатив використанню закодованих знань і пошуку ходів є метод Монте-Карло. Суть цього методу полягає в тому, що спочатку на поточній дошці вибираються позиції, на які можна піти, а потім починаючи послідовно з кожної з них розігрується велика кількість випадкових партій. Позиція, яка дає найбільше співвідношення перемог до поразок, вибирається для наступного ходу. Переваги цього методу в тому, що він вимагає дуже невеликих знань проблемної галузі і не вимагає багато пам'яті. Однак у цього методу є й очевидні недоліки. Через те, що ходи генеруються навмання і розглядаються не всі можливі продовження, якісь ходи будуть помилково оцінені як хороші. Навіть попри те, що випадкова вибірка продовжень буде сприятливою, у противника можуть виявитися нечисленні, але досить очевидні ходи, які дозволять йому отримати перевагу. Ці ходи або не потраплять у випадкову вибірку, або кількість хороших продовжень виявиться більшою. Як наслідок, вийде програма, яка сильна в стратегічному, але слабка в тактичному плані. Цю проблему можна пом'якшити доданням деяких експертних знань і глибшого пошуку. У число програм, що використовують метод Монте-Карло входять такі як Zen, The Many Faces of Go v12, Leela, MoGo, Crazy Stone[19], Olga і Gobble.

2006 року розроблено нову методику upper confidence bounds applied to trees[20], що використовується в багатьох програмах для гри в ґо на дошці 9х9 з чудовими результатами. Техніка UCT спільно з багатьма іншими техніками оптимізації для гри на дошці 19х19 дозволила MoGo стати однією з найсильніших програм. Техніку UCT для гри на дошці 19х19 використовують такі програми: MoGo, Crazy Stone, Mango. MoGo виграла комп'ютерну олімпіаду 2007 року і виграла одну з трьох бліц-ігор проти Го Цзюаня (Guo Juan), 5-й професійний дан. 2008 року The Many Faces of Go виграла комп'ютерну олімпіаду після додання UCT до її, заснованого на експертних знаннях, механізму.

2008 року MoGo виграла одну з трьох ігор[21] проти Каталіна Церану, 5 про-дан, на дошці 9х9 зі стандартним часом (30 хвилин на гру кожному гравцеві). MoGo запустили на кластерному комп'ютері (32 вузли по 8 ядер частотою 3 ГГц). Ці результати схвалила Французька федерація ґо[22]. MoGo також грала на дошці 19х19 проти того ж Каталіна Церану і програла, маючи фору 9 каменів. Варто, однак, відзначити, що програма грала сильно і програла лише через поганий вибір в ко-боротьбі в кінці гри, в якій комп'ютери традиційно слабкі.

7 серпня 2008 року MoGo виграла гру на дошці 19х19 проти Кіма Менвана (Kim MyungWan), 8p, маючи фору 9 каменів з перевагою 1,5 очка. Кім використав 13 хвилин на обдумування, тоді як MoGo — близько 55-ти, однак він відчував, що використання більшої кількості часу не допоможе йому виграти. MoGo запускали з Нідерландів на суперкомп'ютері з 800 вузлів, що містить по 4 ядра на вузол, частотою 4,7 ГГц і продуктивністю 15 терафлопс[23]. Менхван і MoGo грали чотири гри з різним гандикапом і часовими обмеженнями і виграли по дві гри. Звіти про ігри доступні на КГС[24], де MoGo грала під ніком MogoTitan.

У лютому 2009 року MoGo здобула ще більшу перемогу — з гандикапом 7 каменів вона перемогла гравця 9 дану Чжоу Цзюньсюня (Jun-Xun Zhou), а з форою 6 каменів зломила опір гравця першого дану Цзянь Ліченя (Li-Chen Chien)[25].

До початку 2012 року CrazyStone[26], заснована на тому ж методі Монте-Карло, що й MoGo, має стабільний 5 дан на сервері КГС[27].

У грудні 2010 року комп'ютерна програма Zen досягла рівня 4 дану на сервері КГС. Створив програму японський програміст Йодзі Одзіма (Yoji Ojima). У червні 2011 року комп'ютерна програма Zen19d досягла рівня 5 дану на сервері КГС, граючи зі швидкістю 15 секунд на хід. Ця версія програми працювала на 26-ядерному комп'ютері. У березні 2012 року комп'ютерна програма Zen19D досягла рівня 6 дану на сервері КГС, граючи зі швидкістю 15 секунд на хід. Ця версія програми працювала на 28-ядерному комп'ютері[28].

У березні 2012 року Zen19D виграла у Масакі Такемії (Takemiya Masaki) 9 дан з 4 каменями фори. Для цього матчу використовувався кластер з 4 комп'ютерів (dual 6-core Xeon X5680/4.2 GHz, 6-core Xeon W3680/4 GHz і два 4-core i7 920/3.5 GHz) з'єднаних через GbE LAN. Таке ж обладнання використовується для Zen19S і Zen19D на сервері КГС[29].

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

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

Перші змагання з комп'ютерного ґо спонсорувалися USENIX. Вони проводилися в 1984—1988 роках. Ці змагання відкрили Nemesis, першу конкурентоспроможну програму, здатну грати в ґо від Брюса Вілкокса (Bruce Wilcox) і G2.5 Девіда Фотланда, яка згодом розвинеться в Cosmos і The Many Faces of Go.

Одним з ранніх заохочень розробок у галузі комп'ютерного ґо став кубок Інга, змагання з відносно великим грошовим призом, спонсороване тайванським банкіром і засновником Кубка Інга Ін Чанці (Ing Chang-ki), яке проводилося від 1988 до 2000 раз на чотири роки. Переможцю цього турніру дозволялося кинути виклик молодим професіоналам у форовій грі з коротким часом. Якщо програма вигравала, то її автору присуджували грошовий приз і встановлювали новий приз за перемогу професіонала з меншим гандикапом. Призи Інга мали закінчитися 1) 2000 року 2) коли програма обіграє гравця 1-го професійного дану в рівній грі (40.000.000 нових тайваньських доларів). Останнім переможцем був Handtalk 1993 року, отримав 250.000 NT$ за перемогу над трьома 11-13 річними аматорами 2—6 дану з форою 11 каменів. До 2000 року залишився незатребуваним приз 400.000 NT$ за перемогу над професіоналом з форою 9 каменів[30].

Дивно, але Японія лише недавно почала спонсорувати свої власні чемпіонати з комп'ютерного ґо. Змагання кубку FOST проводилися щорічно від 1995 до 1999 року в Токіо. Його витіснив Виклик Ґіфу, що проводився щорічно від 2003 до 2006 року в Оґакі, префектура Ґіфу.

У жовтні 2015 року програма AlphaGo, розроблена компанією DeepMind виграла у триразового чемпіона Європи Фань Хуея (2 професійний дан) матч із п'яти партій з рахунком 4—1. Це перший в історії випадок, коли комп'ютер виграв у ґо в професіонала в рівній грі[3][31][32].

У березні 2016 року AlphaGo перемогла професіонала 9 дану Лі Седоля у чотирьох партіях з п'яти.[4]

У травні 2017 року на саміті «Future of Go Summit» AlphaGo виграла три партії з трьох у міні-матчі з одним з найсильніших гравців у світі, лідером світового рейтингу Ело Ке Цзе[8]

Коли два комп'ютери грають в ґо один з одним, то, в ідеалі, повинна вийти картина гри, властива грі людини з людиною. Однак цього важко досягти, особливо в кінці гри. Основна проблема полягає в тому, що програма не може вести діалогу з противником. Так якщо є якісь розбіжності в статусі груп, то для програм немає ніяких способів вирішити їх. Одним зі способів вирішення цієї проблеми може бути введення людини-судді або високоспеціалізованого програмного середовища для оцінки фінальної позиції. Альтернативний метод — дозволити програмам робити ходи доти, поки остаточно не визначаться статуси всіх спірних груп. Головна перешкода до реалізації цього рішення полягає в тому, що в деяких варіантах правил ґо (наприклад, японські правила) гравців штрафують за зайві ходи, і вони недоотримують очок. Тому існує ризик, що, засумнівавшись у своїй перевазі, програма програє після догравання переможної ситуації.

• AI-oriented survey of Go
• Co-Evolving a Go-Playing Neural Network, written by Alex Lubberts & Risto Miikkulainen, 2001
• Computer Game Playing: Theory and Practice, edited by M.A. Brauner (The Ellis Horwood Series in Artificial Intelligence), Halstead Press, 1983. A collection of computer-go articles. The American Go Journal, vol. 18, No 4. page 6. [ISSN 0148-0243]
• A Machine-Learning Approach to Computer Go, Jeffrey Bagdis, 2007.
• Minimalism in Ubiquitous Interface Design Wren, C. і Reynolds, C. (2004) Personal and Ubiquitous Computing, 8(5), стор. 370—374. Video of computer go vision system in operation shows interaction and users exploring Joseki and Fuseki.
• Monte-Carlo Go, представив Markus Enzenberger, Computer Go Seminar, Альбертський університет, квітень 2004
• Monte-Carlo Go, автори B. Bouzy і B. Helmstetter із Scientific Literature Digital Library
• Static analysis of life and death in the game of Go, автори Ken Chen і Zhixing Chen, 20 лютого 1999

• Mick's Computer Go Page
• Extensive list of computer Go events
• All systems Go від Девіда Мехнера (David A. Mechner) (1998), обговорення гри, де професійний гравець у ґо Дженіс Кім виграв у програми Handtalk з форою 25 каменів.
• Kinger, Tim and Mechner, David. An Architecture for Computer Go (1996)
• Стоірнки Computer Go і Computer Go Programming на Sensei's Library
• Computer Go bibliography
• Another Computer Go Bibliography
• Computer Go mailing list
• Статті про комп'ютерне ґо, опубліковані в Ideosphere дає поточну оцінку того, чи стане програма найкращим у світі гравцем у ґо
• Information on the Go Text Protocol, зазвичай використовується для взаємодії ігрових механізмів ґо з графічними клієнтами та інтернет-серверами
• Кімната комп'ютерного ґо на K Go Server (KGS) для онлайнових обговорень і запуску ботів
• Two Representative Computer Go Games, стаття про дві гри в ґо за участі комп'ютів 1999 року, в одній з двома комп'ютерними гравцями, а в іншій — гра людини з комп'ютером із форою 29 каменів
• What A Way to Go описує роботу Microsoft Research над створенням комп'ютерного гравця в ґо.
• Cracking Go, by Feng-hsiung Hsu, IEEE Spectrum magazine, October 2007 — доводиться, чому має бути можливість побудувати машину ґо, сильнішу за будь-якого гравця-людину

• AYA Хіросі Ямасіти (Hiroshi Yamashita)
• Crazy Stone Ремі Кулома (Rémi Coulom)
• GNU Go, найсильніша відкрита програма для ґо
• Go++ Майкла Райсса (Michael Reiss) (в Японії продається як Strongest Go або Tuyoi Igo)
• Go Intellect Кена Чена (Ken Chen)
• Handtalk/Goemate, розробив у Китаї Zhixing Chen (в Японії продається як Shudan Taikyoku)
• Haruka by Ryuichi Kawa (в Японії продається як Saikouhou)
• Indigo by Bruno Bouzy
• Katsunari by Shin-ichi Sei
• KCC Igo, з Північної Кореї (в Японії продається як Silver Star або Ginsei Igo)
• Leela, перша програма з методом Монте-Карло для продажу
• The Many Faces of Go Девіда Фотланда (David Fotland; в Японії продається як AI Igo)
• MoGo Сильвейна Ґеллі (Sylvain Gelly); паралельна версія команди розробників.
• Smart Go Андерса Кірфула (Anders Kierulf), розробника Smart Game Format