✖


Jump to content

Компьютер Го

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

Компьютерное Го — это область искусственного интеллекта (ИИ), посвященная созданию компьютерной программы , играющей в традиционную настольную игру Го . Поле резко разделено на две эпохи. До 2015 года программы той эпохи были слабыми. Лучшие усилия 1980-х и 1990-х годов создавали только ИИ, которые могли победить новички, а ИИ начала 2000-х годов были в лучшем случае промежуточным уровнем. Профессионалы могли бы победить эти программы даже с учетом форы в 10+ камней в пользу ИИ. Многие из алгоритмов, таких как альфа-бета-минимакс , которые хорошо работали в качестве ИИ для шашек и шахмат, развалились на доске Го 19x19, поскольку было слишком много возможностей ветвления, чтобы их можно было учитывать. Создание программы профессионального качества человека с использованием технологий и оборудования того времени было недостижимо. Некоторые исследователи ИИ предположили, что проблема неразрешима без создания человекоподобного ИИ .

Применение поиска по дереву Монте-Карло к алгоритмам Go обеспечило заметное улучшение в конце 2000-х годов , когда программы наконец смогли достичь низкого уровня : уровня продвинутого любителя. Любители и профессионалы с высоким даном все еще могли использовать слабости этих программ и стабильно побеждать, но производительность компьютеров уже превысила средний (однозначный кю ) уровень. Дразнящая невыполненная цель победить лучших игроков-людей без каких-либо недостатков, которую долгое время считали недостижимой, вызвала новый всплеск интереса. Ключевой идеей оказалось применение машинного и глубокого обучения . DeepMind , приобретение Google , занимающееся исследованиями в области искусственного интеллекта, выпустило AlphaGo в 2015 году и объявило о нем миру в 2016 году. AlphaGo победила Ли Седоля , профессионала с 9 даном, в матче без гандикапа в 2016 году, а затем победила Ке Цзе в 2017 году , который в то время в течение двух лет непрерывно занимал первое место в мировом рейтинге. Подобно тому, как шашки уступили место машинам в 1995 году , а шахматы — в 1997 году , компьютерные программы наконец победили величайших чемпионов человечества по го в 2016–2017 годах. DeepMind не выпускала AlphaGo для публичного использования, но с тех пор были созданы различные программы на основе опубликованных DeepMind журнальных статей с описанием AlphaGo и его вариантов.

Обзор и история [ править ]

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

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

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

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

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

статью В апреле 1981 года Джонатан К. Миллен опубликовал в журнале Byte , в которой обсуждалась Wally, программа Go с платой 15x15, которая помещалась в KIM-1 . 1 КБ ОЗУ микрокомпьютера [10] Брюс Ф. Вебстер опубликовал в журнале в ноябре 1984 года статью, в которой обсуждалась программа Go, которую он написал для Apple Macintosh , включая исходный код MacFORTH . [11] Программы для Go были слабыми; в статье 1983 года было подсчитано, что они в лучшем случае были эквивалентны 20 кю , рейтингу наивного начинающего игрока, и часто ограничивались досками меньшего размера. [12] ИИ, игравшие на сервере Internet Go (IGS) на досках размером 19x19, в 2003 году имели силу около 20–15 кю , после существенных улучшений аппаратного обеспечения. [13]

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

: Поиск по дереву Монте 2007–2014 - Карло

В 2006 году (со статьей, опубликованной в 2007 году) Реми Кулом разработал новый алгоритм, который он назвал поиском по дереву Монте-Карло . [16] В нем, как обычно, создается игровое дерево потенциальных вариантов будущего, которые разветвляются с каждым ходом. Однако компьютеры «засчитывают» конечный лист дерева путем повторяющихся случайных игр (аналогично стратегиям Монте-Карло для других задач). Преимущество в том, что такие случайные плейауты можно проводить очень быстро. Интуитивное возражение о том, что случайные результаты не соответствуют фактической стоимости позиции, оказалось не столь фатальным для процедуры, как ожидалось; часть алгоритма «поиск по дереву» исправлена ​​достаточно хорошо, чтобы находить разумные будущие игровые деревья для исследования. Программы, основанные на этом методе, такие как MoGo и Fuego, показали лучшую производительность, чем классические ИИ, существовавшие ранее. Лучшие программы могли особенно хорошо работать на маленькой доске 9x9, у которой было меньше возможностей для исследования. В 2009 году появились первые подобные программы, способные достигать и удерживать ранги низкого уровня дан на сервере KGS Go на плате 19х19.

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

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

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

