Next revision
|
Previous revision
Next revision
Both sides next revision
|
en:dydaktyka:ggp:gdl [2018/01/16 00:27] msl created |
en:dydaktyka:ggp:gdl [2019/01/03 22:51] msl |
Let's start with players "nought" and "cross". There is a special fact ''role'' just to do that: | Let's start with players "nought" and "cross". There is a special fact ''role'' just to do that: |
| |
<code prolog> | <code> |
role(nought) | role(nought) |
role(cross) | role(cross) |
</code> | </code> |
| |
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. | 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 sentence. All constants start with a lower-cased letter and variables are upper-cased. |
| |
==== Fluents ==== | ==== Fluents ==== |
To define the fluents one uses the ''base'' facts: | To define the fluents one uses the ''base'' facts: |
| |
<code prolog> | <code> |
base(cell(M,N,x)) :- index(M) & index(N) | base(cell(M,N,x)) :- index(M) & index(N) |
base(cell(M,N,o)) :- index(M) & index(N) | base(cell(M,N,o)) :- index(M) & index(N) |
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: | 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: |
| |
<code prolog> | <code> |
base(cell(1,1,x)) base(cell(1,1,o)) base(cell(1,1,b)) | 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,2,x)) base(cell(1,2,o)) base(cell(1,2,b)) |
In order to define an action we use the ''input'' predicate: | In order to define an action we use the ''input'' predicate: |
| |
<code prolog> | <code> |
input(R, mark(M,N)) :- role(R) & index(M) & index(N) | input(R, mark(M,N)) :- role(R) & index(M) & index(N) |
input(R, noop) :- role(R) | input(R, noop) :- role(R) |
| |
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. | 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. |
<code prolog> | |
| <code> |
init(cell(M,N,b)) :- index(M) & index(N) | init(cell(M,N,b)) :- index(M) & index(N) |
init(control(nought)) | init(control(nought)) |
| |
==== State Changes ==== | ==== State Changes ==== |
| Now the most difficult part --- how does the state evolve in the game. We assume that the new state is created after the very move and depends only on the previous state and actions made by the players. On could notice the [[https://en.wikipedia.org/wiki/Frame_problem#Fluent_calculus_solution|frame problem occurring here]]. The etymology of the ''frame'' is the movie tape, where every frame differs in details from the previous one. Similarly here, we would like the next state to be exactly like the previous one except some changes made //explicitly// by the players. The problem is that in our case we have also to model lack of 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 [[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 :-( | To define the state evolution we use the ''next'' predicate, defining the fluent state in the next turn. The 'does' predicate check what actions were made by the players during the current turn. |
| |
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> |
| |
<code prolog> | |
next(cell(M,N,x)) :- | next(cell(M,N,x)) :- |
does(cross,mark(M,N)) & | does(cross,mark(M,N)) & |
</code> | </code> |
| |
Akcje te kolejno oznaczają: | The defined actions mean that: |
- jeżeli komórka jest pusta, a gracz krzyżyk ją zaznaczył, to w kolejnej turze w tej komórce będzie krzyżyk | - if the cell is empty and the 'cross' player marked it then there will be a 'x' in this cell next turn |
- jeżeli komórka jest pusta, a gracz kółko ją zaznaczył, to w kolejnej turze w tej komórce będzie kółko | - if the cell is empty and the 'nought' player marked it then there will be an 'o' in this cell next turn |
- 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ść | - if the cell wasn't empty (''distinct'' checks equality of the arguments), then it will stay the same next turn |
- 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!) | - if the cell was empty and wasn't mark this turn, it will be still empty next turn (two rules!) |
- jeżeli dana tura należała do kółka, to kolejna będzie należała do krzyżyka | - if the current turn belongs to the the 'nought' player, next will belong to the 'cross' player |
- jeżeli dana tura należała do krzyżyka, to kolejna będzie należała do kółka | - if the current turn belongs to the the 'cross' player, next will belong to the 'nought' player |
| |
Warto zauważyć, że akcje 3 i 4 służą właśnie walce z problemem ramki. | It's worth to note, that actions 3 and 4 are designed only to cope with the frame problem. |
| ==== Game Ending Conditions ==== |
| |
==== Warunki końca gry ==== | Every player knows that there are two ways to finish the game: make a line or fill all the available cells. Now we will check if there was a line made by the player. |
| |
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> |
| |
<code prolog> | |
line(Z) :- row(M,Z) | line(Z) :- row(M,Z) |
line(Z) :- column(M,Z) | line(Z) :- column(M,Z) |
</code> | </code> |
| |
Zapytanie ''true(line(kolko))'' powie nam teraz, czy na planszy jest linia kółek. | The ''true(line(naught))'' query will tell if there is a line made of the 'o's on the board. |
| |
Teraz należy zdefiniować kryteria zakończenia gry, używając predykatu ''terminal'': | Now we can define the ending conditions with the ''terminal'' predicate: |
| |
<code prolog> | <code> |
terminal :- line(x) | terminal :- line(x) |
terminal :- line(o) | terminal :- line(o) |
</code> | </code> |
| |
Gra się kończy, gdy: | Game ends when: |
* istnieje linia krzyżyków | * there is a line of crosses |
* istnieje linia kółek | * there is a line of naughts |
* wszystkie pola są zajęte | * there is no empty cell |
| |
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]]). | The '~' operator means negation. Similarly to the Prolog it follows [[https://en.wikipedia.org/wiki/Closed-world_assumption|the closed world assumption]], ie. sentence is false if can't prove otherwise. In GDL ther are additional restrictions we want worry about for now (more info [[http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/winter09/ggp/kapitel2.pdf|here]]). |
| |
==== Kryterium zwycięstwa ==== | ==== Winning Conditions ==== |
| |
{{ :pl:dydaktyka:ggp:tyle_wygrac.jpg?200|}} | {{ :en:dydaktyka:ggp:somuchwin.jpg?direct&400|}} |
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'': | Bots don't have feelings but we still should give them prize for the good game. And we do this with the ''goal'' predicate: |
| |
<code prolog> | <code> |
goal(krzyzyk,100) :- line(x) & ~line(o) | goal(cross,100) :- line(x) & ~line(o) |
goal(krzyzyk,50) :- ~line(x) & ~line(o) | goal(cross,50) :- ~line(x) & ~line(o) |
goal(krzyzyk,0) :- ~line(x) & line(o) | goal(cross,0) :- ~line(x) & line(o) |
| |
goal(kolko,100) :- ~line(x) & line(o) | goal(nought,100) :- ~line(x) & line(o) |
goal(kolko,50) :- ~line(x) & ~line(o) | goal(nought,50) :- ~line(x) & ~line(o) |
goal(kolko,0) :- line(x) & ~line(o) | goal(nought,0) :- line(x) & ~line(o) |
</code> | </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. | According to the rules above winner gets 100 (so much win!), in case of tie only 50, and loser gets 0. We don't what this number represent but it has to be something good like cookies. |
| |
<WRAP center round tip 60%> | <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. | There is no arithmetics in GLD --- numbers are only used to define indexes, prizes, time, etc. |
</WRAP> | </WRAP> |
| |
| ==== End ==== |
| |
==== Koniec ==== | That's all folks, you've just modeled a simple tic-tac-toe game. |
| |
To by było na tyle, właśnie udało się zamodelować prostą grę w kółko i krzyżyk. | === - Assignment 1 === |
| |
=== - Zad 1 === | Let's take an even simpler game: |
| |
Weźmy przykładowy model jeszcze prostszej gry. | <code> |
| |
<code prolog> | |
role(white) | role(white) |
role(black) | role(black) |
| |
terminal :- true(p) & true(q) & true(r) | terminal :- true(p) & true(q) & true(r) |
| |
</code> | </code> |
| |
Odpowiedz na poniższe pytania: | Answer the following questions: |
- jak wielu graczy występuje w grze? | - how many players are there? <fs xx-small> (correct answer: 2, why?)</fs> |
- jak wiele fluentów opisuje stan gry? | - how many fluents are defined? <fs xx-small>(correct answer: 4, why?)</fs> |
- jak wiele jest dostępnych akcji? | - how many actions are there? <fs xx-small>(correct answer: 8, why?)</fs> |
- ile akcji może wykonać gracz 'white' w początkowym stanie gry? | - how many legal moves does the 'white' player have in the initial state of the game? <fs xx-small>(correct answer: 3, why?)</fs> |
- jak wiele fluentów jest prawdziwych w początkowym stanie gry? | - how many fluents are true in the initial state of the game? <fs xx-small>(correct answer: 1, why?)</fs> |
- załóżmy, że pierwszej turze gracz 'white' wykonał akcję 'a', a gracz 'black' akcję 'd'. Ile fluentów jest prawdziwych w drugiej turze? | - assume in the first turn, the white player performed the 'a' action and the 'black' player action 'd'. How many fluents are true in the second turn? <fs xx-small>(correct answer: 1, why?)</fs> |
- jaka jest najmniejsza liczba kroków potrzebna do zakończenia gry? | - what is the smallest number of turns required to end the game? <fs xx-small>(correct answer: 4, why?)</fs> |
- czy gra zawsze się kończy? (czy mogłaby się zapętlić?) | - does the game always end? (is it possible to loop the game indefinitely?) |
| |
=== - Zad 2 === | === - Assignment 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. | Please model the 'crosses and crosses' game. The rules are similar to the tic-tac-toe, again we have nine cells, but both players use the crosses. Player loses when he first creates the line. |
| |
=== - Zad 3 === | === - Assignment 3 === |
| |
{{ :pl:dydaktyka:ggp:rock-paper-spock.jpg?300|}} | {{ :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...]]. | Please model the "Rock Paper Scissors Lizard Spock" game. You can learn the rules from this [[https://www.youtube.com/watch?v=iapcKVn7DdY|video]]. The image on the right is also a good reference. You can practice it with a colleague or like a modern man: [[http://www.playmycode.com/play/game/cainy393/rock-paper-scissors-lizard-spock|online...]]. |
| |
===== - Knowledge Interchange Format ===== | ===== - 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: | Everything we learned so far is true, but the GDL has an alternative syntax used to store and transfer the games: the Knowledge Interchange Format. It's based on a lisp and uses a prefix notation. Moreover '':-'' operator is replaced with ''<='', ''&'' with ''and'', negation ''~'' with ''not''. The variables start with the ''?''. Below you can see an example of translation between Prolog: |
| |
<code prolog> | <code> |
p(a,Y) | p(a,Y) |
~p(a,Y) | ~p(a,Y) |
</code> | </code> |
| |
do formatu KIF: | and KIF: |
| |
<code lisp> | <code scheme> |
(p a ?y) | (p a ?y) |
(not (p a ?y)) | (not (p a ?y)) |
</code> | </code> |
| |
=== - Zad 1 === | === - Assignemnt 1 === |
| |
Dla każdej z poniższych par określ, czy wersja prefixowa, jest wiernym tłumaczeniem wersji Prologowej. | For every example below, tell if the KIF version is a faithful translation of the Prolog one. |
| |
<code lisp> | <code scheme> |
r(a,b) :- p(a) & q(b) | r(a,b) :- p(a) & q(b) |
(<= (r a b) (and (p a) (q b))) | (<= (r a b) (and (p a) (q b))) |
</code> | </code> |
<code lisp> | <code scheme> |
r(a,b) :- p(a) & q(b) | r(a,b) :- p(a) & q(b) |
(<= (r a b) (p a) (q b)) | (<= (r a b) (p a) (q b)) |
</code> | </code> |
<code lisp> | <code scheme> |
r(x,y) :- p(x) & q(y) | r(x,y) :- p(x) & q(y) |
(<= (r ?x ?y) (p ?x) (q ?y)) | (<= (r ?x ?y) (p ?x) (q ?y)) |
</code> | </code> |
<code lisp> | <code scheme> |
r(X,Y) :- p(X) & q(Y) | r(X,Y) :- p(X) & q(Y) |
(<= (r ?x ?y) (p ?x) (q ?y)) | (<= (r ?x ?y) (p ?x) (q ?y)) |
</code> | </code> |
| |
=== - Zad 2 === | === - Assignment 2 === |
| |
Zapoznaj się z {{:pl:dydaktyka:ggp:tictactoe.kif.zip|wersją 'kółka i krzyżyk' zapisaną w KIF}}. | Download {{:pl:dydaktyka:ggp:tictactoe.kif.zip|the KIF version of the tic-tac-toe game}}. |
Jakie różnice widzisz między nią a naszym poprzednim modelem? | What are the differences between it and our model? |
| |
=== - Zad 3 === | === - Assignment 3 === |
| Read the {{:pl:dydaktyka:ggp:blocks.kif.zip|simple blocks' world model}}. |
| * what are the ending contitions? |
| * how do we count the turns? |
| |
Zapoznaj się z {{:pl:dydaktyka:ggp:blocks.kif.zip|modelem prostego świata klocków w GDL}}. | === - Assignment 4 === |
* jakie są kryteria zakończenia tej gry? | |
* w jaki sposób liczone są tury? | |
| |
=== - Zad 4 === | Translate all the models you've created today to the KIF format. |
| |
Przepisz modele 'kólka i krzyżyka', 'krzyżyka i krzyżyka' oraz 'papier, kamień, nożyce, spocka i jaszczurki' do postaci KIF. | ===== - Validation ===== |
| |
===== - Walidacja modeli ===== | |
| |
<WRAP center round tip 60%> | <WRAP center round tip 60%> |
Poniższe instrukcje przygotowane są z myślą o laboratorium C2 316, gdzie każdy komputer ma Eclipse. | The instructions below require an Eclipse IDE. |
</WRAP> | </WRAP> |
| |
Proszę uruchomić Eclipse i następnie: | Please run the Eclipse IDE and: |
* ''File -> Import Project'' | * ''File -> Import Project'' |
* Wybrać opcję importowania z repozytorium git | * Import the git repository |
* 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 | * If there is no such option (Eclipse is too old), one has to download the repository by hand and ignore the further instructions. |
* Wybrać opcję klonowania z zewnętrznego URI | * Clone from the remote URI |
* Wpisać URI: ''https://github.com/ggp-org/ggp-base.git'' | * Fill URI: ''https://github.com/ggp-org/ggp-base.git'' |
* Wybrać gałąź ''master'' | * Select the ''master'' branch |
* Wybrać jakiś //rozsądny// katalog dla projektu | * Select a //reasonable// catalogue for the project |
* Wybrać projekt ''ggp-base'' do zaimportowania | * Select a ''ggp-base'' project to be imported |
| |
==== - Dodanie gier do środowiska ==== | ==== - Adding Custom Games ==== |
| |
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: | In the project directory go to the ''games/games'' catalogue and create there three directories ''tic-tac-toe'', ''cross-cross'' and ''spock''. Every directory should contain two files: |
* plik ''.kif'' z modelem gry | * ''<name>.kif'' file with the model |
* plik ''METADATA'' z zawartością: | * ''METADATA'' file containing: |
| |
<code javascript> | <code javascript> |
{ | { |
"gameName": "<nazwa gry>", | "gameName": "<game name>", |
"rulesheet": "<nazwa pliku kif>" | "rulesheet": "<kif file name>" |
} | } |
</code> | </code> |
| |
==== - Walidacja gier ==== | ==== - Games' Validation ==== |
| |
| From the Eclipse run the ''Validator'' app (one of the targets next to the ''play'' button). |
| |
Z poziomu Eclipse proszę uruchomić aplikację ''Validator'' (rozwijana lista przy guziki ''play''). | ''Validator'' will check if the model is a valid GDL model. |
| |
''Validator'', jak sama nazwa wskazuje, ma na celu sprawdzenie, czy dany model jest prawidłowym modelem GDL. | === Assignment === |
| |
=== Ćwiczenia === | - In the ''Repository'' field choose ''Local Game Repository'' |
| - In the ''Game'' field select ''Tic-Tac-Toe'' |
| - Press ''Validate'' --- There should be no failure |
| - Repeat the same for your custom models |
| - Fix your models to be playable |
| |
- 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 ===== | ===== - Fun ===== |
| |
Z poziomu Eclipse proszę uruchomić aplikację ''Kiosk'' (rozwijana lista przy guziki ''play''). | Run the ''Kiosk'' app in the Eclipse (select from the list next to the ''play'' button). |
| |
=== Ćwiczenia === | === Assignment === |
| |
- W polu ''Opponent'' proszę wybrać ''SimpleMonteCarloPlayer'' | - As an ''Opponent'' select ''SimpleMonteCarloPlayer'' |
- Wybrać jakąś znajomą grę | - Choose a game you are familiar with |
- Wygrać! | - Win! |
| |
{{ :pl:dydaktyka:ggp:have-fun.jpg?400 |}} | {{ :pl:dydaktyka:ggp:have-fun.jpg?400 |}} |
| |