Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:dydaktyka:ggp:gdl [2016/04/27 08:31]
msl [4 Knowledge Interchange Format]
pl:dydaktyka:ggp:gdl [2019/06/27 15:50]
Linia 1: Linia 1:
-====== - 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(kolko,​mark(M,​N)) & 
-  true(cell(M,​N,​b)) 
- 
-next(cell(M,​N,​o)) :- 
-  does(krzyzyk,​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 kółko ją zaznaczył, to w kolejnej turze w tej komórce będzie kółko 
-  - 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 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 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(M,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. ​ 
- 
-W GDL nie ma arytmetyki --- liczby nie różnią się niczym od innych stałych. Co gorsza, jest ich tyle, co kot napłakał ​ 
- 
- 
-==== 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 '​krzyżyka i krzyżyka'​ oraz '​papier,​ kamień, nożyce, spocka i jaszczurki'​ do postaci KIF. 
pl/dydaktyka/ggp/gdl.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0