Створюємо свого бота для гри в Го



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

Коротка історія комп'ютерного Го:1968 — перша програма, яка грає в Го, написана Альбертом Зобристом
1984 — перший чемпіонат серед го-програм
1990-ті — програми програють професіоналам при форе 25-30 каміння
2006 — програма CrazyStone виграє комп'ютерну олімпіаду використовуючи метод Монте-Карло
2008 — програма MoGo виграє на 9 каменях фори у професіонала 8-го дана на дошці 19 х 19 х
2010 — програма Zen отримує 3-й дан на сервері KGS, граючи з людьми
2013 — CrazyStone перемогла професіонала 9-го дана на 4-х каменях фори
2015 — AlphaGo виграє у європейського чемпіона 5 партій з 5, без фори
2016 — AlphaGo перемагає в серії матчів професіонала Чи Седоля, без фори

В основі штучного інтелекту більшості сучасних го-движків знаходиться метод Монте-Карло, а точніше його реалізація, алгоритм UCT. Я вже писав докладно про цей алгоритм тут. Але якщо коротко і без формул, то його роботу можна описати наступним чином:

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

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

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

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

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

Нерівномірність дерева в алгоритмі MCTS

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

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


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

Тут варто згадати про правило Ко. Нагадаю, що правило До це правило забороняє повторення на дошці позиції, яка була перед попереднім ходом.


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

Виглядає це приблизно так:
<i>black_stone = 1
 
white_stone = 2
 
...
 
table = zobrist_init(board_size)
 
...
 
h = h XOR table[i][j]</i>
 

Де h це поточне хеш-значення дошки, i — індекс позиції на дошці, а індекс j фігури (1 або 2).

Цей хеш можна використовувати ще й для відсікання повторюваних позицій в дереві Монте-Карло, щоб не витрачати час на оцінку позицій, які вже були відвідані.

Також, можна використовувати таке визначення правила До:
Не можна знімати з дошки один і тільки один камінь, якщо він був поставлений на попередньому ходу, при цьому він зняв з дошки тільки один камінь супротивника.

Тут замість перевірки стану дошки можна просто упевнитися у виконанні цієї умови.

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

Щоб зробити випадкові гри не випадковими, використовується безліч різних підходів. Насправді, саме тут починається етап творчості і задається характер гри майбутнього ІІ.

Багато програм для цієї мети використовують шаблони. Наприклад в MoGo і Fuego Go використовуються шаблони розміром 3x3, де в центрі розташовано розглянуте полі. У GNUGo шаблони набагато різноманітніше і складніше.
В якості прикладу, давайте розглянемо ось такий шаблон розміру 3x3:
["XO?", 
 
"O. o",
 
"?o?"]
 

Тут X і O це кольори, x і o це «не X» і «O» відповідно? — це будь-яке значення поля, а точка означає порожнє поле. Цей шаблон імітує розрізання каменів одного кольору або захист від розрізання для каменів іншого кольору. Тобто він буде хороший для обох гравців. В центрі знаходиться те саме пусте поле куди ми хочемо поставити камінь.
Насправді таких шаблонів не потрібно багато. Достатньо всього десятка, щоб гра стала нагадувати реальну партію. Шаблони можна знайти в публікаціях-описах програм типу Fuego і MoGo або у їх коді.

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

Спільно з шаблонами використовуються також і інші евристики. Тут можна не обмежувати політ фантазії і придумати щось своє. Ось приклад евристик, які використовує програма Pachi, KGS 2d:

  • Накадэ — поширена техніка вбивства групи. Хід робиться всередину групи для запобігання створення опонентом двох очей. Програма відстежує такі ситуації і ставить камінь в життєво важливу точку.

  • Якщо останнім ходом противник поставив свою групу в атарі (за один хід до смерті групи), ми захоплюємо її, якщо наша група опинилася в атарі, ми намагаємося втекти або захопити сусідню групу противника.

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

Кожна евристика у випадкових партіях застосовується, так само як і шаблони, не для всієї дошки, а тільки для її частини. Застосовуватися вони можуть як всі разом, так і по черзі. Другий варіант більш кращий для економії ресурсів.

Під час пошуку в дереві, для алгоритму Монте-Карло всі ходи рівні. В значеннях кожного нового сайту стоять нулі. Програма не розуміє, який з цих ходів хороший чи поганий, до тих пір, поки не зіграє кілька випадкових ігор. Для того, щоб на ранньому етапі відсікти розгляд явно непотрібних або поганих ходів, або дати пріоритет завідомо хорошим, під час пошуку теж застосовуються евристичні функції.
Тут можуть використовуватися ті ж функції, що і під час випадкових ігор, але тільки застосовуються вже до всієї дошці. Можуть використовуватися й додаткові евристики, не включені до випадкові партії.
Наприклад, якщо розглянутий хід розташований на 1-й або 2-ї лінії дошки, а навколо немає ні одного каменю, то цього ходу потрібно присвоїти негативний пріоритет. Якщо ж ми хочемо поставити камінь на 3-ю лінію при тих же умовах, то такому ходу хотілося б привласнити позитивний пріоритет. Цей хід має розглядатися алгоритмом більш докладно.