В 2013 году Crazy Stone обыграл Ёсио Исиду (9 очков) в игре 19х19 с гандикапом в четыре камня. [20]

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

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

Дополнительная информация: AlphaGo , AlphaGo против Фань Хуэя , AlphaGo против Ли Седоля и AlphaGo против Ке Цзе.

AlphaGo , разработанная Google DeepMind , стала значительным шагом вперед в компьютерной мощности по сравнению с предыдущими программами Go. В нем использовались методы, сочетающие глубокое обучение и поиск по дереву Монте-Карло . [22] В октябре 2015 года она победила Фань Хуэя , чемпиона Европы по го. пять раз из пяти в турнирных условиях [23] В марте 2016 года AlphaGo обыграла Ли Седоля в первых трех матчах из пяти. [24] Это был первый раз, когда мастер с 9 даном сыграл профессиональную игру против компьютера без каких-либо ограничений. [25] Ли выиграл четвертый матч, назвав свою победу «бесценной». [26] Два дня спустя AlphaGo выиграла финальный матч. [27] [28] Благодаря этой победе AlphaGo стала первой программой, которая обыграла человека-профессионала с 9 даном в игре без гандикапов на полноразмерной доске.

В мае 2017 года AlphaGo обыграла Кэ Цзе , который на тот момент занимал первое место в мире. [29] [30] в матче из трёх игр во время Future of Go Summit . [31]

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

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

стратегии и производительности классических Проблемы ИИ

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

Размер доски

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

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

Количество вариантов хода

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

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

Одна из самых основных задач в игре — оценить положение на доске: какая сторона имеет преимущество и насколько? В шахматах многие будущие позиции в дереве являются прямыми победами одной стороны, и доски имеют разумную эвристику для оценки при простом подсчете материала, а также определенные позиционные факторы, такие как пешечная структура. Будущее, в котором одна сторона без всякой выгоды потеряла свою королеву, явно благоприятствует другой стороне. Эти типы правил позиционной оценки не могут быть эффективно применены к Го. Ценность позиции Го зависит от комплексного анализа, позволяющего определить, жива ли группа, какие камни могут быть связаны друг с другом, а также от эвристики, определяющей степень влияния сильной позиции или степень влияния слабой позиции. позиция может быть атакована. Размещенный камень может не иметь немедленного влияния, но после многих ходов может стать очень важным в ретроспективе, когда формируются другие области доски.

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

Жизнь и смерть

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

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

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

Проектирование системы [ править ]

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

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

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

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

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

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

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

Новички часто учатся на игровых записях старых игр, в которые играли опытные игроки. Работа над искусственным интеллектом в 1990-е годы часто включала попытки «обучить» искусственный интеллект человеческим эвристическим знаниям го. В 1996 году Тим Клингер и Дэвид Мехнер признали силу лучших ИИ на начальном уровне и заявили, что «мы убеждены, что с лучшими инструментами для представления и поддержания знаний Го можно будет разрабатывать более сильные программы Го». [34] Они предложили два пути: распознать общие конфигурации камней и их положения и сконцентрироваться на локальных сражениях. В 2001 году в одной статье был сделан вывод, что «программам Go по-прежнему не хватает качества и количества знаний», и что исправление этой проблемы улучшит производительность Go AI. [35]

