Введение

Изучение игры Го в области искусственного интеллекта. Область искусственного интеллекта, связанная с компьютерными программами для игры Го.

Компьютерное Го – это область искусственного интеллекта (ИИ), посвященная созданию компьютерной программы, играющей в традиционную настольную игру Го. Эта область чётко разделена на две эпохи. До 2015 года программы этой эпохи были слабыми. Лучшие разработки 1980-х и 1990-х годов привели к созданию ИИ, которые могли быть побеждены начинающими игроками, а ИИ начала 2000-х годов достигали, в лучшем случае, среднего уровня. Профессиональные игроки могли побеждать эти программы даже при гандикапе в 10+ камней в пользу ИИ. Многие алгоритмы, такие как альфа-бета отсечение, успешно применявшиеся в ИИ для шашек и шахмат, оказались неэффективными на доске Го 19x19 из-за огромного количества возможных вариантов развития событий. Создание программы профессионального уровня, используя технологии и оборудование того времени, было невозможным. Некоторые исследователи в области ИИ предполагали, что проблема неразрешима без создания ИИ, подобного человеческому. Применение метода поиска по деревьям Монте-Карло к алгоритмам Го привело к заметному улучшению в конце 2000-х годов, и программы наконец смогли достичь уровня низкого дана – продвинутого любителя. Игроки высокого дана и профессионалы всё ещё могли использовать слабости этих программ и выигрывать стабильно, но производительность компьютеров вышла за пределы среднего (однозначного кю) уровня. Заманчивая, но долгое время считавшаяся недостижимой цель – победить лучших игроков без гандикапа – вызвала всплеск нового интереса. Ключевым прорывом оказалось применение машинного обучения и глубокого обучения. DeepMind, приобретённая Google компания, специализирующаяся на исследованиях в области ИИ, разработала AlphaGo в 2015 году и представила её миру в 2016 году. AlphaGo победила Ли Седола, профессионала 9 дана, в матче без гандикапа в 2016 году, а затем победила Ке Цзе в 2017 году, который в то время два года подряд непрерывно занимал первое место в мировом рейтинге. Подобно тому, как шашки покорились машинам в 1995 году, а шахматы – в 1997 году, компьютерные программы, наконец, одержали победу над величайшими чемпионами мира по Го в 2016–2017 годах. DeepMind не предоставила AlphaGo для общего пользования, но с тех пор было создано множество программ, основанных на научных статьях, опубликованных DeepMind, описывающих AlphaGo и её варианты.

Обзор и история

Профессиональные игроки в го рассматривают эту игру как требующую интуиции, творческого и стратегического мышления. Долгое время она считалась сложной задачей в области искусственного интеллекта (ИИ) и значительно превосходит шахматы по сложности решения. Многие специалисты полагали, что для игры в го требуется больше элементов, имитирующих человеческое мышление, чем для шахмат. Математик И. Дж. Гуд писал в 1965 году:

До 2015 года лучшие программы для игры в го достигали лишь уровня любительского дана. На небольшой доске 9×9 компьютер показывал лучшие результаты, и некоторым программам удавалось выигрывать небольшую часть партий 9×9 у профессиональных игроков. До появления AlphaGo некоторые исследователи утверждали, что компьютеры никогда не смогут победить лучших игроков в го.

Ранние десятилетия

Первая программа для игры в го была написана Альбертом Линдси Зобристом в 1968 году в рамках его диссертации по распознаванию образов. Она представила функцию влияния для оценки территории и хеширование Зобриста для обнаружения ко. В апреле 1981 года Джонатан К. Миллен опубликовал статью в журнале Byte, посвященную Wally – программе для игры в го с доской 15x15, которая помещалась в 1КБ оперативной памяти микрокомпьютера KIM 1. В ноябре 1984 года Брюс Ф. Уэбстер опубликовал в журнале статью о программе для игры в го, написанной им для Apple Macintosh, включая исходный код на MacFORTH. Программы для игры в го были слабыми; в статье 1983 года оценивалось, что они в лучшем случае соответствуют уровню 20 кю, что соответствует уровню наивного начинающего игрока, и часто ограничивались меньшими размерами доски. ИИ, игравшие на сервере Internet Go (IGS) на досках 19x19, к 2003 году, после значительных улучшений в аппаратном обеспечении, имели силу около 20–15 кю. В 1998 году очень сильные игроки могли побеждать компьютерные программы, предоставляя им гандикап в 25–30 камней – огромный гандикап, на который мало кто из игроков-людей согласился бы. В 1994 году на Чемпионате мира по компьютерному го произошел случай, когда победившая программа Go Intellect проиграла все три игры молодым игрокам, получив гандикап в 15 камней. В целом, игроки, понимавшие и использующие слабые стороны программы, могли побеждать даже при большом гандикапе.

