Язык описания игры
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Язык описания игр (GDL) — специализированный язык логического программирования, разработанный Майклом Дженезеретом . Цель GDL — обеспечить разработку агентов искусственного интеллекта, способных участвовать в обычных играх . Это часть проекта General Game Playing в Стэнфордском университете .
GDL — это инструмент для выражения тонкостей игровых правил и динамики в форме, понятной для систем искусственного интеллекта, посредством сочетания логических конструкций и декларативных принципов.
На практике GDL часто используется для соревнований по обычным играм и исследовательских работ. В этих контекстах GDL используется для определения правил игр, в которые должны играть агенты ИИ. Разработчики и исследователи ИИ используют GDL для создания алгоритмов, которые могут понимать игры и взаимодействовать с ними на основе описаний их правил. Использование GDL открывает путь к разработке легко адаптируемых агентов ИИ, способных конкурировать и преуспевать в различных игровых сценариях.
Это нововведение является свидетельством сближения логического формализма и мира игр, открывая новые горизонты для потенциала ИИ в понимании и освоении множества игр. Язык описания игры дает ИИ универсальный ключ, позволяющий раскрыть тайны разнообразных игровых сред и стратегий.
Цель GDL [ править ]
Цитируемый в статье в New Scientist Генесерет отметил, что, хотя Deep Blue может играть в шахматы на уровне гроссмейстера , он вообще не способен играть в шашки, поскольку является специализированным игроком. [1] И шахматы, и шашки можно описать в GDL. Это позволяет создавать обычных игроков, способных играть в обе эти игры, а также в любую другую игру, которую можно описать с помощью GDL.
Спецификация [ править ]
Синтаксис [ править ]
GDL — это вариант Datalog , синтаксис которого во многом тот же. Обычно он дается в префиксной записи . Переменные начинаются с " ?". [2]
Ключевые слова [ править ]
Ниже приводится список ключевых слов в GDL, а также краткое описание их функций:
distinct- Этот предикат используется, чтобы потребовать, чтобы два термина были синтаксически разными.
does- Предикат
does(?r,?m)означает, что игрок (или роль )?rделает ход?mв текущем состоянии игры.
goal- Предикат
goal(?r,?n)используется для определения ценности цели?n(обычно натуральное число от 0 до 100) для роли?rв нынешнем состоянии.
init- Этот предикат относится к истинному факту начального состояния игры.
legal- Предикат
legal(?r,?m)означает, что?mэто законный ход за роль?rв нынешнем состоянии.
next- Этот предикат относится к истинному факту о следующем состоянии игры.
role- Этот предикат используется для добавления имени игрока.
terminal- Этот предикат означает, что текущее состояние является терминальным.
true- Этот предикат относится к истинному факту о текущем состоянии игры.
Правила [ править ]
Описание игры в GDL содержит полные правила для каждого из следующих элементов игры.
Игроки [ править ]
Факты, определяющие роли в игре. Следующий пример взят из описания GDL игры для двух игроков « Крестики-нолики» :
(role xplayer) (role oplayer)
Исходное состояние [ править ]
Правила, которые включают в себя все факты об исходном состоянии игры. Пример:
(init (cell 1 1 blank)) ... (init (cell 3 3 blank)) (init (control xplayer))
Законные ходы [ править ]
Правила, описывающие каждый ход условиями на текущей позиции, при которых он может быть сделан игроком. Пример:
(<= (legal ?player (mark ?m ?n))
(true (cell ?m ?n blank))
(true (control ?player)))
Обновление состояния игры [ править ]
Правила, которые описывают все факты о следующем состоянии относительно текущего состояния и ходов, предпринятых игроками. Пример:
(<= (next (cell ?m ?n x))
(does xplayer (mark ?m ?n)))
(<= (next (cell ?m ?n o))
(does oplayer (mark ?m ?n)))
Прекращение действия [ править ]
Правила, описывающие условия, при которых текущее состояние является терминальным. Пример:
(<= terminal
(line x))
(<= terminal
(line o))
(<= terminal
not boardopen)
Состояния целей [ править ]
Целевые значения для каждого игрока в терминальном состоянии. Пример:
(<= (goal xplayer 100)
(line x))
(<= (goal oplayer 0)
(line x))
Расширения [ править ]
ГДЛ-II [ править ]
С помощью GDL можно описать конечные игры с произвольным числом игроков. Однако GDL не может описывать игры, содержащие элемент случайности (например, бросок кубиков) или игры, в которых игроки имеют неполную информацию о текущем состоянии игры (например, во многих карточных играх карты противников не видны). GDL-II , язык описания игр для игр с неполной информацией , расширяет GDL двумя ключевыми словами, которые позволяют описывать элементы случайности и неполной информации: [3]
sees- Предикат
sees(?r,?p)означает, что роль?rвоспринимает?pв следующем игровом состоянии.
random- Эта константа относится к заранее определенному игроку, который выбирает ходы случайным образом.
Ниже приведен пример описания карточной игры Техасский холдем в GDL-II :
(<= (sees ?player ?card)
(does random (deal_face_down ?player ?card)))
(<= (sees ?r ?card)
(role ?r)
(does random (deal_river ?card)))
ГДЛ-III [ править ]
Майкл Тильшер также создал дальнейшее расширение, GDL-III , общий язык описания игр с несовершенной информацией и самоанализом , который поддерживает спецификацию эпистемических игр — игр, характеризующихся правилами, зависящими от знаний игроков. [4]
представления Другие формализмы и языки игр
В классической теории игр игры могут быть формализованы в развернутой и нормальной формах. В теории кооперативных игр игры представляются с помощью характеристических функций. Некоторые подклассы игр допускают специальные представления меньших размеров, также известные как краткие игры . Некоторые из новейших разработок формализмов и языков для представления некоторых подклассов игр или представлений, адаптированных к потребностям междисциплинарных исследований, обобщены в следующей таблице. [5] Некоторые из этих альтернативных представлений также кодируют аспекты, связанные со временем:
| Имя | Год | Означает | Тип игр | Время |
|---|---|---|---|---|
| Игра с пробками [6] | 1973 | функции | подмножество игр для n человек, одновременные ходы | Нет |
| Последовательная форма [7] | 1994 | матрицы | Игры для двоих с несовершенной информацией | Нет |
| Игры на время [8] [9] | 1994 | функции | игры для двоих | Да |
| Гала [10] | 1997 | логика | игры с несовершенной информацией для n человек | Нет |
| Графические игры [11] [12] | 2001 | графики, функции | игры для n человек, одновременные ходы | Нет |
| Игры с локальным эффектом [13] | 2003 | функции | подмножество игр для n человек, одновременные ходы | Нет |
| Игры Сети Петри [14] | 2006 | сеть Петри | детерминированные игры для n человек, одновременные ходы | Нет |
| Непрерывные игры [15] | 2007 | функции | подмножество игр для двоих с несовершенной информацией | Да |
| ПНСИ [16] [17] | 2008 | сеть Петри | игры с несовершенной информацией для n человек | Да |
| Графические игры действия [18] | 2012 | графики, функции | игры для n человек, одновременные ходы | Нет |
Приложения [ править ]
![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( июль 2019 г. ) |
В статье 2016 года «описывается многоуровневый алгоритм, компилирующий общее описание игры на GDL в оптимизированное средство рассуждения на языке низкого уровня». [19]
В статье 2017 года GDL используется для моделирования процесса посредничества в разрешении спора между двумя сторонами и представлен алгоритм, который эффективно использует для этого имеющуюся информацию. [20]
См. также [ править ]
Ссылки [ править ]
- ^ Бивер, Селеста (29 июля 2006 г.). «Создание совершенных игровых ботов — технологии — 29 июля 2006 г. — New Scientist Tech» . Архивировано из оригинала 11 августа 2007 года.
- ^ Любовь, Н; Генесерет, М; Хинрикс, Т. (2006). «Общая игра: спецификация языка описания игры. Технический представитель LG-2006-01» (PDF) . Стэнфордский университет . Стэнфордский университет, Стэнфорд . Проверено 1 июля 2019 г.
- ^ Тильшер, М. (2010). Фокс, М; Пул, Д. (ред.). «Общий язык описания игр для игр с неполной информацией» . Материалы двадцать четвертой конференции AAAI по искусственному интеллекту, AAAI 2010 . Атланта: AAAI Press . Проверено 1 июля 2019 г.
- ^ Тильшер, Майкл (2017). «GDL-III: язык описания для эпистемических общих игр» (PDF) . Материалы двадцать шестой Международной совместной конференции по искусственному интеллекту . IJCAI. ISBN 978-0-9992411-0-3 . Проверено 1 июля 2019 г.
- ^ Тагиев, Рустам (3 мая 2011 г.). «Если для прогнозирования стратегического взаимодействия реальных агентов необходимо нечто большее, чем аналитическое моделирование». arXiv : 1105.0558 [ cs.GT ].
- ^ Розенталь, Роберт В. (декабрь 1973 г.). «Класс игр, обладающих чисто стратегическим равновесием Нэша». Международный журнал теории игр . 2 (1): 65–67. дои : 10.1007/BF01737559 . S2CID 121904640 .
- ^ Коллер, Дафна ; Мегиддо, Нимрод ; фон Стенгель, Бернхард (1994). «Быстрые алгоритмы поиска рандомизированных стратегий в деревьях игр». Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '94 . стр. 750–759. дои : 10.1145/195058.195451 . ISBN 0-89791-663-8 . S2CID 1893272 .
- ^ Алур, Раджив; Дилл, Дэвид Л. (апрель 1994 г.). «Теория синхронизированных автоматов» . Теоретическая информатика . 126 (2): 183–235. дои : 10.1016/0304-3975(94)90010-8 .
- ^ Томлин, CJ; Лигерос, Дж.; Шанкар Шастри, С. (июль 2000 г.). «Теоретико-игровой подход к проектированию контроллеров для гибридных систем». Труды IEEE . 88 (7): 949–970. CiteSeerX 10.1.1.129.8347 . дои : 10.1109/5.871303 . S2CID 1844682 .
- ^ Коллер, Дафна; Пфеффер, Ави (1997). «Представления и решения теоретико-игровых задач» (PDF) . Искусственный интеллект . 94 (1–2): 167–215. дои : 10.1016/S0004-3702(97)00023-4 .
- ^ Майкл, Майкл Кернс; Литтман, Майкл Л. (2001). «Графические модели для теории игр». В УАИ : 253–260. CiteSeerX 10.1.1.22.5705 .
- ^ Кернс, Майкл; Литтман, Майкл Л.; Сингх, Сатиндер (7 марта 2011 г.). «Графические модели для теории игр». arXiv : 1301.2281 [ cs.GT ].
- ^ Лейтон-Браун, Кевин; Тенненхольц, Моше (2003). «Игры с локальным эффектом» . IJCAI'03: Материалы 18-й Международной совместной конференции по искусственному интеллекту : 772–777.
- ^ Клемпнер, Хулио (2006). «Моделирование игр по кратчайшему пути с помощью сетей Петри: теория, основанная на Ляпунове» . Международный журнал прикладной математики и информатики . 16 (3): 387–397. ISSN 1641-876X .
- ^ Санников, Юлий (сентябрь 2007 г.). «Игры с несовершенно наблюдаемыми действиями в непрерывном времени» (PDF) . Эконометрика . 75 (5): 1285–1329. дои : 10.1111/j.1468-0262.2007.00795.x .
- ^ Тагиев, Рустам (декабрь 2008 г.). «Мультиагентные игры Петри». 2008 Международная конференция по вычислительному интеллекту для моделирования управления и автоматизации . стр. 130–135. дои : 10.1109/CIMCA.2008.15 . ISBN 978-0-7695-3514-2 . S2CID 16679934 .
- ^ Тагиев, Рустам (2009). «О многоагентных моделях сетей Петри для вычисления обширных конечных игр». Новые вызовы в области вычислительного коллективного разума . Исследования в области вычислительного интеллекта. Том. 244. Спрингер. стр. 243–254. дои : 10.1007/978-3-642-03958-4_21 . ISBN 978-3-642-03957-7 .
- ^ Бхат, Навин; Лейтон-Браун, Кевин (11 июля 2012 г.). «Вычисление равновесия Нэша в играх с графом действий». arXiv : 1207.4128 [ cs.GT ].
- ^ Ковальски, Якуб; Шикула, Марек (2013). «Создание компилятора языка описания игры» . AI 2013: Достижения в области искусственного интеллекта: 26-я Австралазийская совместная конференция, Данидин, Новая Зеландия, 1–6 декабря 2013 г. Материалы . стр. 234–245 . Проверено 1 июля 2019 г.
- ^ де Йонге, Дэйв; Трескак, Томас; Сьерра, Карлес; Симофф, Симеон; Лопес де Мантарас, Рамон (2017). «Использование языка описания игры для опосредованного разрешения споров». ИИ и общество . 2017 (4). Спрингер: 767–784. дои : 10.1007/s00146-017-0790-8 . S2CID 22738517 .