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

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

Общие видеоигры (GVGP) - это концепция GGP, адаптированная к цели игры видеоигры. Для видеоигр правила игры должны быть либо научился за несколько итераций искусственными игроками, такими как TD-Gammon,[5] или предопределены вручную в предметно-ориентированный язык и отправлено заранее искусственным игрокам[6][7] как в традиционном GGP. Начиная с 2013 года был достигнут значительный прогресс после глубокое обучение с подкреплением подход, включая разработку программ, позволяющих научиться играть Atari 2600 игры[8][5][9][10][11] а также программу, которая может научиться играть Система развлечений Nintendo игры.[12][13][14]

Первое коммерческое использование общей игровой технологии было Миллионы игр в 1998 году. Общая игра была также предложена для торговые агенты в система управления цепями поставок в соответствии с этим переговоры о цене в онлайн-аукционы с 2003 г.[15][16][17][18]

История

В 1992 г. Барни Пелл определил концепцию Meta-Game Playing и разработал систему MetaGame. Это была первая программа, которая автоматически генерировала правила игры в шахматные игры, и одна из первых программ, использующих автоматическую генерацию игр. Затем Пелл разработал систему Metagamer.[19] Эта система могла играть в несколько шахматных игр, учитывая определение правил игры на специальном языке, называемом языком описания игр, без какого-либо человеческого взаимодействия после создания игр.[20]

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

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

В 2005 году Стэнфордский проект Общая игра был основан.[3]

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

Реализации GGP

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

Общая игра это проект Stanford Logic Group of Стэндфордский Университет, Калифорния, целью которой является создание платформы для обычных игр. Это наиболее известная попытка стандартизации искусственного интеллекта GGP, которая обычно считается стандартом для систем GGP. Игры определяются наборами правил, представленных в Язык описания игры. Чтобы играть в игры, игроки взаимодействуют с сервером игрового хостинга.[25][26] который контролирует ходы на предмет законности и информирует игроков об изменениях состояния.

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

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

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

  • Система под названием AiAi Стивена Тавенера (предыдущего разработчика Zillions)[31] восходит к 2015 году и активно развивается по состоянию на конец 2017 года.[32][33]
  • Система под названием PolyGamo Player от Дэвида М. Беннета, выпущенная в сентябре 2017 года на основе Игровой движок Unity.[34]

Реализации GVGP

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

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

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

В Общий конкурс видеоигр AI (GVGAI ) проводится с 2014 года. В этом соревновании используются двумерные видеоигры, похожие (а иногда и основанные на) аркадные и консольные игры 80-х годов, вместо настольных игр, используемых в соревнованиях GGP. Это позволило исследователям и практикам протестировать и сравнить свои лучшие общие алгоритмы игры в видеоигры. У конкурса есть связанная программная среда, включающая большое количество игр, написанных на Язык описания видеоигр (VGDL), который не следует путать с GDL и является языком кодирования, использующим простую семантику и команды, которые легко анализируются. Одним из примеров VGDL является PyVGDL, разработанный в 2013 году.[6][24] Игры, используемые в GVGP, на данный момент часто являются двумерными аркадными играми, поскольку они наиболее просты и легче всего поддаются количественной оценке.[36] Чтобы упростить процесс создания ИИ, который может интерпретировать видеоигры, игры для этой цели пишутся на VGDL вручную. VGDL можно использовать для описания игры специально для процедурной генерации уровней с использованием программирования набора ответов (ASP) и эволюционного алгоритма (EA). Затем GVGP можно использовать для проверки достоверности процедурных уровней, а также сложности или качества уровней в зависимости от того, как работал агент.[37]

Алгоритмы

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