Теоретически использование экспертных знаний могло бы улучшить программное обеспечение Go. Сотни рекомендаций и практических правил сильной игры были сформулированы как любителями, так и профессионалами высокого уровня. Задача программиста — взять эти эвристики , формализовать их в компьютерный код и использовать алгоритмы сопоставления и распознавания образов, чтобы определить, когда эти правила применяются. Также важно иметь возможность «оценивать» эти эвристики, чтобы, когда они предлагают противоречивые рекомендации, у системы были способы определить, какая эвристика более важна и применима к ситуации. Большинство относительно успешных результатов обусловлены индивидуальными навыками программистов в Go и их личными предположениями о Go, а не формальными математическими утверждениями; они пытаются заставить компьютер имитировать то, как они играют в го. Соревновательные программы примерно 2001 года могли содержать 50–100 модулей, посвященных различным аспектам и стратегиям игры, например дзёсэки. [35]

Некоторыми примерами программ, которые в значительной степени полагались на экспертные знания, являются Handtalk (позже известный как Goemate), The Multiple Faces of Go, Go Intellect и Go++, каждая из которых в какой-то момент считалась лучшей программой Go в мире. Однако в конечном итоге эти методы имели уменьшающуюся отдачу и никогда не продвигались дальше промежуточного уровня, в лучшем случае на полноразмерной доске. Одной из особых проблем была общая стратегия игры. Даже если экспертная система распознает закономерность и знает, как разыграть локальную стычку, она может упустить из виду надвигающуюся более глубокую стратегическую проблему в будущем. В результате получается программа, мощность которой меньше суммы ее частей; Хотя ходы могут быть хороши с точки зрения индивидуальной тактики, программу можно обмануть и заставить уступить слишком много в обмен, и она окажется в общей проигрышной позиции. Как показало исследование 2001 года, «всего один плохой ход может испортить хорошую игру. Производительность программы в течение всей игры может быть намного ниже мастерского уровня». [35]

Методы Монте-Карло [ править ]

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

Одной из основных альтернатив использованию знаний и поиска, закодированных вручную, является использование методов Монте-Карло . Это делается путем создания списка потенциальных ходов и для каждого хода на полученной доске случайным образом разыгрываются тысячи игр. Ход, который приводит к наилучшему набору случайных игр для текущего игрока, выбирается как лучший ход. Никакой потенциально ошибочной системы, основанной на знаниях, не требуется. Однако, поскольку ходы, используемые для оценки, генерируются случайным образом, возможно, что ход, который был бы отличным, за исключением одного конкретного ответа противника, был бы ошибочно оценен как хороший ход. Результатом этого являются программы, которые сильны в общем стратегическом смысле, но несовершенны тактически. [ нужна ссылка ] Эту проблему можно смягчить, добавив некоторые знания предметной области при генерации ходов и более высокий уровень глубины поиска поверх случайной эволюции. Некоторые программы, использующие методы Монте-Карло, — это Fuego, [36] Многоликий Го v12, [37] Лила, [38] MoGo, [39] Сумасшедший камень , MyGoFriend, [40] и Дзен.

В 2006 году появился новый метод поиска: верхние доверительные границы, применяемые к деревьям (UCT), [41] был разработан и применен во многих программах 9х9 Монте-Карло Го с отличными результатами. UCT использует результаты собранных на данный момент результатов игр , чтобы направлять поиск по наиболее успешным направлениям игры, в то же время позволяя исследовать альтернативные варианты. Методика UCT вместе со многими другими оптимизациями для игры на доске большего размера 19x19 позволила MoGo стать одной из самых сильных исследовательских программ. Успешные ранние применения методов UCT в 19x19 Go включают MoGo, Crazy Stone и Mango. [42] MoGo выиграл Компьютерную олимпиаду 2007 года и выиграл одну (из трёх) блиц-партию у Го Хуана, 5-го дана-профессионала, в гораздо менее сложной игре 9х9 Го. Многоликий го [43] выиграла Компьютерную олимпиаду 2008 года после добавления поиска UCT к своей традиционной системе, основанной на знаниях.

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

