Компьютер Go - Computer Go

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

Представление

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

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

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

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

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

В апреле 1981 года Джонатан Миллен опубликовал в Byte статью, в которой обсуждалась Wally, программа Go с платой 15x15, которая умещалась в 1K RAM микрокомпьютера KIM-1 . Брюс Ф. Вебстер опубликовал в журнале статью в ноябре 1984 года, в которой обсуждал программу Go, которую он написал для Apple Macintosh , включая исходный код MacFORTH .

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

21-го века

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

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

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

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

В 2013 году Crazy Stone победил Йошио Исида (9 очков) в игре 19 × 19 с форой в четыре камня.

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

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

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

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

В мае 2017 года AlphaGo победила Ке Джи , который на тот момент занимал первое место в мире, в матче из трех игр на Future of Go Summit .

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

Поскольку основные принципы AlphaGo были опубликованы в журнале Nature , другие команды смогли создавать программы высокого уровня. К 2017 году и Zen, и проект Tencent Fine Art были способны иногда побеждать профессионалов очень высокого уровня, и был выпущен движок Leela Zero с открытым исходным кодом .

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

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

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

Размер доски

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

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

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

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

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

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

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

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

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

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

Эндшпиль

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

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

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

  • Даже если компьютер может безупречно воспроизвести каждую локальную зону эндшпиля, мы не можем сделать вывод, что его игра будет безупречной в отношении всей доски. Дополнительные области рассмотрения в эндшпиле включают отношения сэнтэ и готэ , приоритизацию различных локальных эндшпилей, подсчет и оценку территорий и так далее.
  • Финал может включать многие другие аспекты го, включая «жизнь и смерть», которые также известны как NP-трудные .
  • Каждая из локальных зон эндшпиля может влиять друг на друга. Другими словами, они динамичны по своей природе, хотя визуально изолированы. Это затрудняет рассуждение как для компьютеров, так и для людей. Такая природа приводит к некоторым сложным ситуациям, таким как тройное ко, четверное ко, мелассовое ко и самогонная жизнь.

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

Порядок игры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует несколько методов, которые могут значительно улучшить производительность деревьев поиска как с точки зрения скорости, так и с точки зрения памяти. Такие методы отсечения , как альфа-бета-отсечение , поиск основных вариаций и MTD (f), могут снизить эффективный фактор ветвления без потери прочности. В тактических областях, таких как жизнь и смерть, Go особенно подходит для таких методов кэширования, как таблицы транспонирования . Это может уменьшить количество повторяемых усилий, особенно в сочетании с итеративным подходом к углублению . Чтобы быстро сохранить полноразмерную доску Go в таблице транспонирования, обычно требуется метод хеширования для математического обобщения. Хеширование Zobrist очень популярно в программах Go, потому что оно имеет низкую частоту конфликтов и может итеративно обновляться на каждом шаге с помощью всего двух операций XOR , а не вычисляться с нуля. Даже при использовании этих методов повышения производительности полный поиск по дереву на полноразмерной плате по-прежнему слишком медленный. Поиски можно ускорить, используя большое количество техник отсечения, зависящих от предметной области, например, игнорирование ходов, когда ваш противник уже силен, и выборочные расширения, такие как постоянный учет ходов рядом с группами камней, которые собираются захватить . Однако оба этих варианта сопряжены со значительным риском игнорирования жизненно важного шага, который изменил бы ход игры.

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

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

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

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

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

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

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

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

Одной из основных альтернатив использования знаний и поиска, закодированных вручную, является использование методов Монте-Карло . Это делается путем создания списка возможных ходов, и для каждого хода разыгрываются тысячи игр в случайном порядке на получившейся доске. Ход, который приводит к лучшему набору случайных игр для текущего игрока, выбирается как лучший ход. Преимущество этого метода состоит в том, что он требует очень мало знаний в предметной области или участия экспертов, а компромисс заключается в увеличении требований к памяти и процессору. Однако, поскольку ходы, используемые для оценки, генерируются случайным образом, возможно, что ход, который был бы отличным, за исключением одного конкретного ответа оппонента, был бы ошибочно оценен как хороший ход. Результатом этого являются программы, которые сильны в общем стратегическом смысле, но несовершенны в тактическом плане. Эту проблему можно смягчить, добавив некоторые знания предметной области при генерации ходов и увеличив глубину поиска поверх случайной эволюции. Некоторые программы, использующие методы Монте-Карло, - это Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend и Zen.

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

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

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

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

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

AlphaGo

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

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

  • AlphaGo , первая компьютерная программа, выигравшая в равных матчах с профессиональным игроком в го.
  • АЯ Хироши Ямасита
  • BaduGI, автор Jooyoung Lee
  • Crazy Stone от Реми Кулом (продается как Saikyo no Igo в Японии)
  • Darkforest от Facebook
  • Изобразительное искусство от Tencent
  • Fuego, программа Монте-Карло с открытым исходным кодом
  • Goban, программа Macintosh OS X Go от Sen: te (требуются бесплатные расширения Goban)
  • GNU Go , классическая программа Go с открытым исходным кодом
  • Go ++ Майкла Рейсса (продается как Strongest Go или Tuyoi Igo в Японии)
  • Лила , первая публичная программа Монте-Карло.
  • Лила Зеро , повторная реализация системы, описанной в статье AlphaGo Zero
  • Многоликая го, Дэвид Фотланд (продается как AI Igo в Японии)
  • MyGoFriend, Фрэнк Каргер
  • MoGo Сильвена Гелли; параллельная версия многими людьми.
  • Программа Монте-Карло с открытым исходным кодом Pachi от Петра Баудиша, онлайн-версия Peepo от Джонатана Четвинда, с картами и комментариями во время игры
  • Smart Go от Андерса Керульфа, изобретателя формата Smart Game
  • Steenvreter Эрика ван дер Верфа
  • Дзен от Ёдзи Одзимы, он же Ямато (продается как Тэнчо но Иго в Японии); параллельная версия Хидеки Като.

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

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

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

История

Первые соревнования по компьютерному Го спонсировала Acornsoft , а первые регулярные соревнования - 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 тайваньских долларов за победу в матче с гандикапом с 11 стоунами против трех 11–13-летних любителей со 2–6 данами. На момент истечения срока действия приза в 2000 году невостребованный приз составлял 400 000 новых тайваньских долларов за победу в матче с гандикапом с девятью камнями.

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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

внешние ссылки