Computer Go - Computer Go

Эта статья посвящена изучению Go (игра) в искусственном интеллекте. Для компьютерного языка программирования Go см. Go (язык программирования).
Не путать с Программное обеспечение Go.
Часть серии по
Идти
Перейти к доске part.jpg
Особенности игры
История и культура
Игроки и организации
Компьютеры и математика

Computer Go это область искусственный интеллект (AI), посвященный созданию компьютерная программа это играет традиционный настольная игра Идти. Игра Го была плодотворным предметом исследований искусственного интеллекта на протяжении десятилетий, кульминацией которых стал 2017 год. AlphaGo Мастер выиграл три игры из трех против Ке Цзе, который в то время непрерывно занимал первое место в мире в течение двух лет.[1][2]

Спектакль

Го - сложная настольная игра, требующая интуиции, творческого и стратегического мышления.[3][4] Это долгое время считалось сложной задачей в области искусственный интеллект (AI) и значительно сложнее[5] решить чем шахматы. Многие в области искусственный интеллект считают, что Go требует больше элементов, имитирующих человеческое мышление, чем шахматы.[6] Математик И. Дж. Хорошо писал в 1965 году:[7]

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

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

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

Первая программа Go была написана Альберт Линдси Зобрист в 1968 г. в рамках его диссертации по распознавание образов.[11] Он представил функция влияния оценить территорию и Зобристское хеширование обнаружить ко.

В апреле 1981 года Джонатан Миллен опубликовал статью в Байт обсуждая Уолли, программу Го с доской 15x15, которая вписывается в КИМ-1 1K RAM микрокомпьютера.[12] Брюс Ф. Вебстер опубликовал в журнале статью в ноябре 1984 года, в которой обсуждалась программа го, которую он написал для Apple Macintosh, в том числе MacFORTH источник.[13]

В 1998 году очень сильные игроки могли побеждать компьютерные программы, создавая гандикап в 25–30 стоунов, огромный гандикап, который когда-либо могли бы принять немногие игроки. Был случай на чемпионате мира по компьютерному гоу 1994 года, когда победившая программа Go Intellect проиграла все три игры молодым игрокам, получив гандикап в 15 очков.[14] В общем, игроки, которые понимали и использовали слабые стороны программы, могли выиграть с гораздо большими гандикапами, чем обычные игроки.[15]

21-го века

События в Поиск в дереве Монте-Карло и машинное обучение довел лучшие программы до высокого дан уровень на маленькой доске 9х9. В 2009 году появились первые такие программы, которые смогли достичь и удержать низкий уровень звания на уровне дана на KGS Go Сервер на доске 19x19 тоже.

В 2010 году на Европейском Го Конгрессе 2010 года в Финляндии MogoTW сыграли 19x19 Го против Каталин Тарану (5р). MogoTW получил гандикап в семь стоек и выиграл.[16]

В 2011, Дзен достигла 5 дан на сервере сомов, играя в партии по 15 секунд на ход. Учетная запись, которая достигла этого ранга, использует кластерную версию Zen, работающую на 26-ядерном компьютере.[17]

В 2012 году Дзен победил Такемия Масаки (9p) на 11 очков при гандикапе в пять камней, после чего следует победа с 20 очками при гандикапе в четыре камня.[18]

В 2013, Безумный камень бить Ёсио Исида (9p) в игре 19 × 19 с форой четыре камня.[19]

Codecentric Go Challenge 2014, матч до лучших из пяти в игре 19x19, проводился между Crazy Stone и Franz-Jozef Dickhut (6d). Ни один более сильный игрок никогда раньше не соглашался сыграть серьезное соревнование против программы го на равных. Франц-Юзеф Дикхут выиграл, хотя Crazy Stone выиграл первый матч с преимуществом в 1,5 очка.[20]

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

В октябре 2015 г. Google DeepMind программа AlphaGo бить Фань Хуэй, чемпион Европы по го, пять раз из пяти в турнирных условиях.[21]

В марте 2016 года AlphaGo обыграла Ли Седол в первых трех из пяти матчей.[22] Это был первый раз, когда 9 дан Мастер провел профессиональную игру против компьютера без препятствий.[23] Ли выиграл четвертый матч, назвав свою победу «бесценной».[24] Через два дня AlphaGo выиграла финальный матч.[25][26]

