Меню
Главная
Случайная статья
Настройки
|
Компьютерное го — направление искусственного интеллекта по созданию компьютерных программ, играющих в го.
Содержание
Препятствия на пути программ
В течение долгого времени считалось, что компьютерное го имеет существенные различия по сравнению с компьютерными шахматами, поскольку методы, основанные на быстром поиске по сравнению с человеческим опытом, объединённые с относительно низким знанием предметной области не будут эффективны для го. Поэтому большие усилия в области компьютерного го были потрачены на объединение экспертных знаний с локальным поиском для нахождения ответа на вопросы тактической природы игры. Результатом этих усилий были программы, способные находить хорошие решения в некоторых локальных ситуациях, но имевшие явные слабости в полной обработке игры. Кроме того, эти классические программы с увеличением мощности аппаратуры мало получали в плане силы игры и поэтому развитие этой области было в целом медленным. Поэтому считалось, что программа, хорошо играющая в го, может быть создана только в далёком будущем и только с помощью накопленных к тому времени общих знаний в области искусственного интеллекта. Даже написание программы, способной определить победителя в законченной игре, воспринималось как нетривиальная задача.
В 2006 году появились программы, основанные на поиске Монте-Карло. Сила игры искусственного интеллекта улучшилась. Но разрыв с уровнем игры профессиональных игроков в го оставался, и причём значительный.
Однако в 2015 году компьютерная программа (AlphaGo, компании DeepMind) впервые выиграла у профессионала (Фань Хуэя, 2 профессиональный дан) равный матч (со счётом 5—0)[1].
В марте 2016 года AlphaGo победила профессионала Ли Седола в первых трёх партиях из пяти игр.[2] Это был первый случай, когда профессионал 9 дана, один из сильнейших игроков мира, играл с компьютером без гандикапа.[3] В четвёртой игре Ли смог одержать победу, но пятую партию выиграл компьютер, таким образом матч закончился со счетом 41.[4][5] (см. подробно Матч AlphaGo — Ли Седоль)
В мае 2017 года на саммите «Future of Go Summit» был сыгран мини-матч из 3 партий между AlphaGo и одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе, где все партии выиграла программа[6][7][8]. На этом же форуме AlphaGo обыграла команду из 5 профессионалов максимального 9 дана (Ми Ютин[англ.] (№ 3 в рейтинге сильнейших игроков, рейтинг перед матчем 3571 пункт), Чэнь Яое (№ 8, 3513)), Чжоу Жуйян (№ 10, 3509), Си Юэ[англ.] (№ 11, 3508), Тан Вэйсин[кит.] (№ 18, 3474))[9].
Слишком большая доска
Большая доска (19x19, 361 пересечение) часто отмечается как основное препятствие на пути создания сильных го-программ. Проблема большой доски в том, что она препятствует глубокому поиску методом альфа-бета-отсечения.
Пока самой большой доской, на которой к настоящему времени был осуществлён полный перебор позиций является доска 6x7[10].
Большое количество допустимых ходов
По сравнению с шахматами, ходы в го почти не ограничены правилами. В то время как первый ход в шахматах может быть осуществлён двадцатью способами, первый ход в го имеет 55 вариантов, с учётом симметрии доски. После нескольких первых ходов в разных углах доски симметрия игровой ситуации утрачивается и количество возможных ходов возрастает, достигая количества свободных пунктов на доске.
Отсутствие «точной» дебютной теории
Начальная стадия партии в го — фусэки — подчиняется определённым общим принципам развития конфигураций камней, но для неё характерно гораздо большее разнообразие ходов, чем в шахматах. Новинки могут встречаться не на 20-м ходу, а уже на третьем или четвёртом, и грамотная игра в дебюте невозможна без осмысления стратегических перспектив конструкций, возникающих на доске. Дзёсэки (типовые схемы розыгрыша позиции на ограниченной части доски, в частности, в углах), которые в определённом смысле можно считать аналогом разработанных шахматных дебютов, не допускают механического применения и не дают гарантированного результата, поскольку эффект от их использования зависит от общей позиции на всей доске, так что даже выбор подходящего для данной позиции дзёсэки в конкретном углу является сложной интеллектуальной задачей.
Ко-борьба
Правило ко часто приводит к резкому изменению характера борьбы, последствия которой трудно оценить даже опытному игроку. Фактически надо каждый раз соизмерять последствия от «неответа» на ко-угрозу (как свою, так и противника) с ценой проигрыша ко-борьбы. Человеку приходится опираться на свой опыт и интуицию, в то время как для компьютера эти понятия трудно формализуемы.
Аддитивная природа игры
В шахматах, как и во многих других играх, в течение партии фигур на доске становится меньше, что упрощает перебор ходов. В го каждый следующий ход, наоборот, добавляет на доску один камень (хотя возможны и снятия), создавая дополнительные игровые моменты.
Шахматная техника не может быть применена в го
Компьютерные го-программы долгое время были значительно более слабы, чем шахматные программы. Подходы, которые были применены в шахматных программах, показали себя посредственными в компьютерном го.
Шахматные правила легко формализуемы и могут быть представлены машине в удобной форме, которая позволит ей играть на высоком уровне.
Но простые позиционные правила, применяемые в шахматах, не будут эффективны в го[источник не указан 863 дня]. Для определения ценности камня необходим сложный анализ, хотя бы для определения того, жива ли группа, которой он принадлежит, как велико влияние группы и какие опасности ей грозят.
Функция оценки
Ещё одна проблема состоит в создании хорошей оценочной функции для го. На каждом ходу может существовать несколько хороших ходов и чтобы выбрать лучший ход, компьютер должен оценить различные возможные исходы. Это становится трудной задачей в го. Например, может представиться возможность захвата камней противника за счёт укрепления его группы в другом месте. Решение о том, является ли такой обмен выгодным, может показаться слишком тяжёлым даже для игрока-человека. Также может оказаться, что ход в другой части доски и построение там формы может оказаться более важным.
Комбинаторная сложность
Иногда упоминается, что некоторые трудные комбинаторные проблемы (фактически любая NP-полная задача) могут быть преобразованы применительно к го; однако то же верно и для других настольных игр, подобных шахматам, обобщённым для доски произвольной размерности. NP-полные задачи не могут решаться людьми быстрее, чем компьютерами: сомнительно, что человек в состоянии, например, решить Задачу коммивояжёра за время, сопоставимое с тем, за которое её решает компьютер. Следовательно, возможность применить методы решения NP-полных задач к компьютерному го не позволяет объяснить превосходства человека над компьютером в этой игре.
Завершение игры
Учитывая, что завершающая стадия игры го (ёсэ) содержит меньшее количество возможных ходов, чем начало или середина, можно было бы предположить, что компьютеру будет намного легче играть эту часть игры. Но и здесь нашлось место для проблем:
- Окончание партии в го — самая «математическая» часть партии; в ней почти каждому ходу можно дать оценку с точки зрения количества приносимых ходом очков. Тем не менее, и эта стадия оказывается компьютеру не по зубам — во многом из-за ко-борьбы, неожиданно возникающей в вариантах тактики, а также вследствие трудностей, связанных с численной оценкой понятия инициативы. В отличие от шахмат, в го к концу игры доска не освобождается от фигур, а тесно заполняется камнями — что делает невозможным создание глобальных баз данных для окончаний.
- Ёсэ может повлечь за собой рассмотрение таких аспектов го, как «жизнь и смерть», которые являются NP-полными.
- Каждая область, рассматриваемая в ёсэ, может затрагивать другие области, или повлечь к изменениям в общей картине игры. Это приводит к таким непростым даже для человека ситуациям, как Тройное ко, учетверённое ко и им подобные.
Таким образом очень сложно запрограммировать эффективный алгоритм даже для игры завершающей стадии го, не говоря обо всей партии[11].
Почему люди играли в го лучше компьютера
|
|