Loading AI tools
Из Википедии, свободной энциклопедии
Компьютерное го — направление искусственного интеллекта по созданию компьютерных программ, играющих в го.
В течение долгого времени считалось, что компьютерное го имеет существенные различия по сравнению с компьютерными шахматами, поскольку методы, основанные на быстром поиске по сравнению с человеческим опытом, объединённые с относительно низким знанием предметной области не будут эффективны для го. Поэтому большие усилия в области компьютерного го были потрачены на объединение экспертных знаний с локальным поиском для нахождения ответа на вопросы тактической природы игры. Результатом этих усилий были программы, способные находить хорошие решения в некоторых локальных ситуациях, но имевшие явные слабости в полной обработке игры. Кроме того, эти классические программы с увеличением мощности аппаратуры мало получали в плане силы игры и поэтому развитие этой области было в целом медленным. Поэтому считалось, что программа, хорошо играющая в го, может быть создана только в далёком будущем и только с помощью накопленных к тому времени общих знаний в области искусственного интеллекта. Даже написание программы, способной определить победителя в законченной игре, воспринималось как нетривиальная задача.
В 2006 году появились программы, основанные на поиске Монте-Карло. Сила игры искусственного интеллекта улучшилась. Но разрыв с уровнем игры профессиональных игроков в го оставался, и причём значительный.
Однако в 2015 году компьютерная программа (AlphaGo, компании DeepMind) впервые выиграла у профессионала (Фань Хуэя, 2 профессиональный дан) равный матч (со счётом 5—0)[1].
В марте 2016 года AlphaGo победила профессионала Ли Седола в первых трёх партиях из пяти игр.[2] Это был первый случай, когда профессионал 9 дана, один из сильнейших игроков мира, играл с компьютером без гандикапа.[3] В четвёртой игре Ли смог одержать победу, но пятую партию выиграл компьютер, таким образом матч закончился со счетом 4：1.[4][5] (см. подробно： Матч AlphaGo — Ли Седоль)
В мае 2017 года на саммите «Future of Go Summit» был сыгран мини-матч из 3 партий между AlphaGo и одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе, где все партии выиграла программа[6][7][8]. На этом же форуме AlphaGo обыграла команду из 5 профессионалов максимального 9 дана (Ми Ютин[англ.] (№ 3 в рейтинге сильнейших игроков, рейтинг перед матчем 3571 пункт), Чэнь Яое (№ 8, 3513)), Чжоу Жуйян (№ 10, 3509), Си Юэ[англ.] (№ 11, 3508), Тан Вэйсин[кит.] (№ 18, 3474))[9].
Большая доска (19x19, 361 пересечение) часто отмечается как основное препятствие на пути создания сильных го-программ. Проблема большой доски в том, что она препятствует глубокому поиску методом альфа-бета-отсечения.
Пока самой большой доской, на которой к настоящему времени был осуществлён полный перебор позиций является доска 6x7[10].
По сравнению с шахматами, ходы в го почти не ограничены правилами. В то время как первый ход в шахматах может быть осуществлён двадцатью способами, первый ход в го имеет 55 вариантов, с учётом симметрии доски. После нескольких первых ходов в разных углах доски симметрия игровой ситуации утрачивается и количество возможных ходов возрастает, достигая количества свободных пунктов на доске.
Начальная стадия партии в го — фусэки — подчиняется определённым общим принципам развития конфигураций камней, но для неё характерно гораздо большее разнообразие ходов, чем в шахматах. Новинки могут встречаться не на 20-м ходу, а уже на третьем или четвёртом, и грамотная игра в дебюте невозможна без осмысления стратегических перспектив конструкций, возникающих на доске. Дзёсэки (типовые схемы розыгрыша позиции на ограниченной части доски, в частности, в углах), которые в определённом смысле можно считать аналогом разработанных шахматных дебютов, не допускают механического применения и не дают гарантированного результата, поскольку эффект от их использования зависит от общей позиции на всей доске, так что даже выбор подходящего для данной позиции дзёсэки в конкретном углу является сложной интеллектуальной задачей.
Правило ко часто приводит к резкому изменению характера борьбы, последствия которой трудно оценить даже опытному игроку. Фактически надо каждый раз соизмерять последствия от «неответа» на ко-угрозу (как свою, так и противника) с ценой проигрыша ко-борьбы. Человеку приходится опираться на свой опыт и интуицию, в то время как для компьютера эти понятия трудно формализуемы.
В шахматах, как и во многих других играх, в течение партии фигур на доске становится меньше, что упрощает перебор ходов. В го каждый следующий ход, наоборот, добавляет на доску один камень (хотя возможны и снятия), создавая дополнительные игровые моменты.
Компьютерные го-программы долгое время были значительно более слабы, чем шахматные программы. Подходы, которые были применены в шахматных программах, показали себя посредственными в компьютерном го.
Шахматные правила легко формализуемы и могут быть представлены машине в удобной форме, которая позволит ей играть на высоком уровне.
Но простые позиционные правила, применяемые в шахматах, не будут эффективны в го[источник не указан 545 дней]. Для определения ценности камня необходим сложный анализ, хотя бы для определения того, жива ли группа, которой он принадлежит, как велико влияние группы и какие опасности ей грозят.
Ещё одна проблема состоит в создании хорошей оценочной функции для го. На каждом ходу может существовать несколько хороших ходов и чтобы выбрать лучший ход, компьютер должен оценить различные возможные исходы. Это становится трудной задачей в го. Например, может представиться возможность захвата камней противника за счёт укрепления его группы в другом месте. Решение о том, является ли такой обмен выгодным, может показаться слишком тяжёлым даже для игрока-человека. Также может оказаться, что ход в другой части доски и построение там формы может оказаться более важным.
Иногда упоминается, что некоторые трудные комбинаторные проблемы (фактически любая NP-полная задача) могут быть преобразованы применительно к го; однако то же верно и для других настольных игр, подобных шахматам, обобщённым для доски произвольной размерности. NP-полные задачи не могут решаться людьми быстрее, чем компьютерами: сомнительно, что человек в состоянии, например, решить Задачу коммивояжёра за время, сопоставимое с тем, за которое её решает компьютер. Следовательно, возможность применить методы решения NP-полных задач к компьютерному го не позволяет объяснить превосходства человека над компьютером в этой игре.
Учитывая, что завершающая стадия игры го (ёсэ) содержит меньшее количество возможных ходов, чем начало или середина, можно было бы предположить, что компьютеру будет намного легче играть эту часть игры. Но и здесь нашлось место для проблем:
Таким образом очень сложно запрограммировать эффективный алгоритм даже для игры завершающей стадии го, не говоря обо всей партии[11].
 | Информация в этой статье или некоторых её разделах устарела. |
 | Проверить информацию. |
