Компьютерное Го

,

в

Компьютерное Го — направление искусственного интеллекта по созданию компьютерных программ, играющих в Го.

Препятствия на пути программ

В течение долгого времени считалось, что компьютерное Го имеет существенные различия по сравнению с компьютерными шахматами, поскольку методы, основанные на быстром поиске по сравнению с человеческим опытом, объединённые с относительно низким знанием предметной области не будут эффективны для Го. Поэтому большие усилия в области компьютерного Го были потрачены на объединение экспертных знаний с локальным поиском для нахождения ответа на вопросы тактической природы игры. Результатом этих усилий были программы, способные находить хорошие решения в некоторых локальных ситуациях, но имевшие явные слабости в полной обработке игры. Кроме того, эти классические программы с увеличением мощности аппаратуры мало получали в плане силы игры и поэтому развитие этой области было в целом медленным. Поэтому считалось, что программа, хорошо играющая в Го, может быть создана только в далёком будущем и только с помощью накопленных к тому времени общих знаний в области искусственного интеллекта. Даже написание программы, способной определить победителя в законченной игре воспринималось как нетривиальная задача.

В 2006 году появились программы, основанные на поиске Монте-Карло. Сила игры искусственного интеллекта улучшилась. Но еще остается довольно значительный разрыв с уровнем игры профессиональных игроков в Го.

  • Слишком большая доска

Большая доска (19×19, 361 игровой пункт) часто отмечается как основное препятствие на пути создания сильных го-программ. Проблема большой доски в том, что она препятствует глубокому поиску методом альфа-бета отсечения.

Пока самой большой доской, на которой к настоящему времени был осуществлён полный перебор позиций является доска 6×7.

  • Большое количество допустимых ходов

Продолжая сравнение с шахматами, следует отметить, что ходы в Го почти не ограничены правилами. В то время как первый ход в шахматах может быть осуществлён двадцатью способами, первый ход в Го имеет 55 вариантов, с учётом симметрии доски. Постепенно симметрия игровой ситуации перестаёт иметь место и количество ходов возрастает, достигая количества свободных клеток на доске.

  • Отсутствие «точной» дебютной теории

Начальная стадия партии в Го — фусэки — подчиняется определенным законам развития камней. Но для неё характерно гораздо большее разнообразие ходов, чем в шахматах. Новинки могут встречаться не на 20 ходу, а уже на третьем или четвёртом, и грамотная игра в дебюте невозможна без осмысления стратегических перспектив конструкций, возникающих на доске.

  • Ко-борьба

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

  • Аддитивная природа игры Го

В шахматах, как и во многих других играх, в течение партии фигур на доске становится меньше, что упрощает перебор ходов. В Го каждый следующий ход, наоборот, добавляет на доску один камень (хотя возможны и снятия), создавая дополнительные игровые моменты.

  • Шахматная техника не может быть применена в Го

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

Шахматные правила легко формализуемы и могут быть представлены машине в удобной форме, которая позволит ей играть на высоком уровне.

Но простые позиционные правила, применяемые в шахматах, не будут эффективны в Го. Для определения ценности камня необходим сложный анализ, хотя бы для определения того, жива ли группа, которой он принадлежит, как велико влияние группы и какие опасности ей грозят.

  • Функция оценки

Ещё одна проблема состоит в создании хорошей оценочной функции для Го. На каждом ходе может существовать несколько хороших ходов и чтобы выбрать лучший ход, компьютер должен оценить различные возможные исходы. Это становится трудной задачей в Го. Например, может представиться возможность захвата камней противника засчёт укрепления его группы в другом месте. Решение о том, является ли такой обмен выгодным, может показаться слишком тяжёлым даже для игрока-человека. Также может оказаться, что ход в другой части доски и построение там формы может оказаться более важным.

  • Завершение игры

Учитывая, что завершающая стадия игры Го (ёсэ) содержит меньшее количество возможных ходов, чем начало или середина, можно было бы предположить, что компьютеру будет намного легче играть эту часть игры. Но и здесь нашлось место для проблем:

Окончание партии в Го — самая «математическая» часть партии; в ней почти каждому ходу можно дать оценку с точки зрения количества приносимых ходом очков. Тем не менее, и эта стадия оказывается компьютеру не по зубам — во многом из-за ко-борьбы, неожиданно возникающей в вариантах тактики, а также вследствие трудностей, связанных с численной оценкой понятия инициативы. В отличие от шахмат, в Го к концу игры доска не освобождается от фигур, а тесно заполняется камнями — что делает невозможным создание глобальных баз данных для окончаний.

Ёсэ может повлечь за собой рассмотрение таких аспектов Го, как «жизнь и смерть», которые являются NP-полными.

