Компьютер Аримаа

Компьютерное Аримаа означает игру в настольную игру Аримаа с помощью компьютерных программ .

В 2002 году индийско-американский компьютерный инженер Омар Сайед опубликовал правила для Arimaa и объявил приз в размере 10 000 долларов, который будет разыгрываться ежегодно до 2020 года, за первую компьютерную программу (работающую на стандартном, готовом оборудовании), способную победить каждую из трех лучших программ. - ранжирование игроков-людей в серии из трех игр. Приз был получен в 2015 году, когда компьютерная программа сыграла 7:2 против трёх игроков-людей. Игра стала предметом нескольких исследовательских работ .

Государственное пространство Аримаа

Открытие

Количество различных способов, которыми каждый игрок может расставить свои фигуры в начале игры, равно:

${\dbinom {16}{8}}\cdot {\dbinom {8}{2}}\cdot {\dbinom {6}{2}}\cdot {\dbinom {4}{2}}\cdot {\dbinom {2}{1}}\cdot {\dbinom {1}{1}}=64{,}864{,}800$

Игрок может разместить 8 кроликов на 16 возможных клетках, затем 2 кошек на 8 оставшихся клеток, 2 собак на 6 оставшихся клеток, 2 лошадей на четыре оставшихся клетки, одного верблюда на одну из двух оставшихся клеток и слона. на последнем неиспользуемом квадрате.

Поскольку каждый игрок может начать игру с одной из 64 864 800 дебютных расстановок, общее пространство состояний для дебюта составляет:

$64{,}864{,}800^{2}\approx 4.2\cdot 10^{15}$

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

Методы искусственного интеллекта

Оценка материала

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

Техники, используемые в ботах Arimaa

Следующие методы используются некоторыми или всеми программами искусственного интеллекта, играющими в Arimaa:

• Битборды
• Таблицы транспонирования
• Зобристское хеширование
• Минимаксная и альфа-бета-обрезка
• Убийственные ходы и таблицы опровержений
• Статическая функция оценки
• Поиск покоя
• Поиск по дереву Монте-Карло
• УКТ

Техники, редко используемые в ботах Arimaa

• Открытие книги
• База таблицы эндшпиля

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

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

Поиск методом грубой силы

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

Когда к Аримаа применяется поиск методом грубой силы, глубина поиска ограничена огромным количеством вариантов, которые каждый игрок имеет на каждом ходу. В вычислительном отношении количество вариантов, доступных игроку, определяет количество различных путей игры, которые могут быть уменьшены. Это известно как фактор ветвления . Средний коэффициент ветвления в игре в шахматы составляет около 35. тогда как в Аримаа их около 17 000.

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

$35^{8}\approxeq 17000^{3}$

Альфа-бета обрезка

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

Более того, полезность отсечения альфа-бета сильно зависит от порядка, в котором рассматриваются ходы. Хорошие ходы необходимо рассматривать раньше плохих, чтобы плохими можно было пренебречь. В частности, проверка и захват ходов являются ключевыми для сокращения, потому что они часто намного лучше, чем другие ходы. В программном обеспечении Arimaa ускорение, обеспечиваемое обрезкой альфа-бета, меньше, поскольку захваты происходят реже. В рейтинговых играх на arimaa.com только 3% шагов приводят к взятию, по сравнению с примерно 19% шахматных ходов, которые приводят к взятию.

В большинстве позиций Аримаа, особенно в начале игры, когда доска еще заполнена, компетентный игрок может избежать потери фигур в течение следующих двух ходов. По сравнению с шахматами, Аримаа позволяет любому игроку дольше откладывать захват. Действительно, среднее число ходов при первом взятии в шахматах составляет 6 ход, тогда как в Аримаа - 12 ход. В Аримаа борьба изначально более позиционная и вращается вокруг того, чтобы сделать захваты неизбежными в какой-то момент в будущем. Это усиливает важность правильного суждения о том, кто добивается успехов в нематериальных отношениях. Таким образом, сила компьютерных программ (исследующих миллионы позиций) не так значительна, как их слабость (оценка позиции по тому, у кого больше фигур).

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

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