В мае 2017 года AlphaGo обыграла Ке Цзе, который в то время занимал первое место в мире,[27][28] в матч из трех игр вовремя Будущее Go Summit.[29]

В октябре 2017 года DeepMind представила новую версию AlphaGo, обучаемую только путем самостоятельной игры, которая превзошла все предыдущие версии, превзойдя версию Ке Цзе в 89 из 100 игр.[30]

Поскольку основные принципы AlphaGo были опубликованы в журнале Природа, другие команды смогли создать программы высокого уровня. К 2017 г. Дзен и Tencent проект Изобразительное искусство были способны иногда побеждать профессионалов очень высокого уровня, а открытый исходный код Лила Зеро двигатель был выпущен.

Препятствия на пути к высокому уровню производительности

В течение долгого времени было широко распространено мнение, что компьютерный Go представляет собой проблему, принципиально отличную от компьютерные шахматы. Считалось, что методы, основанные на быстром глобальном поиске с относительно небольшими знаниями предметной области, не будут эффективны против людей-экспертов. Таким образом, большая часть усилий по разработке компьютерного Go в то время была сосредоточена на способах представления экспертных знаний, подобных человеку, и сочетанию их с локальным поиском для ответа на вопросы тактического характера. Результатом этого были программы, которые хорошо справлялись со многими ситуациями, но имели очень явные недостатки по сравнению с их общей обработкой игры. Кроме того, эти классические программы почти ничего не получили от увеличения доступной вычислительной мощности. как таковой и прогресс в этой области был в целом медленным.

Несколько исследователей осознали потенциал вероятностных методов и предсказали, что они станут доминирующими в компьютерных играх.[31] но многие другие считали сильную программу игры в го чем-то, что может быть достигнуто только в далеком будущем в результате фундаментальных достижений в общей технологии искусственного интеллекта. Даже написание программы, способной автоматически определять победителя законченной игры, считалось нетривиальным делом.

Появление программ, основанных на Монте-Карло поиск (начатый в 2006 г.) во многом изменил эту ситуацию: первые профессиональные игроки с 9 данами в го проиграли в 2013 г. многоядерный компьютеры, хоть и с четырехсторонним дефектом.

Размер доски

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

В 2002 году компьютерная программа под названием MIGOS (MIni GO Solver) полностью решила игру го для доски 5 × 5. Черные выигрывают, забирая всю доску.[32]

Количество вариантов перемещения

Продолжая сравнение с шахматами, ходы го не так ограничены правилами игры. Для первого хода в шахматах у игрока есть двадцать вариантов. Игроки в го начинают с выбора из 55 различных разрешенных ходов с учетом симметрии. Это число быстро растет, поскольку симметрия нарушается, и вскоре придется оценивать почти все 361 балл на доске. Некоторые ходы намного популярнее других, а некоторые практически не используются, но все возможны.

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

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

Эти типы правил позиционной оценки не могут эффективно применяться к Go. Ценность позиции го зависит от комплексного анализа, позволяющего определить, жива группа или нет, какие камни могут быть связаны друг с другом, а также эвристики, оценивающей степень влияния сильной позиции или степень влияния слабой позиции. позиция может быть атакована.

Лучшим может считаться более одного хода в зависимости от того, какая стратегия используется. Чтобы выбрать ход, компьютер должен оценить различные возможные исходы и решить, какой из них лучше. Это сложно из-за тонких компромиссов, присутствующих в Go. Например, можно захватить некоторые вражеские камни за счет усиления вражеских камней в другом месте. Хорошая сделка или нет, может быть трудным решением даже для игроков-людей. Вычислительная сложность также проявляется здесь, поскольку ход может быть важен не сразу, но после множества ходов может стать очень важным, поскольку другие области доски обретают форму.

Комбинаторные задачи

Иногда в этом контексте упоминается, что различные сложные комбинаторные задачи (фактически, любые NP-жесткий проблема) может быть преобразована в Go-подобные задачи на достаточно большой доске; однако то же самое верно и для других абстрактных настольных игр, включая шахматы и тральщик, при подходящем обобщении на доску произвольного размера. НП-полный В общем случае проблемы не имеют тенденции быть проще для людей без посторонней помощи, чем для компьютеров, запрограммированных соответствующим образом: сомнительно, что люди без посторонней помощи смогут успешно конкурировать с компьютерами в решении, например, примеров проблема суммы подмножества.

