Общая игра - General game playing

Часть серии о
Искусственный интеллект
Анатомия-1751201 1280.png
Основные цели
Подходы
Философия
История
Технология
Глоссарий

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

Общая игра в видеоигры ( GVGP ) - это концепция GGP, адаптированная для использования в видеоиграх . Для видеоигр правила игры должны быть либо изучены искусственными игроками, такими как TD-Gammon , за несколько итераций , либо заранее определены вручную на предметно-ориентированном языке и отправлены заранее искусственным игрокам, как в традиционном GGP. Начиная с 2013 года, был достигнут значительный прогресс благодаря подходу к глубокому обучению с подкреплением , включая разработку программ, которые могут научить играть в игры Atari 2600, а также программы, которая может научиться играть в игры Nintendo Entertainment System .

Первым коммерческим использованием общей игровой технологии была Zillions of Games в 1998 году. Общая игра была также предложена для торговых агентов в управлении цепочкой поставок в рамках переговоров о ценах на онлайн-аукционах с 2003 года.

История

В 1992 году Барни Пелл определил концепцию игры в мета-игры и разработал систему «MetaGame». Это была первая программа, которая автоматически генерировала правила игры в шахматные игры, и одна из первых программ, использующих автоматическую генерацию игр. Затем Пелл разработал систему Metagamer . Эта система могла играть в несколько шахматных игр, учитывая определение правил игры на специальном языке, называемом Game Description Language (GDL), без какого-либо вмешательства человека после того, как игры были созданы.

В 1998 году Джефф Маллет и Марк Лефлер разработали коммерческую систему Zillions of Games . Система использовала LISP-подобный язык для определения правил игры. Zillions of Games автоматически извлекла функцию оценки из правил игры, основанных на подвижности фигур, структуре доски и целях игры. Он также использовал обычные алгоритмы, используемые в компьютерных шахматных системах: альфа-бета-отсечение с упорядочением ходов, таблицы транспонирования и т. Д. В 2007 году пакет был расширен добавлением подключаемого модуля Axiom, альтернативного движка метагеймов, который включает в себя полный Форт. язык программирования.

В 1998 году z-Tree был разработан Урсом Фишбахером . z-Tree - это первый и наиболее цитируемый программный инструмент для экспериментальной экономики . z-Tree позволяет определять правила игры на языке z-Tree для теоретико-игровых экспериментов с людьми . Он также позволяет определять компьютерных игроков, которые участвуют в игре с людьми.

В 2005 году был основан Стэнфордский проект General Game Playing .

В 2012 году началась разработка PyVGDL.

Реализации GGP

Стэнфордский проект

General Game Playing - это проект Stanford Logic Group из Стэнфордского университета , Калифорния, целью которого является создание платформы для обычных игр. Это наиболее известная попытка стандартизации искусственного интеллекта GGP, которая обычно считается стандартом для систем GGP. Игры определяются наборами правил, представленных на языке описания игр . Чтобы играть в игры, игроки взаимодействуют с игровым хост-сервером, который отслеживает ходы на предмет законности и информирует игроков об изменениях состояния.

С 2005 года на конференции AAAI ежегодно проводятся соревнования по играм в общую игру . Соревнования оценивают способности ИИ конкурента играть в различные игры, записывая их результативность в каждой отдельной игре. На первом этапе конкурса участники оцениваются по их способности выполнять разрешенные ходы, одерживать верх и быстрее завершать игры. В следующем раунде ИИ сражаются друг с другом во все более сложных играх. ИИ, выигравший наибольшее количество игр на этом этапе, побеждает в соревновании, и до 2013 года его создатель выигрывал приз в размере 10 000 долларов. Пока победили следующие программы:

Год Имя Разработчик Учреждение Ссылка
2005 г. Cluneplayer Джим Клун UCLA
2006 г. Fluxplayer Стефан Шиффель и Майкл Тильшер Дрезденский технологический университет
2007 г. Кадиаплеер Ингви Бьёрнссон и Хильмар Финнссон Рейкьявикский университет
2008 г. Кадиаплеер Ингви Бьёрнссон, Хильмар Финнссон и Гильфи Тор Гудмундссон Рейкьявикский университет
2009 г. Ары Жан Меха Университет Париж 8
2010 г. Ары Жан Меха Университет Париж 8
2011 г. ТурбоЧерепаха Сэм Шрайбер
2012 г. Кадиаплеер Хильмар Финнссон и Ингви Бьёрнссон Рейкьявикский университет
2013 ТурбоЧерепаха Сэм Шрайбер
2014 г. Санчо Стив Дрейпер и Эндрю Роуз
2015 г. Гальванизировать Ричард Эмсли
2016 г. WoodStock Эрик Пьетт Университет Артуа