Популярным методом разработки GGP AI является Поиск в дереве Монте-Карло (MCTS) алгоритм.[39] Часто используется вместе с методом UCT (Верхняя граница уверенности, примененная к деревьям), были предложены варианты MCTS, чтобы лучше играть в определенные игры, а также чтобы сделать его совместимым с видеоиграми.[40][41][42] Другой вариант используемого алгоритма поиска по дереву - Направленный Поиск в ширину (BFS), в котором дочерний узел текущего состояния создается для каждого доступного действия и посещает каждого дочернего элемента, упорядоченного по наивысшей средней награде, до тех пор, пока игра не закончится или не истечет время.[43] В каждом методе поиска по дереву ИИ моделирует потенциальные действия и оценивает каждое на основе среднего наивысшего вознаграждения за каждый путь с точки зрения заработанных очков.[39][43]

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

Чтобы взаимодействовать с играми, алгоритмы должны работать в предположении, что все игры имеют общие характеристики. В книге Half-Real: видеоигры между реальным и вымышленным мирамиДжеспер Джул дает следующее определение игр: игры основаны на правилах, у них есть переменные результаты, разные результаты дают разные значения, усилия игрока влияют на результаты, игрок привязан к результатам, и игра имеет обсуждаемые последствия.[44] Используя эти предположения, можно создать игровой ИИ, оценивая вклад игрока, результаты игры и то, как применяются различные правила, а также используя алгоритмы для вычисления наиболее благоприятного пути.[36]

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

