Gra parzystości
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: Styl, poza tym nie ma podane, jakie ruchy wolno a jakich nie wolno wykonywać. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Gry parzystości są grami pomiędzy dwoma graczami, toczonymi na skierowanym grafie etykietowanym (V,E), gdzie V to zbiór wierzchołków grafu, a E to zbiór jego krawędzi. Potencjalnie zbiór V może być nieskończony. Gracze są z angielskiego nazywani Odd i Even. Każdy wierzchołek 
jest wierzchołkiem jednego z graczy, to znaczy to ten gracz wykonuje z niego ruch. Dana jest funkcja 
, która każdemu wierzchołkowi przypisuje nieujemną liczbę całkowitą zwaną rankiem. Zakłada się, że obraz funkcji rank jest skończony. Gra polega na tym, że gracze wykonują ruchy (zgodne z krawędziami ze zbioru E) na grafie gry, w danym momencie rusza się ten, który jest właścicielem danego wierzchołka. Jeśli w pewnym momencie któryś z graczy nie może wykonać ruchu, to przegrywa, natomiast jeśli gra toczy się w nieskończoność, to przyglądamy się liczbie 
, czyli największemu rankowi, który pojawia się na wybranej ścieżce nieskończenie wiele razy. Jeśli liczba ta jest parzysta, to wygrywa gracz Even, a jeśli nieparzysta, to gracz Odd.
Spis treści |
[edytuj] Własności
- Gry parzystości są grami zdeterminowanymi[1], to znaczy dla każdej pozycji w grze istnieje gracz, który z tej pozycji ma strategię wygrywającą.
[edytuj] Rozwiązywanie gier
Poprzez rozwiązanie gry parzystości rozumiemy odpowiedzenie dla każdej pozycji który gracz posiada z tej pozycji strategię wygrywającą (wiemy, że taki istnieje dzięki determinacji gier parzystości) oraz wskazanie tej strategii. Dla gier parzystości wystarczy umieć wskazywać który gracz posiada strategię wygrywającą, a już umiemy wskazywać tę strategię.
Dotychczas nie jest znany wielomianowy algorytm rozwiązywania gier parzystości, najlepsze znane dziś algorytmy są podwykładnicze, jak na przykład [2].
Wiadomo natomiast, że dla gier parzystości z ograniczoną z góry liczbą ranków istnieją algorytmy wielomianowe rozwiązujące te gry, najlepsze osiągają złożoność czasową rzędu 
, gdzie d to ograniczenie na ilość różnych ranków [3].
[edytuj] Zastosowania
Najpoważniejszym powodem, dla którego interesujemy się grami parzystości, jest ich bliskie powiązanie z rachunkiem Mi. Rachunek Mi jest obecnie jednym z najlepszych formalizmów do automatycznej weryfikacji systemów za pomocą metody model checking [4]. Potocznie mówiąc, gry parzystości są przydatne do automatycznego weryfikowania poprawności programów. Automatyczne weryfikowanie programów jest bardzo istotne, gdyż programista nie jest nigdy w stanie w stu procentach zapewnić poprawności napisanego kodu. Dlatego informatyka intensywnie pracuje nad tym problemem .
[edytuj] Literatura
- ↑ D. A. Martin: Borel determinacy, The Annals of Mathematics, Vol 102 No. 2 pp. 363-371 (1975)
- ↑ Marcin Jurdziński, Mike Peterson, Uri Zwick: A deterministic subexpotensional algorithm for solving parity games, ACM-SIAM Symposium on Discrete Algorithms (2006)
- ↑ H. Seidl. Fast and simple nested fixpoin Information Processing Letter, 59:303-308, 1997
- ↑ Michał Sokołowski: Porównanie implementacyjne algorytmów rozwiązywania gier, Praca magisterska na kierunku Informatyka, Październik 2005