Эндшпиль

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

Применение сюрреалистические числа к эндшпилю в го, общий анализ игры, впервые проведенный Джон Х. Конвей, был разработан Элвин Р. Берлекамп и Дэвид Вулф и изложены в их книге, Математическая игра (ISBN  978-1-56881-032-4). Несмотря на то, что в большинстве игровых обстоятельств он не является универсальным, он очень помогает при анализе определенных классов позиций.

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

  • Даже если компьютер может безупречно воспроизвести каждую локальную зону эндшпиля, мы не можем сделать вывод, что его игра будет безупречной в отношении всей доски. Дополнительные области рассмотрения в эндшпиле включают: сэнтэ и готэ отношения, приоритезация различных локальных эндшпилей, подсчет и оценка территории и так далее.
  • Эндшпиль может включать в себя многие другие аспекты го, включая «жизнь и смерть», которые также известны как NP-жесткий.[33][34]
  • Каждая из локальных зон эндшпиля может влиять друг на друга. Другими словами, они динамичны по своей природе, хотя визуально изолированы. Это затрудняет рассуждение как компьютеров, так и людей. Такая природа приводит к некоторым сложным ситуациям, таким как Triple Ko,[35] Четверной Ко,[36] Меласса Ко,[37] и Самогонная жизнь.[38]

Таким образом, традиционные алгоритмы го не могут безупречно разыграть эндшпиль в смысле прямого вычисления лучшего хода. Сильные алгоритмы Монте-Карло могут достаточно хорошо справляться с обычными эндшпильными ситуациями в го, и, как правило, самые сложные классы задач на жизнь и смерть в эндшпиле вряд ли возникнут в игре высокого уровня.[39]

Порядок игры

Двигатели го на базе Монте-Карло имеют репутацию гораздо более склонных к игре. тенуки, перемещается в другое место на доске, а не продолжает бой локально, а не игроки-люди. Непосредственный расчет, когда требуется конкретный локальный переезд, может быть трудным.[40] В начале существования программы это часто воспринималось как недостаток.[41] Тем не менее, эта тенденция сохранилась в стиле игры AlphaGo с доминирующими результатами, так что это может быть скорее «причудой», чем «слабостью».[42]

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

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

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

С Алгоритм Бенсона, можно определить цепи, которые безусловно живы и, следовательно, не нуждаются в проверке в будущем на предмет безопасности.

Государственное представительство

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

Самый прямой способ представления доски - в виде одномерного или двухмерного массива, где элементы в массиве представляют точки на доске и могут принимать значение, соответствующее белому камню, черному камню или пустому перекрестку. . Дополнительные данные необходимы, чтобы сохранить, сколько камней было захвачено, чья очередь, и какие пересечения являются незаконными из-за Ко правило.

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

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

Системный дизайн

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

Исторически, ГОФАИ (Старый добрый AI) методы были использованы для решения проблемы Go AI. В последнее время, нейронные сети были использованы в качестве альтернативного подхода. Одним из примеров программы, использующей нейронные сети, является WinHonte.[43]

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

Результаты исследования Computer Go применяются в других подобных областях, таких как наука о мышлении, распознавание образов и машинное обучение.[44] Комбинаторная теория игр, филиал Прикладная математика, это тема, имеющая отношение к компьютерному Go.[45]

Философия дизайна

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

Некоторые программы используют только один из этих методов исключительно; большинство объединяет части каждого в одну синтетическую систему.

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

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

