Вікіпедія

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

Комп'ютерне ґо — напрямок штучного інтелекту зі створення комп'ютерних програм, що грають у ґо.

Гра ґо є плідною темою досліджень зі штучного інтелекту протягом десятиліть, кульмінацією чого став 2017 рік, коли AlphaGo Master виграла три з трьох ігор проти Ке Цзе[ru], який на той час неперервно утримував світовий рейтинг № 1 протягом двох років.[1][2]

Перешкоди на шляху програм ред.

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

2006 року з'явилися програми, засновані на пошуку Монте-Карло. Сила гри штучного інтелекту покращилася, але розрив з рівнем гри професійних гравців в ґо залишався, і причому значний.

Однак у 2015 році комп'ютерна програма (AlphaGo, компанія DeepMind) вперше виграла у професіонала (Фань Хуея[ru], 2 професійний дан) рівний матч (з рахунком 5-0)[3].

У березні 2016 року AlphaGo перемогла професіонала Лі Седоля у перших трьох партіях з п'яти ігор.[4] Це був перший випадок, коли професіонал 9 дану, один з найсильніших гравців світу, грав з комп'ютером без гандикапу.[5] У четвертій грі Лі зміг здобути перемогу, але п'яту партію виграв комп'ютер, таким чином матч закінчився з рахунком 4:1.[6][7] (див . докладно： Матч AlphaGo — Лі Седоль)

У травні 2017 року на саміті «Future of Go Summit» зіграно міні-матч із 3 партій між AlphaGo і одним з найсильніших гравців у світі, лідером світового рейтингу Ело Ке Цзе[ru], де всі партії виграла програма[8][9][10]. На цьому ж форумі AlphaGo обіграла команду з 5 професіоналів максимального 9 дану (Мі Ютін[en] (№ 3 в рейтингу найсильніших гравців, рейтинг перед матчем 3571 пункт), Чень Яоє[ru] (№ 8, 3513)), Чжоу Жуйян[ru] (№ 10, 3509), Си Юэ[en] (№ 11, 3508), Тан Вэйсин[zh] (№ 18, 3474))[11].

Занадто велика дошка ред.

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

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

Велика кількість допустимих ходів ред.

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

Відсутність «точної» дебютної теорії ред.

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

Ко-боротьба ред.

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

Адитивна природа гри ред.

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

Шахова техніка незастосовна в ґо ред.

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

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

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

Функція оцінки ред.

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

Комбінаторна складність ред.

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

Завершення гри ред.

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

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

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

Чому люди грали в ґо краще від комп'ютера ред.

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

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

Тактичний пошук ред.

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

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

Проблема подання ред.

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

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

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

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

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

Системний дизайн ред.

Нові підходи до проблем ред.

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

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

Розробка системи ШІ ред.

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

Пошук за мінімаксним деревом ред.

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

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

Існують методи, здатні поліпшити роботу дерев пошуку як щодо швидкості, так і щодо пам'яті. Метод альфа-бета-відсікання, пошуку основних відхилень[en], MDT-f можуть зменшити коефіцієнт розгалуження практично без втрати сили гри. Аналогічно, таблиця перестановок[en] дозволяє зменшити кількість повторних обчислень, особливо коли вона використовується спільно з методом ітеративного заглиблення. Для швидкого доступу до даних, розташованих у таблиці перестановок, доводиться використовувати гешування. Гешування Зобріста[en] часто зустрічається в програмах, що грають у ґо, оскільки забезпечує малу кількість колізій і дозволяє оперативно оновлювати інформацію про кожен хід з використанням лише двох операцій 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 [Архівовано 26 Червня 2014 у Wayback Machine.], The Many Faces of Go v12 [Архівовано 5 Серпня 2004 у Wayback Machine.], 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)[1] [Архівовано 11 Серпня 2021 у Wayback Machine.], 5-й професійний дан. 2008 року The Many Faces of Go [Архівовано 29 Травня 2003 у Wayback Machine.] виграла комп'ютерну олімпіаду після додання UCT до її, заснованого на експертних знаннях, механізму.