Другие подходы

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

  • Система под названием FRAMASI разрабатывалась с 2009 года.
  • Система под названием AiAi, созданная Стивеном Тавенером (предыдущим разработчиком Zillions), была создана в 2015 году и активно развивалась с конца 2017 года.
  • Система под названием PolyGamo Player от Дэвида М. Беннета, выпущенная в сентябре 2017 года на основе игрового движка Unity .

Реализации GVGP

Обучение с подкреплением

GVGP потенциально может использоваться для автоматического создания реального ИИ видеоигр , а также «для тестирования игровых сред, включая те, которые создаются автоматически с использованием процедурной генерации контента, и для поиска потенциальных лазеек в игровом процессе, которые может использовать игрок-человек». GVGP также использовался для генерации правил игры и оценки качества игры на основе профилей относительной производительности алгоритмов (RAPP), которые сравнивают различие навыков, которое позволяет игра между хорошим ИИ и плохим ИИ.

Язык описания видеоигр

Соревнование General Video Game AI Competition ( GVGAI ) проводится с 2014 года. В этом соревновании вместо настольных игр, используемых в GGP, используются двухмерные видеоигры, похожие на (а иногда и основанные на) аркадные и консольные игры 1980-х годов. конкуренция. Это дало возможность исследователям и практикам протестировать и сравнить свои лучшие общие алгоритмы игры в видеоигры. У конкурса есть связанная программная среда, включающая большое количество игр, написанных на языке описания видеоигр (VGDL) , который не следует путать с GDL, и представляет собой язык кодирования, использующий простую семантику и команды, которые можно легко проанализировать. Одним из примеров VGDL является PyVGDL, разработанный в 2013 году. Игры, используемые в GVGP, на данный момент часто являются двумерными аркадными играми, поскольку их проще всего определить количественно. Чтобы упростить процесс создания ИИ, который может интерпретировать видеоигры, игры для этой цели пишутся на VGDL вручную. VGDL можно использовать для описания игры специально для процедурной генерации уровней с использованием программирования набора ответов (ASP) и эволюционного алгоритма (EA). Затем GVGP можно использовать для проверки достоверности процедурных уровней, а также сложности или качества уровней в зависимости от того, как работает агент.

Алгоритмы

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

Популярным методом разработки GGP AI является алгоритм поиска по дереву Монте-Карло (MCTS). Варианты MCTS, часто используемые вместе с методом UCT ( верхняя граница уверенности, применяемая к деревьям ), были предложены для лучшего воспроизведения определенных игр, а также для обеспечения совместимости с видеоиграми. Другой вариант используемого алгоритма поиска по дереву - это направленный поиск в ширину (DBS), в котором дочерний узел для текущего состояния создается для каждого доступного действия и посещает каждого дочернего элемента, упорядоченного по наивысшему среднему вознаграждению, до тех пор, пока игра не закончится. или не хватает времени. В каждом методе поиска по дереву ИИ моделирует потенциальные действия и оценивает каждое на основе средней наивысшей награды за каждый путь с точки зрения заработанных очков.

Предположения

Чтобы взаимодействовать с играми, алгоритмы должны работать в предположении, что все игры имеют общие характеристики. В книге Half-Real: Video Games Between Real Worlds and Fictionals , Джеспер Джул дает следующее определение игр: игры основаны на правилах, у них есть переменные результаты, разные результаты дают разные значения, усилия игрока влияют на результаты, игрок привязаны к результатам, и игра имеет подлежащие обсуждению последствия. Используя эти предположения, можно создать игровой ИИ путем количественной оценки вклада игрока, результатов игры и того, как применяются различные правила, а также использования алгоритмов для вычисления наиболее благоприятного пути.

Смотрите также

использованная литература

внешние ссылки

См. Также CS227B - страницу общего курса по игре в игры , GGP.org , страницу GGP.org GitHub и games.stanford.edu .

видео