20072014: поиск дерева в Монте-Карло

В 2006 году (в статье, опубликованной в 2007 году) Реми Кулом разработал новый алгоритм, который он назвал поиском по деревьям Монте-Карло. В этом алгоритме, как и обычно, строится дерево игры, представляющее возможные будущие ходы, ветвящиеся с каждым шагом. Однако компьютеры "оценивают" конечные листья дерева, проводя многократные случайные розыгрыши (аналогично стратегиям Монте-Карло для других задач). Преимущество заключается в том, что такие случайные розыгрыши можно выполнять очень быстро. Интуитивное возражение, что случайные розыгрыши не отражают реальную ценность позиции, оказалось не столь критичным для алгоритма, как ожидалось; компонент "поиска по деревьям" достаточно хорошо корректировал процесс, позволяя находить разумные игровые деревья для исследования. Программы, основанные на этом методе, такие как MoGo и Fuego, продемонстрировали более высокую производительность, чем классические ИИ предыдущих поколений. Лучшие программы особенно хорошо проявляли себя на маленькой доске 9x9, где было меньше вариантов для исследования. В 2009 году появились первые программы, способные достигать и удерживать ранги низкого дана на KGS Go Server на доске 19x19. В 2010 году на Европейском конгрессе по го в Финляндии MogoTW сыграла партию в го 19x19 против Каталина Тарану (5p). MogoTW получила гандикап в семь камней и выиграла. В 2011 году Zen достиг 5 дана на сервере KGS, играя партии по 15 секунд на ход. Аккаунт, достигший этого ранга, использовал кластерную версию Zen, работающую на 26-ядерном компьютере. В 2012 году Zen обыграл Такемию Масаки (9p) с преимуществом в 11 очков при гандикапе в пять камней, а затем выиграл с преимуществом в 20 очков при гандикапе в четыре камня. В 2013 году Crazy Stone победил Йосио Исиду (9p) в партии 19x19 с гандикапом в четыре камня. В 2014 году Codecentric Go Challenge, состоящий из пяти матчей на доске 19x19, был сыгран между Crazy Stone и Францем Йозефом Дикхутом (6d). До этого ни один более сильный игрок не соглашался на серьезное соревнование с программой для игры в го на равных. Франц Йозеф Дикхут победил, хотя Crazy Stone выиграла первый матч с перевесом в 1,5 очка.

2015 год и далее: эра глубокого обучения

AlphaGo, разработанный Google DeepMind, стал значительным прорывом в вычислительной силе по сравнению с предыдущими программами для игры в Го. Он использовал методы, сочетающие глубокое обучение и поиск по дереву Монте-Карло. В октябре 2015 года AlphaGo одержал пять побед над Фан Хуэй, чемпионом Европы по Го, в турнирных условиях. В марте 2016 года AlphaGo выиграл у Ли Седола в первых трех из пяти матчей. Это был первый случай, когда мастер 9 дан сыграл профессиональную партию против компьютера без гандикапа. Ли выиграл четвертый матч, назвав свою победу «бесценной». AlphaGo выиграл финальный матч два дня спустя. С этой победой AlphaGo стала первой программой, победившей профессионального игрока 9 дан в игре без гандикапа на полноразмерной доске. В мае 2017 года AlphaGo победил Ке Цзе, который на тот момент занимал первое место в мировом рейтинге, в матче из трех партий на саммите Future of Go. В октябре 2017 года DeepMind представил новую версию AlphaGo, обученную исключительно методом самообучения, которая превзошла все предыдущие версии, выиграв у версии, игравшей против Ке Цзе, в 89 из 100 партий. После публикации основных принципов AlphaGo в журнале Nature другие команды смогли создать программы высокого уровня. Последующие работы в области ИИ для Го в основном сводились к эмуляции техник, использованных при создании AlphaGo, который оказался значительно сильнее всех остальных. К 2017 году проекты Zen и Fine Art от Tencent были способны время от времени побеждать профессионалов очень высокого уровня. Также был создан движок Leela Zero с открытым исходным кодом.

Представительство государства

