Złożoność gry - Game complexity
Teoria gier kombinatorycznych ma kilka sposobów mierzenia złożoności gry . W tym artykule opisano pięć z nich: złożoność przestrzeni stanów, rozmiar drzewa gry, złożoność decyzji, złożoność drzewa gry i złożoność obliczeniowa.
Miary złożoności gry
Złożoność przestrzeni stanów
Stan przestrzeni złożoności z gry jest liczba stanowisk prawnych gier osiągalnych z początkowej pozycji w grze.
Gdy jest to zbyt trudne do obliczenia, górną granicę można często obliczyć, licząc również (niektóre) nielegalne pozycje, czyli pozycje, które nigdy nie mogą powstać w trakcie gry.
Rozmiar drzewa gry
Rozmiar drzewa gry to całkowita liczba możliwych gier, w które można grać: liczba węzłów liści w drzewie gry zakorzenionych w początkowej pozycji gry.
Drzewo gry jest zazwyczaj znacznie większe niż przestrzeń stanów, ponieważ te same pozycje mogą występować w wielu grach, wykonując ruchy w innej kolejności (na przykład w grze w kółko i krzyżyk z dwoma X i jednym O na planszy pozycja mogła zostać osiągnięta na dwa różne sposoby, w zależności od tego, gdzie został umieszczony pierwszy X). Górną granicę rozmiaru drzewa gry można czasem obliczyć, upraszczając grę w sposób, który tylko zwiększa rozmiar drzewa gry (na przykład, zezwalając na nielegalne ruchy), aż stanie się wykonalny.
W grach, w których liczba ruchów nie jest ograniczona (na przykład wielkością planszy lub zasadą powtarzania pozycji), drzewo gry jest generalnie nieskończone.
Drzewa decyzyjne
Kolejne dwie miary wykorzystują ideę drzewa decyzyjnego , które jest poddrzewem drzewa gry, z każdą pozycją oznaczoną jako „wygrywa gracz A”, „wygrywa gracz B” lub „remis”, jeśli można udowodnić, że ta pozycja ma tę wartość (zakładając najlepszą grę obu stron), badając tylko inne pozycje na wykresie. (Pozycje końcowe mogą być oznaczone bezpośrednio; pozycja z graczem A do przesunięcia może być oznaczona jako „gracz A wygrywa”, jeśli jakakolwiek następna pozycja jest wygrana dla A, lub jako „gracz B wygrywa”, jeśli wszystkie kolejne pozycje są wygrane dla B, lub oznaczone jako „remis”, jeśli wszystkie kolejne pozycje są albo wylosowane, albo wygrane dla B. I odpowiednio dla pozycji z B do ruchu.)
Złożoność decyzji
Złożoność decyzyjna gry to liczba węzłów liści w najmniejszym drzewie decyzyjnym, które ustala wartość pozycji początkowej.
Złożoność drzewa gry
Złożoność gry drzewo z gry jest liczba węzłów liściowych w najmniejszym pełnej szerokości drzewa decyzyjnego, który ustanawia wartości początkowej pozycji. Drzewo o pełnej szerokości zawiera wszystkie węzły na każdej głębokości.
Jest to szacunkowa liczba pozycji, które należałoby ocenić w wyszukiwaniu minimaksowym, aby określić wartość pozycji początkowej.
Trudno jest nawet oszacować złożoność drzewa gry, ale w przypadku niektórych gier przybliżenie można uzyskać, podnosząc średni współczynnik rozgałęzienia gry b do potęgi liczby warstw d w przeciętnej grze lub:
.
Złożoność obliczeniowa
Złożoność obliczeniowa z gry opisuje asymptotyczne trudności w grze, jak rośnie dowolnie duże, wyrażone w asymptotyczne tempo wzrostu lub członkostwa w klasie złożoności . Ta koncepcja nie odnosi się do konkretnych gier, ale raczej do gier, które zostały uogólnione, aby mogły być dowolnie duże, zazwyczaj grając je na planszy n -by- n . (Z punktu widzenia złożoności obliczeniowej gra na planszy o ustalonym rozmiarze jest skończonym problemem, który można rozwiązać w O(1), na przykład za pomocą tabeli przeglądowej z pozycji do najlepszego ruchu w każdej pozycji.)
Asymptotyczna złożoność jest zdefiniowana przez najbardziej wydajny (pod względem dowolnego rozważanego zasobu obliczeniowego ) algorytm rozwiązywania gry; najczęstsza miara złożoności ( czas obliczeń ) jest zawsze dolna ograniczona przez logarytm asymptotycznej złożoności w przestrzeni stanów, ponieważ algorytm rozwiązania musi działać dla każdego możliwego stanu gry. Będzie to ograniczone przez złożoność dowolnego konkretnego algorytmu, który działa w rodzinie gier. Podobne uwagi dotyczą drugiej najczęściej używanej miary złożoności, ilości miejsca lub pamięci komputera używanej do obliczeń. Nie jest oczywiste, że dla typowej gry istnieje jakakolwiek dolna granica złożoności przestrzeni, ponieważ algorytm nie musi przechowywać stanów gry; jednak wiele interesujących gier jest znanych jako PSPACE-trudne , i wynika z tego, że ich złożoność przestrzenna będzie również ograniczona przez logarytm asymptotycznej złożoności w przestrzeni stanów (technicznie granica jest tylko wielomianem w tej ilości; ale zwykle wiadomo, że jest liniowy).
- Głębi pierwsza strategia minimax użyje czas obliczeń proporcjonalny do gry drzewiastej złożoności, ponieważ musi zbadać całe drzewo i kwotę wielomianu pamięci w logarytmu drzewiastej złożoności, ponieważ algorytm musi zawsze przechowywać jeden węzeł drzewo na każdej możliwej głębokości ruchu, a liczba węzłów na największej głębokości ruchu jest dokładnie złożonością drzewa.
- Indukcja wsteczna wykorzystuje zarówno pamięć, jak i czas proporcjonalnie do złożoności przestrzeni stanów, ponieważ musi obliczyć i zarejestrować poprawny ruch dla każdej możliwej pozycji.
Przykład: kółko i krzyżyk (kółko i krzyżyk)
W przypadku gry w kółko i krzyżyk proste górne ograniczenie rozmiaru przestrzeni stanów wynosi 3 9 = 19 683. (Istnieją trzy stany dla każdej komórki i dziewięć komórek.) Ta liczba obejmuje wiele nielegalnych pozycji, takich jak pozycja z pięcioma krzyżykami i bez zer lub pozycja, w której obaj gracze mają rząd trzech. Dokładniejsze liczenie, usuwając te nielegalne pozycje, daje 5478. A kiedy rotacje i odbicia pozycji są uważane za identyczne, istnieje tylko 765 zasadniczo różnych pozycji.
Aby ograniczyć drzewo gry, istnieje 9 możliwych początkowych ruchów, 8 możliwych odpowiedzi i tak dalej, więc jest ich najwyżej 9! lub łącznie 362.880 gier. Jednak rozgrywka może zająć mniej niż 9 ruchów, a dokładne wyliczenie daje 255 168 możliwych gier. Gdy rotacje i odbicia pozycji są uważane za takie same, jest tylko 26 830 możliwych gier.
Złożoność obliczeniowa gry w kółko i krzyżyk zależy od sposobu jego uogólnienia . Naturalnym uogólnieniem jest m , n , k -games : grał na m przez n pokładzie zwycięzca jako pierwszy gracz, który zbierze k rzędu. Od razu widać, że tę grę można rozwiązać w DSPACE ( mn ), przeszukując całe drzewo gry. To umieszcza go w ważnej klasie złożoności PSPACE . Po kilku dodatkowych pracach można wykazać, że jest to PSPACE-kompletne .
Złożoność niektórych znanych gier
Ze względu na duży rozmiar złożoności gier, tabela ta podaje pułap ich logarytmu o podstawie 10. (Innymi słowy, liczba cyfr). Wszystkie poniższe liczby należy traktować z ostrożnością: pozornie drobne zmiany w zasadach gry mogą zmienić liczby (które i tak często są przybliżonymi szacunkami) przez ogromne czynniki, które z łatwością mogą być znacznie większe niż liczby pokazane.
Uwaga: uporządkowane według rozmiaru drzewa gry
Gra | Rozmiar płyty
(pozycje) |
Złożoność przestrzeni stanów
(jako log do bazy 10) |
Złożoność drzewa gry
(jako log do bazy 10) |
Średnia długość gry
( warstwy ) |
Współczynnik rozgałęzienia | Ref | Klasa złożoności odpowiedniej gry uogólnionej |
---|---|---|---|---|---|---|---|
Kółko i krzyżyk | 9 | 3 | 5 | 9 | 4 | PSPACE-kompletny | |
Sim | 15 | 3 | 8 | 14 | 3,7 | PSPACE-kompletny | |
Pentomina | 64 | 12 | 18 | 10 | 75 | ?, ale w PSPACE | |
Kalah | 14 | 13 | 18 | 50 | Uogólnienie jest niejasne | ||
Połącz cztery | 42 | 13 | 21 | 36 | 4 | ?, ale w PSPACE | |
Dominujący (8 × 8) | 64 | 15 | 27 | 30 | 8 | ?, ale w PSPACE ; w P dla niektórych wymiarów | |
Congkak | 14 | 15 | 33 | ||||
Warcaby angielskie (8x8) (warcaby) | 32 | 20 lub 18 | 40 | 70 | 2,8 | EXPTIME-ukończony | |
Awari | 12 | 12 | 32 | 60 | 3,5 | Uogólnienie jest niejasne | |
Qubic | 64 | 30 | 34 | 20 | 54,2 | PSPACE-kompletny | |
Podwójny most atrapy | (52) | <17 | <40 | 52 | 5,6 | PSPACE-kompletny | |
Fanorona | 45 | 21 | 46 | 44 | 11 | ?, ale w EXPTIME | |
Morris dziewięciu mężczyzn | 24 | 10 | 50 | 50 | 10 | ?, ale w EXPTIME | |
Tablut | 81 | 27 | |||||
Warcaby międzynarodowe (10x10) | 50 | 30 | 54 | 90 | 4 | EXPTIME-ukończony | |
Warcaby chińskie (2 komplety) | 121 | 23 | 180 | EXPTIME -Complete | |||
Warcaby chińskie (6 kompletów) | 121 | 78 | 600 | EXPTIME -Complete | |||
Reversi (Otello) | 64 | 28 | 58 | 58 | 10 | PSPACE-kompletny | |
OnTop (podstawowa gra 2p) | 72 | 88 | 62 | 31 | 23,77 | ||
Linie działania | 64 | 23 | 64 | 44 | 29 | ?, ale w EXPTIME | |
Gomoku (15x15, styl dowolny) | 225 | 105 | 70 | 30 | 210 | PSPACE-kompletny | |
Sześciokątny (11x11) | 121 | 57 | 98 | 50 | 96 | PSPACE-kompletny | |
Szachy | 64 | 44 | 123 | 70 | 35 | EXPTIME-complete (bez zasady rysowania 50 ruchów ) | |
Bejeweled i Cukierki Crush (8x8) | 64 | <50 | 70 | NP-twarde | |||
GIF | 37 | 25 | 132 | 90 | 29,3 | ||
Połącz6 | 361 | 172 | 140 | 30 | 46000 | PSPACE-kompletny | |
Tryktrak | 28 | 20 | 144 | 55 | 250 | Uogólnienie jest niejasne | |
Xiangqi | 90 | 40 | 150 | 95 | 38 | ?, uważany za EXPTIME-complete | |
Uchowiec | 61 | 25 | 154 | 87 | 60 | PSPACE-trudno , a w EXPTIME | |
Hawana | 271 | 127 | 157 | 66 | 240 | PSPACE-kompletny | |
Twixt | 572 | 140 | 159 | 60 | 452 | ||
Janggi | 90 | 44 | 160 | 100 | 40 | ?, uważany za EXPTIME-complete | |
Quorydor | 81 | 42 | 162 | 91 | 60 | ?, ale w PSPACE | |
Carcassonne (podstawowa gra 2p) | 72 | >40 | 195 | 71 | 55 | Uogólnienie jest niejasne | |
Amazonki (10x10) | 100 | 40 | 212 | 84 | 374 lub 299 | PSPACE-kompletny | |
Shogi | 81 | 71 | 226 | 115 | 92 | EXPTIME-ukończony | |
Thurn i Taxi (2 graczy) | 33 | 66 | 240 | 56 | 879 | ||
Idź (19x19) | 361 | 170 | 360 | 150 | 250 | EXPTIME-ukończony | |
Arimaa | 64 | 43 | 402 | 92 | 17281 | ?, ale w EXPTIME | |
Strategii | 92 | 115 | 535 | 381 | 21,739 | ||
Nieskończone szachy | nieskończony | nieskończony | nieskończony | nieskończony | nieskończony | Nieznane, ale mate-in-n jest rozstrzygalne | |
Magia: zgromadzenie | Nieskończony | Bezgraniczny | Bezgraniczny | nieskończony | nieskończony | AH-twardy |
Uwagi
Bibliografia
Zobacz też
- Idź i matematyka
- Rozwiązana gra
- Rozwiązywanie szachów
- Numer Shannona
- lista NP-kompletnych gier i łamigłówek
- lista kompletnych gier i łamigłówek PSPACE