Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Язык описания игр , или GDL, - это язык логического программирования [1], разработанный Майклом Дженезеретом в рамках проекта General Game Playing Project в Стэнфордском университете , Калифорния . GDL описывает состояние игры как набор фактов, а игровую механику как логические правила. Таким образом, GDL является одним из альтернативных представлений теоретико-игровых задач. [2]

Назначение GDL [ править ]

Цитируемый в статье New Scientist , Джинесерет указал, что, хотя Deep Blue может играть в шахматы на уровне гроссмейстера , он вообще не способен играть в шашки, потому что он специализированный игрок. [3] И шахматы, и шашки могут быть описаны в GDL. Это позволяет создавать обычных игроков, которые могут играть как в эти игры, так и в любую другую игру, которую можно описать с помощью GDL.

Спецификация [ править ]

Синтаксис [ править ]

GDL - это вариант Datalog , и его синтаксис в основном тот же. Обычно это дается в виде префикса . Переменные начинаются с " ?". [4]

Ключевые слова [ править ]

Ниже приводится список ключевых слов в 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 игры « Крестики-нолики» для двух игроков :

(роль xplayer)(ролевой игрок)

Исходное состояние [ править ]

Правила, которые включают в себя все факты о начальном состоянии игры. Пример:

(инициализация (ячейка 1 1 пустая))...(инициализация (ячейка 3 3 пустая))(init (контроль xplayer))

Правовые ходы [ править ]

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

( <= ( законный  ? игрок  ( отметка  ? m  ? n ))  ( true  ( ячейка  ? m  ? n  пусто ))  ( true  ( control  ? player )))

Обновление состояния игры [ править ]

Правила, описывающие все факты о следующем состоянии относительно текущего состояния и ходы, сделанные игроками. Пример:

( <= ( next  ( cell  ? m  ? n  x ))  ( делает ли  xplayer  ( mark  ? m  ? n ))) ( <= ( next  ( cell  ? m  ? n  o ))  ( делает ли  oplayer  ( mark  ? m  ? n ) ))

Прекращение действия [ править ]

Правила, описывающие условия, при которых текущее состояние является конечным. Пример:

(<= терминал (строка x))(<= терминал (строка o))(<= терминал не доска открыта)

Состояния целей [ править ]

Ценность целей для каждого игрока в конечном состоянии. Пример:

( <= ( цель  x игрок  100 )  ( строка  x )) ( <= ( цель  игрок  0 )  ( строка  x ))

Расширения [ править ]

GDL-II [ править ]

С помощью GDL можно описывать конечные игры с произвольным числом игроков. Однако GDL не может описывать игры, которые содержат элемент случая (например, бросание кубиков) или игры, в которых у игроков есть неполная информация о текущем состоянии игры (например, во многих карточных играх карты оппонентов не видны). GDL-II , язык описания игр для игр с неполной информацией, расширяет GDL двумя ключевыми словами, которые позволяют описывать элементы случайности и неполной информации: [5]

sees
Предикат sees(?r,?p)означает, что роль ?rвоспринимается ?pв следующем игровом состоянии.
random
Эта константа относится к заранее определенному игроку, который выбирает ходы случайным образом.

Ниже приводится пример из описания GDL-II карточной игры Техасский холдем :

( <= ( видит  ?  карту игрока )  ( делает  random  ( deal_face_down  ? player  ? card ))) ( <= ( видит  ? r  ? карту )  ( role  ? r )  ( делает  random  ( deal_river  ? card )))

GDL-III [ править ]

Майкл Тильшер также создал дальнейшее расширение, GDL-III , общий язык описания игр с несовершенной информацией и самоанализом , который поддерживает спецификацию эпистемических игр - игр, для которых характерны правила, зависящие от знаний игроков. [6]

Другие формализмы и языки для представления игр [ править ]

Смотрите также: Теория игр § Представление игр

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

ИмяГодСредстваТип игрВремя
Игра с перегрузкой [8]1973функцииподмножество игр n человек, одновременные ходыНет
Последовательная форма [9]1994 г.матрицыИгры для двоих с несовершенной информациейНет
Игры на время [10] [11]1994 г.функцииИгры на двоихда
Гала [12]1997 г.логикаигры с несовершенной информацией для n человекНет
Игры с локальным эффектом [13]2003 г.функцииподмножество игр n человек, одновременные ходыНет
Игровые сети Петри [14]2006 г.Сеть Петридетерминированные игры от n человек, одновременные ходыНет
Непрерывные игры [15]2007 г.функцииподмножество игр для двух человек с несовершенной информациейда
PNSI [16] [17]2008 г.Сеть Петриигры с несовершенной информацией для n человекда
Графические игры действий [18]2012 г.графики, функцииигры n человек, одновременные ходыНет
Графические игры [19]2015 г.графики, функцииигры n человек, одновременные ходыНет

Приложения [ править ]

В статье 2016 года «описан многоуровневый алгоритм, объединяющий общее описание игры в GDL в оптимизированный модуль рассуждений на языке низкого уровня». [20]

В документе 2017 года GDL используется для моделирования процесса посредничества в разрешении спора между двумя сторонами и представлен алгоритм, который для этого эффективно использует доступную информацию. [21]

См. Также [ править ]

  • Общая игра
  • Искусственный интеллект

Ссылки [ править ]

  1. ^ «Язык определения игры» . games.stanford.edu .
  2. ^ Tagiew Рустам (2011). Аверкин, Алексей Н .; Игнатов, Дмитрий И .; Митра, Сушмита; Poelmans, Йонас (ред.). «Помимо аналитического моделирования, сбор данных для прогнозирования стратегического взаимодействия реальных агентов» [Приложения для мягких вычислений и обнаружение знаний] (PDF) . Материалы семинара CEUR . Москва, Россия. Том 758: 113--124. |volume=есть дополнительный текст ( справка )
  3. ^ Бивер, Celeste (2006-07-29). «Производство лучших игровых ботов - технология - 29 июля 2006 года - New Scientist Tech» . Архивировано 11 августа 2007 года.
  4. ^ Любовь, N; Genesereth, M; Хинрикс, Т. (2006). «Общие игры: спецификация языка описания игр. Tech. Rep. LG-2006-01» (PDF) . Стэнфордский университет . Стэнфордский университет, Стэнфорд . Проверено 1 июля 2019 года .
  5. ^ Thielscher, M (2010). Фокс, М; Пул, Д. (ред.). «Общий язык описания игр для игр с неполной информацией» . Материалы двадцать четвертой конференции AAAI по искусственному интеллекту, AAAI 2010 . Атланта: AAAI Press . Проверено 1 июля 2019 года .
  6. ^ Тильшер, Майкл (2017). «GDL-III: язык описания эпистемической общей игры» (PDF) . Материалы двадцать шестой международной совместной конференции по искусственному интеллекту . IJCAI. ISBN  978-0-9992411-0-3. Проверено 1 июля 2019 года .
  7. ^ Tagiew Рустам (3 мая 2011). «Если для прогнозирования стратегического взаимодействия реальных агентов необходимо нечто большее, чем аналитическое моделирование». arXiv : 1105.0558 [ cs.GT ].
  8. ^ Розенталь, Роберт В. (декабрь 1973). «Класс игр, обладающих равновесием Нэша чистой стратегией». Международный журнал теории игр . 2 (1): 65–67. DOI : 10.1007 / BF01737559 . S2CID 121904640 . 
  9. ^ Коллер, Дафна ; Мегиддо, Нимрод ; фон Стенгель, Бернхард (1994). «Быстрые алгоритмы поиска рандомизированных стратегий в деревьях игр». STOC '94: Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений : 750–759. DOI : 10.1145 / 195058.195451 . ISBN 0-89791-663-8. S2CID  1893272 .
  10. ^ Алур, Раджив; Дилл, Дэвид Л. (апрель 1994 г.). «Теория временных автоматов». Теоретическая информатика . 126 (2): 183–235. DOI : 10.1016 / 0304-3975 (94) 90010-8 .
  11. ^ Томлин, CJ; Lygeros, J .; Шанкар Састри, С. (июль 2000 г.). «Теоретико-игровой подход к разработке контроллера для гибридных систем». Труды IEEE . 88 (7): 949–970. DOI : 10.1109 / 5.871303 . S2CID 1844682 . 
  12. ^ Коллер, Дафна; Пфеффер, Ави (1997). "Представления и решения теоретико-игровых задач" (PDF) . Искусственный интеллект . 94 (1-2): 167-215. DOI : 10.1016 / S0004-3702 (97) 00023-4 .
  13. ^ Лейтон-Браун, Кевин; Тенненхольц, Моше (2003). «Игры с локальным эффектом» . IJCAI'03: Материалы 18-й Международной совместной конференции по искусственному интеллекту .
  14. ^ Клемпнер, Хулио (2006). «Моделирование игр кратчайшего пути с помощью сетей Петри: теория, основанная на Ляпунове» . Международный журнал прикладной математики и информатики . 16 (3): 387–397. ISSN 1641-876X . 
  15. ↑ Санников, Юлий (сентябрь 2007 г.). «Игры с несовершенно наблюдаемыми действиями в непрерывном времени» (PDF) . Econometrica . 75 (5): 1285–1329. DOI : 10.1111 / j.1468-0262.2007.00795.x .
  16. ^ Tagiew Рустам (декабрь 2008). "Мультиагентные игры Петри". 2008 Международная конференция по вычислительному интеллекту для моделирования автоматизации управления : 130–135. DOI : 10.1109 / CIMCA.2008.15 . ISBN 978-0-7695-3514-2. S2CID  16679934 .
  17. ^ Tagiew Рустам (2009). "О многоагентных моделях сетей Петри для вычисления обширных конечных игр". Новые вызовы вычислительного коллективного разума . Исследования в области вычислительного интеллекта. Springer. 244 : 243–254. DOI : 10.1007 / 978-3-642-03958-4_21 . ISBN 978-3-642-03957-7.
  18. ^ Бхат, Навин; Лейтон-Браун, Кевин (11 июля 2012 г.). "Вычисление равновесия Нэша в играх с графическим действием". arXiv : 1207.4128 [ cs.GT ].
  19. ^ Кирнс, Майкл; Littman, Michael L .; Сингх, Сатиндер (7 марта 2015 г.). «Графические модели для теории игр». arXiv : 1301.2281 [ cs.GT ].
  20. ^ Ковальский, Якуб; Шикула, Марек (2013). «Создание компилятора языка описания игр» . AI 2013: достижения в области искусственного интеллекта: 26-я Австралазийская совместная конференция, Данидин, Новая Зеландия, 1-6 декабря 2013 г. Материалы . С. 234–245 . Проверено 1 июля 2019 года .
  21. ^ де Джонг, Дэйв; Трескак, ​​Томаш; Сьерра, Карлес; Симофф, Симеон; Лопес де Мантарас, Рамон (2017). «Использование языка описания игр для урегулирования споров при посредничестве». AI и общество . Springer. 2017 (4): 767–784. DOI : 10.1007 / s00146-017-0790-8 .

Внешние ссылки [ править ]

  • Спецификация языка описания игры
  • Реферированный документ, знакомящий с GDL-II