Каждая область, рассматриваемая в ёсэ, может затрагивать другие области, или повлечь к изменениям в общей картине игры. Это приводит к таким непростым даже для человека ситуациям, как Тройное ко, учетверённое ко и им подобные.

Таким образом очень сложно запрограммировать эффективный алгоритм для игры завершающей стадии Го, не говоря обо всей партии.

Почему люди лучше играют в Го

Люди чувствуют, что играют в Го лучше, чем компьютеры, потому что сравнивают их с людьми. Однако, возможно это не компьютеры играют плохо, а люди играют очень хорошо. Го, по сравнению с другими играми с полной информацией, имеет особенности, которые делают её особенно лёгкой для людей. Камни не перемещаются, как фигуры в шахматах, не меняют цвет, как в реверси. Эти особенности позволяют людям просчитывать длинные цепочки ходов, что очень сложно для машины.

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

Тактический поиск

Один очень важный раздел игры Го, связанный с определением того, какие группы камней способны выжить, а какие могут быть захвачены, известен как «жизнь и смерть». Самая прямая стратегия для определения жизни и смерти — это построение дерева поиска ходов, которые затрагивают рассматриваемую группу и определение статуса группы в концевых вершинах этого дерева.

Однако в пределах временных ограничений и ограничений по доступной оперативной памяти невозможно определить с полной точностью, какие ходы затрагивают выбранную группу. Нередки, например, ситуации, когда жизнь одной группы может быть обеспечена только за счёт пленения другой. Это значит, что для решения поставленной задачи должны быть применены некоторые эвристики для определения ходов, требующих рассмотрения. Как результат у программ, играющих в Го прослеживается зависимость между временными затратами на обдумывание и качеством определения жизнеспособности групп.

Новые подходы к проблемам

Исторически основным подходом к проблеме компьютерного Го был «старый добрый ИИ». Позже в качестве альтернативы такому подходу стали рассматривать нейронные сети. Одной из программ, использующих алгоритм нейронных сетей для игры в Го является WinHonte.

Результаты этих разработок в области компьютерного Го используются в других областях: когнитивистика, распознавание образов и машинное обучение. Теория игр (раздел прикладной математики) тоже применяется к компьютерному Го.

Дизайн системы искусственного интеллекта

Единственное, что должна сделать программа в результате обдумывания хода — указать место, в которое следует поместить следующий камень. Однако даже такое простое решение трудно принять из-за неоднозначности позиций, к которым может привести эта постановка. Для решения этой проблемы были приспособлены различные архитектуры. Самые популярные основаны на использовании дерева поиска, применении методов Монте-Карло, создании экспертных систем и использовании машинного обучения. Немногие программы используют только что-то одно из перечисленного; большинство объединяют в себе несколько подходов.

Минимаксное дерево поиска

Одна из традиционных техник в области ИИ для создания программ, играющих в игры использует минимаксное дерево поиска. Для этого рассматривают все гипотетически возможные последовательности ходов до определённой глубины, а затем используют оценочную функцию, чтобы оценить ценность хода, с которого начиналась каждая последовательность. Ход, который приводит к наилучшему результату повторяется на доске и далее такая же процедура проводится для каждого хода компьютерного игрока. В то время, как способы, основанные на использовании дерева поиска давали хорошие результаты применительно к шахматам, они были менее успешны в применении к Го.

Частично причина этого кроется в том, что тяжело создать эффективную оценочную функцию и частично из-за большого количества возможных ходов, которое приводит к большому коэффициенту ветвления. Это делает технику дерева поиска слишком ресуркоёмкой. Поэтому программы, интенсивно использующие деревья поиска могут хорошо играть только на маленькой доске 9×9, но не на большой 19×19.

Существуют методы, способные улучшить работу деревьев поиска как в отношении скорости, так и памяти. Методы альфа-бета отсечения, Поиском Основных Отклонений, MDT-f могут уменьшить коэффициент ветвления практически без потери силы игры. Аналогично таблица перестановок позволяет уменьшить количество повторных вычислений, особенно когда она используется совместно с методом итеративного углубления. Для быстрого доступа к данным, расположенным в таблице перестановок необходимо использовать хеширование. Хэширование Зобриста часто встречается в программах, играющих в Го, так как обеспечивает малое количество коллизий и позволяет оперативно обновлять информацию о каждом ходе с использованием лишь двух операций XOR, вместо полного вычисления.

