1 Od struktur do gier. Dlaczego gry nas ciekawią. Jak grać optymalnieOd struktur do gier. Dlaczego gry nas ciekawią? Jak grać optymalnie? Związki z innymi problemami. Mateusz Lewandowski
2 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
3 Od struktur do gier - Mateusz LewandowskiMonety na stole Dwaj gracze na przemian kładą jednakowe monety na stole tak, aby na siebie nie nachodziły Przegrywa ten, kto nie może dołożyć monety Od struktur do gier - Mateusz Lewandowski
4 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
5 Od struktur do gier - Mateusz LewandowskiSkomplikowany świat Polityka Religia Nauka Emocje ... Od struktur do gier - Mateusz Lewandowski
6 Od struktur do gier - Mateusz LewandowskiOgraniczenia Jesteśmy w pewnym stopniu ograniczeni Dlatego wprowadzamy schematy mniej lub bardziej złożone I tak mamy sposoby zachowań, stereotypy, diagramy, modele matematyczne, itd... Od struktur do gier - Mateusz Lewandowski
7 Od struktur do gier - Mateusz LewandowskiCzy to dobrze? Świat wykazuje pewną stukturę My szczególnie to wiemy: Algebry, topologia, klasy abstrakcji, klasy złożoności algorytmów... Dzięki poznawianiu tych struktur wykształca się w nas intuicja Ale czasem jesteśmy zaskoczeni... Od struktur do gier - Mateusz Lewandowski
8 Lubimy szukać strukturOdkrycia dają pewną wiedzę o czymś, satysfakcję Od struktur do gier - Mateusz Lewandowski
9 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
10 Lubimy szukać struktur... w grachWłaściwie jest to istota gier Mamy zazwyczaj proste reguły, które prowadzą do bardzo różnych struktur kryjących się w logice gry Od struktur do gier - Mateusz Lewandowski
11 Od struktur do gier - Mateusz LewandowskiLubimy grać w gry Gramy by kogoś pokonać Dążymy do najlepszych rezulatów Lubimy myśleć, że mamy najlepszą strategię Od struktur do gier - Mateusz Lewandowski
12 Jakie gry nie są ciekawe?Te, o których wiemy „prawie wszystko” Monety na stole? Kółko i krzyżyk? Warcaby? Kostka rubika? 3 5 1 4 2 Od struktur do gier - Mateusz Lewandowski
13 Od struktur do gier - Mateusz LewandowskiWniosek? Gra pozostaje ciekawa, jeśli nie jest jasna strategia wygrywająca (trudna do zapamiętania) Ciekawe są rzeczy nieznane, ale w zasięgu. Od struktur do gier - Mateusz Lewandowski
14 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
15 Poziomy rozwiązania gry - bardzo-słabyDowód że pierwszy gracz przegra, wygra lub doprowadzi do remisu z pozycji początkowej zakładając optymalną grę obu stron Argument kradnięcia strategii zugzwang Najczęściej nie wpływa na grywalność Od struktur do gier - Mateusz Lewandowski
16 Poziomy rozwiązania grySłaby: algorytm postępowania dla jakiegoś gracza zabezpieczający wygraną lub remis od początku gry Warcaby, kończą się remisem przy optymalnej grze obu stron Maharajah and the Sepoys Gra może przestać być interesująca, jeśli strategia wygrywająca jest łatwa do zapamiętania Od struktur do gier - Mateusz Lewandowski
17 Poziomy rozwiązania grySilny: algorytm postępowania dla jakiegoś gracza z dowolnej pozycji startowej, dający wygraną lub remis Nim Kółko i krzyżyk Connect four Gra pozostaje interesująca, jeśli optymalna strategia jest trudna do zapamiętania Od struktur do gier - Mateusz Lewandowski
18 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
19 Od struktur do gier - Mateusz LewandowskiGry GGP W GGP ruchy są synchroniczne, przez co nie muszą istnieć strategie wygrywające Gracz L Gracz R
20 Od struktur do gier - Mateusz LewandowskiRóżności Zawody w papier-kamień-nożyce (http://webdocs.cs.ualberta.ca/~darse/rsbpc.html) RTS Game Engine https://skatgame.net/mburo/orts/orts.html The University of Alberta GAMES Group Od struktur do gier - Mateusz Lewandowski https://skatgame.net/mburo/orts/orts.html#Screenshots
21 Od struktur do gier - Mateusz LewandowskiDrzewo gry Od struktur do gier - Mateusz Lewandowski
22 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
23 Alternatywa dla α-β (Victor Allis)Conspiracy-number search proof-number search (pn-search) drzewa AND-OR awari, chess, connect-four, go-moku, othello, qubic dependency-based search (db-search) (1994) Od struktur do gier - Mateusz Lewandowski
24 Db-search - ilustracja Od struktur do gier - Mateusz Lewandowski
25 Czym zajmuje się teraz Victor Allis? Od struktur do gier - Mateusz Lewandowski
26 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
27 Od struktur do gier - Mateusz LewandowskiDrzewo gry Od struktur do gier - Mateusz Lewandowski
28 Od struktur do gier - Mateusz LewandowskiDrzewo gry – lepiej? Od struktur do gier - Mateusz Lewandowski
29 Znajdowanie symetrii w GGPStephan Schiffel (Fluxplayer, Dresden) Przekształcenie GDL do Rule Graph (Enhanced) Szukanie automorfizmu, tabele transpozycji Od struktur do gier - Mateusz Lewandowski Stephan Schiffel, Symmetry Detection in General Game Playing
30 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
31 Constraint Programming (CP)Constraints Satisfaction Problem (CSP) =
32 Constraint Programming (CP)Backtracking Constraint propagation Local search Decomposition methods Symmetry detection Od struktur do gier - Mateusz Lewandowski
33 Od struktur do gier - Mateusz LewandowskiPrzykłady CSP Przykład – SAT: X = {x1, x2, ..., xN} - zmienne Di = {0,1} Ci – podzbiór zmiennych, relacja OR Sudoku Conway's Game of Life Problemy optymalizacyjne: Szeregowanie zadań Znajdowanie tras Od struktur do gier - Mateusz Lewandowski
34 Quantified Constraint Satisfaction Problem (QCSP)Uogólnienie CSP, gdzie zmienne mogą być kwantyfikowane Rozwiązywanie kiedyś – redukcja do QBF Ulepszone rozwiązywanie: Preprocessing Look-ahead Symmetry breaking Solution-directed pruning Od struktur do gier - Mateusz Lewandowski
35 Od struktur do gier - Mateusz LewandowskiDeadline 24 Eliminacje – algorytmy Finał – 30 drużyn 3-osobowych, 24 godzin na 3 zadania-gry Od struktur do gier - Mateusz Lewandowski
36 Od struktur do gier - Mateusz LewandowskiPrzykład Budynek z piętrami – na każdym z nich co jakiś czas pojawiają się pasażerowie, którzy chcą dojechać na określone piętra Każda drużyna dostaje na początku jedną windę o ograniczonej pojemności, szybkości (piętra na turę) i zakresie pięter Co turę można kazać windzie jechać w górę lub w dół z jakąś prędkością, zatrzymać ją, załadować/wyładować pasażerów Za każdego pasażera dostaje się sumę pieniędzy (każdy pasażer określa ma swój przelicznik) Z nabyte pieniądze można kupować nowe windy Cel: zebrać jak najwięcej pieniędzy pod koniec gry Od struktur do gier - Mateusz Lewandowski
37 Od struktur do gier - Mateusz LewandowskiKrótka filozofia Ciekawość gier Poziomy rozwiązania gier Synchroniczne wykonywanie ruchów w GGP Podejścia do końcówek gier Wykrywanie symetrii Związki z innymi dziedzinami Konspekt Od struktur do gier - Mateusz Lewandowski
38 Od struktur do gier - Mateusz LewandowskiReferencje: Rozwiązane gry: Solving 8×8 Hex - Checkers, Solved! - Maharajah and the Sepoys - A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins (1988) - General games Symmetry Detection in General Game Playing - Searching for Solutions in Games and Articial Intelligence - (Q)CSP Sudoku as a Constraint Problem - A Game-Theoretic Approach to Constraint Satisfaction A CSP-Based Approach for Solving Parity Game - QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems - Consistency for Quantified Constraint Satisfaction Problems - Od struktur do gier - Mateusz Lewandowski
39 Dziękuję za uwagę!