Есть несколько методов, которые могут значительно улучшить производительность деревьев поиска с точки зрения скорости и памяти. Техники обрезки, такие как альфа – бета обрезка, Поиск основной вариации, и МПД-ф может снизить эффективный коэффициент ветвления без потери прочности. В тактических областях, таких как жизнь и смерть, Go особенно подходит для таких методов кеширования, как таблицы транспонирования. Это может уменьшить количество повторяемых усилий, особенно в сочетании с итеративное углубление подход. Чтобы быстро разместить полноразмерную доску Го в таблице транспонирования, хеширование техника для математического обобщения обычно необходима. Зобристское хеширование очень популярен в программах Go, потому что у него низкая частота столкновений, и его можно итеративно обновлять при каждом движении всего за два XOR, а не рассчитывается с нуля. Даже при использовании этих методов повышения производительности полный поиск по дереву на полноразмерной плате по-прежнему слишком медленный. Поиски можно ускорить, используя большое количество техник отсечения, зависящих от предметной области, например, не рассматривая ходы, когда ваш оппонент уже силен, и выборочные расширения, такие как постоянный учет ходов рядом с группами камней, которые вот-вот будет схвачен. Однако оба этих варианта сопряжены со значительным риском игнорирования жизненно важного шага, который изменил бы ход игры.

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

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

Новички часто многому учатся из игровых записей старых игр, в которые играли опытные игроки. Существует сильная гипотеза, согласно которой получение знаний о го - это ключ к созданию сильного компьютерного го. Например, Тим Кингер и Дэвид Мехнер утверждают, что «мы верим, что с лучшими инструментами для представления и поддержания знаний Go можно будет разработать более сильные программы Go». Они предлагают два пути: распознавание общих конфигураций камней и их позиций и сосредоточение внимания на локальных сражениях. «Программам го по-прежнему не хватает как качества, так и количества знаний».[46]

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

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

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

Тем не менее, добавление знаний о го иногда ослабляет программу, потому что некоторые поверхностные знания могут привести к ошибкам: «лучшие программы обычно играют хорошие, мастерские ходы. Однако, как известно каждому игроку, всего один неудачный ход может испортить хорошую игру. Производительность программы за полную игру может быть намного ниже уровня мастера ».[47]

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

Основная статья: Поиск по дереву Монте-Карло

Одной из основных альтернатив использования знаний и поиска, закодированных вручную, является использование Методы Монте-Карло. Это делается путем создания списка возможных ходов, и для каждого хода разыгрываются тысячи игр в случайном порядке на получившейся доске. Ход, который приводит к лучшему набору случайных игр для текущего игрока, выбирается как лучший ход. Преимущество этого метода состоит в том, что он требует очень мало знаний в предметной области или участия экспертов, а компромисс заключается в увеличении требований к памяти и процессору. Однако, поскольку ходы, используемые для оценки, генерируются случайным образом, возможно, что ход, который был бы отличным, за исключением одного конкретного ответа оппонента, был бы ошибочно оценен как хороший ход. Результатом этого являются программы, сильные в общем стратегическом смысле, но несовершенные тактически.[нужна цитата ] Эту проблему можно смягчить, добавив некоторые знания предметной области при генерации ходов и увеличив глубину поиска поверх случайной эволюции. Некоторые программы, использующие методы Монте-Карло: Fuego,[48] Многоликая игра v12,[49] Лила,[50] MoGo,[51] Безумный камень, MyGoFriend,[52] и дзен.

В 2006 году появилась новая методика поиска, верхние доверительные границы, применяемые к деревьям (UCT),[53] был разработан и применен ко многим программам 9x9 Monte-Carlo Go с отличными результатами. UCT использует результаты разыграть собраны до сих пор, чтобы направлять поиск по более успешным линиям игры, при этом позволяя исследовать альтернативные линии. Техника UCT вместе со многими другими оптимизациями для игры на большой доске 19x19 позволила MoGo стать одной из самых сильных исследовательских программ. Ранние успешные применения методов UCT к 19x19 Go включают MoGo, Crazy Stone и Mango.[54] MoGo выиграл 2007 Компьютерная олимпиада и выиграл одну (из трех) блиц-партию против Guo Juan, Pro 5-го дана, в гораздо менее сложном 9x9 Go. Многоликая го[55] выиграл 2008 Компьютерная олимпиада после добавления поиска UCT к своей традиционной системе, основанной на знаниях.

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

Хотя системы, основанные на знаниях, оказались очень эффективными в Go, их уровень навыков тесно связан со знаниями их программистов и связанных с ними экспертов в предметной области. Один из способов обойти это ограничение - использовать машинное обучение методы, позволяющие программному обеспечению автоматически генерировать правила, шаблоны и / или стратегии разрешения конфликтов правил.

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

