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

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Компьютер Аримаа»  – Новости  · газеты  · книги  · ученый  · JSTOR (Март 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья использование внешняя ссылка может не следовать политикам или рекомендациям Википедии. Пожалуйста улучшить эту статью путем удаления излишний или же неприличный внешние ссылки и преобразование полезных ссылок, где это необходимо, в ссылки на сноски. (Март 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

Компьютер Аримаа относится к игре настольная игра Аримаа к компьютерные программы.

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

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

Открытие

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

${ displaystyle { 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 лошадей на 4 оставшихся квадратах, одного верблюда на одном из двух оставшихся квадратов и слона. на последней неиспользованной площади.

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

${ displaystyle 64 864 800 ^ {2} приблизительно 4,2 cdot 10 ^ {15}}$

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

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

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

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

Приемы, используемые в ботах Arimaa

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

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

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

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

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

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

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

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

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

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

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

${ displaystyle 35 ^ {8} приблизительно 17000 ^ {3}}$

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

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

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

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

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

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

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

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

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

Сравнение Arimaa Challenge с шахматными задачами

Эта секция возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Апрель 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Утверждалось, что компьютер победил чемпиона мира по шахматам, но не победил человека в Arimaa Challenge (до 2015 года) по шести причинам:

1. Аримаа - новая игра. Таким образом, количество программистов и количество времени, уделяемого компьютерной Ариме намного меньше, чем компьютерным шахматам. В компьютерных шахматах было на тысячи программистов и на 40 лет больше, чем в компьютерных Аримаа. Более поздние и меньшие усилия привели к меньшему и медленному прогрессу в компьютерной Аримаа.
2. Правила Arimaa Challenge требовали, чтобы компьютер показал более высокие игровые способности, чем правила для шахматных матчей. В Arimaa Challenge компьютер должен обыграть трех игроков-людей в трех матчах. В шахматных матчах компьютер должен выиграть один матч против одного человека.
3. В Arimaa Challenge компьютер должен набрать 2/3 от общего количества очков для победы. В шахматных матчах для победы компьютеру необходимо набрать более 1/2 от общего количества очков.
4. В Arimaa Challenge компьютер должен выиграть квалификационный матч. Людям разрешено изучать предыдущие компьютерные игры, чтобы найти слабые места компьютера. В шахматах нет квалификационных матчей и не требуется, чтобы предыдущие компьютерные партии были общедоступными.^{[сомнительный – обсуждать]}
5. В Arimaa Challenge компьютер нельзя улучшать между играми. В шахматах компьютер улучшался между партиями.
6. В Arimaa Challenge правила запрещают мощные или изготовленные на заказ компьютеры стоимостью более 1000 долларов. Однако мощный компьютер, сделанный на заказ, обыграл чемпиона мира по шахматам.

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

Остальные пять баллов сравнивают Arimaa Challenge только с Каспаровым против Deep Blue, игнорируя все другие шахматные матчи человек против машин, в которых преобладали компьютеры. Шахматный матч, который больше всего можно сравнить с матчем Arimaa Challenge, - это Человек против машин командный чемпионат мира. В 2004 и 2005 годах команда людей играла против команды компьютерных противников. В оба года компьютеры выиграли с большим отрывом. В 2005 году проиграли все три человека, компьютеры выиграли 2/3 от общего количества очков, шахматные движки были коммерчески доступны для изучения людьми, а используемое машинное оборудование не было суперкомпьютером, а скорее сопоставимо с оборудованием, используемым в Arimaa Challenge. .

Шахматные матчи «человек против машины» с 2005 года показали растущее доминирование компьютеров. Например, 2006 г. Дип Фриц против Владимира Крамника и матчи 2007 года Рыбка против Яана Эльвеста дали игроку-человеку дополнительные преимущества, но компьютеры (работающие на стандартном оборудовании) все равно преобладали.

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

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

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

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

Научно-исследовательские работы

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

Сноски