|
|
pl:dydaktyka:ggp:gdl [2016/04/27 10:25] msl [Kryterium zwycięstwa] |
pl:dydaktyka:ggp:gdl [2019/06/27 15:50] |
====== - Modelowanie gier w GDL ====== | |
| |
Celem laboratorium jest zrozumienie regułowego opisu gier turowych. Student po zakończeniu laboratorium powinien potrafić zamodelować proste gry oraz wskazać trudności związane z tym zadaniem. | |
| |
===== - Preliminaria ===== | |
| |
GDL (Game Description Language) jest językiem opisu gier turowych. Powstał na potrzeby General Game Playing - działu sztucznej inteligencji, który zajmuje się szukaniem strategii grania, które działałyby niezależnie od zasad gry. Innymi słowy, bot powinien być w stanie grać (i wygrać) w dowolną grę opisaną w języku GDL. | |
| |
Laboratoria bazują w dużej mierze na [[http://logic.stanford.edu/ggp/chapters/chapter_02.html|tutorialu ze Stanfordu]] oraz [[http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/winter09/ggp/kapitel2.pdf|slajdach z uniwersytetu z Dresden]]. | |
| |
===== - Modelowania świata gry ===== | |
| |
Istnieją dwa zasadnicze podejścia do modelowania świata/środowiska gry. Jedno z nich (nazwijmy je gruboziarnistym) traktuje świat jako maszynę stanową - gdzie każdy unikalny stan świata jest reprezentowany jako oddzielny stan maszyny. Unikalność stanu traktujemy tu na poważnie, //co do jednego zaplutego, spróchniałego pnia//, zatem można się domyślić, że maszyna stanowa nawet dla prostych gier będzie ogromna. Poza tym stan jest czymś pozbawionym struktury, co nie pomaga w inteligentnym rozwiązywaniu problemu. | |
| |
Z drugiej strony mamy języki w stylu PDDL, które dynamikę świata modelują przy użyciu fluentów - zdań logicznych, które zmieniają wartość. Tutaj stan świata ma strukturę (aktualne wartościowanie fluentów), które można wykorzystać podczas planowania, wnioskowania, etc. | |
| |
GDL należy do drugiego podejścia - stan gry modelowany jest poprzez fluenty. Poza nimi w skład gry wchodzą akcje graczy (również modelowane w postaci fluentów) oraz reguły gry, które są reprezentowane w postaci... reguł. | |
| |
| |
===== - Przykład: Kółko i krzyżyk ===== | |
| |
Przedstawmy GDL na przykładzie gry [[http://playtictactoe.org/|kółko i krzyżyk]]. | |
| |
==== Gracze ==== | |
| |
Zacznijmy od tego, że w grze występuje dwóch graczy o pięknych imionach "kolko" i "krzyzyk". Służy do tego predefiniowany fakt ''role'': | |
| |
<code prolog> | |
role(kolko) | |
role(krzyzyk) | |
</code> | |
| |
Składnia jest taka sama jak w języku [[pl:prolog:start|Prolog]] (lub Datalog) z tą różnicą, że na końcu nie ma kropki. Ponownie stałe pisane są małą, a zmienne wielką literą. | |
| |
==== Definiowanie fluentów ==== | |
| |
Następnie należy zdefiniować fluenty, które będą opisywać stan gry. W przypadku kółka i krzyżyk stan gry opisany jest przy pomocy 29 fluentów: | |
* po 1 fluencie na każdą komórkę, mówiącym, czy w tej komórce jest krzyżyk (razem 9 fluentów) | |
* po 1 fluencie na każdą komórkę, mówiącym, czy w tej komórce jest kółko (razem 9 fluentów) | |
* po 1 fluencie na każdą komórkę, mówiącym, czy ta komórka jest pusta (razem 9 fluentów) | |
* po 1 fluencie na każdego gracza, mówiącym, czy to jest tura danego gracza (razem 2 fluenty). | |
| |
W celu zdefiniowania fluentów należy się posłużyć predefiniowanym predykatem ''base'': | |
| |
<code prolog> | |
base(cell(M,N,x)) :- index(M) & index(N) | |
base(cell(M,N,o)) :- index(M) & index(N) | |
base(cell(M,N,b)) :- index(M) & index(N) | |
| |
base(control(R)) :- role(R) | |
| |
index(1) | |
index(2) | |
index(3) | |
</code> | |
| |
Symbol '':-'' to podobnie jak w Prologu implikacja ''<-''. ''&'' reprezentuje koniunkcję. W języku naturalnym można powiedzieć, że pierwsza linijka powyższego kodu oznacza: "jeżeli M i N to prawidłowe indeksy komórki, to istnieje fluent dla komórki o współrzędnych M i N, mówiący o tym, że jest w niej krzyżyk". Bez użycia reguł musielibyśmy wszystkie fluenty definiować wprost: | |
| |
<code prolog> | |
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(kolko)) | |
base(control(krzyzyk)) | |
</code> | |
| |
| |
Reguły w GDL'u różnią się od reguł Prologowych pod jednym ważnym aspektem: musi być zapewniony fakt, że się nie zapętlą. Więcej szczegółów na ten temat w [[http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/winter09/ggp/kapitel2.pdf|slajdach z uniwersytetu z Dresden]]. | |
| |
==== Dostępne akcje ==== | |
| |
Teraz należy się zastanowić nad tym, jakie akcje są wykonywalne w grze. W przypadku kółka i krzyżyk jest ich 20: | |
| |
* 1 akcja dla każdej komórki, mówiąca, że gracz 'kółko' ją zaznacza (łącznie 9) | |
* 1 akcja dla każdej komórki, mówiąca, że gracz 'krzyżyk' ją zaznacza (łącznie 9) | |
* 1 akcja ''noop'' dla każdego grazca, mówiąca, że gracz nie wykonał ruchu (łącznie 2). | |
| |
Akcja ''noop'' istnieje tylko po to, żeby zasymulować odpowiednio ruchy graczy //na zmianę//. Gracz w nie swojej turze może jedynie wykonać ''noop''. | |
| |
W celu zdefiniowania akcji posługujemy się wbudowanym predykatem ''input'': | |
| |
<code prolog> | |
input(R,mark(M,N)) :- role(R) & index(M) & index(N) | |
input(R, noop) :- role(R) | |
</code> | |
| |
Predykat ''input'' przyjmuje dwa argumenty, pierwszy to nazwa gracza, który może wykonać akcję, drugim jest sama akcja. | |
| |
==== Dozwolone ruchy ==== | |
| |
Teraz, znając już możliwe akcje, wypadałoby powiedzieć, kiedy dany ruch jest dozwolony. Służy do tego predykat ''legal''. Aby sprawdzić, czy dany fluent jest aktualnie prawdziwy posługujemy się predykatem ''true''. | |
| |
<code> | |
legal(W,mark(X,Y)) :- | |
true(cell(X,Y,b)) & | |
true(control(W)) | |
| |
legal(kolko,noop) :- | |
true(control(krzyzyk)) | |
| |
legal(krzyzyk,noop) :- | |
true(control(kolko)) | |
</code> | |
| |
Innymi słowy - gracz może zaznaczyć dane pole, o ile jest puste i jest jego tura. Gracz może też wykonać akcję ''noop'', jeżeli tura należy do przeciwnika. | |
| |
==== Stan początkowy ==== | |
| |
Podobnie jak w PDDL'u, musimy zdefiniować stan początkowy świata. Służy do tego tego predykat ''init''. Możemy przy jego pomocy określić, które fluenty są prawdziwe u zarania dziejów. Dla kółka i krzyżyk, wszystkie komórki są puste, a tura należy do kółka: | |
| |
<code prolog> | |
init(cell(M,N,b)) :- index(M) & index(N) | |
init(control(kolko)) | |
</code> | |
| |
==== Zmiana stanu ==== | |
| |
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 [[https://en.wikipedia.org/wiki/Frame_problem#Fluent_calculus_solution|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: | |
| |
<code prolog> | |
next(cell(M,N,x)) :- | |
does(krzyzyk,mark(M,N)) & | |
true(cell(M,N,b)) | |
| |
next(cell(M,N,o)) :- | |
does(kolko,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(kolko)) :- | |
true(control(krzyzyk)) | |
| |
next(control(krzyzyk)) :- | |
true(control(kolko)) | |
</code> | |
| |
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: | |
| |
<code prolog> | |
line(Z) :- row(M,Z) | |
line(Z) :- column(M,Z) | |
line(Z) :- diagonal(Z) | |
| |
row(M,Z) :- | |
true(cell(M,1,Z)) & | |
true(cell(M,2,Z)) & | |
true(cell(M,3,Z)) | |
| |
column(N,Z) :- | |
true(cell(1,N,Z)) & | |
true(cell(2,N,Z)) & | |
true(cell(3,N,Z)) | |
| |
diagonal(Z) :- | |
true(cell(1,1,Z)) & | |
true(cell(2,2,Z)) & | |
true(cell(3,3,Z)) | |
| |
diagonal(Z) :- | |
true(cell(1,3,Z)) & | |
true(cell(2,2,Z)) & | |
true(cell(3,1,Z)) | |
</code> | |
| |
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'': | |
| |
<code prolog> | |
terminal :- line(x) | |
terminal :- line(o) | |
terminal :- ~open | |
| |
open :- true(cell(M,N,b)) | |
</code> | |
| |
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 [[https://en.wikipedia.org/wiki/Closed-world_assumption|ś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 [[http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/winter09/ggp/kapitel2.pdf|slajdach z uniwersytetu z Dresden]]). | |
| |
==== Kryterium zwycięstwa ==== | |
| |
{{ :pl:dydaktyka:ggp:tyle_wygrac.jpg?200|}} | |
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'': | |
| |
<code prolog> | |
goal(kolko,100) :- line(x) & ~line(o) | |
goal(kolko,50) :- ~line(x) & ~line(o) | |
goal(kolko,0) :- ~line(x) & line(o) | |
| |
goal(krzyzyk,100) :- ~line(x) & line(o) | |
goal(krzyzyk,50) :- ~line(x) & ~line(o) | |
goal(krzyzyk,0) :- line(x) & ~line(o) | |
</code> | |
| |
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. | |
| |
<WRAP center round tip 60%> | |
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. | |
</WRAP> | |
| |
| |
==== Koniec ==== | |
| |
To by było na tyle, właśnie udało się zamodelować prostą grę w kółko i krzyżyk. | |
| |
=== - Zad 1 === | |
| |
Weźmy przykładowy model jeszcze prostszej gry. | |
| |
<code prolog> | |
role(white) | |
role(black) | |
| |
base(p) | |
base(q) | |
base(r) | |
base(s) | |
| |
input(R,a) :- role(R) | |
input(R,b) :- role(R) | |
input(R,c) :- role(R) | |
input(R,d) :- role(R) | |
| |
init(s) | |
| |
legal(white,a) | |
legal(white,b) | |
legal(white,c) | |
legal(black,d) | |
| |
next(p) :- does(white,a) & ~true(p) | |
next(p) :- ~does(white,a) & true(p) | |
next(q) :- does(white,b) & true(p) | |
next(q) :- does(white,c) & true(r) | |
next(q) :- ~does(white,b) & ~does(white,c) & true(q) | |
next(r) :- does(white,c) & true(q) | |
next(r) :- ~does(white,c) & true(r) | |
| |
goal(white,100) :- terminal | |
goal(white,0) :- ~terminal | |
goal(black,100) :- terminal | |
goal(black,0) :- ~terminal | |
| |
terminal :- true(p) & true(q) & true(r) | |
</code> | |
| |
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ć?) | |
| |
=== - 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. | |
| |
=== - Zad 3 === | |
| |
{{ :pl:dydaktyka:ggp:rock-paper-spock.jpg?300|}} | |
Proszę zamodelować grę w "kamień, papier, nożyce, spocka i jaszczurkę". W razie problemów ze zrozumieniem reguł, proszę obejrzeć [[https://www.youtube.com/watch?v=iapcKVn7DdY|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, [[http://www.playmycode.com/play/game/cainy393/rock-paper-scissors-lizard-spock|online...]]. | |
| |
===== - Knowledge Interchange Format ===== | |
| |
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: | |
| |
<code prolog> | |
p(a,Y) | |
~p(a,Y) | |
p(a,Y) & p(Y,c) | |
q(Y) :- p(a,Y) & p(Y,c) | |
q(Y) :- p(a,Y) & p(Y,c) | |
</code> | |
| |
do formatu KIF: | |
| |
<code lisp> | |
(p a ?y) | |
(not (p a ?y)) | |
(and (p a ?y) (p ?y c)) | |
(<= (q ?y) (and (p a ?y) (p ?y c))) | |
(<= (q ?y) (p a ?y) (p ?y c)) | |
</code> | |
| |
=== - Zad 1 === | |
| |
Dla każdej z poniższych par określ, czy wersja prefixowa, jest wiernym tłumaczeniem wersji Prologowej. | |
| |
<code lisp> | |
r(a,b) :- p(a) & q(b) | |
(<= (r a b) (and (p a) (q b))) | |
</code> | |
<code lisp> | |
r(a,b) :- p(a) & q(b) | |
(<= (r a b) (p a) (q b)) | |
</code> | |
<code lisp> | |
r(x,y) :- p(x) & q(y) | |
(<= (r ?x ?y) (p ?x) (q ?y)) | |
</code> | |
<code lisp> | |
r(X,Y) :- p(X) & q(Y) | |
(<= (r ?x ?y) (p ?x) (q ?y)) | |
</code> | |
| |
=== - Zad 2 === | |
| |
Zapoznaj się z {{:pl:dydaktyka:ggp:tictactoe.kif.zip|wersją 'kółka i krzyżyk' zapisaną w KIF}}. | |
Jakie różnice widzisz między nią a naszym poprzednim modelem? | |
| |
=== - Zad 3 === | |
| |
Zapoznaj się z {{:pl:dydaktyka:ggp:blocks.kif.zip|modelem prostego świata klocków w GDL}}. | |
* jakie są kryteria zakończenia tej gry? | |
* w jaki sposób liczone są tury? | |
| |
=== - 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. | |
| |
===== - Walidacja modeli ===== | |
| |
<WRAP center round tip 60%> | |
Poniższe instrukcje przygotowane są z myślą o laboratorium C2 316, gdzie każdy komputer ma Eclipse. | |
</WRAP> | |
| |
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 FIXME | |
* Wybrać opcję klonowania z zewnętrznego URI | |
* Wpisać URI: ''https://github.com/ggp-org/ggp-base.git'' | |
* Wybrać gałąź ''master'' | |
* Wybrać jakiś //rozsądny// katalog dla projektu | |
* Wybrać projekt ''ggp-base'' do zaimportowania | |
| |
==== - 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: | |
* plik ''.kif'' z modelem gry | |
* plik ''METADATA'' z zawartością: | |
| |
<code javascript> | |
{ | |
"gameName": "<nazwa gry>", | |
"rulesheet": "<nazwa pliku kif>" | |
} | |
</code> | |
| |
==== - 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. | |
| |
| |
| |
===== - 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ć! | |
| |
{{ :pl:dydaktyka:ggp:have-fun.jpg?400 |}} | |
| |