Люди чувствуют, что играют в го лучше, чем компьютеры, потому что сравнивают их с людьми. «Возможно это не компьютеры играют в го плохо, а люди играют в него слишком хорошо»[12]. Го, по сравнению с другими играми с полной информацией, имеет особенности, которые делают её особенно лёгкой для людей. Камни не перемещаются, как фигуры в шахматах, не меняют цвет, как в реверси. Эти особенности позволяют людям просчитывать длинные цепочки ходов, что очень сложно для машины.
Однако в тех редких случаях, когда камни неоднократно захватываются и переигрываются на тех же самых пунктах, у людей есть проблемы, в то время как они лёгки для компьютеров.
Один очень важный раздел игры го, связанный с определением того, какие группы камней способны выжить, а какие могут быть захвачены, известен как «жизнь и смерть». Самая прямая стратегия для определения жизни и смерти — это построение дерева поиска ходов, которые затрагивают рассматриваемую группу и определение статуса группы в концевых вершинах этого дерева.
Однако в пределах временных ограничений и ограничений по доступной оперативной памяти невозможно определить с полной точностью, какие ходы затрагивают выбранную группу. Нередки, например, ситуации, когда жизнь одной группы может быть обеспечена только за счёт пленения другой. Это значит, что для решения поставленной задачи должны быть применены некоторые эвристики для определения ходов, требующих рассмотрения. Как результат у программ, играющих в го прослеживается зависимость между временными затратами на обдумывание и качеством определения жизнеспособности групп.
Существует проблема представления позиции в го для программ. Если в процессе обдумывания хода происходит интенсивный поиск хода, то представление нуждается в малом размере данных, которые можно было бы легко скопировать и уничтожить. Если информация о позиции будет содержать сильно-структурированные данные, то их будет тяжело копировать и это приведёт к замедлению процесса поиска.
Самый простой способ представления — завести одно- или двухмерный массив, в котором будет содержаться информация о том, камни какого цвета стоят на каждой позиции поля и возможность хода на пустые позиции.
Большинство программ, однако, используют более сырую информацию о доске для представления позиции. Это может быть информация о том, как соединены камни в каждой строке и как строки ассоциируются между собой, информация о группах камней, которые рискуют быть захваченными и которые живы. И хотя эта информация может быть извлечена из прямого представления, будет намного быстрее изменять её на каждом ходе и передавать в готовом виде. Такие добавочные изменения требуют запоминания большего количества информации и могут понизить скорость копирования, поэтому проблема представления игровой ситуации также остро стоит перед создателями го-программ.
В качестве альтернативы можно хранить только одну копию доски, а, делая ход, запоминать сделанные изменения. Это позволяет сократить затраты памяти и скорость копирования и избавляет от копирования лишней информации снова и снова. Но следует учесть, что такая форма представления может требовать иных подходов к её интерпретации, нежели хранение полной информации о доске.
Использование представлений, отличных от прямого, сталкивается в го с ещё одним подводным камнем, связанным с самой структурой игры. Позиция в го состоит из одиночных камней, образующих изменяющиеся структуры (группы и наборы групп). С точки зрения стратегии и тактики игры, более полезны варианты представления, которые содержат в явном виде информацию о структурах и состояниях. Но такая информация может существенно меняться буквально на каждом ходе (например, единственный ход, создающий соединение между двумя группами, имеющими по одному глазу, фактически превращает эти две группы, находящиеся под угрозой, в одну, гарантированно живую, что должно отразиться в представлении как объединение этих групп). Задача адекватного изменения сложного представления в подобных случаях сама по себе весьма нетривиальна.
Исторически основным подходом к проблеме компьютерного го был «старый добрый ИИ». Позже в качестве альтернативы такому подходу стали рассматривать нейронные сети. Одной из программ, использующих алгоритм нейронных сетей для игры в го является WinHonte[13].
Результаты этих разработок в области компьютерного го используются в других областях: когнитивистика, распознавание образов и машинное обучение[14]. Теория игр, раздел прикладной математики, тоже применяется к компьютерному го[14].
Единственное, что должна сделать программа в результате обдумывания хода — указать место, в которое следует поместить следующий камень. Однако даже такое простое решение трудно принять из-за неоднозначности позиций, к которым может привести эта постановка. Для решения этой проблемы были приспособлены различные архитектуры. Самые популярные основаны на использовании дерева поиска, применении методов Монте-Карло, создании экспертных систем и использовании машинного обучения. Немногие программы используют только что-то одно из перечисленного; большинство объединяют в себе несколько подходов.
Одна из традиционных техник в области ИИ для создания программ, играющих в игры использует минимаксное дерево поиска. Для этого рассматривают все гипотетически возможные последовательности ходов до определённой глубины, а затем используют оценочную функцию, чтобы оценить ценность хода, с которого начиналась каждая последовательность. Ход, который приводит к наилучшему результату повторяется на доске и далее такая же процедура проводится для каждого хода компьютерного игрока. В то время, как способы, основанные на использовании дерева поиска давали хорошие результаты применительно к шахматам, они были менее успешны в применении к го.
Частично причина этого кроется в том, что тяжело создать эффективную оценочную функцию и частично из-за большого количества возможных ходов, которое приводит к большому коэффициенту ветвления. Это делает технику дерева поиска слишком ресурсоёмкой. Поэтому программы, интенсивно использующие деревья поиска могут хорошо играть только на маленькой доске 9x9, но не на большой 19x19.
Существуют методы, способные улучшить работу деревьев поиска как в отношении скорости, так и памяти. Методы альфа-бета-отсечения, Поиска основных отклонений, MDT-f могут уменьшить коэффициент ветвления практически без потери силы игры. Аналогично таблица перестановок позволяет уменьшить количество повторных вычислений, особенно когда она используется совместно с методом итеративного углубления. Для быстрого доступа к данным, расположенным в таблице перестановок, необходимо использовать хеширование. Хеширование Зобриста часто встречается в программах, играющих в го, так как обеспечивает малое количество коллизий и позволяет оперативно обновлять информацию о каждом ходе с использованием лишь двух операций XOR вместо полного вычисления.
Даже с использованием этих уменьшающих трудоёмкость методов дерево поиска на полной доске всё ещё является очень медленным. Поиск может быть ускорен, если ветвление ещё больше ограничить, не рассматривая варианты ходов в область влияния противника, или выбирать для рассмотрения в первую очередь группы камней, находящиеся в положении атари. Однако оба эти метода приводят к риску нерассмотрения жизненно важных ходов, которые могли бы изменить курс игры.
Результаты компьютерных соревнований показывают, что методы соответствия образца для выбора цепочки шагов, объединённые с быстрым ограниченным тактическим поиском (объяснённый выше), достаточны, чтобы произвести конкурентоспособную программу. Например, GNU Go конкурентоспособна, но она не использует поиск по всей доске.
Новички часто учатся, просматривая записи старых партий мастеров игры. Есть сильная гипотеза, что накопление знаний — ключ к созданию сильного ИИ. Например, Тим Кингер (Tim Kinger) и Дэвид Мичнер (David Mechner) говорят: «Мы верим, что, только используя инструменты накопления и поддержания знаний в области го, можно создать намного более сильные программы, чем есть сейчас.» Они предлагают два пути: рассмотрение общих форм и их использования, или рассмотрение местных противостояний. «…Программам для игры в го всё ещё недостаёт как качества, так и количества знаний.»[15]
После реализации использование опытных знаний показало себя очень эффективным. Сотни руководящих принципов и эмпирических правил для сильной игры были сформулированы и любителями высокого уровня и профессионалами. Задача программиста состоит в том, чтобы взять эти эвристики, формализовать их в машинном коде, и использовать сравнение с образцом (pattern matching) и распознавание образов (pattern recognition) для выявления того, когда их сто́ит применять. Также стоит разработать систему для выявления лучшего решения в случае, когда применимы сразу несколько принципов.
Большинство относительно успешных результатов получены на основе навыков игры в го программистов, которыми написаны программы, и их личными догадками по поводу игры мастеров, а не на основе формальных математических просчётов; они пытаются заставить компьютер подражать тем способам, которыми они сами играют в го. «Большинство конкурентоспособных программ потребовало 5-15 лет человеческих усилий и содержит 50-100 модулей, имеющих дело с различными аспектами игры.»[16]
Этот метод до недавнего времени был самой успешной техникой в производстве конкурентоспособных программ игры в го на полноразмерном поле. Примерами программ, которые положились в большей степени на опытное знание, является Handtalk (позже известный как Goemate), The Many Faces of Go, Go Intellect и Go++, каждую из которых в некоторый момент считали лучшей программой го в мире.
Однако добавление экспертных знаний иногда ослабляет программу, потому что просто поверхностное ориентирование в ситуации может привести к ошибкам. «Лучшие программы обычно делают хорошие ходы уровня мастера, однако, как знают все игроки, один плохой ход может разрушить хорошую игру.»[16]
Одной из главных альтернатив использованию закодированных знаний и поиску ходов является метод Монте-Карло. Суть этого метода состоит в том, что сначала на текущей доске выбираются позиции, на которые можно пойти, а затем начиная последовательно с каждой из них разыгрывается большое количество случайных партий. Позиция, которая даёт наибольшее соотношение побед к поражениям, выбирается для следующего хода. Преимущества этого метода в том, что он требует очень небольших знаний проблемной области и не требует много памяти. Однако у этого метода есть и очевидные недостатки. Из-за того, что ходы генерируются наугад и рассматриваются не все возможные продолжения, какие-то ходы будут по ошибке оценены как хорошие. Даже несмотря на то, что случайная выборка продолжений будет благоприятной, у противника могут оказаться немногочисленные, но довольно очевидные ходы, которые позволят ему получить преимущество. Эти ходы либо не попадут в случайную выборку, либо количество хороших продолжений окажется больше. В результате получится программа, которая сильна в стратегическом, но слаба в тактическом плане. Эта проблема может быть смягчена путём добавления некоторых экспертных знаний и более глубокого поиска. В число программ, использующих метод Монте-Карло входят такие как Zen, The Many Faces of Go v12, Leela, MoGo, Crazy Stone[17], Olga и Gobble.
В 2006 году разработана новая методика upper confidence bounds applied to trees[18], использующаяся во многих программах для игры в го на доске 9х9 с превосходными результатами. Техника UCT совместно со многими другими техниками оптимизации для игры на доске 19х19 позволила MoGo стать одной из сильнейших программ. Технику UCT для игры на доске 19х19 используют следующие программы: MoGo, Crazy Stone, Mango. MoGo выиграла компьютерную олимпиаду в 2007 году и выиграла одну из трёх блиц-игр против Го Цзюань (Guo Juan)[19], 5-й профессиональный дан. В 2008 году The Many Faces of Go выиграла компьютерную олимпиаду после добавления UCT к её, основанному на экспертных знаниях, механизму.
В 2008 году MoGo выиграла одну из трёх игр[20] против Каталина Цэрану, 5 про-Дан, на доске 9х9 со стандартным временем (30 минут на игру каждому игроку). MoGo была запущена на кластерном компьютере (32 узла по 8 ядер частотой 3 ГГц). Эти результаты были одобрены Французской федерацией го[21]. MoGo также играла на доске 19х19 против того же Каталина Цэрану и проиграла имея фору в 9 камней. Однако, программа играла сильно и проиграла всего лишь из-за плохого выбора в ко-борьбе в конце игры, в которой компьютеры традиционно слабы.
7 августа 2008 года MoGo выиграла игру на доске 19х19 против Ким Мёнвана (Kim MyungWan), 8p имея фору в 9 камней с преимуществом в 1,5 очка. Ким использовал 13 минут на обдумывание, в то время как MoGo — около 55-ти, однако он чувствовал, что использование большего количества времени не поможет ему выиграть. MoGo был запущен из Нидерландов на суперкомпьютере из 800 узлов, содержащем по 4 ядра на узел, частотой 4,7 ГГц и производительностью 15 Терафлопс.[22]. Мёнхван и MoGo играли четыре игры с различным гандикапом и временными ограничениями и выиграли по две игры. Отчёты об играх доступны на КГС[23], где MoGo играла под ником MogoTitan.
В феврале 2009 года MoGo одержала ещё большую победу — с гандикапом в 7 камней она победила игрока 9 дана Чжоу Цзюньсюня (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Цзянь Личэня (Li-Chen Chien)[24].
К началу 2012 года СrazyStone[25], основанная на том же методе Монте-Карло, что и MoGo, имеет стабильный 5 дан на сервере КГС[26].
В декабре 2010 года компьютерная программа Zen достигла уровня 4 дан на сервере КГС. Создал программу Zen Японский программист Ёдзи Одзима (Yoji Ojima). В июне 2011 года компьютерная программа Zen19d достигла уровня 5 дан на сервере КГС, играя со скоростью 15 секунд на ход. Эта версия программы работала на 26-ядерном компьютере. В марте 2012 года компьютерная программа Zen19D достигла уровня 6 дан на сервере КГС, играя со скоростью 15 секунд на ход. Эта версия программы работала на 28-ядерном компьютере[27].
В марте 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 на КГС сервере[28].
Основанные на знаниях программы для игры в го являются очень эффективными, но всё же их уровень знаний близко связан с уровнем их программистов и связанных с ними специалистов в предметной области. Обойти эту проблему позволяет использование методов машинного обучения, которые позволяют программе генерировать шаблоны и стратегии поведения, не заложенные в неё заранее.
В основном такой подход реализуется с помощью нейронных сетей или генетических алгоритмов, которые позволяют либо найти нужную ситуацию в большой базе данных игр, либо сыграть множество игр против себя или других программ или людей. Известными программами, которые используют нейроные сети являются NeuroGo и WinHonte.
Существуют несколько известных ежегодных соревнований среди компьютерных программ, играющих в го, самое известное из которых — Компьютерная олимпиада. Регулярные и менее формальные соревнования проводятся на КГС (ежемесячно) и 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$ за победу над 8-9 летними профессионалами с форой в 11 камней. К 2000 году остался невостребованным приз в 400.000 NT$ за победу над профессионалом с форой в 9 камней[29].
Удивительно, но Япония лишь недавно начала спонсировать свои собственные чемпионаты по компьютерному Го. Соревнования кубка FOST проводились ежегодно с 1995 по 1999 год в Токио. Его вытеснил Вызов Гифу, проводившийся ежегодно с 2003 по 2006 годы в Огаки, префектура Гифу.
В октябре 2015 года программа AlphaGo, разработанная компанией DeepMind выиграла у трехкратного чемпиона Европы Фань Хуэя (2 профессиональный дан) матч из пяти партий со счётом 4—1. Это первый в истории случай, когда компьютер выиграл в го у профессионала в равной игре[1][30][31].
В марте 2016 года AlphaGo победила профессионала 9 дана Ли Седола в четырёх партиях из пяти.[2]
В мае 2017 года на саммите «Future of Go Summit» AlphaGo выиграла три партии из трёх в мини-матче с одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе[6]
Когда два компьютера играют в го друг с другом, то в идеале должна получиться картина игры, свойственная игре человека с человеком. Однако этого трудно добиться, особенно в конце игры. Основная проблема заключается в том, что программа не может вести диалог с противником. Так если есть какие-то разногласия в статусе групп, то для программ нет никаких способов решить их. Одним из способов решения этой проблемы может быть введение человека-судьи или высокоспециализированной программной среды для оценки финальной позиции. Альтернативный метод — позволить программам делать ходы до тех пор, пока окончательно не определятся статусы всех спорных групп. Главное препятствие к реализации этого решения состоит в том, что в некоторых вариантах правил го (например, японские правила) игроки штрафуются за лишние ходы, недополучая очки. Поэтому существует риск, что засомневавшись в своём преимуществе программа проиграет после доигрывания победной ситуации.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