2008 року MoGo виграла одну з трьох ігор[21] проти Каталіна Церану[ru], 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 грали чотири гри з різним гандикапом і часовими обмеженнями і виграли по дві гри. Звіти про ігри доступні на КГС[en][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 виграла у Масакі Такемії[ru] (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.

Змагання серед комп'ютерних програм гри в ґо ред.

Існують кілька відомих щорічних змагань серед комп'ютерних програм, що грають в ґо, найвідоміше з яких — Комп'ютерна олімпіада. Регулярні та менш формальні змагання проводяться на КГС [Архівовано 30 Грудня 2019 у Wayback Machine.] (щомісяця) і CKS (неперервно).

Серед найвідоміших програм, що грають в ґо, — північнокорейська Silver Star KCC Igo, Handtalk (автор Чень Чжісін), GoPlusPlus (Michael Reiss) і Many Faces of Go Девіда Фотланда (David Fotland). GNU Go — вільна програма, яка також вигравала комп'ютерні змагання.

Історія ред.

Перші змагання з комп'ютерного ґо спонсорувалися 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]

Проблеми гри комп'ютера з комп'ютером ред.

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

Див. також ред.

Примітка ред.

  1. ↑ 柯洁迎19岁生日 雄踞人类世界排名第一已两年 (кит.). May 2017. Архів оригіналу за 11 Серпня 2017. Процитовано 11 Серпня 2021.
  2. ↑ World's Go Player Ratings. 24 травня 2017. Архів оригіналу за 1 Квітня 2017. Процитовано 11 Серпня 2021.
  3. ↑ а б David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre. Mastering the game of Go with deep neural networks and tree search // Nature. — 2016. — Vol. 529, iss. 7587 (28 January). — P. 484–489. — ISSN 0028-0836. — DOI:10.1038/nature16961. Архівовано з джерела 24 Вересня 2019. Процитовано 11 Серпня 2021.
  4. ↑ а б Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol. BBC News Online. 12 березня 2016. Архів оригіналу за 11 Серпня 2021. Процитовано 12 березня 2016.
  5. ↑ Google's DeepMind defeats legendary Go player Lee Se-dol in historic victory. www.theverge.com. Архів оригіналу за 11 Серпня 2021. Процитовано 9 березня 2016.
  6. ↑ Artificial intelligence: Go master Lee Se-dol wins against AlphaGo program. BBC News Online. 13 березня 2016. Архів оригіналу за 5 Травня 2021. Процитовано 13 березня 2016.
  7. ↑ Google's AlphaGo AI beats Lee Se-dol again to win Go series 4-1. The Verge. Архів оригіналу за 15 Березня 2016. Процитовано 15 березня 2016.
  8. ↑ а б Программа AlphaGo со счетом 3-0 обыграла сильнейшего игрока в го. INTERFAX.RU. 27 травня 2017. Архів оригіналу за 11 Серпня 2021. Процитовано 27 травня 2017.
  9. ↑ Чемпион мира по игре в го проиграл три матча подряд компьютерной программе. интернет-издание «Лента.Ру». 27 травня 2017. Архів оригіналу за 11 Серпня 2021. Процитовано 27 травня 2017.
  10. ↑ Антон Бабошин (27 травня 2017). Восстание машин. Детище Google обыграло лидера мирового рейтинга. «Спорт-Экспресс». Архів оригіналу за 26 Лютого 2019. Процитовано 27 травня 2017.
  11. ↑ Go Ratings. Архів оригіналу за 15 Серпня 2021. Процитовано 11 Серпня 2021.
  12. ↑ Сравнение форматов доски Го. Архів оригіналу за 27 січня 2011. Процитовано 24 червня 2009.
  13. ↑ См. Computer Go Programming [Архівовано 15 Серпня 2006 у Wayback Machine.] pages at Sensei's Library
  14. ↑ Raiko, Tapani: «The Go-Playing Program Called Go81» [Архівовано 11 Жовтня 2010 у Wayback Machine.] section 1.2
  15. ↑ WinHonte 2.01. Архів оригіналу за 3 липня 2007. Процитовано 24 червня 2009.
  16. ↑ а б Müller, Martin. Computer Go[недоступне посилання з Октябрь 2017], Artificial Intelligence 134 (2002): p150
  17. ↑ Müller, Martin. Computer Go[недоступне посилання з Октябрь 2017], Artificial Intelligence 134 (2002): p151
  18. ↑ а б Müller, Martin. Computer Go[недоступне посилання з Октябрь 2017], Artificial Intelligence 134 (2002): p148
  19. ↑ Crazy Stone. Архів оригіналу за 29 Жовтня 2007. Процитовано 11 Серпня 2021.
  20. ↑ UCT. Архів оригіналу за 7 Липня 2021. Процитовано 11 Серпня 2021.
  21. ↑ Архивированная копия. Архів оригіналу за 28 травня 2009. Процитовано 24 червня 2009.
  22. ↑ Fédération Française de Go. Архів оригіналу за 13 Серпня 2021. Процитовано 11 Серпня 2021.
  23. ↑ Sensei's Library: MoGo. Архів оригіналу за 15 Травня 2021. Процитовано 11 Серпня 2021.
  24. ↑ KGS Game Archives. Архів оригіналу за 11 Серпня 2021. Процитовано 11 Серпня 2021.
  25. ↑ Машинный разум нанёс человеку удар в го. Архів оригіналу за 19 червня 2009. Процитовано 24 червня 2009.
  26. ↑ CrazyStone at Sensei's Library. Архів оригіналу за 16 Липня 2009. Процитовано 11 Серпня 2021.
  27. ↑ KGS Go Server Rank Graph. Архів оригіналу за 11 Серпня 2021. Процитовано 11 Серпня 2021.
  28. ↑ Sensei's Library KGS Bot Ratings. Архів оригіналу за 6 Травня 2021. Процитовано 11 Серпня 2021.
  29. ↑ Zen computer Go program beats Takemiya Masaki with just 4 stones!. Архів оригіналу за 20 січня 2013. Процитовано 4 січня 2013.
  30. ↑ World Computer Go Championships. Архів оригіналу за 24 Вересня 2015. Процитовано 11 Серпня 2021.
  31. ↑ Искусственный интеллект впервые победил профессионального игрока в го (рос.). Meduza. Архів оригіналу за 4 Лютого 2016. Процитовано 27 січня 2016.
  32. ↑ AlphaGo: Mastering the ancient game of Go with Machine Learning. Research Blog. Архів оригіналу за 1 Лютого 2016. Процитовано 27 січня 2016.

Наукові статті ред.

Сайти, присвячені комп'ютерному ґо ред.

Комп'ютерні програми ред.

  • AYA Хіросі Ямасіти (Hiroshi Yamashita)
  • Crazy Stone [Архівовано 29 Жовтня 2007 у Wayback Machine.] Ремі Кулома (Rémi Coulom)
  • GNU Go, найсильніша відкрита програма для ґо
  • Go++ [Архівовано 25 Травня 2003 у Wayback Machine.] Майкла Райсса (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 [Архівовано 5 Серпня 2004 у Wayback Machine.] Девіда Фотланда (David Fotland; в Японії продається як AI Igo)
  • MoGo Сильвейна Ґеллі (Sylvain Gelly); паралельна версія [2] команди розробників.
  • Smart Go [Архівовано 11 Червня 2003 у Wayback Machine.] Андерса Кірфула (Anders Kierulf), розробника Smart Game Format
Отримано з https://uk.wikipedia.org/w/index.php?title=Комп%27ютерне_ґо&oldid=40445191