Еще один прием компьютерных шахмат, который не применим к Аримаа, - это настольные базы эндшпиля . Шахматные игры на уровне мастера иногда сводятся к неясным эндшпилям, состоящим всего из нескольких фигур, например, король и конь против короля и ладьи. можно построить Путем ретроградного анализа исчерпывающую таблицу правильного хода во всех таких позициях. В таких позициях программам нужно только сверяться с заранее созданной таблицей, а не «думать» заново, что дает им относительное преимущество перед людьми. Аримаа, напротив, редко доходит до финала. Равный размен фигур встречается реже, чем в шахматах, поэтому игра Аримаа редко бывает «разменом» и остается неясной. В средней игре Аримаа всего восемь взятий (по сравнению с семнадцатью в шахматах), и лучшие люди часто могут побеждать лучшие программы в Аримаа, не теряя ни одной фигуры, например, во второй игре матча Challenge 2014 . Еще один пример низкой плотности захвата – полуфинальная игра чемпионата мира 2012 года. , в котором есть только один захват - жертвоприношение слона, заставляющее забить гол.

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

Структура задачи Сайеда «Человек против машины» ориентирована на вознаграждение за достижения в области программного обеспечения искусственного интеллекта, а не на достижения в области аппаратного обеспечения. В ежегодном конкурсе программы запускаются на машинах, выбранных и предоставленных самим Саедом, при условии, что это будет типичный недорогой готовый домашний компьютер. Задача не будет открыта для тех, кому нужны дорогие многопроцессорные машины, такие как те, которые используются для борьбы с шахматистами высшего уровня, и тем более что-то вроде специально созданного суперкомпьютера Deep Blue , даже несмотря на то, что этот аппаратно-емкий подход оказался успешным. который вдохновил Аримаа на изобретение. Сайед считает, что даже компьютер, использованный в соревновании 2004 года (система Pentium 4 с тактовой частотой 2,4 ГГц и 512 МБ оперативной памяти), имел достаточно аппаратного обеспечения, чтобы выиграть переходящий приз, если бы на нем было установлено подходящее программное обеспечение. Суперкомпьютеры, возможно, уже смогут завоевать Аримаа грубой силой, используя обычное программное обеспечение искусственного интеллекта, и в конечном итоге персональные компьютеры тоже смогут это сделать, если оборудование продолжит развиваться такими же темпами. Именно поэтому изначально приз конкурса Аримаа предлагался только до 2020 года.

Ресурсы для разработчиков программного обеспечения

Интерфейс механизма Arimaa , разработанный Брайаном Хаскином, определяет протокол, который позволяет механизму Arimaa взаимодействовать с контроллером.

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

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

Научные статьи

• Ву, Дэвид Дж. (2015). «Разработка выигрышной программы Аримаа» (PDF) . Журнал ICGA . 38 (1): 19–40. doi : 10.3233/ICG-2015-38104 .
• Задача Аримаа - сравнительное исследование методов MCTS и альфа-бета
  диссертация Томаса Якла (Карлов университет, Прага), октябрь 2011 г.
• Рейтинг и оценка перемещений в игре Аримаа
  диссертация Дэвида Цзянь Ву (Гарвардский колледж, Кембридж, Массачусетс, США), май 2011 г.
• Аримаа: новый вызов искусственному интеллекту
  диссертация Стефано Карлини (Университет Модены и Реджо-Эмилии, Италия), апрель 2010 г.
• Методы MCTS и игра Аримаа
  диссертация Томаса Козелека (Пражский университет Карла, Чехия), декабрь 2009 г.
• Моделирование игры Аримаа с помощью лингвистической геометрии
  статья Хосеоберто Меркадо Вега и Цви Речкимана Кёсберга (из Национального политического института, представленная на материалах 5-й международной конференции по вычислительному интеллекту и играм, Милан, Италия), сентябрь 2009 г.
• Исследование и реализация компьютерного агента для игры в Аримаа
  диссертация Сэма Миллера (Университет Саутгемптона, Великобритания), май 2009 г.
• Планы, схемы и категории перемещений, определяющие высокоселективный поиск
  статья Герхарда Триппена (представленная на конференции «Достижения в компьютерных играх 12» 2009 г., Памплона, Испания), май 2009 г.
• Аримаа, игра реального интеллекта?
  презентация Николаса А. Барриги (Технический университет Федерико Санта-Мария, Чили), август 2006 г.
• Анализ и реализация игры Arimaa и приложения B
  диссертация Криста-Яна Кокса (Маастрихтский университет, Институт знаний и агентных технологий), март 2006 г.
• Создание сильной программы игры на Аримаа
  диссертация Хайчжи Чжуна (Университет Альберты, факультет компьютерных наук), сентябрь 2005 г.
• Создание программы чемпиона мира Аримаа
  статья Дэвида Фотланда (www.Smart-Games.com), 2004 г.
• Arimaa — новая игра, сложная для компьютеров
  статья Омара Сайеда и Аамира Сайеда; Журнал Международной ассоциации компьютерных игр ; июнь 2003 г.