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

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

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

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

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

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

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

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

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

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

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

Иногда упоминается, что некоторые трудные комбинаторные проблемы (фактически любая NP-полная задача) могут быть преобразованы применительно к го; однако то же верно и для других настольных игр, подобных шахматам, обобщённым для доски произвольной размерности. 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), 5-й профессиональный дан. В 2008 году The Many Faces of Go выиграла компьютерную олимпиаду после добавления UCT к её, основанному на экспертных знаниях, механизму.

В 2008 году MoGo выиграла одну из трёх игр[19] против Каталина Цэрану, 5 про-Дан, на доске 9х9 со стандартным временем (30 минут на игру каждому игроку). MoGo была запущена на кластерном компьютере (32 узла по 8 ядер частотой 3 ГГц). Эти результаты были одобрены Французской федерацией го[20]. MoGo также играла на доске 19х19 против того же Каталина Цэрану и проиграла имея фору в 9 камней. Стоит, однако, отметить, что программа играла сильно и проиграла всего лишь из-за плохого выбора в ко-борьбе в конце игры, в которой компьютеры традиционно слабы.

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

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

К началу 2012 года СrazyStone[24], основанная на том же методе Монте-Карло, что и MoGo, имеет стабильный 5 дан на сервере КГС[25].

В декабре 2010 года компьютерная программа Zen достигла уровня 4 дан на сервере КГС. Создал программу Zen Японский программист Ёдзи Одзима (Yoji Ojima). В июне 2011 года компьютерная программа Zen19d достигла уровня 5 дан на сервере КГС, играя со скоростью 15 секунд на ход. Эта версия программы работала на 26-ядерном компьютере. В марте 2012 года компьютерная программа Zen19D достигла уровня 6 дан на сервере КГС, играя со скоростью 15 секунд на ход. Эта версия программы работала на 28-ядерном компьютере[26].

В марте 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 на КГС сервере[27].

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

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

Первые соревнования по компьютерному го спонсировались 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 камней[28].

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

В октябре 2015 года программа AlphaGo, разработанная компанией DeepMind выиграла у трехкратного чемпиона Европы Фань Хуэя (2 профессиональный дан) матч из пяти партий со счётом 4—1. Это первый в истории случай, когда компьютер выиграл в го у профессионала в равной игре[1][29][30].

В марте 2016 года AlphaGo победила профессионала 9 дана Ли Седола в четырёх партиях из пяти.[2]

В мае 2017 года на саммите «Future of Go Summit» AlphaGo выиграла три партии из трёх в мини-матче с одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе[6]

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

• AI-oriented survey of Go
• Co-Evolving a Go-Playing Neural Network, written by Alex Lubberts & Risto Miikkulainen, 2001
• Computer Game Playing: Theory and Practice, edited by M.A. Brauner (The Ellis Horwood Series in Artificial Intelligence), Halstead Press, 1983. A collection of computer-go articles. The American Go Journal, vol. 18, No 4. page 6. [ISSN 0148-0243]
• A Machine-Learning Approach to Computer Go, Jeffrey Bagdis, 2007.
• Minimalism in Ubiquitous Interface Design Wren, C. and Reynolds, C. (2004) Personal and Ubiquitous Computing, 8(5), pages 370—374. Video of computer go vision system in operation shows interaction and users exploring Joseki and Fuseki.
• Monte-Carlo Go, presented by Markus Enzenberger, Computer Go Seminar, University of Alberta, April 2004
• Monte-Carlo Go, written by B. Bouzy and B. Helmstetter from Scientific Literature Digital Library
• Static analysis of life and death in the game of Go, written by Ken Chen & Zhixing Chen, 20 February 1999

• Mick’s Computer Go Page
• Extensive list of computer Go events
• All systems Go by David A. Mechner (1998), discusses the game where professional go player Janice Kim won a game against program Handtalk after giving a 25-stone handicap.
• Kinger, Tim and Mechner, David. An Architecture for Computer Go (1996)
• Computer Go and Computer Go Programming pages at Sensei’s Library
• Computer Go bibliography
• Another Computer Go Bibliography
• Computer Go mailing list
• Published articles about computer go on Ideosphere gives current estimate of whether a Go program will be best player in the world
• Information on the Go Text Protocol commonly used for interfacing Go playing engines with graphical clients and internet servers
• The Computer Go Room on the K Go Server (KGS) for online discussion and running «bots»
• Two Representative Computer Go Games, an article about two computer go games played in 1999, one with two computers players, and the other a 29-stone handicap human-computer game
• What A Way to Go describes work at Microsoft Research on building a computer go player.
• Cracking Go, by Feng-hsiung Hsu, IEEE Spectrum magazine, October 2007 argues why it should be possible to build a Go machine stronger than any human player

• AYA by Hiroshi Yamashita
• Crazy Stone by Rémi Coulom
• GNU Go, the strongest open source Go program
• Go++ by Michael Reiss (sold as Strongest Go or Tuyoi Igo in Japan)
• Go Intellect by Ken Chen
• Handtalk/Goemate, developed in China by Zhixing Chen (sold as Shudan Taikyoku in Japan)
• Haruka by Ryuichi Kawa (sold as Saikouhou in Japan)
• Indigo by Bruno Bouzy
• Katsunari by Shin-ichi Sei
• KCC Igo, from North Korea (sold as Silver Star or Ginsei Igo in Japan)
• Leela, the first Monte Carlo program for sale to the public
• The Many Faces of Go by David Fotland (sold as AI Igo in Japan)
• MoGo by Sylvain Gelly; parallel version by many people.
• Smart Go by Anders Kierulf, inventor of the Smart Game Format