Проблема, с которой сталкиваются все программы для игры Го, – это представление текущего состояния игры. Самый простой способ представить доску – это использовать одномерный или двумерный массив, где элементы массива соответствуют точкам на доске и могут иметь значение, обозначающее белый камень, черный камень или пустое пересечение. Кроме того, необходимы данные для хранения количества захваченных камней, хода игрока и запрещенных пересечений из-за правила ко. Как правило, программы машинного обучения ограничиваются этой простой формой и позволяют алгоритмам, основанным на принципах человеческого мышления, самостоятельно интерпретировать значение доски, вероятно, используя игровые разыгрывания Монте-Карло для оценки доски как выгодной или невыгодной для игрока. "Классические" программы ИИ, которые пытались напрямую моделировать стратегию человека, могли использовать более сложные представления, добавляя информацию о камнях, считающихся мертвыми, безусловно живых камнях, камнях в состоянии секи и т.д. для описания состояния игры.

Поиск по минимальному дереву

Одним из традиционных методов ИИ для создания игрового программного обеспечения является поиск по дереву минимакса. Он включает в себя просчитывание всех гипотетических ходов на доске до определенной точки, а затем использование оценочной функции для оценки ценности этой позиции для текущего игрока. Выбирается ход, который ведет к наилучшей гипотетической позиции, и процесс повторяется с каждым ходом. Хотя поиск по деревьям оказался очень эффективным в компьютерных шахматах, в программах для игры в Го он достиг меньших успехов. Это отчасти связано с тем, что традиционно сложно создать эффективную оценочную функцию для доски Го, а отчасти с тем, что большое количество возможных ходов для каждой стороны приводит к высокому коэффициенту ветвления. Это делает данный метод очень ресурсоемким с точки зрения вычислений. Из-за этого многие программы, активно использующие деревья поиска, могут играть только на меньшей доске 9×9, а не на полной доске 19×19. Существует несколько методов, которые могут значительно повысить производительность деревьев поиска как по скорости, так и по объему используемой памяти. Методы отсечения, такие как альфа-бета отсечение, Principal Variation Search и MTD(f), могут уменьшить эффективный коэффициент ветвления без потери эффективности. В тактических ситуациях, таких как борьба за жизнь и смерть, Го особенно хорошо поддается методам кэширования, таким как таблицы транспозиций. Они могут уменьшить объем повторяющихся вычислений, особенно в сочетании с методом итеративного углубления. Для быстрого хранения полноразмерной доски Го в таблице транспозиций обычно требуется метод хеширования для математического суммирования. Хеширование Зобриста очень популярно в программах для Го, поскольку оно имеет низкую вероятность коллизий и может итеративно обновляться с каждым ходом всего двумя операциями XOR, а не вычисляться заново. Даже при использовании этих методов повышения производительности полный поиск по дереву на полноразмерной доске все еще остается неприемлемо медленным. Скорость поиска можно увеличить, используя большое количество специализированных методов отсечения, например, не рассматривая ходы, при которых противник уже силен, и выборочное расширение поиска, например, всегда рассматривая ходы рядом с группами камней, которые вот-вот будут захвачены. Однако оба этих варианта несут в себе значительный риск упустить важный ход, который мог бы изменить ход игры. Результаты компьютерных соревнований показывают, что методов сопоставления с образцом для выбора нескольких подходящих ходов в сочетании с быстрыми локализованными тактическими поисками (описанными выше) когда-то было достаточно для создания конкурентоспособной программы. Например, GNU Go была конкурентоспособной до 2008 года.

Системы, основанные на знаниях

Люди-новички часто учатся, изучая записи партий старых игр, сыгранных мастерами. Работа над ИИ в 1990-х годах часто заключалась в попытках "обучить" ИИ человеческим эвристикам и знаниям о Го. В 1996 году Тим Клингер и Дэвид Мехнер признали силу лучших ИИ на уровне начинающих и утверждали, что "мы полагаем, что с помощью более совершенных инструментов для представления и хранения знаний о Го станет возможным разработать более сильные программы Го". Они предложили два подхода: распознавание распространенных конфигураций камней и их позиций, а также концентрацию на локальных сражениях. В 2001 году в одной статье было заключено, что "программам Го по-прежнему не хватает знаний как по качеству, так и по количеству", и что исправление этого улучшит производительность ИИ для Го. Среди программ: The Many Faces of Go v12, Leela, MoGo, Crazy Stone, MyGoFriend и Zen. В 2006 году была разработана новая техника поиска – верхние доверительные границы, применяемые к деревьям (UCT), и успешно применена ко многим программам Monte Carlo Go для доски 9x9. UCT использует результаты проведенных симуляций для направления поиска по наиболее перспективным вариантам игры, при этом не исключая возможность исследования альтернативных линий. Техника UCT, наряду с множеством других оптимизаций для игры на доске 19x19, позволила MoGo стать одной из сильнейших исследовательских программ. К успешным ранним применениям методов UCT для Го на доске 19x19 относятся MoGo, Crazy Stone и Mango. MoGo выиграла компьютерную олимпиаду 2007 года и выиграла одну (из трех) блиц-партию у Гуо Хуана, профессионального игрока 5 дана, в гораздо менее сложной игре Го на доске 9x9. The Many Faces of Go выиграла компьютерную олимпиаду 2008 года после добавления поиска UCT к своему традиционному движку, основанному на знаниях. Программы Го, основанные на методе Монте-Карло, имеют репутацию более склонных к ходам тенуки – перемещениям в другие области доски, чем продолжение локального боя, в отличие от человеческих игроков. Это часто воспринималось как слабость на ранних этапах развития этих программ. Однако эта тенденция сохранилась в стиле игры AlphaGo и привела к доминирующим результатам, поэтому, возможно, это скорее "особенность", чем "слабость".