Методы машинного обучения также можно использовать в менее амбициозном контексте для настройки определенных параметров программ, которые в основном полагаются на другие методы. Например, Безумный камень изучает шаблоны генерации ходов из нескольких сотен образцов игр, используя обобщение Система рейтинга Эло.[56]

AlphaGo

Основная статья: AlphaGo

AlphaGo, разработан Google DeepMind, добился значительного прогресса, победив профессионального игрока-человека в октябре 2015 года, используя приемы, сочетающие глубокое обучение и Поиск в дереве Монте-Карло.[57] AlphaGo значительно мощнее, чем другие предыдущие программы Go, и первой, кто победил профессионального человека с 9 данами в игре без препятствий на полноразмерной доске.

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

Смотрите также: Программное обеспечение Go
  • AlphaGo, первая компьютерная программа, выигравшая в равных матчах против профессионального игрока в го.
  • АЯ[58] Хироши Ямасита
  • Бадуги Джуён Ли
  • Безумный камень к Реми Кулом (продается как Saikyo no Igo в Японии)
  • Темный лес к Facebook
  • Изобразительное искусство к Tencent
  • Фуэго,[48] ан Открытый исходный код Программа Монте-Карло
  • Гобан,[59] Macintosh OS X Программа Go от Sen: te (требуются бесплатные расширения Goban)[60]
  • GNU Go, классическая программа Go с открытым исходным кодом
  • Go ++[61] от Майкла Рейсса (продается как Сильнейший Go или Туёи Иго в Японии)
  • Лила,[50] первая программа Монте-Карло для продажи общественности
  • Лила Зеро,[50] повторная реализация системы, описанной в AlphaGo Zero бумага
  • Многоликая го[49] Дэвида Фотланда (продается как AI Igo в Японии)
  • MyGoFriend[52] Фрэнк Каргер
  • MoGo[62] Сильвен Гелли; параллельная версия[51] многими людьми.
  • Пачи[63] программа с открытым исходным кодом Монте-Карло Петра Баудиша, онлайн-версия Peepo[64] Джонатан Четвинд, с картами и комментариями во время игры
  • Smart Go[65] Андерса Керульфа, изобретателя Формат умной игры
  • Steenvreter[66] Эрик ван дер Верф
  • Дзен[67] Ёдзи Одзима, он же Ямато (продается в Японии как Тэнчо но Иго); параллельная версия Хидеки Като.

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

Между компьютерными программами го проводится несколько ежегодных соревнований, наиболее заметными из которых являются соревнования по игре в го. Компьютерная олимпиада. Регулярные, менее формальные соревнования между программами, которые раньше проводились на сервере KGS Go.[68] (ежемесячно) и Computer Go Server[69] (непрерывный).

Известные программы для игры в го включают Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi и Fuego, все перечисленные выше; а также холодное молоко тайваньского автора, Steenvreter голландского автора и DolBaram корейского автора.

История

Первое соревнование по компьютерному Го было спонсировано Acornsoft,[70] и первые регулярные от USENIX. Они проводились с 1984 по 1988 год. Эти соревнования представили Nemesis, первую соревновательную программу Го от Брюс Уилкокс, а G2.5 на Дэвид Фотланд, который позже эволюционировал в Cosmos и The Many Faces of Go.

Одним из первых двигателей исследований компьютерного го была премия Ing Prize, относительно крупная денежная премия, спонсируемая тайваньским банкиром. Инг Чан-ки, предлагаемый ежегодно в период с 1985 по 2000 год на Всемирном конгрессе компьютерного го (или Ing Cup). Победителю этого турнира разрешили бросить вызов молодым игрокам с гандикапом в коротком матче. Если компьютер выигрывал матч, приз присуждается и объявляется новый приз: больший приз за победу над игроками с меньшим гандикапом. Срок действия серии призов Ing был истек либо 1) в 2000 году, либо 2) когда программа могла победить профессионала с 1 даном без гандикапа на 40 000 000 NT долларов. Последним победителем был Handtalk в 1997 году, который потребовал 250 000 NT долларов за победу в матче с гандикапом с 11 стоунами против трех 11–13-летних любителей со 2–6 данами. На момент истечения срока действия приза в 2000 году невостребованный приз составлял 400 000 новых тайваньских долларов за победу в матче с гандикапом с девятью камнями.[71]