Машинное обучение [ править ]

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

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

Самый известный пример такого подхода — AlphaGo, который оказался гораздо более эффективным, чем предыдущие ИИ. В своей первой версии он имел один уровень, который анализировал миллионы существующих позиций, чтобы определить вероятные ходы, которые необходимо расставить по приоритетам как достойные дальнейшего анализа, и другой уровень, который пытался оптимизировать свои собственные шансы на выигрыш, используя предложенные вероятные ходы из первого уровня. AlphaGo использовала поиск по дереву Монте-Карло для оценки полученных позиций. Более поздняя версия AlphaGo, AlphaGoZero, избегала обучения в существующих играх Го и вместо этого обучалась только путем неоднократной игры в себя. Другие более ранние программы, использующие нейронные сети, включают NeuroGo и WinHonte.

Computer Go и другие области [ править ]

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

Джон Х. Конвей предложил применять сюрреалистические числа для анализа эндшпиля в го. Эта идея была далее развита Элвином Р. Берлекэмпом и Дэвидом Вулфом в их книге Mathematical Go . [48] Доказано, что эндшпиль в го является PSPACE-сложным , если абсолютный лучший ход должен быть рассчитан на произвольной, почти полностью заполненной доске. Некоторые сложные ситуации, такие как Triple Ko, Quadruple Ko, Molasses Ko и Moonshine Life, усложняют эту задачу. [49] (На практике сильные алгоритмы Монте-Карло все еще могут достаточно хорошо справляться с обычными ситуациями эндшпиля в Го, а самые сложные классы задач эндшпиля, требующие жизни и смерти, вряд ли возникнут в игре высокого уровня.) [50]

Различные сложные комбинаторные задачи (любая NP-трудная задача) могут быть преобразованы в задачи типа Го на достаточно большой доске; однако то же самое верно и для других абстрактных настольных игр, включая шахматы и «Сапер» , если их соответствующим образом обобщить на доску произвольного размера. NP-полные задачи в общем случае не кажутся более простыми для людей без посторонней помощи, чем для правильно запрограммированных компьютеров: люди без посторонней помощи намного хуже, чем компьютеры, решают, например, примеры задачи о сумме подмножества . [51] [52]

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

См. также: Программное обеспечение Go
  • AlphaGo — программа машинного обучения от Google DeepMind и первая компьютерная программа, выигравшая в матчах без гандикапа человека, играющего в го с 9 даном.
  • BaduGI, программа Джуён Ли [53]
  • Crazy Stone , Реми Кулом (продается в Японии как Saikyo no Igo)
  • Темный лес , Facebook
  • Изобразительное искусство от Tencent
  • Fuego, с открытым исходным кодом. программа Монте-Карло [36]
  • Goban, программа Go для Macintosh от Sen:te (требуются бесплатные расширения Goban) [54]
  • GNU Go — классическая программа Go с открытым исходным кодом.
  • KataGo , Дэвид Ву.
  • Лила , первая программа Монте-Карло, выставленная на продажу публике [38]
  • Leela Zero , повторная реализация системы, описанной в статье AlphaGo Zero. [38]
  • «Многоликость го» Дэвида Фотланда (продается в Японии как AI Igo) [37]
  • MyGoFriend, программа Фрэнка Каргера [40]
  • MoGo Сильвена Джелли; параллельная версия многих людей. [55] [39]
  • Pachi, программа Монте-Карло с открытым исходным кодом Петра Баудиша. [56]
  • Smart Go, автор Андерс Кирульф, изобретатель формата смарт-игр [57]
  • Стеенвретер, Эрик ван дер Верф [58]
  • Дзен Ёдзи Одзимы, он же Ямато (продается в Японии как Tencho no Igo, параллельная версия Хидеки Като); [59]

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

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

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

История [ править ]

