stringtranslate.com

Общая игра

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

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

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

История

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

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

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

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

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

Реализации GGP

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

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

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

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

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

Реализации GVGP

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

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

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

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

Алгоритмы

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

Популярным методом разработки ИИ GGP является алгоритм поиска по дереву Монте-Карло (MCTS). [46] Часто используемые вместе с методом UCT ( верхняя граница доверия, применяемая к деревьям ), вариации MCTS были предложены для лучшей игры в определенные игры, а также для того, чтобы сделать его совместимым с игрой в видеоигры. [47] [48] [49] Другой вариант используемых алгоритмов поиска по дереву — направленный поиск в ширину (DBS), [50] в котором для каждого доступного действия создается дочерний узел для текущего состояния, и посещает каждый дочерний узел, упорядоченный по наибольшему среднему вознаграждению, пока игра не закончится или не истечет время. [51] В каждом методе поиска по дереву ИИ имитирует потенциальные действия и ранжирует каждое на основе среднего наибольшего вознаграждения каждого пути с точки зрения заработанных очков. [46] [51]

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

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

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

Ссылки

  1. ^ Pell, Barney (1992). H. van den Herik; L. Allis (ред.). «Метаигра: новый вызов для игр и обучения» [Эвристическое программирование в искусственном интеллекте 3–третья компьютерная олимпиада] (PDF) . Ellis-Horwood. Архивировано (PDF) из оригинала 2020-02-17 . Получено 2020-02-17 .
  2. ^ Пелл, Барни (1996). «Стратегический метаигрок для общих шахматных игр». Computational Intelligence . 12 (1): 177–198. doi :10.1111/j.1467-8640.1996.tb00258.x. ISSN  1467-8640. S2CID  996006.
  3. ^ ab Genesereth, Michael; Love, Nathaniel; Pell, Barney (15 июня 2005 г.). «Общая игра: обзор соревнования AAAI». Журнал AI . 26 (2): 62. doi :10.1609/aimag.v26i2.1813. ISSN  2371-9621.
  4. ^ Канаан, Родриго; Сальге, Кристоф; Тогелиус, Джулиан; Нилен, Энди (2019). Труды 14-й Международной конференции по основам цифровых игр [ Труды 14-й Международной конференции по выравниванию игрового поля: справедливость в ИИ по сравнению с человеческими игровыми эталонами ]. стр. 1–8. doi :10.1145/3337722. ISBN 9781450372176. S2CID  58599284.
  5. ^ ab Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Graves, Alex; Antonoglou, Ioannis; Wierstra, Daan; Riedmiller, Martin (2013). "Игра в Atari с глубоким подкреплением" (PDF) . Семинар по системам обработки нейронной информации 2013. Архивировано (PDF) из оригинала 12 сентября 2014 г. . Получено 25 апреля 2015 г. .
  6. ^ ab Schaul, Tom (август 2013 г.). «Язык описания видеоигр для обучения на основе моделей или интерактивного обучения». Конференция IEEE 2013 г. по вычислительному интеллекту в играх (CIG) . стр. 1–8. CiteSeerX 10.1.1.360.2263 . doi :10.1109/CIG.2013.6633610. ISBN  978-1-4673-5311-3. S2CID  812565.
  7. ^ ab Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen, Risto; Schaul, Tom; Thompson, Tommy (2013). "General Video Game Playing". Искусственный и вычислительный интеллект в играх . 6. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 77–83. Архивировано из оригинала 9 апреля 2016 года . Получено 25 апреля 2015 года .
  8. ^ Боулинг, М.; Венесс, Дж.; Наддаф, И.; Беллемар, М.Г. (14.06.2013). «Среда обучения в аркадах: оценочная платформа для агентов общего назначения». Журнал исследований искусственного интеллекта . 47 : 253–279. arXiv : 1207.4708 . doi : 10.1613/jair.3912. ISSN  1076-9757. S2CID  1552061.
  9. ^ Мних, Владимир; Кавукчуоглу, Корай; Сильвер, Дэвид; Русу, Андрей А.; Венесс, Джоэл; Хассабис, Демис; Бельмар, Марк Г.; Грейвс, Алекс; Ридмиллер, Мартин; Фиджеланд, Андреас К.; Стиг Петерсен, Георг Островски; Битти, Чарльз; Садик, Амир; Антоноглу, Иоаннис; Король, Хелен; Кумаран, Дхаршан; Виерстра, Даан; Легг, Шейн (26 февраля 2015 г.). «Контроль на человеческом уровне посредством глубокого обучения с подкреплением». Природа . 518 (7540): 529–533. Бибкод : 2015Natur.518..529M. дои : 10.1038/nature14236. PMID  25719670. S2CID  205242740.
  10. ^ Корьюс, Кристьян; Кузовкин, Илья; Тампуу, Арди; Пунгас, Тайво (2014). «Повторение статьи «Игра в Atari с глубоким обучением с подкреплением»» (PDF) . Тартуский университет . Архивировано (PDF) из оригинала 18 декабря 2014 г. . Получено 25 апреля 2015 г. .
  11. ^ Го, Сяосяо; Сингх, Сатиндер; Ли, Хонглак; Льюис, Ричард Л.; Ван, Сяоши (2014). «Глубокое обучение для игр Atari в реальном времени с использованием автономного планирования поиска по дереву Монте-Карло» (PDF) . Труды NIPS β . Конференция по системам обработки нейронной информации . Архивировано (PDF) из оригинала 17 ноября 2015 г. . Получено 25 апреля 2015 г. .
  12. ^ Мерфи, Том (2013). «Первый уровень Super Mario Bros. прост с лексикографическим порядком и путешествием во времени... после этого становится немного сложнее». (PDF) . SIGBOVIK. Архивировано (PDF) из оригинала 26 апреля 2013 года . Получено 25 апреля 2015 года .
  13. ^ Мерфи, Том. "learnfun & playfun: Общая методика автоматизации игр NES". Архивировано из оригинала 19 апреля 2015 г. Получено 25 апреля 2015 г.
  14. ^ Теллер, Суижек (28 октября 2013 г.). «Неделя 2: Уровень 1 Super Mario Bros. легко с лексикографическими порядками и». Гик в шляпе . Архивировано из оригинала 30 апреля 2015 г. Получено 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 (на французском). 8 марта 2019 г. Архивировано из оригинала 2 августа 2021 г. Получено 5 марта 2020 г.
  18. ^ Михаэль, Фридрих; Игнатов, Дмитрий (2019). «Общая игра в ценовые переговоры B-to-B» (PDF) . Материалы семинара CEUR . -2479: 89–99. Архивировано (PDF) из оригинала 6 декабря 2019 г. . Получено 5 марта 2020 г. .
  19. ^ Исследование Барни Пелла о компьютерных играх. Архивировано 12 августа 2007 г. на Wayback Machine .
  20. ^ "Метаигра и общая игра". Метаигра и общая игра . Архивировано из оригинала 3 марта 2001 года . Получено 27 марта 2016 года .
  21. ↑ Доступно: Universal Game Engine. Архивировано 03.11.2012 в электронном письме Wayback Machine comp.ai.games Джеффом Маллеттом, 10 декабря 1998 г.
  22. ^ "UZH - z-Tree - Zurich Toolbox for Readymade Economic Experiments". www.ztree.uzh.ch . Архивировано из оригинала 21 февраля 2016 года . Получено 17 февраля 2020 года .
  23. ^ Бекенкамп, Мартин; Хенниг-Шмидт, Хайке; Майер-Риго, Франк П. (1 марта 2007 г.). «Сотрудничество в симметричных и асимметричных играх «Дилемма заключенного»». Исследовательская сеть социальных наук. SSRN  968942.
  24. ↑ Аб Шауль, Том (7 февраля 2020 г.). "шауль/py-vgdl". Гитхаб . Архивировано из оригинала 11 июня 2018 года . Проверено 9 февраля 2020 г.
  25. ^ Сервер GGP Архивировано 21 февраля 2014 г. на Wayback Machine , платформе для соревнований игровых систем общего назначения.
  26. ^ Сервер GGP в Дрездене. Архивировано 07.04.2013 на Wayback Machine , платформе для соревнований игровых систем общего назначения с автоматическим планированием матчей.
  27. ^ "General Game Playing". www.general-game-playing.de . Архивировано из оригинала 2008-12-26 . Получено 2008-08-21 .
  28. ↑ Информация о Fluxplayer. Архивировано 19 июля 2011 г. на Wayback Machine , победителе 2-го Международного конкурса по общим играм.
  29. ^ Информация о CADIAPlayer Архивировано 22 июля 2011 г. на Wayback Machine , дополнительная информация о победителе 3-го, 4-го и 8-го международных соревнований по общей игре.
  30. ^ Санчо — чемпион GGP 2014! Архивировано 22 декабря 2015 г. в Wayback Machine , победитель Международного конкурса по общей игре 2014 г.
  31. ^ Тагиев, Рустам (2009). Филипе, Жоаким; Фред, Ана; Шарп, Бернадетт (ред.). К структуре управления стратегическим взаимодействием [ Труды Международной конференции по агентам и искусственному интеллекту ] (PDF) . Порту, Португалия. стр. 587–590. ISBN 978-989-8111-66-1. Архивировано (PDF) из оригинала 2021-03-09 . Получено 2021-06-02 .{{cite book}}: CS1 maint: location missing publisher (link)
  32. ^ Тагиев, Рустам (2011). Strategische Interaktion Realer Agenten Ganzheitliche Konzeptualisierung und SoftwarekomComponenten einer interdisziplinären Forschungsinfrastruktur (новое издание). Саарбрюккен. ISBN 9783838125121.{{cite book}}: CS1 maint: location missing publisher (link)
  33. ^ "Zillions of Games - Who Are We?". www.zillions-of-games.com . Архивировано из оригинала 2017-11-15 . Получено 2017-11-16 .
  34. ^ "AiAi Home Page – Stephen Tavener". mrraow.com . Архивировано из оригинала 2015-09-06 . Получено 2017-11-16 .
  35. ^ "Ai Ai announcement thread". BoardGameGeek . Архивировано из оригинала 2017-11-16 . Получено 2017-11-16 .
  36. ^ "Проект PolyGamo Player | Языки программирования и общие проигрыватели для абстрактных игр и головоломок". www.polyomino.com . Архивировано из оригинала 2002-09-23 . Получено 2017-11-16 .
  37. ^ Ковальски, Якуб; Мика, Максимилиан; Сутович, Якуб; Шикула, Марек (17 июля 2019 г.). «Обычные настольные игры». Материалы конференции AAAI по искусственному интеллекту . 33 (1): 1699–1706. дои : 10.1609/aaai.v33i01.33011699 . ISSN  2374-3468. S2CID  20296467.
  38. ^ Ковальски, Якуб; Мирник, Радослав; Мика, Максимилиан; Павлик, Войцех; Сутович, Якуб; Шикула, Марек; Ткачик, Анджей (2020). «Эффективное рассуждение в обычных настольных играх». Конференция IEEE по играм (CoG) 2020 года . стр. 455–462. arXiv : 2006.08295 . дои : 10.1109/cog47356.2020.9231668. ISBN 978-1-7281-4533-4. S2CID  219687404 . Получено 2023-11-19 .
  39. ^ "Ludii Portal | Домашняя страница Ludii General Game System". www.ludii.games . Архивировано из оригинала 2021-10-27 . Получено 2021-10-27 .
  40. ^ "Digital Ludeme Project | Моделирование эволюции традиционных игр". www.ludeme.eu . Архивировано из оригинала 2021-10-02 . Получено 2021-10-27 .
  41. ^ Piette, E.; Soemers, DJNJ; Stephenson, M.; Sironi, C.; Stephenson, M.; Winands MHM; Browne, C. (2020). "Ludii – The Ludemic General Game System" (PDF) . Европейская конференция по искусственному интеллекту (ECAI 2020), Сантьяго-де-Компестела . Архивировано (PDF) из оригинала 21-01-2022 . Получено 27-10-2021 .
  42. ^ Нильсен, Торбьёрн С.; Баррос, Габриэлла АБ; Тогелиус, Джулиан; Нельсон, Марк Дж. «К созданию правил аркадных игр с помощью VGDL» (PDF) . Архивировано (PDF) из оригинала 12.09.2015 . Получено 24.02.2018 .
  43. ^ ab Левин, Джон; Конгдон, Клэр Бейтс; Эбнер, Марк; Кендалл, Грэм; Лукас, Саймон М.; Мииккулайнен Ристо, Шауль; Том, Томпсон; Томми. "General Video Game Playing" (PDF) . Архивировано (PDF) из оригинала 2016-04-18 . Получено 2016-04-09 .
  44. ^ Нойфельд, Ксения; Мостагим, Саназ; Перес-Лиебана, Диего. «Процедурная генерация уровней с программированием набора ответов для обычных видеоигр» (PDF) . Архивировано (PDF) из оригинала 28.03.2016 . Получено 24.02.2018 .
  45. ^ Свиховски, Мачей; Пак, Хёнсу; Мандзюк, Яцек; Ким, Кёнджунг (2015). «Последние достижения в области общих игр». Журнал Scientific World . 2015. Издательская корпорация Hindawi: 986262. doi : 10.1155/2015/986262 . PMC 4561326. PMID  26380375 . 
  46. ^ ab "Поиск дерева Монте-Карло для общей игры". ResearchGate . Получено 01.04.2016 .
  47. ^ Финнссон, Хильмар (2012). «Обобщенные расширения поиска по дереву Монте-Карло для общих игр». Труды Двадцать шестой конференции AAAI по искусственному интеллекту . Архивировано из оригинала 2013-10-15 . Получено 2016-04-09 .
  48. ^ Фрайденберг, Фредерик; Андерсон, Каспер Р.; Ризи, Себастьян; Тогелиус, Джулиан. «Исследование модификаций MCTS в общих видеоиграх» (PDF) . Архивировано (PDF) из оригинала 2016-04-12 . Получено 2016-04-09 .
  49. ^ M. Swiechowski; J. Mandziuk; YS Ong, «Специализация универсальной игровой программы на основе UCT для однопользовательских игр», в IEEE Transactions on Computational Intelligence and AI in Games , т. PP, № 99, стр. 1-1 doi :10.1109/TCIAIG.2015.2391232
  50. ^ "Изменение корневого узла из предыдущего игрового шага". Архивировано из оригинала 2021-01-17. DBS: Алгоритм направленного поиска в ширину (DBS)
  51. ^ ab Перес, Диего; Дискау, Йенс; Хюнермунд, Мартин. "Поиск в открытом цикле для общих видеоигр" (PDF) . Архивировано (PDF) из оригинала 28.03.2016 . Получено 09.04.2016 .
  52. ^ Йеспер Юул. Half-Real: Видеоигры между реальными правилами и вымышленными мирами. MIT Press, 2005.

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