Ко многим другим крупным региональным турнирам по го («конгрессам») были подключены компьютерные соревнования по го. Европейский Конгресс Го спонсирует компьютерный турнир с 1987 года, а мероприятие USENIX превратилось в Чемпионат США / Северной Америки по компьютерному Го, который ежегодно проводится с 1988 по 2000 год на Конгрессе США по Го.

Япония начала спонсировать соревнования по компьютерному го в 1995 году. Кубок FOST проводился ежегодно с 1995 по 1999 год в Токио. Этот турнир был заменен Gifu Challenge, который проводился ежегодно с 2003 по 2006 год в Огаки, Гифу. В Computer Go Кубок УЭК проводится ежегодно с 2007 года.

Проблемы формализации правил в компьютерно-компьютерных играх

Когда два компьютера играют в игру в го друг против друга, в идеале нужно вести себя так, как играют два человека, избегая при этом вмешательства реальных людей. Однако это может быть сложно во время подсчета очков в конце игры. Основная проблема заключается в том, что программное обеспечение для игры в го, которое обычно общается с помощью стандартизированных Протокол Go Text (GTP), не всегда соглашается относительно статуса камней живым или мертвым.

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

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

Главный недостаток вышеупомянутой системы заключается в том, что некоторые наборы правил (такие как традиционные японские правила) наказывают игроков за эти дополнительные ходы, что исключает использование дополнительного воспроизведения для двух компьютеров. Тем не менее, большинство современных программ Го поддерживают японские правила против людей и компетентны как в игре, так и в подсчете очков (Fuego, Many Faces of Go, SmartGo и т. Д.).

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

Тестирование

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

GoGUI и его аддон gogui-twogtp можно использовать для игры двух движков друг против друга в одной компьютерной системе.[72] SmartGo и Many Faces of Go также предоставляют эту функцию.

Чтобы играть с максимально широким кругом противников, KGS Go Server позволяет играть движок Go против движка Go, а также движок Go против человека в рейтинговых и нерейтинговых матчах. CGOS - это выделенный компьютер по сравнению с компьютерным сервером Go.

Смотрите также

