Компьютерная Аримаа относится к настольной игре Аримаа с использованием компьютерных программ .
В 2002 году индийско-американский компьютерный инженер Омар Сайед опубликовал правила в Arimaa и объявил о призе в размере 10 000 долларов, который будет доступен ежегодно до 2020 года, за первую компьютерную программу (работающую на стандартном, готовом к использованию оборудовании), способную победить каждого из трех лучших игроков-людей в серии из трех игр. [1] Приз был получен в 2015 году, когда компьютерная программа сыграла 7:2 против трех игроков-людей. [2] Игра стала предметом нескольких исследовательских работ.
Количество различных способов, которыми каждый игрок может расставить свои фигуры в начале игры, составляет:
Игрок может разместить 8 кроликов на 16 возможных квадратах, затем 2 кошек на 8 оставшихся квадратов, 2 собак на 6 оставшихся квадратов, 2 лошадей на четыре оставшихся квадрата, одного верблюда на один из двух оставшихся квадратов и слона на последний неиспользованный квадрат.
Поскольку каждый игрок может начать игру с одной из 64 864 800 начальных конфигураций, общее пространство состояний для начального варианта составляет:
Как сказал Крист-Ян Кокс в своей магистерской диссертации, поскольку число возможных начальных состояний столь велико, «из этого следует, что очень сложно разработать полные базы данных дебютных ходов». [3] [4]
Важно, чтобы компьютер мог оценить ценность фигур на доске, чтобы он мог оценить, будет ли желательным захват или обмен. Оценка относительной ценности фигур является областью текущих исследований Arimaa. Некоторые из используемых в настоящее время систем — DAPE и FAME.
Некоторые или все программы искусственного интеллекта, играющие в Arimaa, используют следующие методы:
Несколько аспектов Arimaa затрудняют для компьютерных программ победу над хорошими игроками-людьми. Поскольку так много усилий было вложено в разработку сильного программного обеспечения для игры в шахматы , особенно важно понять, почему методы, применимые к шахматам, менее эффективны для Arimaa.
Простейшие шахматные программы используют поиск методом грубой силы в сочетании со статической оценкой позиции, в которой доминируют материальные соображения. Они рассматривают множество возможных ходов, но они не очень хороши (по сравнению с людьми) в определении того, кто выигрывает в конце серии ходов, если только у одной стороны нет больше фигур, чем у другой. То же самое относится и к программам Arimaa, но их результаты на практике не столь хороши.
Когда к Arimaa применяется поиск методом грубой силы, глубина поиска ограничена огромным количеством вариантов, которые есть у каждого игрока на каждом ходу. С вычислительной точки зрения количество вариантов, доступных игроку, определяет количество различных путей, по которым может пойти игра. Это известно как фактор ветвления . Средний фактор ветвления в игре в шахматы составляет около 35, [5] тогда как в Arimaa он составляет около 17 000. [6]
Эти различные факторы ветвления означают, что компьютер, который может производить поиск на глубину восьми ходов для каждого игрока в шахматах, может производить поиск только на глубину около трех ходов для каждого игрока в Аримаа:
Глубина поиска методом перебора для шахматного программного обеспечения почти удваивается с помощью альфа-бета-отсечения , что позволяет программному обеспечению делать вывод о том, что один ход лучше другого, не рассматривая каждое возможное продолжение более слабого хода. Если противник может сокрушить определенный ход одним ответом, нет необходимости рассматривать другие ответы, что значительно увеличивает скорость поиска. Однако в Arimaa сторона для хода переключается только каждые четыре шага, что сокращает количество доступных отсечек в пошаговом поиске.
Более того, полезность альфа-бета-отсечения во многом зависит от порядка, в котором рассматриваются ходы. Хорошие ходы должны рассматриваться до плохих, чтобы плохие были проигнорированы. В частности, проверка и захват ходов являются ключевыми для отсечения, потому что они часто намного лучше других ходов. В программном обеспечении Arimaa ускорение, обеспечиваемое альфа-бета-отсечением, меньше, потому что захваты происходят реже. В рейтинговых играх, сыгранных на arimaa.com, только 3% шагов заканчиваются захватом, по сравнению с примерно 19% шахматных ходов, которые заканчиваются захватом.
В большинстве позиций Arimaa, особенно в начале игры, когда доска все еще заполнена, компетентный игрок может избежать потери фигур в течение следующих двух ходов. По сравнению с шахматами Arimaa позволяет любому игроку откладывать взятия на более длительное время. Действительно, медианный номер хода первого взятия в шахматах — ход 6, тогда как в Arimaa — ход 12. В Arimaa борьба изначально более позиционная и вращается вокруг того, чтобы сделать взятия неизбежными в какой-то момент в будущем. Это увеличивает важность правильной оценки того, кто набирает силу нематериальными способами. Таким образом, сила компьютерных программ (исследование миллионов позиций) не так значительна, как их слабость (оценка позиции отдельно от того, у кого больше фигур).
Слабость программ Arimaa в начальных фазах еще больше усиливается фазой настройки. В шахматах каждая игра начинается с одной и той же позиции. Составляя перед игрой список стандартных ответов на все стандартные начальные ходы, шахматные программы часто могут сделать дюжину или более превосходных ходов, прежде чем начать «думать». Люди делают то же самое, но имеют меньшую и менее надежную память об дебютах, что ставит людей в относительно невыгодное положение в шахматах. Arimaa, напротив, имеет миллионы возможных способов расставить фигуры еще до того, как они сделают первый ход. Это не позволяет программам иметь какую-либо осмысленную дебютную книгу.
По мере развития игры обмены и продвижение кроликов, как правило, делают позицию более открытой и тактической. Программы Arimaa обычно играют лучше в таких позициях, потому что они видят тактические удары, которые люди не замечают. Однако люди обычно могут избегать широко открытых позиций консервативной игрой и подбирать стратегические позиции, в которых компьютеры справляются хуже. Против консервативного противника практически невозможно взломать позицию в Arimaa, тогда как в шахматах это просто сложно. Нужно побеждать оборонительную игру накоплением небольших долгосрочных преимуществ, с чем программы справляются не очень хорошо.
Еще одна техника из компьютерных шахмат, которая не применима к Arimaa, — это таблицы эндшпиля . Шахматные игры мастерского уровня иногда переходят в неясные эндшпили всего с несколькими фигурами, например, король и конь против короля и ладьи. С помощью ретроградного анализа можно построить исчерпывающую таблицу правильного хода во всех таких позициях. Программам достаточно лишь свериться с заранее сгенерированной таблицей в таких позициях, а не «думать» заново, что дает им относительное преимущество перед людьми. Arimaa, напротив, редко доходит до эндшпиля. Равные обмены фигурами встречаются реже, чем в шахматах, поэтому редко бывает, чтобы игра Arimaa «перешла в низшую стадию» и все равно оставалась неясной. В средней игре Arimaa всего восемь взятий (по сравнению с семнадцатью в шахматах), и лучшие люди часто могут победить лучшие программы в Arimaa, не потеряв ни одной фигуры, например, вторая игра матча Challenge 2014 года. Еще одним примером низкой плотности захватов является эта полуфинальная игра чемпионата мира 2012 года, в которой был зафиксирован только один захват — жертвоприношение слона с целью добиться цели.
Омар Сайед надеется, что, поскольку традиционные методы искусственного интеллекта лишь умеренно эффективны для Arimaa, программисты будут вынуждены использовать новые методы искусственного интеллекта для создания сильной программы, играющей в Arimaa. Успешные поиски создания шахматной программы уровня чемпионата мира породили множество методов для успешной игры в игры, но по сути ничего не внесли в более общие рассуждения; на самом деле, методы программ, играющих в шахматы, были исключены из некоторых определений искусственного интеллекта ; цель Arimaa заключается в том, чтобы методы, используемые в игре, помогали более масштабным целям искусственного интеллекта.
Структура состязания Сайеда «человек против машины» сосредоточена на поощрении достижений в области программного обеспечения ИИ, а не достижений в области оборудования. В ежегодном состязании программы запускаются на машинах, выбранных и предоставленных самим Сайедом, по критерию, что это должен быть типичный, недорогой, готовый домашний компьютер. Состязание не будет открыто для тех, кому требуются дорогие многопроцессорные машины, такие как те, которые используются для соревнования с шахматистами высшего уровня, не говоря уже о чем-то вроде специально созданного суперкомпьютера Deep Blue , хотя именно успех этого подхода с интенсивным использованием оборудования вдохновил Аримаа на изобретение. Сайед считает, что даже компьютер, использованный в матче-состязании 2004 года (система Pentium 4 2,4 ГГц с 512 МБ ОЗУ), имел достаточно оборудования, чтобы выиграть приз, если бы только на нем работало надлежащее программное обеспечение. Суперкомпьютеры уже могут обладать мощностью, чтобы победить Аримаа методом грубой силы с использованием обычного программного обеспечения ИИ, и в конечном итоге персональные компьютеры тоже будут, если оборудование продолжит совершенствоваться такими же темпами. Вот почему премия «Аримаа» изначально предлагалась только до 2020 года.
Интерфейс Arimaa Engine, разработанный Брайаном Хаскином, определяет протокол, позволяющий движку Arimaa взаимодействовать с контроллером.
Согласно документации: «Движок — это программа, способная брать состояние игры Arimaa и выбирать допустимый ход. Контроллер — это все, что хочет взаимодействовать с движком и управлять им. Это может быть что угодно: от простого скрипта, позволяющего движку анализировать отдельную позицию, до программы с графическим интерфейсом, которая позволяет играть в игры с людьми или другими движками». [7]
Интерфейс Arimaa Engine включает в себя реализацию движка и контроллера, документацию и различные скрипты для управления движком и запуска игр на любом веб-сайте, поддерживающем протокол, включая официальный веб-сайт Arimaa. [8] [9]