Машинное обучение

Уровень мастерства систем, основанных на знаниях, тесно связан со знаниями их программистов и соответствующих экспертов в предметной области. Это ограничение затруднило создание действительно сильных ИИ. Альтернативный подход – использование методов машинного обучения. В этом случае программистам необходимо запрограммировать лишь правила и простые алгоритмы оценки полезности позиции. Затем программное обеспечение, теоретически, автоматически формирует собственное понимание закономерностей, эвристик и стратегий. Обычно это достигается путем предоставления нейронной сети или генетическому алгоритму возможности анализировать большую базу данных профессиональных игр или играть множество партий против себя, других людей или программ. Эти алгоритмы затем используют эти данные для повышения своей эффективности. Методы машинного обучения также могут применяться в менее масштабных задачах для тонкой настройки конкретных параметров программ, которые в основном полагаются на другие методы. Например, Crazy Stone изучает шаблоны генерации ходов на основе нескольких сотен образцов игр, используя обобщение системы рейтинга Эло. Наиболее известным примером этого подхода является AlphaGo, который оказался значительно эффективнее предыдущих ИИ. В своей первой версии он содержал один слой, анализирующий миллионы существующих позиций для определения перспективных ходов, заслуживающих дальнейшего анализа, и другой слой, пытающийся оптимизировать собственные шансы на победу, используя перспективные ходы, предложенные первым слоем. AlphaGo использовал поиск по дереву Монте-Карло для оценки полученных позиций. Более поздняя версия AlphaGo, AlphaGoZero, отказалась от обучения на существующих партиях в го и вместо этого училась, играя исключительно против себя. К другим ранним программам, использующим нейронные сети, относятся NeuroGo и WinHonte.

Компьютер Go и другие поля

Результаты исследований в области компьютерного го применяются в других схожих областях, таких как когнитивная наука, распознавание образов и машинное обучение. Комбинаторная теория игр, являющаяся разделом прикладной математики, имеет отношение к компьютерному го. Джон Х. Конвей предложил использовать сюрреальные числа для анализа эндшпиля в го. Эта идея была далее развита Элвином Р. Берлекампом и Дэвидом Вулфом в их книге «Математическое го». Эндшпили в го оказались PSPACE-полными, если требуется вычислить абсолютно лучший ход на произвольной, преимущественно заполненной доске. Определенные сложные ситуации, такие как Triple Ko, Quadruple Ko, Molasses Ko и Moonshine Life, усложняют эту задачу. (На практике, мощные алгоритмы Монте-Карло все еще достаточно хорошо справляются с обычными эндшпильными ситуациями в го, и наиболее сложные классы задач о жизни и смерти в эндшпиле вряд ли встретятся в игре высокого уровня.) Различные сложные комбинаторные задачи (любая NP-трудная задача) могут быть сведены к задачам, подобным го, на достаточно большой доске; однако то же самое верно и для других абстрактных настольных игр, включая шахматы и сапёр, при соответствующей обобщенности до доски произвольного размера. NP-полные задачи, как правило, не легче для человека без посторонней помощи, чем для специально запрограммированного компьютера: человек без посторонней помощи значительно хуже справляется с решением, например, экземпляров задачи о сумме подмножеств.

Соревнования между компьютерными программами Go

Несколько ежегодных соревнований проводятся между компьютерными программами для игры в го, включая турниры по го на Компьютерной олимпиаде. Ранее регулярные, менее формальные соревнования между программами проходили на KGS Go Server (ежемесячно) и Computer Go Server (в режиме реального времени). Существует множество программ, позволяющих компьютерным движкам го играть друг с другом; они почти всегда взаимодействуют посредством протокола Go Text Protocol (GTP).

