[[
✎ pl:dydaktyka:ggp:gdl
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== - 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. == 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. == 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 === Proszę zamodelować grę "kamień, papier, nożyce, spocka i jaszczurkę". Poniższe obrazki powinny jednoznacznie przedstawić zasady: {{:pl:dydaktyka:ggp:rock-paper-spock.jpg?400|}} {{ :pl:dydaktyka:ggp:rock-paper-spock-hand.jpg?400|}}
pl/dydaktyka/ggp/gdl.1461713327.txt.gz
· ostatnio zmienione: 2019/06/27 15:52 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry