Język opisu gry
Game Description Language lub GDL to logiczny język programowania zaprojektowany przez Michaela Geneseretha do ogólnych gier , jako część projektu General Game Playing na Uniwersytecie Stanforda . GDL opisuje stan gry jako ciąg faktów, a mechanikę gry jako reguły logiczne. GDL jest tym samym jedną z alternatywnych reprezentacji problemów teorii gier.
Cel GDL
Cytowany w artykule w New Scientist , Genesereth zwrócił uwagę, że chociaż Deep Blue jest w stanie grać w szachy na poziomie arcymistrzowskim , to w ogóle nie jest w stanie grać w warcaby , ponieważ jest wyspecjalizowanym graczem. Zarówno szachy, jak i warcaby można opisać w GDL. Umożliwia to zbudowanie ogólnych graczy, którzy mogą grać w obie te gry i każdą inną grę, którą można opisać za pomocą GDL.
Specyfikacja
Składnia
GDL jest odmianą Datalog , a składnia jest w dużej mierze taka sama. Zwykle podaje się go w notacji przedrostkowej . Zmienne zaczynają się od „ ? ”.
Słowa kluczowe
Poniżej znajduje się lista słów kluczowych w GDL wraz z krótkimi opisami ich funkcji:
odrębność- Ten predykat jest używany, aby wymagać, aby dwa terminy były składniowo różne.
robi- Predykat
robi(?r,?m)oznacza, że gracz (lub rola )?rwykonuje ruch?mw bieżącym stanie gry.
cel- Predykat
cel(?r,?n)służy do definiowania wartości celu?n(zwykle jest to liczba naturalna z przedziału od 0 do 100) dla roli?rw bieżącym stanie.
init- Ten predykat odnosi się do prawdziwego faktu dotyczącego początkowego stanu gry.
prawny- Predykat
legal(?r,?m)oznacza, że?mjest legalnym ruchem dla roli?rw bieżącym stanie.
next- Ten predykat odnosi się do prawdziwego faktu dotyczącego następnego stanu gry.
rola- Ten predykat służy do dodania nazwy gracza.
terminal- Ten predykat oznacza, że bieżącym stanem jest terminal.
true- Ten predykat odnosi się do prawdziwego faktu dotyczącego bieżącego stanu gry.
Zasady
Opis gry w GDL zawiera pełne zasady dla każdego z poniższych elementów gry.
Gracze
Fakty określające role w grze. Poniższy przykład pochodzi z opisu GDL gry dwuosobowej Kółko i krzyżyk :
(gracz roli) (gracz roli)
Stan początkowy
Zasady, które obejmują wszystkie fakty dotyczące początkowego stanu gry. Przykładem jest:
(init (komórka 1 1 pusta)) ... (init (komórka 3 3 pusta)) (init (sterowanie xplayer))
Ruchy prawne
Reguły, które opisują każdy ruch według warunków na aktualnej pozycji, w których gracz może go wykonać. Przykładem jest:
( <= ( legalny ?gracz ( znak ?m ?n )) ( prawda ( komórka ?m ?n pusta )) ( prawda ( kontrola ?gracz )))
Aktualizacja stanu gry
Reguły, które opisują wszystkie fakty dotyczące następnego stanu w stosunku do obecnego stanu i ruchów wykonywanych przez graczy. Przykładem jest:
( <= ( następna ( komórka ?m ?n x )) ( czy xplayer ( zaznacza ?m ?n ))) ( <= ( następna ( komórka ?m ?n o )) ( czy oplayer ( zaznacza ?m ?n ) ))
Zakończenie
Reguły opisujące warunki, w których obecny stan jest stanem końcowym. Przykładem jest:
(<= zacisk (linia x)) (<= zacisk (linia o)) (<= zacisk nieotwarty)
Stany celu
Wartości bramek dla każdego gracza w stanie terminalnym. Przykładem jest:
0
( <= ( bramka xgracz 100 ) ( linia x )) ( <= ( bramka gracza ) ( linia x ))
Rozszerzenia
GDL-II
Za pomocą GDL można opisać skończone gry z dowolną liczbą graczy. GDL nie może jednak opisywać gier, które zawierają element losowy (np. rzucanie kośćmi) lub gier, w których gracze mają niepełne informacje o aktualnym stanie gry (np. w wielu grach karcianych karty przeciwników są niewidoczne). GDL-II , Game Description Language for Incomplete Information Games , rozszerza GDL o dwa słowa kluczowe, które pozwalają na opisanie elementów przypadku i niekompletnych informacji:
widzi- Predykat
widzi(?r,?p)oznacza, że rola?rpostrzega?pw następnym stanie gry.
random- Ta stała odnosi się do predefiniowanego gracza, który losowo wybiera ruchy.
Poniżej znajduje się przykład z opisu GDL-II gry karcianej Texas Hold'em :
( <= ( widzi ? kartę ? gracza ) ( robi losowo ( deal_face_down ?player ?card ))) ( <= ( widzi ?r ?kartę ) ( role ?r ) ( robi losowo ( deal_river ?card )))
GDL III
Michael Thielscher stworzył również dalsze rozszerzenie, GDL-III , ogólny język opisu gier z niedoskonałymi informacjami i introspekcją , który wspiera specyfikację gier epistemicznych — charakteryzujących się regułami zależnymi od wiedzy graczy.
Inne formalizmy i języki reprezentacji gier
W klasycznej teorii gier gry można sformalizować w postaci ekstensywnej i normalnej . W teorii gier kooperacyjnych gry są reprezentowane za pomocą funkcji charakterystycznych. Niektóre podklasy gier umożliwiają specjalne reprezentacje w mniejszych rozmiarach, znane również jako gry zwięzłe . Niektóre z nowszych rozwinięć formalizmów i języków reprezentacji niektórych podklas gier lub reprezentacji dostosowanych do potrzeb badań interdyscyplinarnych podsumowano w poniższej tabeli. Niektóre z tych alternatywnych reprezentacji kodują również aspekty związane z czasem:
| Nazwa | Rok | Oznacza | Rodzaj gier | Czas |
|---|---|---|---|---|
| Gra w zatory | 1973 | Funkcje | podzbiór gier n-osobowych, jednoczesne ruchy | NIE |
| Forma sekwencyjna | 1994 | macierze | Gry 2-osobowe z niedoskonałą informacją | NIE |
| Gry na czas | 1994 | Funkcje | Gry 2-osobowe | Tak |
| Gala | 1997 | logika | n-osobowe gry niedoskonałych informacji | NIE |
| Gry graficzne | 2001 | wykresy, funkcje | gry n-osobowe, ruchy symultaniczne | NIE |
| Gry z efektem lokalnym | 2003 | Funkcje | podzbiór gier n-osobowych, jednoczesne ruchy | NIE |
| Gra Sieci Petriego | 2006 | Sieć Petriego | deterministyczne gry n-osobowe, ruchy symultaniczne | NIE |
| Ciągłe gry | 2007 | Funkcje | podzbiór 2-osobowych gier o niedoskonałych informacjach | Tak |
| PNSI | 2008 | Sieć Petriego | n-osobowe gry niedoskonałych informacji | Tak |
| Gry z wykresem akcji | 2012 | wykresy, funkcje | gry n-osobowe, ruchy symultaniczne | NIE |
Aplikacje
Artykuł z 2016 roku „opisuje wielopoziomowy algorytm kompilujący ogólny opis gry w GDL w zoptymalizowany mechanizm rozumujący w języku niskiego poziomu”.
Artykuł z 2017 roku wykorzystuje GDL do modelowania procesu mediacji w celu rozwiązania sporu między dwiema stronami i przedstawia algorytm, który skutecznie wykorzystuje w tym celu dostępne informacje.