Первые компьютерные соревнования по Го спонсировались компанией Acornsoft . [62] и первые обычные от USENIX . Они проводились с 1984 по 1988 год. На этих соревнованиях были представлены «Немезида», первая соревновательная программа го Брюса Уилкокса , и G2.5 Дэвида Фотланда, которая позже превратилась в «Космос» и «Многоликость го».

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

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

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

Формализация подсчета очков в компьютерно-компьютерных играх [ править ]

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Мец, Кейд (9 марта 2016 г.). «ИИ Google выиграл первую игру в историческом матче с чемпионом по го» . ПРОВОДНОЙ .
  2. ^ «AlphaGo снова победила» . 10 марта 2016 г.
  3. ^ Бузи, Бруно; Казенав, Тристан (9 августа 2001 г.). «Computer Go: опрос, ориентированный на искусственный интеллект». Искусственный интеллект . 132 (1): 39–103. дои : 10.1016/S0004-3702(01)00127-8 .
  4. ^ Джонсон, Джордж (29 июля 1997 г.), «Чтобы протестировать мощный компьютер, сыграйте в древнюю игру» , The New York Times , получено 16 июня 2008 г.
  5. ^ «Иди, Джек Гуд» .
  6. ^ Сильвер, Дэвид ; Хуанг, Аджа ; Мэддисон, Крис Дж.; Гез, Артур; Сифре, Лоран; Дрессе, Джордж ван ден; Шритвизер, Джулиан; Антоноглу, Иоаннис; Паннеершелвам, Веда; Ланкто, Марк; Дилеман, Сандер; Греве, Доминик; Нэм, Джон; Кальхбреннер, Нал; Суцкевер, Илья ; Лилликрап, Тимоти; Лич, Мадлен; Кавукчуоглу, Корай; Грепель, Торе; Хассабис, Демис (28 января 2016 г.). «Освоение игры в го с помощью глубоких нейронных сетей и поиска по дереву». Природа . 529 (7587): 484–489. Бибкод : 2016Natur.529..484S . дои : 10.1038/nature16961 . ISSN   0028-0836 . ПМИД   26819042 . S2CID   515925 . Значок закрытого доступа
  7. ^ Уэдд, Ник. «Задачи человеко-компьютерного взаимодействия» . компьютер-go.info . Проверено 28 октября 2011 г.
  8. ^ « Огромный скачок вперед»: компьютер, имитирующий человеческий мозг, побеждает профессионала в игре в го» .
  9. ^ Альберт Зобрист (1970), Извлечение и представление функций для распознавания образов и игры в го . доктор философии Диссертация (152 стр.), Университет Висконсина. Также опубликовано в виде технического отчета.
  10. ^ Миллен, Джонатан К. (апрель 1981 г.). «Программирование игры Го» . Байт . п. 102 . Проверено 18 октября 2013 г.
  11. ^ Вебстер, Брюс (ноябрь 1984 г.). «Go Board для Macintosh» . Байт . п. 125 . Проверено 23 октября 2013 г.
  12. ^ Кэмпбелл, Дж. А. (1983). «Часть III: Введение в Go». В Брамере, Массачусетс (ред.). Компьютерные игры: теория и практика . Эллис Хорвуд Лимитед. п. 138. ИСБН  0-85312-488-4 .
  13. ^ Шотвелл, Питер (2003). Идти! Больше, чем игра . Издательство Таттл. п. 164. ИСБН  0-8048-3475-Х .
  14. ^ «Отчет о компьютерных технологиях CS-TR-339» . Архивировано из оригинала 4 февраля 2014 года . Проверено 28 января 2016 г.
  15. ^ См., например, intgofed.org. Архивировано 28 мая 2008 г., на Wayback Machine.
  16. ^ Реми Кулом (2007). «Эффективные операторы избирательности и резервного копирования в поиске по дереву Монте-Карло». Компьютеры и игры, 5-я Международная конференция, CG 2006, Турин, Италия, 29–31 мая 2006 г. Пересмотренные статьи . Х. Яап ван ден Херик, Паоло Чианкарини, HHLM Донкерс (ред.). Спрингер. стр. 72–83. CiteSeerX   10.1.1.81.6817 . ISBN  978-3-540-75537-1 .
  17. ^ «Новости EGC 2010 Тампере» . Архивировано из оригинала 14 августа 2009 года . Проверено 28 января 2016 г.
  18. ^ «Архив игр KGS» . Проверено 28 января 2016 г.
  19. ^ «Программа Zen Computer Go побеждает Такемию Масаки всего с 4 камнями!» . Иди, гуру игры . Архивировано из оригинала 1 февраля 2016 г. Проверено 28 января 2016 г.
  20. ^ «Сила любителя с 6 даном. Он может быть гением». Игрок в го проигрывает компьютеру в первом официальном матче» . Архивировано из оригинала 24 марта 2013 г. Проверено 27 марта 2013 г.
  21. ^ «codecentric go Challenge — еще один сайт WordPress» . Проверено 28 января 2016 г.
  22. ^ «Исследовательский блог: AlphaGo: освоение древней игры го с помощью машинного обучения» . Блог исследований Google . 27 января 2016 г.
  23. ^ Гибни, Элизабет (2016). «Алгоритм Google AI освоил древнюю игру го» . Новости природы и комментарии . 529 (7587): 445–446. Бибкод : 2016Natur.529..445G . дои : 10.1038/529445а . ПМИД   26819021 . S2CID   4460235 .
  24. ^ «Искусственный интеллект: AlphaGo от Google превосходит мастера го Ли Се Доля» . Новости BBC онлайн . 12 марта 2016 года . Проверено 12 марта 2016 г.
  25. ^ «Компания Google DeepMind одержала историческую победу над легендарным игроком в го Ли Седолем» . www.theverge.com. 9 марта 2016 года . Проверено 9 марта 2016 г.
  26. ^ «Искусственный интеллект: мастер го Ли Седол побеждает программу AlphaGo» . Новости BBC онлайн . 13 марта 2016 года . Проверено 13 марта 2016 г.
  27. ^ «ИИ AlphaGo от Google снова обыграл Ли Се Доля и выиграл серию Го со счетом 4–1» . Грань . 15 марта 2016 года . Проверено 15 марта 2016 г.
  28. ^ Мец, Кейд (27 мая 2017 г.). «После победы в Китае дизайнеры AlphaGo изучают новый искусственный интеллект» . Проводной .
  29. ^ «Мировые рейтинги игроков в го» . Май 2017.
  30. ^ «Ке Цзе празднует свой 19-й день рождения и уже два года занимает первое место в человеческом мире» (на китайском языке, май 2017 г.).
  31. ^ Мец, Кейд (25 мая 2017 г.). «Google AlphaGo продолжает доминировать, одержав вторую победу в Китае» . Проводной .
  32. ^ Сильвер, Дэвид ; Шритвизер, Джулиан; Симонян, Карен; Антоноглу, Иоаннис; Хуанг, Аджа ; Гез, Артур; Юбер, Томас; Бейкер, Лукас; Лай, Мэтью; Болтон, Адриан; Чен, Ютянь ; Лилликрап, Тимоти; Фань, Хуэй ; Сифре, Лоран; Дрессе, Джордж ван ден; Грепель, Торе; Хассабис, Демис (19 октября 2017 г.). «Освоение игры в го без ведома человека» (PDF) . Природа . 550 (7676): 354–359. Бибкод : 2017Natur.550..354S . дои : 10.1038/nature24270 . ISSN   0028-0836 . ПМИД   29052630 . S2CID   205261034 . Значок закрытого доступа
  33. ^ «5х5 Го решена» . Проверено 28 января 2016 г.
  34. ^ Клингер, Тим и Мехнер, Дэвид. Архитектура для компьютера Go (1996)
  35. ^ Jump up to: Перейти обратно: а б с д Мюллер, Мартин (январь 2002 г.). «Компьютер Гоу». Искусственный интеллект . 134 (1–2): 148–151. дои : 10.1016/S0004-3702(01)00121-7 .
  36. ^ Jump up to: Перейти обратно: а б «Фуэго» .
  37. ^ Jump up to: Перейти обратно: а б Дэвид Фотланд. «Программное обеспечение Dan Level Go – многообразие Go» .
  38. ^ Jump up to: Перейти обратно: а б с «Сженг – шахматы, аудио и прочее программное обеспечение» .
  39. ^ Jump up to: Перейти обратно: а б «Архивная копия» . Архивировано из оригинала 10 августа 2008 г. Проверено 3 июня 2008 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
  40. ^ Jump up to: Перейти обратно: а б «MyGoFriend – золотой медалист 15-й компьютерной олимпиады по игре Го (9х9)» . Архивировано из оригинала 8 декабря 2010 г.
  41. ^ «ЮКТ» .
  42. ^ "Манго" . Архивировано из оригинала 3 ноября 2007 г.
  43. ^ Дэвид Фотланд. «Умные игры» .
  44. ^ «Facebook обучает ИИ побеждать людей в настольной игре го – BBC News» . Новости Би-би-си . 27 января 2016 года . Проверено 24 апреля 2016 г.
  45. ^ Ормерод, Дэвид (12 марта 2016 г.). «AlphaGo показывает свою истинную силу в третьей победе над Ли Седолем» . Иди, гуру игры. Архивировано из оригинала 13 марта 2016 года . Проверено 12 марта 2016 г.
  46. ^ «Вычисление рейтингов Эло моделей ходов в игре Го» . Проверено 28 января 2016 г.
  47. ^ Мухаммад, Мохсин. Мыслительные игры , Искусственный интеллект 134 (2002): стр. 150.
  48. ^ Берлекамп, Элвин ; Вулф, Дэвид (1994). Математическая игра: охлаждение достигает последней точки . Тейлор и Фрэнсис. ISBN  978-1-56881-032-4 .
  49. ^
  50. ^ «Компьютерное программирование Go» .
  51. ^ На странице 11: «Красмару показывает, что NP-полно для определения статуса некоторых ограниченных форм задач жизни и смерти в Го». (См. следующую ссылку.) Эрик Д. Демейн, Роберт А. Хирн (22 апреля 2008 г.). «Игры с алгоритмами: алгоритмико-комбинаторная теория игр». arXiv : cs/0106019 .
  52. ^ Марсель Красмару (1999). «О сложности Цумэ-го». Компьютеры и игры . Конспекты лекций по информатике. Том. 1558. Лондон, Великобритания: Springer-Verlag . стр. 222–231. дои : 10.1007/3-540-48957-6_15 . ISBN  978-3-540-65766-8 .
  53. ^ БадуГИ
  54. ^
  55. ^ «Домашняя страница Сильвена ГЕЛЛИ» . Архивировано из оригинала 28 ноября 2006 г. Проверено 21 февраля 2007 г.
  56. ^ «Пачи — настольная игра Го/Вэйци/Бадук» .
  57. ^ Андерс Кирульф. «Умный ход» .
  58. ^ «СТИНВРЕТЕР» .
  59. ^ «Дзен (программа го)» .
  60. ^ «Турниры по компьютерному го на СОМ» .
  61. ^ «Сервер 9x9 Go» . Архивировано из оригинала 19 января 2007 г. Проверено 25 марта 2007 г.
  62. ^ «Жёлудь 1984. Первый турнир по компьютерному го» . компьютер-go.info .
  63. ^ Дэвид Фотланд. «Чемпионат мира по компьютерному го» . Проверено 28 января 2016 г.

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

В Wikibooks есть книга на тему: Computer Go.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Computer_Go&oldid=1219939188"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cee880548c338b72276154d02f894bfe__1713634140
URL1:https://arc.ask3.ru/arc/aa/ce/fe/cee880548c338b72276154d02f894bfe.html
Заголовок, (Title) документа по адресу, URL1:
Computer Go - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)