История

Первое компьютерное соревнование по го было спонсировано Acornsoft, а первые регулярные – USENIX. Они проводились с 1984 по 1988 год. Эти соревнования представили Nemesis, первую конкурентоспособную программу для игры в го, разработанную Брюсом Уилкоксом, и G2.5 Дэвида Фотланда, которая впоследствии развилась в Cosmos и The Many Faces of Go. Одним из первых стимулов для исследований в области компьютерного го стал приз Инга – значительная денежная награда, спонсируемая тайваньским банкиром Ингом Чанки, которая ежегодно вручалась с 1985 по 2000 год на Всемирном конгрессе компьютерного го (или Кубке Инга). Победитель этого турнира получал право сыграть короткий матч с молодыми игроками с предоставлением гандикапа. Если компьютер выигрывал матч, приз присуждался, и объявлялся новый приз – более крупный за победу над игроками с меньшим гандикапом. Серия призов Инга должна была завершиться либо 1) в 2000 году, либо 2) когда программа сможет победить профессионального игрока 1 дан без гандикапа за 40 000 000 NT долларов. Последним победителем стала программа Handtalk в 1997 году, получившая 250 000 NT долларов за победу в матче с гандикапом в 11 камней против трех любителей в возрасте 11–13 лет, имеющих рейтинг 2–6 дан. К моменту истечения срока действия приза в 2000 году, невостребованная сумма составляла 400 000 NT долларов за победу в матче с гандикапом в девять камней. Многие другие крупные региональные турниры по го ("конгрессы") включали в себя соревнования компьютерных программ. Европейский конгресс по го спонсирует компьютерный турнир с 1987 года, а мероприятие USENIX превратилось в чемпионат США/Северной Америки по компьютерному го, который ежегодно проводился с 1988 по 2000 год на конгрессе США по го. Япония начала спонсировать компьютерные соревнования по го в 1995 году. Кубок FOST проводился ежегодно с 1995 по 1999 год в Токио. Этот турнир был заменен Gifu Challenge, который проводился ежегодно с 2003 по 2006 год в Огаки, префектура Гифу. Кубок Computer Go UEC проводится ежегодно с 2007 года.

Формализация оценки в компьютерных компьютерных играх

Когда два компьютера играют в Го друг против друга, идеальным считается отношение к игре так же, как к игре двух людей, избегая при этом вмешательства реальных игроков. Однако это может быть сложно на этапе подсчёта очков в окончании партии. Основная проблема заключается в том, что программное обеспечение для игры в Го, которое обычно общается с использованием стандартизированного протокола Go Text Protocol (GTP), не всегда приходит к согласию относительно живого или мёртвого статуса камней. Хотя не существует универсального способа для двух разных программ "обсудить" ситуацию и разрешить конфликт, этой проблемы в основном удаётся избежать, используя китайские, правила Тромпа-Тейлора или Американской ассоциации Го (AGA), которые требуют продолжения игры (без штрафных санкций) до тех пор, пока не исчезнут разногласия относительно статуса каких-либо камней на доске. На практике, например, на KGS Go Server, сервер может выступать посредником в споре, отправляя специальную команду GTP двум клиентским программам с указанием продолжать размещать камни, пока не останется сомнений в статусе какой-либо конкретной группы (все мёртвые камни будут захвачены). CGOS Go Server обычно наблюдает, как программы сдаются до того, как игра достигнет фазы подсчёта очков, но тем не менее поддерживает модифицированную версию правил Тромпа-Тейлора, требующую полной разыгрывания партии. Эти правила означают, что программа, находившаяся в выигрышной позиции в конце игры по японским правилам (когда оба игрока сделали проход), теоретически может проиграть из-за неудачной игры на этапе разрешения, однако это крайне маловероятно и считается нормальной частью игры при использовании любых правил подсчёта территории. Главный недостаток описанной системы заключается в том, что некоторые правила (например, традиционные японские правила) наказывают игроков за совершение этих дополнительных ходов, что исключает возможность дополнительного разыгрывания партии для двух компьютеров. Тем не менее, большинство современных программ для игры в Го поддерживают японские правила при игре с людьми. Исторически, другим способом решения этой проблемы было привлечение эксперта-человека для оценки финальной позиции. Однако это вносит субъективность в результаты и риск того, что эксперт упустит что-то, что заметила программа.