May 2016
Abstrakt
Na ogół brak doskonałej informacji wyraźnie utrudnia wybór dobrego zagrania, zarówno człowiekowi, jak i w sytuacji gdy dokonuje go komputer. Dopiero na przestrzeni kilku ostatnich lat udało się napisać silne programy grające w niektóre z gier bez doskonałej informacji. W dużej mierze sukces osiągnięto dzięki zastosowaniu algorytmów, które rozwiązują szereg pomocniczych problemów z doskonałą informacją, otrzymanych poprzez, zazwyczaj losowe, ustalenie pełnego obrazu aktualnego stanu rozpatrywanej gry, tj. np. założenie konkretnego rozmieszczenia zakrytych kart. Następnie, na podstawie otrzymanych rezultatów, wybierane jest zagranie, np. takie, które najczęściej zapewniło wygraną albo takie, które maksymalizuje średni wynik. Efektywność takiego postępowania zależy m.in. od szybkości z jaką rozwiązywane są problemy pomocnicze, czyli gry z doskonałą informacją, dlatego duża część rozprawy poświęcona jest właśnie tego typu grom.
Opisana metoda obecnie cieszy się dużą popularnością. Z powodzeniem użyto jej zarówno do gier karcianych takich jak brydż, skat, jak i np. do planszowej gry scrabble. W tej pracy, do celów badawczych oraz do zilustrowania opisywanych algorytmów posłużono się brydżem (ściślej, fazą rozgrywki tej gry). David Levy już w publikacji z 1989 roku zaproponował, by wyżej opisaną ideę zastosować do brydża. Jednakże, by uzyskać jej rozsądnie wydajną implementację, należało opracować metody, które dostatecznie szybko rozwiązywałyby problem rozgrywki w otwarte karty, czyli związaną z brydżem grę z doskonałą informacją. Dokonał tego Matthew L. Ginsberg, m.in. dzięki odkryciu przełomowego algorytmu Partition Search.
Poza analizą dotychczas istniejących metod rozprawa zawiera elementy nowe, które stanowią autorski wkład w badania nad algorytmami decyzyjnymi, zarówno dla gier z doskonałą, jak i bez doskonałej informacji.
Sporo uwagi poświecono odkrytemu przez Matthew L. Ginsberga algorytmowi Partition Search. Rozprawa zawiera zarówno wyjątkowo dokładną analizę (m.in. przeprowadzono w niej formalny dowód poprawności i formalnie zdefiniowano tzw. system podziału gry dla brydża), jak i autorskie ulepszenia tej techniki. Jak wskazują przeprowadzone badania, najważniejsze z tych rozszerzeń, nazwane lokalnym Partition Search, prowadzi w przypadku brydża do znacznej (prawie o połowę) redukcji wielkości drzewa poszukiwań i czasu obliczeń. W pracy opisano także inne metody zwiększające efektywność programu rozwiązującego problem rozgrywki w otwarte karty, np. zaproponowano nowatorską, szybką i dokładną metody liczenia tzw. lew natychmiastowych.
W części pracy poświęconej grom bez doskonałej informacji zaproponowano dwa nowe algorytmy decyzyjne, które w trakcie działania rozwiązują problemy pomocnicze z doskonałą informacją. Nazwano je: największa liczba wygranych par i największy zbiór wygranych par. Ponadto, w rozprawie sformalizowano koncepcję gwarantowanej wypłaty w zbiorze pozycji (obydwa nowe algorytmy z niej korzystają) oraz koncepcję szukania największego zbioru wygranych pozycji (używa jej tylko drugi z algorytmów), a także wskazano jak skorzystać z tej drugiej koncepcji w grach, których zbiór możliwych rezultatów nie ogranicza się do pary wygrana-przegrana. Sformalizowano także metodę analizy potencjalnych, dotychczasowych przebiegów gry, pozwalającą oszacować jak prawdopodobne są poszczególne z nich (takie szacowania pozwalają wyciągać wnioski z przeszłych poczynań rywali i często zwiększają skuteczność badanych algorytmów decyzyjnych). Zaproponowano, by w tym celu także wykorzystać rozwiązania problemów pomocniczych będących grami z doskonałą informacją. Skuteczność proponowanych rozwiązań potwierdzono doświadczalnie.