Co bylo na wykladzie ?
4.10.2005
- Roznorodnosc zjawisk okreslonych jako "gra" - proba ogolnej
definicji:
proces ksztaltowany przez kilka podmiotow, z ktorych zaden nie ma
pelnej kontroli, a kazdy dazy do swoich celow.
Parametry gry: losowosc, (nie)pelna informacja, jednoczesne ruchy.
- Przyklady gier z pelna informacja: szachy, Nim,
"gra w prawde".
Gra Choqueta (nieskonczona, gracze wybieraja zstepujacy ciag
przedzialow otwartych, jeden z nich dazy do niepustego przeciecia).
- Arena gry dwoch graczy, z pelna informacja to
graf skierowany, gdzie wierzcholki, to pozycje (Adama lub Ewy),
a krawedzie wskazuja mozliwe ruchy.
Strategia dla Ewy, to dowolne drzewo sciezek w
arenie, gdzie kazda sciezka zakonczona w nie-terminalnej
pozycji Ewy ma przedluzenie o jeden ruch, a sciezka zakonczona w
pozycji Adama ma przedluzenia o wszystkie mozliwe ruchy.
Uwaga: pierwszy poziom (sciezki jednoelementowe) moze byc dowolny i
wyznacza pozycje poczatkowe dopuszczalne przez
strategie.
Strategia jest bezpieczna (dla Ewy) jesli nigdy nie
dojdzie do terminalnej pozycji Ewy.
Jest skonczenie wygrywajaca, jesli ponadto nie ma
sciezek nieskonczonych, a zatem kazda rozgrywka w koncu "matuje" Adama.
Pozycja p jest bezpieczna
(skonczenie wygrywajaca) jesli istnieje odpowiednia strategia
zawierajaca p (jako pozycje poczatkowa).
Strategia jest pozycyjna , jesli zalezy tylko od
aktualnej pozycji.
Dokladniej, jesli v,w nalezy do S i last(v) = last(w), to dla kazdej
pozycji p, vp nalezy do S <==> wp nalezy do S.
- Rownanie gry:
X = (E /\ <> X) \/ (A /\ [] X),
gdzie X przebiega zbiory pozycji, E - pozycje Ewy, A -pozycje Adama,
<> Y = {p : istnieje ruch p--> q, gdzie q nalezy do Y},
[] Y = {p : dla kazdego ruchu p--> q, q nalezy do Y}.
11.10.2005
- Okreslamy dwa operatory dzialajace na zbiorach pozycji:
Ewa (X) = (E /\ <> X) \/ (A /\ [] X),
Adam (X) = (A /\ <> X) \/ (E /\ [] X).
- Przypomnienie: Twierdzenie Knastera-Tarskiego o
punktach stalych.
Funkcja monotoniczna na kracie zupelnej, f: L ---> L, ma najmniejszy
punkt staly
Mu x. f(x) = /\ { d: f(d) =< d }
i najwiekszy punkt staly
Nu x. f(x) = \/ { d: d =< f(d) }.
- Lemat. Jesli zbior pozycji L jest zawarty w
Ewa (L), to wszystkie pozycje w L sa bezpieczne dla Ewy.
Co wiecej, Ewa ma bezpieczna strategie pozycyjna zawierajaca wszystkie
pozycje z L.
- Fakt. Kazda pozycja jest bezpieczna
przynajmniej dla jednego z graczy.
Co wiecej, istnieja pozycyjne bezpieczne strategie S_E i S_A dla Ewy i
Adama, odpowiednio, takie
ze zbior wszystkich pozycji jest zawarty w sumie S_E i S_A.
Dla dowodu wystarczy zauwazyc, ze jesli L jest
punktem stalym operatora Ewa (X),
to dopelnienie L jest punktem stalym operatora Adam (X).
Z Tw. Knastera-Tarskiego wiemy, ze jakis punkt staly operatora Ewa (X)
na pewno istnieje.
Dalej teza wynika z Lematu.
- Jesli w arenie nie ma nieskonczonych sciezek, to pozycja
bezpieczna jest zarazem
skonczenie wygrywajaca. Jako wniosek otrzymujemy wiec
Twierdzenie Zermelo. Jesli w arenie nie ma
nieskonczonych sciezek, to kazda pozycja jest
skonczenie wygrywajaca dla dokladnie jednego z graczy.
Co wiecej, istnieja pozycyjne strategie S_E i S_A, skonczenie
wygrywajace dla Ewy i Adama, odpowiednio,
takie ze zbior wszystkich pozycji jest zawarty w sumie S_E i S_A.
Uwaga. Pozycja moze byc bezpieczna dla obu graczy,
ale skonczenie wygrywajaca tylko dla jednego.
Zatem dla aren bez nieskonczonych sciezek punkty stale operatorow Ewa
(X) i Adam (X) sa jedyne.
- Jesli arena dopuszcza nieskonczone sciezki (np. petle), to
najmniejsze i najwieksze punkty stale moga byc rozne.
Fakt. Najwiekszy punkt staly operatora Ewa (X)
jest zarazem zbiorem wszystkich pozycji bezpiecznych dla Ewy.
Dowod. Na podstawie powyzszego Lematu, wszystkie
pozycje w najwiekszym punkcie stalym sa bezpieczne.
Dla inkluzji przeciwnej, z Tw. Knastera-Tarskiego wystarczy pokazac,
ze zbior B_E pozycji bezpiecznych dla Ewy
jest zawarty w Ewa (B_E). Wynika to latwo z definicji operatora Ewa (X)
i faktu, ze po odcieciu pozycji p ze strategii
bezpiecznej S, strategia p^{-1} S jest nadal bezpieczna.
18.10.2005
- Typowe operacje na strategiach:
zawezenie do jednej pozycji: q {q}-1 S ;
suma rozlaczna ;
wydluzenie z pozycji Ewy, p: jesli (p,q) in Mov i S_q jest strategia z
q, to p q {q}-1 S_q jest strategia z p;
wydluzenie z pozycji Adama, p: jesli dla kazdego q, takiego ze (p,q) in
Mov, S_q jest strategia z q,
to suma (po q) strategii p q {q}-1 S_q jest strategia z p.
Wszystkie te operacje zachowuja bezpieczenstwo i skonczona
wygrywalnosc, ale
suma i przedluzenia moga nie zachowac pozycyjnosci.
- Fakt. Najmniejszy punkt staly operatora Ewa (X)
jest zarazem zbiorem wszystkich pozycji skonczenie wygrywajacych
dla Ewy. Co wiecej, Ewa ma pozycyjna skonczenie wygrywajaca strategie
na tym zbiorze.
Dowod. Niech L bedzie tym najmniejszym punktem
stalym. Dopelnienie L jest punktem stalym operatora Adam (X),
a zatem Ewa nie ma tam strategii skonczenie wygrywajacej (Lemat z
11.10).
Pozostaje wskazac pozycyjna strategie Ewy na L. W tym celu
przedstawiamy L jako sume iteracji
operatora Ewa (X) na zbiorze pustym (Ewa (0), Ewa (Ewa (0)),....). Dla
kazdej pozycji p w L istnieje najmniejsza
liczba porzadkowa min(p), ze p nalezy do iteracji o numerze min(p).
Jesli p jest pozycja Ewy, to istnieje nastepnik q, ze min(q) <
min(p), nalezy go wiec wybrac.
Dla dowolnej rozgrywki p_0, p_1, ... zgodnej z ta strategia, ciag liczb
porzadkowych min(p_0),min(p_1),...
jest malejacy, a zatem rozgrywka musi byc skonczona.
- Algorytm. Powyzszy Fakt daje prosty algorytm
dla obliczenia zbioru pozycji skonczenie wygrywajacych
dla Ewy, w przypadku gdy arena jest skonczona: wystarczy obliczac
kolejne iteracje Ewa (0).
Nie moze ich byc wiecej niz ilosc pozycji, a koszt obliczenia Ewa (X)
jest proporcjonalny do liczby ruchow,
co daje zlozonosc |Pos| |Mov|. Nie jest to jednak algorytm optymalny,
propagujac rekurencyjnie informacje o wygranej,
mozna znalezc obszar wygrywajacy Ewy w czasie |Pos| + |Mov| (zob. notatki z 2003, nalezy
jednak poprawic drobny blad: koniecznosc sprawdzenia czy wartosc win[v]
nie zostala juz nadana).
25.10.2005
- Gra nazwiemy uklad (Pos_E, Pos_A, Mov, C), gdzie
(Pos_E, Pos_A, Mov) tworza arene, a C jest
zbiorem nieskonczonych ciagow pozycji, ktory nazywamy warunkiem
wygrywajacym dla Ewy.
Zakladamy, ze
- skonczona rozgrywka zakonczona w pozycji terminalnej jest
wygrana przez gracza, do ktorego ta pozycja nie nalezy,
- nieskonczona rozgrywka nalezaca do C jest wygrana przez Ewe,
nienalezaca do C przez Adama.
Strategia (Ewy) jest wygrywajaca
jesli kazda rozgrywka zgodna z ta strategia jest wygrana przez Ewe.
Pozycja jest wygrywajaca (dla
Ewy) jesli nalezy do pewnej strategii wygrywajacej.
- Warunek wygrywajacy C jest niezalezny od prefiksu
jesli wydluzenie
lub skrocenie rozgrywki o skonczony prefiks nie zmienia zwyciezcy.
Fakt. Jesli C jest niezalezny od prefiksu, to
zbior W_E pozycji wygrywajacych dla Ewy
jest punktem stalym rownania gry:
W_E = (E /\ <> W_E) \/ (A /\ [] W_E),
symetryczny fakt zachodzi dla Adama.
- Nie zachodzi jednak prosty analogon Twierdzenia Zermelo.
Twierdzenie. Istnieje gra, w ktorej pewna pozycja
nie jest wygrywajaca dla zadnego z graczy.
Dowod patrz notatki z 2003.
8.11.2005
Gra na nieskończonej arenie.
Na wykładzie 18.10 poznaliśmy algorytm rozstrzygający, czy dana
pozycja jest skończenie wygrywająca dla Ewy, w czasie liniowym względem
rozmiaru areny.
A co jeśli arena jest nieskończona?
Okazuje się, że czasem potrafimy zredukować taka grę do przypadku
skończonego.
Automatem ze stosem nazwiemy
układ Q - zbiór stanów, Gamma - alfabet i delta -zbiór reguł (przejść)
postaci q z ---> q' z' z (push z') lub q z ---> q' (pop). Ponadto zakładamy, że Q
dzieli sie na stany Ewy Q_E
i stany Adama Q_A. Automat wyznacza grę, w ktorej pozycjami są
konfiguracje automatu, dokładniej
Pos_E = Q_E Gamma*,
Pos_A = Q_A Gamma* , a
ruchy polegają na wykonaniu jednego przejścia,
tzn. q z w ---> q' z' z w, o ile jest reguła q z ---> q'
z' z, oraz q z w ---> q' w, o ile jest reguła q z
---> q'.
Przykład. Q = {p,q}, Gamma = {a}, delta = { q a ---> q a a, q
a ---> p, p a ---> p }, generuje graf:
qa ---> qaa ---> qaaa --->
...
|
| |
v
v v
p <--- pa <---
paa <--- ...
Twierdzenie (I.Walukiewicz,
1996). Istnieje algorytm, który dla danego automatu ze stosem A
rozstrzyga,
czy pozycja "q z" w wyżej opisanej grze jest skończenie
wygrywająca dla Ewy, w czasie wykładniczym ze względu na |A|.
Uwaga.
Twierdzenie jest w istocie mocniejsze i dotyczy tzw. gier
parzystosci, o których będziemy jeszcze mówic.
Dla dowodu okreslmy najpierw
wariant powyższej gry: G(q,z,S), gdzie S jest podzbiorem Q; w tej
grze pozycją
poczatkową jest "qz", natomiast wszystkie pozycje "p" (tzn. stos pusty,
stan p), gdzie p jest w S, są pozycjami Adama
(oczywiscie
terminalnymi, a więc wygrywa w nich Ewa).
Z kolei określamy grę skończoną G*.
Ma ona nastepujace pozycje:
Good
(q,z,S) pozycja Ewy lub Adama, zależnie czyje jest q,
intuicja: Ewa potrafi wygrać grę
G(q,z,S),
T (terminalna Adama),
F (terminalna Ewy),
Push (q,z,S,q',z') pozycja Ewy,
Choose (q,z,S,q',z',S')
pozycja Adama.
Ruchy:
Good
(q,z,S) ---> T, gdy q z ---> q' , gdzie q' jest w
S,
Good
(q,z,S) ---> F, gdy q z ---> q' , gdzie q' nie jest w
S,
Good (q,z,S) ---> Push(q,z,S,q',z')
, gdy q z ---> q' z' z,
Push (q,z,S,q',z')
---> Choose (q,z,S,q',z',S')
(S' dowolny)
Choose (q,z,S,q',z',S')
---> Good (q',z',S')
Choose (q,z,S,q',z',S')
---> Good (q'',z,S), dla każdego
q'' w S'.
Intuicja: Przypomnijmy, że w pozycji Good
(q,z,S) Ewa twierdzi, że potrafi wygrać grę
G(q,z,S). Jesli wykonane jest przejście q z ---> q' z' z
(ruch do pozycji Push),
Ewa pokazuje nowy zbior
S' (ruch do pozycji Choose),
o którym twierdzi dwie rzeczy:
(1) potrafię wygrac grę G(q',z',S'), a zatem jeśli z' zostanie po raz
pierwszy zdjęte ze stosu, to
stan będzie w S' (pozycja Good (q',z',S')),
(2) z każdego stanu q'' w S' potrafię wygrać grę G(q'',z,S)
(pozycja Good (q'',z,S)).
Zauwazmy, że koniunkcja (1) i (2) oznacza, że Ewa rzeczywiście potrafi
wygrać grę
G(q,z,S) z pozycji q'z'z.
W dwóch ruchach z pozycji Choose,
Adam może "sprawdzić", czy Ewa mówila prawdę.
Lemat. Pozycja Good
(q,z,S) jest skończenie wygrywająca dla Ewy w G* <===> pozycja
startowa
qz jest skończenie wygrywająca dla Ewy w G(q,z,S).
Dowód lematu:
"==> " Przez indukcję na min (Good
(q,z,S) ), patrz wykład z 18.10.
"<==" Przez indukcje na dlugość strategii w grze G(q,z,S)
(patrz zadanie 1 ).
Ciag dalszy nastapi.