Для заохочення ходу потрібно додати значення пріоритету до ігор і до числа виграшів:
good_node.games = GOOD_MOVE_PRIOR;
 
good_node.wins = GOOD_MOVE_PRIOR;
 

Для зворотного ефекту, значення додається тільки до ігор:
bad_node.games = BAD_MOVE_PRIOR;
 
bad_node.wins = 0;
 

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

Перевірка наявності каменів в околицях точки C7. Використовується метрика відстані міських кварталів.

І так, припустимо, движок готовий і ви хочете протестувати його. Якщо ви хочете підключити до нього графічний інтерфейс або дати можливість грати з ним онлайн, необхідно використовувати Go Text Protocol (GTP), загальновизнаний стандарт для го-програм. З допомогою нього ви зможете підключити свій створення графічного інтерфейсу або запустити його на сервері KGS.
Протокол досить простий в реалізації, потрібно буде навчити бота розуміти кілька команд:

  • list_commands — запитує у бота список підтримуваних команд, результатом повинен бути список з символом кінця рядка після кожної команди.
  • boardsize n — говорить нашій програмі, що гра буде вестися на дошці розміром n
  • komi 6.5 — команда говорить, про те, що використовується в комі 6.5 очок
  • clear_board — створюємо нову, порожню дошку розміром n
  • genmove w — прохання до движка згенерувати хід за білих (за чорних буде b)
  • play b A1 — означає що, гравець поставив чорний камінь в пункт A1


Відповідь бота на кожну команду повинен починатися символу "=". Цей знак так само означає, що ваша програма зрозуміла команду і чекає на наступну. Якщо команда невідома, виводиться знак питання.
Як приклад, наведу обмін повідомленнями в реальній грі:

<i>list_commands
 
= boardsize
 
list_commands
 
name
 
play
 
clear_board
 
komi
 
quit
 
genmove
 

 
boardsize 9
 
=
 
komi 6.5
 
=
 
clear_board
 
=
 
play b E5
 
=
 
genmove w
 
= d4</i>
 


У цьому прикладі гра йде на дошці 9x9, чоловік грає за чорних в пункт E5, програма відповідає в пункт d4. Зверніть увагу, що координати пунктів на дошці мають символьну і буквену частину. Це так зване іменування клітиншахової нотації.

Тепер можна використовувати движок в графічних програмах, що підтримують протокол GTP, наприклад Drago.

Якщо ж ви хочете запустити вашого бота на сервері KGS, потрібно буде використовувати програму посередник kgsGTP.

Для запуску наберіть команду:
java -jar kgsGtp.jar kgsgtp.ini
Тут kgsgtp.ini, це файл налаштувань. Приклад файлу:

name=логин_бота
password=пароль_бота
room=Computer Go// ім'я кімнати, куди заходить бот
mode=custom // режим роботи, детальніше в мануалі kgsGtp
ігриNotes=«Hello i'm knew here» // Рядок привітання
rules.boardSize=9// розмір дошки на якій грає бот
undo=f //підтримка команди «взяти хід назад»
engine=шлях/до/програмі
opponent=логин_оппонента

Якщо вказана опція opponent, програма зможе грати тільки із зазначеним у ній людиною. Це зручно для налагодження бота.

Звичайно ж, це далеко не все, що використовується у ІІ для гри в Го. За межами статті залишились такі цікаві речі, як All Moves-As-First і RAVE, Common Fate Graph, згорткові нейронні мережі і т. д. Але для початку цього матеріалу буде цілком достатньо. У списку джерел ви знайдете багато додаткової інформації.

Список джерелsenseis.xmp.net/?ComputerGo
hal.inria.fr/inria-00117266v3/document
users.soe.ucsc.edu/~glin/docs/Fuego_Fall09Report.pdf
pasky.or.cz/go/pachi-tr.pdf
pdfs.semanticscholar.org/87b8/9babfa66c3bc33ad579e59e65321fb4b6d48.pdf
github.com/pasky/michi
www.cs.cmu.edu/afs/cs/user/mjs/ftp/thesis-program/2008/abstracts/lowEA.pdf
arxiv.org/pdf/1412.6564v2.pdf

Мій бот:Логін на KGS letitgo16
github.com/galvanom/letitGO

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.