Даже с использованием этих, уменьшающих трудоёмкость, методов дерево поиска на полной доске всё ещё является очень медленным. Поиск может быть ускорен, если ветвление ещё больше ограничить, не рассматривая варианты ходов в область влияния противника, или выбирать для рассмотрения в первую очередь группы камней, находящиеся в положении атари. Однако оба эти метода приводят к риску нерассмотрения жизненно важных ходов, которые могли бы изменить курс игры.

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

Экспертные системы

Новички часто учатся, просматривая записи старых партий мастеров игры. Есть сильная гипотеза, что накопление знаний — ключ к созданию сильного ИИ. Например, Тим Киндер (Tim Kinger) и Дэвид мичнер (David Mechner) говорят: «Мы верим, что только используя инструменты накопления и поддержания знаний в области Го можно создать намного более сильные программы, чем есть сейчас.» Они предлагают два пути: рассмотрение общих форм и их использования, или рассмотрение местных противостояний.

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

Большинство относительно успешных результатов получены на основе навыков игры в Го программистов, которыми написаны программы и их личными догадками по поводу игры мастеров, а не на основе формальных математических просчётов; они пытаются заставить компьютер подражать тем способам, которыми они сами играют в Го. «Большинство конкурентоспособных программ потребовало 5-15 лет человеческих усилий и содержит 50-100 модулей, имеющих дело с различными аспектами игры»

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

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

Методы Монте-Карло

Одной из главных альтернатив использованию закодированных знаний и поиску ходов является метод Монте-Карло. Суть этого метода состоит в том, что сначала на текущей доске выбираются позиции, на которые можно пойти, а затем начиная последовательно с каждой из них разыгрывается большое количество случайных партий. Позиция, которая даёт наибольшее соотношение побед к поражениям, выбирается для следующего хода. Преимущества этого метода в том, что он требует очень небольших знаний проблемной области и не требует много памяти. Однако у этого метода есть и очевидные недостатки. Из-за того, что ходы генерируются наугад и рассматриваются не все возможные продолжения, какие-то ходы будут по ошибке оценены как хорошие. Даже несмотря на то, что случайная выборка продолжений будет благоприятной, у противника могут оказаться немногочисленные, но довольно очевидные ходы, которые позволят ему получить преимущество. Эти ходы либо не попадут в случайную выборку, либо количество хороших продолжений окажется больше. В результате получится программа, которая сильна в стратегическом, но слаба в тактическом плане. Эта проблема может быть смягчена путём добавления некоторых экспертных знаний и более глубокого поиска. В число программ, использующих метод Монте-Карло входят такие как The Many Faces of Go v12, Leela, MoGo, Crazy Stone, Olga и Gobble.

В 2006 году разработана новая методика upper confidence bounds applied to trees (UCT), использующаяся во многих программах для игры в Го на доске 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 выиграла одну из трёх игр против Каталин Тарану (Catalin Taranu), 5th про-Дан, на доске 9х9 со стандартным временем (30 минут на игру каждому игроку). MoGo была запущена на кластерном компьютере (32 узла по 8 ядер частотой 3 ГГц). Эти результаты были одобрены Французской федерацией Го. MoGo также играла на доске 19х19 против того же Каталин Тарану и проиграла имея фору в 9 камней. Стоит, однако, отметить, что программа играла сильно и проиграла всего-лишь из-за плохого выбора в ко-борьбе в конце игры, в которой компьютеры традиционно слабы.

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

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

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

Основанные на знаниях программы для игры в Го являются очень эффективными, но всё же их уровень знаний близко связан с уровнем их программистов и связанных с ними специалистов в предметной области. Обойти эту проблему позволяет использование методов машинного обучения, которые позволяют программе генерировать шаблоны и стратегии поведения, не заложенные в неё заранее.

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

Соревнования среди компьютерных программ игры в Го

Существуют несколько известных ежегодных соревнований среди компьютерных программ, играющих в Го, самое известное из которых — Компьютерная олимпиада. Регулярные и менее формальные соревнования проводятся на КГС (ежемесячно) и CKS (непрерывно).

Наиболее известные играющие в Го программы включают северокорейскую Silver Star KCC Igo, Handtalk (автор Чэнь Чжисин), Go++ (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$ за победу над 8-9 летними профессионалами с форой в 11 камней. К 2000 году остался невостребованным приз в 400.000 NT$ за победу над профессионалом с форой в 9 камней.

Удивительно, но япония лишь недавно начала спонсировать свои собственные чемпионаты по компьютерному Го. Соревнования кубка FOST проводились ежегодно с 1995 по 1999 год в Токио. Его вытеснил Вызов Гифу, проводившийся ежегодно с 2003 по 2006 годы в Огаки, префектура Гифу.

Проблемы игры компьютера с компьютером

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




Комментарии

Добавить комментарий