This is an old revision of the document!
Modeling Games in GDL
The main goal of this class is to learn how to model turn games in a rule based language. After finishing the class, student should be able to model simple games and point out the difficulties related with this task.
1 Preliminaries
GDL (Game Description Language) is a language designed to describe turn games. It was created to be used in so called General Game Playing, a subdomain of the AI, focused on creating bots able to play in any game that can be formally described.
The class is based on a tutorial from Stanford and slides from the university in Dresden.
2 Modeling the World
There are two main approaches to model the world of the game:
coarse-grained — where every state of the game is a state in a giant state machine. Every unique state corresponds to one state in the machine. The state machine may grow quite impressive. Beside that state doesn't have any structure so is no really helpful if you want to exploit it to solve the problem in an intelligent manner.
fine-grained — state of the world is defined by so called
fluents, which can be treated as variables. The state here is structured (the current values of the fluents) which we may use.
GDL belongs to the fine-grained family, so there are:
fluents (actions made by the players are a special kind of fluent
game rules, which are represented by… rules
3 Example: Tic-Tac-Toe
We will show the basic features of the GDL on the example of the popular tic-tac-toe game.
Players
Let's start with players “nought” and “cross”. There is a special fact role
just to do that:
role(nought)
role(cross)
Syntax is the same as in the Prolog (or Datalog) language with the only difference, that there is no dot at the end of the sentece. All constants start with a lower-cased letter and variables are upper-cased.
Fluents
Now we should define fluents that make up the game state. In a Tic-Tac-Toe game there are 29 fleunts:
1 fluent per every cell, telling if there is a cross (x
) in the cell (9 fluents)
1 fluent per every cell, telling if there is a nought (o
) in the cell (9 fluents)
1 fluent per every cell, telling if the cell is empty (blank - b
) (9 fluents)
1 fluent per player, telling if it is his turn to play (2 fluents).
To define the fluents one uses the base
facts:
Here :-
reprenst implication ←
. &
is a logical and. In natural language the first line means: “if M and N represent cells' indexes, then there is a fluent for cell with (M, N) coordinates, telling there is a cross in it”. If we didn't use rules, we could write all the fluents by hand:
base(cell(1,1,x)) base(cell(1,1,o)) base(cell(1,1,b))
base(cell(1,2,x)) base(cell(1,2,o)) base(cell(1,2,b))
base(cell(1,3,x)) base(cell(1,3,o)) base(cell(1,3,b))
base(cell(2,1,x)) base(cell(2,1,o)) base(cell(2,1,b))
base(cell(2,2,x)) base(cell(2,2,o)) base(cell(2,2,b))
base(cell(2,3,x)) base(cell(2,3,o)) base(cell(2,3,b))
base(cell(3,1,x)) base(cell(3,1,o)) base(cell(3,1,b))
base(cell(3,2,x)) base(cell(3,2,o)) base(cell(3,2,b))
base(cell(3,3,x)) base(cell(3,3,o)) base(cell(3,3,b))
base(control(nought))
base(control(cross))
Rules in GDL have a one special feature: they can recurse, but they can't loop forever. More details here.
Available Actions
Now, we should model available actions, there are 20 of them here:
1 action per every cell, that the player puts the 'nought' in
1 action per every cell, that the player puts the 'cross' in
1 action noop
per user, telling that player does do nothing
Thee noop
action exists only in order to simulate the players' turns. When one player makes the action then the second one has to take the noop
action.
In order to define an action we use the input
predicate:
input(R, mark(M,N)) :- role(R) & index(M) & index(N)
input(R, noop) :- role(R)
The input
predicates takes two arguments, first is the player, second is the action itself.
Legal Moves
Knowing the available actions, we have to define when the action is a legal move with a legal
predicate. We use the true
predicate to check if the fluent is true at the moment..
legal(W,mark(X,Y)) :-
true(cell(X,Y,b)) &
true(control(W))
legal(nought,noop) :-
true(control(cross))
legal(cross,noop) :-
true(control(nought))
In other words - player may mark a cell only if it is empty and it is his turn. If it is not his turn, he can only perform the 'noop' action.
Initial State
Now we have to define the initial state of the game (draw the empty board). The init
predicate serves this purpose. For the tic-tac-toe every cell should be empty, and the nought
player should play first.
init(cell(M,N,b)) :- index(M) & index(N)
init(control(nought))
State Changes
Teraz przechodzimy do części najtrudniejszej — w jaki sposób zamodelować zmiany stanu świata. Zakładamy, że czas w grze jest dyskretny i w każdej kolejnej turze gry obliczany jest nowy stan świata. Zależy on jedynie od poprzedniego stanu świata oraz akcji wykonanych przez graczy. Pojawia się tutaj problem ramki (lub klatki). Nazwa pochodzi od analogii między następującymi po sobie stanami świata z klatkami na taśmie filmowej. Wszystkie klatki filmowe są od siebie niezależne, różnią się od swoich poprzedników jedynie szczegółami — reszta jest taka sama. Podobnie tutaj chcielibyśmy, żeby poza explicite zamodelowanymi zmianami, reszta świata pozostała bez zmian. W naszym przypadku oznacza to, że musimy zamodelować również brak zmiany
Do definicji reguł zmiany stany w GDL posługujemy się predykatem next
, mówiącym, czy fluent będzie prawdziwy w kolejnej turze. Predykat 'does' pozwala na sprawdzenie, jaką akcję dany gracz wykonał w aktualnej turze:
next(cell(M,N,x)) :-
does(cross,mark(M,N)) &
true(cell(M,N,b))
next(cell(M,N,o)) :-
does(nought,mark(M,N)) &
true(cell(M,N,b))
next(cell(M,N,W)) :-
true(cell(M,N,W)) &
distinct(W,b)
next(cell(M,N,b)) :-
does(W,mark(J,K)) &
true(cell(M,N,b)) &
distinct(M,J)
next(cell(M,N,b)) :-
does(W,mark(J,K))
true(cell(M,N,b)) &
distinct(N,K)
next(control(nought)) :-
true(control(cross))
next(control(cross)) :-
true(control(nought))
Akcje te kolejno oznaczają:
jeżeli komórka jest pusta, a gracz krzyżyk ją zaznaczył, to w kolejnej turze w tej komórce będzie krzyżyk
jeżeli komórka jest pusta, a gracz kółko ją zaznaczył, to w kolejnej turze w tej komórce będzie kółko
jeżeli dana komórka nie była pusta (pomocniczy predykat distinct
sprawdza tożsamość argumentów), to w kolejnej turze będzie miała te samą zawartość
jeżeli dana komórka była pusta, ale nie była komórką, która została zaznaczona, to w kolejnej turze też będzie pusta (aż dwie reguły!)
jeżeli dana tura należała do kółka, to kolejna będzie należała do krzyżyka
jeżeli dana tura należała do krzyżyka, to kolejna będzie należała do kółka
Warto zauważyć, że akcje 3 i 4 służą właśnie walce z problemem ramki.
Warunki końca gry
Każdy wie, że celem gry w kółko i krzyżyk jest ułożenie linii. Żeby sprawdzić, czy w danym stanie ułożona jest linia, należy zdefiniować odpowiednie reguły:
Zapytanie true(line(kolko))
powie nam teraz, czy na planszy jest linia kółek.
Teraz należy zdefiniować kryteria zakończenia gry, używając predykatu terminal
:
Gra się kończy, gdy:
istnieje linia krzyżyków
istnieje linia kółek
wszystkie pola są zajęte
Operator '~' oznacza negację. Podobnie jak w prologu działa ona na zasadzie świata zamkniętego, tzn. zdanie uznajemy za fałszywe, jeżeli nie potrafimy udowodnić, że jest inaczej. W GDL'u istnieją specjalne obostrzenie ograniczające stosowanie negacji, ale na razie nie musimy się tym przejmować (więcej info na slajdach z uniwersytetu z Dresden).
Kryterium zwycięstwa
Koniec zabawy — boty nie mają uczuć, nie mogą więc czerpać z gry przyjemności. Natomiast nadal mogą dostawać nagrody za dobrą grę. I naszym obowiązkiem jest te nagrody rozdać. W tym celu posługujemy się predykatem goal
:
Powyższe reguły mówią, że w przypadku zwycięstwa gracz dostaje całe 100 (tyle wygrać!), w przypadku remisu 50, a w przypadki porażki 0. Nie wiemy, co ta liczba symbolizuje, ale uznajmy, że są to ciasteczka, albo coś, czego nigdy nie za wiele.
W GDL nie ma arytmetyki — liczby nie różnią się niczym od innych stałych. Stosowane są głównie do zliczania kroków oraz rozdawania nagród.
Koniec
To by było na tyle, właśnie udało się zamodelować prostą grę w kółko i krzyżyk.
3.1 Zad 1
Weźmy przykładowy model jeszcze prostszej gry.
Odpowiedz na poniższe pytania:
jak wielu graczy występuje w grze?
jak wiele fluentów opisuje stan gry?
jak wiele jest dostępnych akcji?
ile akcji może wykonać gracz 'white' w początkowym stanie gry?
jak wiele fluentów jest prawdziwych w początkowym stanie gry?
załóżmy, że pierwszej turze gracz 'white' wykonał akcję 'a', a gracz 'black' akcję 'd'. Ile fluentów jest prawdziwych w drugiej turze?
jaka jest najmniejsza liczba kroków potrzebna do zakończenia gry?
czy gra zawsze się kończy? (czy mogłaby się zapętlić?)
3.2 Zad 2
Proszę zamodelować grę w 'krzyżyk i krzyżyk'. Podobnie jak w przypadku 'kółka i krzyżyk' mamy dziewięć pól, tym razem jednak obaj gracze stawiają krzyżyki. Przegrywa ten gracz, który pierwszy doprowadzi do powstania linii.
3.3 Zad 3
Proszę zamodelować grę w “kamień, papier, nożyce, spocka i jaszczurkę”. W razie problemów ze zrozumieniem reguł, proszę obejrzeć instrukcję video. Obrazek obok przedstawia użyteczną referencję. . Poćwiczyć można na żywo w sali, lub, jak na prawdziwego człowieka XXI wieku przystało, online....
O ile wszystko, co zostało powyżej napisane, jest prawdą, o tyle większość systemów GGP nie wspiera reprezentacji w stylu Prolog. Na potrzeby wysyłania i zapisania wiedzy (reprezentowanej w sposób regułowy) powstał format KIF (Knowledge Interchange Format). Podobnie jak w przypadku PDDL, bazuje on na lispie i używa notacji prefixowej. Ponadto symbol :-
zestępowany jest przez strzałkę ⇐
, symbol koniunkcji &
przez and
, symbol negacji ~
przez not
. Nazwy zmiennych poprzedzane są znakiem zapytania ?
. Poniżej przedstawiony jest przykład translacji z wersji a'la Prolog:
do formatu KIF:
4.1 Zad 1
Dla każdej z poniższych par określ, czy wersja prefixowa, jest wiernym tłumaczeniem wersji Prologowej.
4.2 Zad 2
4.3 Zad 3
4.4 Zad 4
Przepisz modele 'kólka i krzyżyka', 'krzyżyka i krzyżyka' oraz 'papier, kamień, nożyce, spocka i jaszczurki' do postaci KIF.
5 Walidacja modeli
Poniższe instrukcje przygotowane są z myślą o laboratorium C2 316, gdzie każdy komputer ma Eclipse.
Proszę uruchomić Eclipse i następnie:
File → Import Project
Wybrać opcję importowania z repozytorium git
Jeżeli tej opcji nie ma (Eclipse jest za stare), to trzeba ręcznie sklonować repo i zaimportować projekt z katalogu. Reszta tutejszej instrukcji nie ma sensu
Wybrać opcję klonowania z zewnętrznego
URI
-
Wybrać gałąź master
Wybrać jakiś rozsądny katalog dla projektu
Wybrać projekt ggp-base
do zaimportowania
5.1 Dodanie gier do środowiska
W katalogu projektu proszę dostać się do ścieżki games/games
i stworzyć tam trzy katalogi kolko-krzyzyk
, krzyzyk-krzyzyk
i spock
. Każdy katalog powinien zawierać dwa pliki:
5.2 Walidacja gier
Z poziomu Eclipse proszę uruchomić aplikację Validator
(rozwijana lista przy guziki play
).
Validator
, jak sama nazwa wskazuje, ma na celu sprawdzenie, czy dany model jest prawidłowym modelem GDL.
Ćwiczenia
W polu Repository
wybrać Local Game Repository
W polu Game
wybrać Tic-Tac-Toe
Wciśnąć przycisk Validate
— program powinien pokazać same sukcesy
Powtórzyć to samo dla własnych modeli
Poprawić własne modele
Zdobyć kolejne sukcesy.
6 Zabawa
Z poziomu Eclipse proszę uruchomić aplikację Kiosk
(rozwijana lista przy guziki play
).
Ćwiczenia
W polu Opponent
proszę wybrać SimpleMonteCarloPlayer
Wybrać jakąś znajomą grę
Wygrać!