Рекомендации

  1. ^ "柯 洁 迎 19 岁 生日 雄踞 人类 世界 排名 第一 已 两年" (на китайском языке). Май 2017.
  2. ^ «Рейтинги игроков World's Go». 24 мая 2017.
  3. ^ «ИИ Google выигрывает первую игру в историческом матче с чемпионом по го». ПРОВОДНОЙ. 9 марта 2016.
  4. ^ https://www.koreatimes.co.kr/www/news/tech/2016/03/325_200068.html
  5. ^ Бузи, Бруно; Казенав, Тристан (9 августа 2001 г.). «Computer Go: исследование, ориентированное на ИИ». Искусственный интеллект. 132 (1): 39–103. Дои:10.1016 / S0004-3702 (01) 00127-8.
  6. ^ Джонсон, Джордж (1997-07-29), «Чтобы протестировать мощный компьютер, сыграйте в древнюю игру», Нью-Йорк Таймс, получено 2008-06-16
  7. ^ http://www.chilton-computing.org.uk/acl/literature/reports/p019.htm
  8. ^ Сильвер, Дэвид; Хуанг, Аджа; Мэддисон, Крис Дж .; Гез, Артур; Сифре, Лоран; Дрише, Джордж ван ден; Шриттвизер, Джулиан; Антоноглоу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нхам, Джон; Кальхбреннер, Нал; Суцкевер Илья; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грэпель, Тор; Хассабис, Демис (28 января 2016 г.). «Освоение игры в го с помощью глубоких нейронных сетей и поиска по дереву». Природа. 529 (7587): 484–489. Bibcode:2016Натура.529..484S. Дои:10.1038 / природа16961. ISSN  0028-0836. PMID  26819042. S2CID  515925.закрытый доступ
  9. ^ Среда, Ник. «Человеко-компьютерные вызовы». computer-go.info. Получено 2011-10-28.
  10. ^ "'Огромный шаг вперед »: компьютер, имитирующий человеческий мозг, побеждает профессионалов в игре го».
  11. ^ Альберт Зобрист (1970), Извлечение и представление признаков для распознавания образов и игры в го. Кандидат наук. Диссертация (152 стр.), Висконсинский университет. Также опубликован как технический отчет
  12. ^ Миллен, Джонатан К. (апрель 1981 г.). «Программирование игры го». Байт. п. 102. Получено 18 октября 2013.
  13. ^ Вебстер, Брюс (Ноябрь 1984 г.). "Плата Go для Macintosh". Байт. п. 125. Получено 23 октября 2013.
  14. ^ "CS-TR-339 Computer Go Tech Report". Получено 28 января 2016.
  15. ^ См., Например, intgofed.org В архиве 28 мая 2008 г. Wayback Machine
  16. ^ "Новости EGC 2010 Тампере". Архивировано из оригинал 14 августа 2009 г.. Получено 28 января 2016.
  17. ^ "Архив игр KGS". Получено 28 января 2016.
  18. ^ «Программа Zen computer Go побеждает Такемию Масаки всего с 4 камнями!». Go Game Guru. Архивировано из оригинал на 2016-02-01. Получено 28 января 2016.
  19. ^ "「 ア マ 六段 の 力。 天才 か も 」囲 碁 棋士 、 コ ン ピ ュ タ ー に 敗 れ 初 の 公式 戦". MSN Sankei News. Архивировано из оригинал 24 марта 2013 г.. Получено 27 марта 2013.
  20. ^ "codecentric go Challenge - Еще один сайт на WordPress". Получено 28 января 2016.
  21. ^ "Алгоритм Google AI осваивает древнюю игру го". Новости и комментарии о природе. Получено 28 января 2016.
  22. ^ «Искусственный интеллект: AlphaGo от Google превосходит мастера го Ли Седола». BBC News Online. 12 марта 2016 г.. Получено 12 марта 2016.
  23. ^ «DeepMind от Google одерживает историческую победу над легендарным игроком в го Ли Седолом». www.theverge.com. Получено 9 марта 2016.
  24. ^ «Искусственный интеллект: мастер игры Ли Седол побеждает программу AlphaGo». BBC News Online. 13 марта 2016 г.. Получено 13 марта 2016.
  25. ^ "AlphaGo AI от Google снова побеждает Ли Седола и выигрывает серию Го 4-1". Грани. Получено 15 марта 2016.
  26. ^ «После победы в Китае дизайнеры AlphaGo исследуют новый ИИ». 2017-05-27.
  27. ^ «Рейтинги игроков World's Go». Май 2017.
  28. ^ "柯 洁 迎 19 岁 生日 雄踞 人类 世界 排名 第一 已 两年" (на китайском языке). Май 2017.
  29. ^ «AlphaGo от Google продолжает доминировать, одержав вторую победу в Китае». 2017-05-25.
  30. ^ Сильвер, Дэвид; Шриттвизер, Джулиан; Симонян, Карен; Антоноглоу, Иоаннис; Хуанг, Аджа; Гез, Артур; Хуберт, Томас; Бейкер, Лукас; Лай, Мэтью; Болтон, Адриан; Чен, Юйтянь; Лилликрап, Тимоти; Фан, Хуэй; Сифре, Лоран; Дрише, Джордж ван ден; Грэпель, Тор; Хассабис, Демис (19 октября 2017 г.). «Освоение игры в го без человеческого знания» (PDF). Природа. 550 (7676): 354–359. Bibcode:2017Натура.550..354С. Дои:10.1038 / природа24270. ISSN  0028-0836. PMID  29052630. S2CID  205261034.закрытый доступ
  31. ^ Поиск в дереве игр с динамическим стохастическим управлением стр. 194–195
  32. ^ «5x5 Go решена». Получено 28 января 2016.
  33. ^ На странице 11: «Красмару показывает, что это NP-полное определение статуса определенных ограниченных форм проблем жизни и смерти в го». (См. Следующую ссылку.) Эрик Д. Демейн, Роберт А. Хирн (22 апреля 2008 г.). «Игры с алгоритмами: алгоритмическая комбинаторная теория игр». arXiv:cs / 0106019.
  34. ^ Марсель Красмару (1999). «О сложности Цумэ-Го». Компьютеры и игры. Конспект лекций по информатике. 1558. Лондон, Великобритания: Springer-Verlag. С. 222–231. Дои:10.1007/3-540-48957-6_15. ISBN  978-3-540-65766-8.
  35. ^ "Тройной Ко".
  36. ^ "Четверной Ко".
  37. ^ "Меласса Ко".
  38. ^ "Самогонная жизнь".
  39. ^ "Компьютерное программирование".
  40. ^ «пример слабой игры компьютерной программы». Архивировано из оригинал на 2012-07-10. Получено 2010-08-28.
  41. ^ «Facebook обучает ИИ побеждать людей в настольной игре го - BBC News». Новости BBC. Получено 2016-04-24.
  42. ^ Ормерод, Дэвид (12 марта 2016 г.). «AlphaGo показывает свою истинную силу в третьей победе над Ли Седолом». Go Game Guru. Архивировано из оригинал 13 марта 2016 г.. Получено 12 марта 2016.
  43. ^ "Jellyfish-Go.com". Архивировано из оригинал 3 июля 2007 г.. Получено 28 января 2016.
  44. ^ Мухаммад, Мохсин. Игры на мышление {{| date = 28 января 2020 | bot = InternetArchiveBot | fix -pting = yes}}, Искусственный интеллект 134 (2002): p150
  45. ^ Мюллер, Мартин. Computer Go[постоянная мертвая ссылка ], Искусственный интеллект 134 (2002): с150.
  46. ^ Мюллер, Мартин. Computer Go[постоянная мертвая ссылка ], Искусственный интеллект 134 (2002): 151 с.
  47. ^ а б Мюллер, Мартин. Computer Go[постоянная мертвая ссылка ], Искусственный интеллект 134 (2002): 148 с.
  48. ^ а б «Фуэго».
  49. ^ а б Дэвид Фотланд. «Программное обеспечение Dan Level Go - много граней го».
  50. ^ а б c "Sjeng - шахматы, аудио и прочее программное обеспечение".
  51. ^ а б «Архивная копия». Архивировано из оригинал на 2008-08-10. Получено 2008-06-03.CS1 maint: заархивированная копия как заголовок (связь)
  52. ^ а б «MyGoFriend - золотой призер 15-й компьютерной олимпиады, го (9x9)». Архивировано из оригинал на 2010-12-08.
  53. ^ «UCT».
  54. ^ «Страница не найдена (404)». Архивировано из оригинал на 2007-11-03. Cite использует общий заголовок (помощь)
  55. ^ Дэвид Фотланд. «Умные игры».
  56. ^ «Вычисление рейтингов Эло для паттернов движений в игре го». Получено 28 января 2016.
  57. ^ «Блог исследований: AlphaGo: освоение древней игры го с помощью машинного обучения». Блог Google Research. 27 января 2016 г.
  58. ^ "Страница ON / サ ー ビ ス 終了 の お 知 ら せ". Архивировано из оригинал 11 декабря 2006 г.
  59. ^ "Goban. Играйте в Go на Mac - Sen: te". Архивировано из оригинал на 2013-05-19. Получено 2013-06-14.
  60. ^ "Расширения Goban - Sen: te". Архивировано из оригинал на 2016-05-18. Получено 2013-06-14.
  61. ^ "Go ++, программа Go play". Архивировано из оригинал на 2003-05-25. Получено 2020-07-27.
  62. ^ «Архивная копия». Архивировано из оригинал на 2006-11-28. Получено 2007-02-21.CS1 maint: заархивированная копия как заголовок (связь)
  63. ^ «Пачи - настольная игра го / Вейки / Бадук».
  64. ^ http://www.peepo.com В архиве 2011-09-04 на Wayback Machine
  65. ^ Андерс Керульф. «SmartGo».
  66. ^ "СТИНВРЕТЕР".
  67. ^ "Дзен (иди программа)".
  68. ^ «Турниры Computer Go на KGS».
  69. ^ «Сервер 9x9 Go». Архивировано из оригинал на 2007-01-19. Получено 2007-03-25.
  70. ^ "Желудь 1984 - первый турнир по компьютерному го". computer-go.info.
  71. ^ Дэвид Фотланд. «Чемпионат мира по компьютерному го». Получено 28 января 2016.
  72. ^ Использование GoGUI для игры компьютеров в го друг против друга В архиве 2011-03-09 на Wayback Machine

дальнейшее чтение

внешняя ссылка