Рекомендации

  1. ^ Пелл, Барни (1992). Х. ван ден Херик; Л. Аллис (ред.). «Метагейм: новый вызов для игр и обучения» [Эвристическое программирование в искусственном интеллекте 3 - третья компьютерная олимпиада] (PDF). Эллис-Хорвуд. Цитировать журнал требует | журнал = (помощь)
  2. ^ Пелл, Барни (1996). «Стратегический игрок в метагейм для общих шахматных игр». Вычислительный интеллект. 12 (1): 177–198. Дои:10.1111 / j.1467-8640.1996.tb00258.x. ISSN  1467-8640.
  3. ^ а б Дженесерет, Майкл; С любовью, Натаниэль; Пелл, Барни (15 июня 2005 г.). «Общие правила игры: Обзор соревнований AAAI». Журнал AI. 26 (2): 62. Дои:10.1609 / aimag.v26i2.1813. ISSN  2371-9621.
  4. ^ Ханаан, Родриго; Салге, Кристоф; Тогелиус, Юлиан; Нилен, Энди (2019). Выравнивание игрового поля [Материалы 14-й Международной конференции по выравниванию игрового поля: справедливость в ИИ по сравнению с тестами человеческих игр]. dl.acm.org. С. 1–8. Дои:10.1145/3337722. ISBN  9781450372176.
  5. ^ а б Мних, Владимир; Кавукчуоглу, Корай; Сильвер, Дэвид; Грейвс, Алекс; Антоноглоу, Иоаннис; Виерстра, Даан; Ридмиллер, Мартин (2013). «Игра в Atari с глубоким обучением с подкреплением» (PDF). Системы обработки нейронной информации Мастерская 2013. Получено 25 апреля 2015.
  6. ^ а б Шауль, Том (август 2013). «Язык описания видеоигр для обучения на основе моделей или интерактивного обучения». Конференция IEEE 2013 г. по вычислительному интеллекту в играх (CIG): 1–8. CiteSeerX  10.1.1.360.2263. Дои:10.1109 / CIG.2013.6633610. ISBN  978-1-4673-5311-3.
  7. ^ а б Левин, Джон; Конгдон, Клэр Бейтс; Эбнер, Марк; Кендалл, Грэм; Лукас, Саймон М .; Мииккулайнен, Ристо; Шауль, Том; Томпсон, Томми (2013). "Обычные видеоигры". Искусственный и вычислительный интеллект в играх. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 6: 77–83. Получено 25 апреля 2015.
  8. ^ Боулинг, М .; Veness, J .; Naddaf, Y .; Беллемар, М. Г. (14.06.2013). «Обучающая среда Arcade: платформа оценки для общих агентов». Журнал исследований искусственного интеллекта. 47: 253–279. arXiv:1207.4708. Дои:10.1613 / jair.3912. ISSN  1076-9757.
  9. ^ Мних, Владимир; Кавукчуоглу, Корай; Сильвер, Дэвид; Русу, Андрей А .; Венесс, Джоэл; Хассабис, Демис; Bellemare, Marc G .; Грейвс, Алекс; Ридмиллер, Мартин; Fidjeland, Andreas K .; Стиг Петерсен, Георг Островски; Битти, Чарльз; Садик, Амир; Антоноглоу, Иоаннис; Король, Хелен; Кумаран, Дхаршан; Виерстра, Даан; Легг, Шейн (26 февраля 2015 г.). «Контроль на уровне человека посредством глубокого обучения с подкреплением». Природа. 518 (7540): 529–533. Bibcode:2015Натура.518..529M. Дои:10.1038 / природа14236. PMID  25719670.
  10. ^ Корюс, Кристьян; Кузовкин, Илья; Тампуу, Арди; Пунгас, Тайво (2014). «Копирование бумаги» Игра в Atari с глубоким обучением с подкреплением"" (PDF). Тартуский университет. Получено 25 апреля 2015.
  11. ^ Го, Сяосяо; Сингх, Сатиндер; Ли, Хонглак; Льюис, Ричард Л .; Ван, Сяоши (2014). «Глубокое обучение для игры в Atari в реальном времени с использованием автономного планирования поиска по дереву Монте-Карло» (PDF). Протоколы NIPSβ. Конференция по нейронным системам обработки информации. Получено 25 апреля 2015.
  12. ^ Мерфи, Том (2013). «Первый уровень Super Mario Bros. прост с лексикографическим порядком и путешествиями во времени ... после этого становится немного сложнее." (PDF). СИГБОВИК. Получено 25 апреля 2015.
  13. ^ Мерфи, Том. «learnfun & playfun: общий метод автоматизации игр NES». Получено 25 апреля 2015.
  14. ^ Teller, Swizec (28 октября 2013 г.). «Неделя 2: Уровень 1 в Super Mario Bros. прост с лексикографическим порядком и». Компьютерщик в шляпе. Получено 25 апреля 2015.
  15. ^ Макмиллен, Колин (2003). «На пути к разработке интеллектуального агента для игры в управление цепочкой поставок конкурса торговых агентов 2003 г.» [Конкурс торговых агентов 2003 г.]. Дипломная работа. Миннеаполис, Миннесота: Университет Миннесоты. S2CID  167336006. Цитировать журнал требует | журнал = (помощь)
  16. ^ Чжан, Донгмо (2009). От общих описаний игр до языка спецификаций рынка для обычных торговых агентов [Электронная торговля через агентов. Разработка торговых стратегий и механизмов для электронных рынков.]. Берлин, Гейдельберг: Springer. С. 259–274. Bibcode:2010aecd.book..259T. CiteSeerX  10.1.1.467.4629.
  17. ^ "AGAPE - Аукцион ЯЗЫК ДЛЯ ОБЫЧНЫХ Аукционистов". AGAPE (На французском). Получено 5 марта 2020.
  18. ^ Майкл, Фридрих; Игнатов, Дмитрий (2019). «Общие переговоры о ценах между компаниями» (PDF). Материалы семинара CEUR. Том 2479: 89–99. Получено 5 марта 2020.
  19. ^ а б Исследование Барни Пелла о компьютерных играх В архиве 2007-08-12 на Wayback Machine.
  20. ^ «Метагейм и общие игры». Метагейм и общая игра. Получено 27 марта 2016.
  21. ^ Доступно: Универсальный игровой движок электронное письмо на comp.ai.games от Джеффа Маллетта, 10 декабря 1998 г.
  22. ^ "UZH - z-Tree - Zurich Toolbox для готовых экономических экспериментов". www.ztree.uzh.ch. Получено 17 февраля 2020.
  23. ^ Бекенкамп, Мартин; Хенниг-Шмидт, Хайке; Майер-Риго, Франк П. (1 марта 2007 г.). "Сотрудничество в симметричных и асимметричных играх дилеммы заключенного". Сеть исследований в области социальных наук. SSRN  968942. Цитировать журнал требует | журнал = (помощь)
  24. ^ а б Шауль, Том (7 февраля 2020 г.). "schaul / py-vgdl".
  25. ^ Сервер GGP, площадка для соревнований общих игровых систем.
  26. ^ Сервер Dresden GGP, площадка для соревнований общих игровых систем с автоматическим планированием матчей.
  27. ^ "Обычная игра". www.general-game-playing.de.
  28. ^ Информация о Fluxplayer, победитель II Международных соревнований по общегражданской игре.
  29. ^ Информация о CADIAPlayer, подробнее о победителях 3-го, 4-го и 8-го Международных соревнований по игре в общую игру.
  30. ^ Санчо стал Чемпионом GGP 2014!, победитель Международного конкурса игровых автоматов 2014 года.
  31. ^ "Миллионы игр - кто мы?". www.zillions-of-games.com. Получено 2017-11-16.
  32. ^ "Домашняя страница AiAi - Стивен Тавенер". mrraow.com. Получено 2017-11-16.
  33. ^ "Тема объявления Ai Ai". НастольнаяИграГик. Получено 2017-11-16.
  34. ^ «Проект PolyGamo Player | Языки программирования и общие проигрыватели для абстрактных игр и головоломок». www.polyomino.com. Получено 2017-11-16.
  35. ^ Nielsen, Thorbjørn S .; Баррос, Габриэлла А. Б .; Тогелиус, Юлиан; Нельсон, Марк Дж. «На пути к созданию правил аркадных игр с помощью VGDL» (PDF).
  36. ^ а б Левин, Джон; Конгдон, Клэр Бейтс; Эбнер, Марк; Кендалл, Грэм; Лукас, Саймон М .; Мииккулайнен Ристо, Шауль; Том, Томпсон; Томми. "Обычные видеоигры" (PDF).
  37. ^ Нойфельд, Ксения; Мостагим, Саназ; Перес-Либана, Диего. «Генерация процедурного уровня с программированием набора ответов для обычных видеоигр» (PDF).
  38. ^ «Последние достижения в игровой индустрии». Научный мировой журнал. Хиндави Издательская Корпорация. 2015 г. Дои:10.1155/2015/986262.
  39. ^ а б «Поиск по дереву Монте-Карло для общей игры». ResearchGate. Получено 2016-04-01.
  40. ^ Финнссон, Хилмар (2012). «Обобщенные расширения поиска по дереву Монте-Карло для обычных игр». Материалы двадцать шестой конференции AAAI по искусственному интеллекту.
  41. ^ Фриденберг, Фредерик; Андерсон, Каспер Р .; Ризи, Себастьян; Тогелиус, Юлиан. «Исследование модификаций MCTS в обычных видеоиграх» (PDF).
  42. ^ М. Свеховски; Я. Мандзюк; Я. С. Онг, «Специализация общей игровой программы на основе UCT для одиночных игр», в IEEE Transactions по вычислительному интеллекту и искусственному интеллекту в играх, т. П.П., No.99, с. 1-1 Дои:10.1109 / TCIAIG.2015.2391232
  43. ^ а б Перес, Диего; Dieskau, Jens; Хюнермунд, Мартин. "Открытый цикл поиска обычных видеоигр" (PDF).
  44. ^ Джеспер Юул. Half-Real: Видеоигры между реальными правилами и вымышленными мирами. MIT Press, 2005.

внешняя ссылка

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

видео