Marcin Jurdziński	Tomasz Waleń
Treść zadania, Opracowanie	Program wzorcowy

Gra w zielone

Gra w zielone jest grą dla dwóch graczy - nazwijmy ich Ania i Bolek - polegającą na przesuwania pionka po planszy.

Część pól planszy jest pokolorowana na zielono, a pozostałe są białe. Wszystkie pola są ponumerowane liczbami naturalnymi z zakresu 1... (a+b), pola o numerach z zakresu 1... a należą do Ani, natomiast pola o numerach (a+1)... (a+b) należą do Bolka.

Dla każdego pola dany jest zbiór następników, zawierający te pola planszy, do których można z niego przejść w jednym ruchu. Zbiory te zostały tak dobrane, że z pola należącego do Ani można przejść w jednym ruchu tylko na pole należące do Bolka i odwrotnie.

Na początku gry ustawiamy pionek na dowolnym polu, a następnie gracze na przemian przestawiają pionek ze swojego pola na dowolny następnik tego pola - należący do przeciwnika. Grę rozpoczyna właściciel pola, z którego zaczynamy rozgrywkę. Zakładamy, że wszystkie pola mają niepuste zbiory następników, a więc zawsze można wykonać ruch. Gra kończy się w momencie, gdy pionek stanie po raz drugi na tym samym polu. Jeśli w sekwencji ruchów, od pierwszego do powtórnego zajęcia tego pola, pionek stanął przynajmniej raz na polu zielonym, to wygrywa Ania, w przeciwnym przypadku wygrywa Bolek.

Powiemy, że Ania ma strategię wygrywającą dla danego pola początkowego, jeśli istnieje metoda gwarantująca jej wygraną w rozgrywce zaczynającej się od tego pola, niezależnie od tego, jakie ruchy będzie wykonywał Bolek.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego gra.in opis planszy do gry w zielone,

• znajdzie zbiór pól planszy, dla których Ania ma strategię wygrywającą,

• zapisze wynik w pliku tekstowym gra.out.

Wejście

W pierwszym wierszu pliku tekstowego gra.in zapisane są dwie nieujemne liczby całkowite a, b oddzielone pojedynczym odstępem, oznaczające odpowiednio: liczbę pól należących do Ani i liczbę pól należących do Bolka. Liczby a, b spełniają warunek: . W kolejnych a+b wierszach opisano pola planszy - najpierw pola należące do Ani, a następnie pola należące do Bolka. Wiersz o numerze i+1, dla , zawiera na początku liczby całkowite z, k oddzielone pojedynczym odstępem, oznaczające odpowiednio kolor pola o numerze i (0 oznacza kolor biały, 1 - kolor zielony), oraz liczbę następników tego pola. Następnie w tym wierszu zapisane jest k liczb całkowitych (), pooddzielanych pojedynczymi odstępami, będącymi numerami następników danego pola. Liczba pól zielonych na planszy nie przekracza 100. Suma liczb następników wszystkich pól na planszy nie przekracza 30 000.

Wyjście

Pierwszy wiersz pliku tekstowego gra.out powinien zawierać dokładnie jedną liczbę całkowitą p, oznaczającą liczbę pól, dla których Ania ma strategię wygrywającą. Następne p wierszy powinno zawierać numery tych pól zapisane w kolejności rosnącej - każda liczba powinna zostać zapisana w osobnym wierszu.

Przykład

5 3
0 2 6 7
0 3 6 7 8
0 1 8
1 1 7
1 1 8
1 2 1 2
0 2 1 2
0 2 3 4

5
1
2
4
6
7

Rozwiązanie

Fakt: Strategia wygrywająca dla Bolka
Bolek ma strategię wygrywającą z każdego pola, które nie jest w zbiorze Wymuś(Z).

Dowód. Fakt, że pole p nie należy do zbioru Wymuś(Z) oznacza, że w uproszczonej grze w zielone rozpoczynającej się w polu p, Bolek potrafi zapobiec dojściu do jakiegokolwiek zielonego pola. Cała rozgrywka toczy się więc i kończy w białej części planszy - to gwarantuje zwycięstwo Bolka w zwyczajnej grze w zielone z pola p.

Przykład:
W tym i w poniższych przykładach ilustrujemy pojęcia i fakty opisane w tym opracowaniu na przykładzie gry w zielone z przykładu z treści zadania.

Zauważ, że oraz Wymuś. W polach spoza zbioru Wymuś(Z), tj. w polach ze zbioru , Bolek ma strategię wygrywającą polegającą na wybraniu pola 3 jako następnika w polu 8.

Następnie spróbujemy ustalić jakie warunki gwarantują, że strategia wygrywająca dla Ani w uproszczonej grze w zielone daje Ani zwycięstwo także w normalnej grze w zielone. W tym celu przydatne okazuje się pojęcie pułapki dla Bolka.

Definicja: Pułapka dla Bolka
Powiemy, że zbiór pól Wymuś(X) jest pułapką dla Bolka, jeśli dla każdego pola p ze zbioru X mamy:

1. pole p należy do Ani i istnieje następnik pola p znajdujący się w zbiorze Wymuś(X); lub
2. pole p należy do Bolka i każdy następnik pola p znajduje się w zbiorze Wymuś(X).

Przykład:
Niech . Zbiór Wymuś jest pułapką dla Bolka, ponieważ:

• istnieje następnik pola 4 (tj. pole 7) w zbiorze Wymuś(X), oraz
• każdy następnik pola 6 (tj. zarówno pole 1 jak i pole 2) należy do zbioru Wymuś(X).

Fakt: Strategia wygrywająca dla Ani
Jeśli zbiór Wymuś(X) jest pułapką dla Bolka, to Ania ma strategię wygrywającą z każdego pola w zbiorze Wymuś(X).

Dowód. Rozważmy następującą strategię dla Ani:

• w każdym białym polu Ani ze zbioru Wymuś(X), Ania gra zgodnie z jej strategią wygrywającą w uproszczonej grze w zielone;
• w każdym zielonym polu Ani ze zbioru Wymuś(X), tj. w każdym polu Ani ze zbioru X, Ania wybiera następnika który należy do zbioru Wymuś(X): taki następnik istnieje, bo zbiór Wymuś(X) jest pułapką dla Bolka.

Zauważ, że w każdej rozgrywce zgodnej z tą strategią, pionek nigdy nie opuszcza zbioru Wymuś(X). Co więcej, żaden cykl (tj. fragment rozgrywki rozpoczynający się i kończący w tym samym polu) w takiej rozgrywce nie składa się tylko z białych pól, ponieważ strategia Ani na białych polach jest wygrywająca w uproszczonej grze w zielone. Dlatego każda rozgrywka zgodna z powyższą strategią jest wygrywająca dla Ani w zwyczajnej grze w zielone.

Pozostaje nam do rozwiązania sytuacja, w której zbiór Wymuś(Z) nie jest pułapką dla Bolka. Niech będzie zbiorem zielonych pól, które spełniają warunki [5]lub [6] definicji pułapki dla Bolka, dla X = Z.

Zauważ, że w zielonych polach nie należących do zbioru Z₁, Bolek ma następującą strategię wygrywającą: najpierw przesuń pionek w jednym kroku do pola nie należącego do zbioru Wymuś(Z), a następnie użyj strategii wygrywającej zagwarantowanej przez Fakt [2]. Możemy zatem odrzucić zielone pola spoza zbioru Z₁, jako ``bezużyteczne'' dla Ani.

Aby ponowić próbę użycia Faktu [8] do wyznaczenia strategii wygrywającej dla Ani, rozważmy zbiór Wymuś(Z₁). Jeśli ten zbiór jest pułapką dla Bolka, to rozwiązanie gry w zielone jest gotowe (można wykazać - patrz dowód ogólniejszego Faktu [] poniżej - że także we wszystkich białych polach spoza zbioru Wymuś(Z₁) Bolek ma strategię wygrywającą.) W przeciwnym wypadku należy ponownie odrzucić zielone pola, które okazały się bezużyteczne dla Ani, itd.

Powyższe rozumowanie motywuje następującą metodę obliczania kolejnych, coraz mniejszych zbiorów zielonych pól, które kandydują do roli pól dających Ani strategię wygrywającą (poprzez Fakt [8]).

1	procedure NajwiększaPułapkaDlaBolka
2	begin
3	Z0 := Z
4	i := 0
5	while Wymuś(Zi) nie jest pułapką dla Bolka do
6	begin
7	zbiór pól z Zi spełniających warunki~\ref{definicja:pulapka-1}\ lub~\ref{definicja:pulapka-2}\ definicji~\ref{definicja:pulapka-dla-bolka}
8	i := i + 1
9	end
10	end

Przykład:

Z przykładu [3] mamy oraz Wymuś. Zauważ, że Z₀ nie jest pułapką dla Bolka, bo pole 5 należy do Ani, ale jedyny następnik pola 5, tj. pole 8, nie należy do zbioru Wymuś(Z₀). Pole 5 jest jedynym polem z Z₀ nie spełniającym warunków [5] lub [6] definicji [4], więc . Z przykładu [7] wiemy, że zbiór Wymuś(Z₁) jest pułapką dla Bolka.

Zauważ, że jeśli warunek kontynuacji wykonywania pętli 5:-9: jest spełniony, to istnieje przynajmniej jedno zielone pole w zbiorze Z_i nie spełniające warunków 1 lub 2definicji [4]. Dlatego ciąg zbiorów Z_i jest malejący, a stąd wynika, że liczba iteracji pętli 5:-9: wynosi O(k).

Niech będzie najmniejszą liczbą dla której zbiór Wymuś jest pułapką dla Bolka. Oczywiście Ania ma strategię wygrywającą ze zbioru Wymuś - wynika to z Faktu [8]. Aby wykazać, że Wymuś to zbiór wszystkich pól z których Ania ma strategię wygrywającą, wystarczy udowodnić, że z każdego pola spoza zbioru Wymuś, strategię wygrywającą ma Bolek.

Fakt: Strategia wygrywająca dla Bolka: ogólny przypadek

Dla każdego , Bolek ma strategię wygrywającą z każdego pola spoza zbioru Wymuś(Z_i).

Dowód. Dowód przebiega przez indukcję ze względu na i. Zauważ, że dla i = 0 teza wynika wprost z Faktu [2].

Załóżmy, że dla pewnego , Bolek ma strategię wygrywającą z każdego pola spoza zbioru Wymuś(Z_i). Wykażemy, że wtedy Bolek ma także strategię wygrywającą z każdego pola spoza zbioru Wymuś.

Wystarczy udowodnić, że Bolek ma strategię wygrywającą z każdego pola ze zbioru WymuśWymuś - dla pól nie należących do zbioru Wymuś(Z_i) teza wynika z hipotezy indukcyjnej.

Rozważmy dwa rodzaje pól ze zbioru WymuśWymuś:

1. Jeśli pole jest zielone, to nie spełnia warunków 1 lub 2 definicji [4], więc Bolek może z tego pola w jednym kroku wymusić przesunięcie pionka poza zbiór Wymuś(Z_i), skąd ma strategię wygrywającą (z hipotezy indukcyjnej).
2. Jeśli pole jest białe, to Bolek korzysta ze strategii w uproszczonej grze w zielone, która zapobiega dojściu pionka do zbioru Wymuś. Jeśli w wyniku rozgrywki pionek stanie na jednym z zielonych pól w zbiorze WymuśWymuś, wtedy Bolek postępuje jak w przypadku [10] i wygrywa. W przeciwnym razie rozgrywka toczy się i kończy w białej części zbioru WymuśWymuś, więc jest wygrywająca dla Bolka.

Aby precyzyjnie oszacować koszt czasowy działania algorytmu NajwiększaPułapkaDlaBolka musimy ustalić, jaki jest koszt rozwiązywania uproszczonej gry w zielone, tj. obliczania zbioru Wymuś(X). Powiemy, że warunek AniaWymusza(T, p) zachodzi dla pewnego zbioru pól T, oraz pola p, jeśli mamy:

• pole p należy do Ani i istnieje następnik pola p należący do zbioru T, lub
• pole p należy do Bolka i każdy następnik pola p należy do zbioru T.

Ćwiczenie: Poprawność algorytmu ObliczZbiórWymuś

Wykaż, że poniższa procedura ObliczWymuś(X) wyznacza poprawnie zbiór pól z których Ania ma strategię wygrywającą w uproszczonej grze w zielone, tj. zbiór Wymuś(X).

1	procedure ObliczWymuś(X)
2	begin
3
4	while istnieje pole takie, że \emph{AniaWymusza}(W, p) do
5	dodaj pole p do zbioru W
6	{\bf return}(W)
7	end

Procedurę ObliczWymuś można zaimplementować tak, aby działała w czasie O(m), gdzie m jest sumą liczb następników dla wszystkich pól. Przykładowa implementacja znajduje się na załączonej dyskietce.

Powyższą algorytmiczną analizę struktury strategii wygrywających dla Ani i Bolka w grze w zielone można podsumować w następujący sposób.

Twierdzenie: Poprawność algorytmu NajwiększaPułapkaDlaBolka

Niech będzie najmniejszą liczbą, dla której w procedurze NajwiększaPułapkaDlaBolka zbiór Wymuś jest pułapką dla Bolka. Wtedy Ania ma strategię wygrywającą z pól ze zbioru Wymuś, a Bolek ma strategię wygrywającą ze wszystkich pozostałych pól. Algorytm można zaimplementować tak, by działał w czasie , gdzie k jest liczbą zielonych pól, a m jest sumą liczb następników dla wszystkich pól.

Inne rozwiązania

W tym podrozdziale omówimy alternatywny warunek wystarczający i konieczny dla istnienia strategii wygrywających dla Bolka lub Ani w Grze w Zielone. Interesującą cechą tego warunku jest jego lokalność: jeśli każde pole jest w odpowiedniej, dość łatwej do sprawdzenia relacji ze zbiorem jego następników, to mamy gwarancję, że istnieje ``globalna'' strategia wygrywająca dla odpowiedniego gracza.

Definicja: Dobre etykietowanie dla Bolka

Rozważmy funkcję : z każdym polem , związana jest etykieta , która jest liczbą naturalną nie większą niż k, lub symbolem . Przyjmujemy umownie, że jest większa od każdej liczby naturalnej, czyli , dla każdej liczby naturalnej i. Powiemy, że etykietowanie jest dobre dla Bolka w polu p, jeśli lub spełnione są następujące warunki:

• jeśli pole p należy do Ani, to dla każdego następnika r pola p zachodzi warunek PostępBolka;
• jeśli pole p należy do Bolka, to istnieje następnik r pola p taki, że zachodzi warunek PostępBolka;

gdzie warunek PostępBolka jest spełniony wtedy i tylko wtedy gdy:

1. , jeśli pole p jest zielone, oraz
2. , jeśli pole p jest białe.

Mówimy, że etykietowanie jest dobre dla Bolka, jeśli jest dobre dla Bolka we wszystkich polach planszy.

Przykład:
Zauważ, że zbiór P pól Gry w Zielone z treści zadania jest równy . Niech etykietowanie będzie zdefiniowane przez następującą tabelę.

Etykietowanie jest dobre dla Bolka ponieważ:

• pole 3 należy do Ani, pole 8 jest jedynym następnikiem pola 3, oraz zachodzi PostępBolka, tj. ; zauważ, że wystarczy tu nieostra nierówność, bo pole 3 jest białe;
• pole 5 należy do Ani, pole 8 jest jedynym następnikiem pola 5, oraz zachodzi PostępBolka, tj. ; zauważ, że wymagana tu jest ostra nierówność, bo pole 5 jest zielone;
• pole 8 należy do Bolka i dla pola 3, które jest następnikiem pola 8, zachodzi PostępBolka, tj. .

Za tą-na pierwszy rzut oka-zawiłą definicją kryje się następująca prosta intuicja. O etykiecie pola p - o ile ta etykieta jest liczbą naturalną, a nie symbolem  - można myśleć jako o górnym ograniczeniu na liczbę zielonych pól, które Bolek może być zmuszony (przez Anię) odwiedzić w rozgrywce, jeśli Bolek wybiera zawsze następnika o jak najmniejszej etykiecie. Wykażemy, że wybieranie następnika o najmniejszej etykiecie gwarantuje Bolkowi zwycięstwo w grze w zielone, jeśli etykietowanie jest dobre dla Bolka.

Fakt: Strategia wygrywająca dla Bolka

Jeśli etykietowanie jest dobre dla Bolka, to Bolek ma strategię wygrywającą z każdego pola p takiego, że .

Dowód: Wykażemy, że następująca strategia jest wygrywająca dla Bolka: w każdym polu p należącym dla Bolka, Bolek wybiera następnika r pola p, o jak najmniejszej etykiecie . Zauważmy, że z definicji dobrego etykietowania dla Bolka wynika, że wtedy dla każdej rozgrywki p₁, p₂, p₃, ..., p_i mamy

Niech p_j = p_i, dla pewnego j < i, tj. p_j = p_i jest pierwszym polem na którym pionek stanął dwa razy. Z powyższego warunku wynika, że , więc musi być . Z definicji dobrego etykietowania dla Bolka - a dokładniej z punktu 1 definicji warunku PostępBolka - wynika, że pola są białe. Inaczej mówiąc, żadne pole odwiedzone pomiędzy pierwszą i drugą wizytą w polu p_j = p_i nie jest zielone, czyli rozgrywka jest wygrywająca dla Bolka.

1	procedure PodnośEtykietowanie
2	begin
3	dla każdego pola p do
4	while nie jest dobre dla Bolka do
5	begin
6	wybierz pole p w którym nie jest dobre dla Bolka
7
8	end
9	end

Powyższy fakt oznacza, że istnienie dobrego etykietowania dla Bolka, dla którego zachodzi , jest warunkiem wystarczającym dla istnienia strategii wygrywającej dla Bolka z pola p. Poniżej naszkicujemy dowód faktu, że jest to również warunek konieczny, oraz przedstawimy wydajny sposób znajdowania dobrych etykietowań. Rozważmy następującą procedurę poszukiwania dobrego etykietowania dla Bolka:

gdzie Popraw to najmniejsza etykieta nie mniejsza od , która przypisana polu p gwarantuje, że etykietowanie staje się dobre w polu p. Wartość Popraw można obliczyć na przykład tak:

gdzie jest zdefiniowane w następujący sposób: Warto tu zwrócić uwagę na to, że Popraw oraz, że Popraw, jeśli etykietowanie nie jest dobre w polu p.

Przykład:
Dla skrócenia i uproszczenia ilustracji działania algorytmu

PodnośEtykietowanie

wprowadzamy następującą notację na oznaczenie ciągu kilku operacji Popraw: Rozważmy następujące wykonanie procedury PodnośEtykietowanie:

Etykietowanie jest dobre dla Bolka. Zauważ, że etykietowanie jest ``mniejsze'' niż etykietowanie  z przykładu 

Można myśleć o procedurze PodnośEtykietowanie jako o metodzie przybliżania etykietowania ,,z dołu'', do ,,najmniejszego'' dobrego etykietowania. Istotnie, początkowe etykietowanie , gdzie , dla każdego pola p, jest ,,mniejsze'' niż jakiekolwiek inne etykietowanie. (Dla ścisłości, mówimy, że etykietowanie jest ,,mniejsze'' lub równe niż etykietowanie , jeśli , dla każdego pola p.) Kolejne ,,poprawki'' polegające na podnoszeniu wartości etykietowania w polu, w którym nie jest dobre dla Bolka, zachowują własność, że etykietowanie jest mniejsze lub równe niż każde dobre etykietowanie. Jest tak dlatego, ponieważ w procedurze PodnośEtykietowanie wartość etykiety w pewnym polu jest zawsze podnoszona tylko o tyle, o ile to jest konieczne, aby etykietowanie stało się dobre dla Bolka w tym polu.

Przykład:
Etykietowanie :

Zauważ, że każde pole może być poprawione przez procedurę PodnośEtykietowanie co najwyżej k+1 razy, zatem liczba powtórzeń pętli 4:-8: wynosi .

Co więcej, etykietowanie po zakończeniu procedury PodnośEtykietowanie jest dobrym etykietowaniem dla Bolka; w ,,najgorszym'' przypadku mamy , dla każdego pola p - ,,największe'' dobre etykietowanie. Z faktu [13] wynika, że Bolek ma strategię wygrywającą z każdego pola p takiego, że . Najmniejsze dobre etykietowanie dla Bolka, tj. etykietowanie obliczane przez procedurę PodnośEtykietowanie, jest szczególnie interesujące ponieważ można z niego łatwo odczytać rozwiązanie gry w zielone, tj. zbiór pól z których istnieje strategia wygrywająca dla Ani.

Twierdzenie: Strategia wygrywająca dla Ani

Etykietowanie obliczone przez procedurę PodnośEtykietowanie ma taką własność, że Ania ma strategię wygrywającą z pola p wtedy i tylko wtedy gdy .

Dowód tego twierdzenia nie jest natychmiastowy i wymaga dość subtelnej argumentacji. Poniżej szkicujemy przydatne w tym celu pojęcia oraz ogólny tok rozumowania. Wypełnienie szczegółów dowodu pozostawiamy jako ćwiczenie dla dociekliwego czytelnika.

Definicja: Dobre etykietowanie dla Ani

Rozważmy etykietowanie . Powiemy, że etykietowanie jest dobre dla Ani w polu p, jeśli lub spełnione są następujące warunki:

• jeśli pole p należy do Ani, to istnieje następnik r pola p taki, że zachodzi warunek PostępAni,
• jeśli pole p należy do Bolka, to dla każdego następnika r pola p, zachodzi warunek PostępAni;

gdzie warunek PostępAni oznacza, że , jeśli pole p jest białe. Mówimy, że etykietowanie jest dobre dla Ani, jeśli jest dobre dla Ani we wszystkich polach planszy.

Przykład:
Etykietowanie zdefiniowane przez następującą tabelę jest dobre dla Ani.

W celu wykazania Twierdzenia [15] do procedury PodnośEtykietowanie dodamy instrukcje obliczające etykietowanie . Zauważ, że te dodatkowe instrukcje nie mają wpływu na obliczenie etykietowania  i służą nam tylko jako pomoc w dowodzie Twierdzenia [15]. Rozważmy następującą modyfikację procedury PodnośEtykietowanie:

1	procedure PodnośEtykietowanie'
2	begin
3	dla każdego pola p do begin ; end
4	while nie jest dobre dla Bolka do
5	begin
6	wybierz pole p w którym nie jest dobre dla Bolka;
7	;
8	if then
9	end
10	end

gdzie

Przykład:

Przekonaj się, że etykietowanie obliczane przez procedurę

PodnośEtykietowanie'

jest równe etykietowaniu z Przykładu [16].

Ćwiczenie: Dobre etykietowanie dla Ani

Wykaż, że etykietowanie: obliczane przez procedurę PodnośEtykietowanie' jest dobre dla Ani.
Wskazówka. Wykaż, że gdyby istniało pole p takie, że i nie jest dobrym etykietowaniem dla Ani w polu p, to , gdzie jest najmniejszym dobrym etykietowaniem dla Bolka.

Powyższą analizę dobrych etykietowań dla Ani i Bolka można podsumować w następujący sposób.

Twierdzenie: Poprawność algorytmu PodnośEtykietowanie

Niech będzie etykietowaniem obliczonym przez procedurę PodnośEtykietowanie. Wtedy Ania ma strategię wygrywającą z każdego pola p dla którego zachodzi , a Bolek ma strategię wygrywającą ze wszystkich pozostałych pól.

Ćwiczenie: Wydajna implementacja algorytmu

Zaimplementuj algorytm PodnośEtykietowanie w taki sposób, aby czas działania twojego programu był .
Wskazówka. Zaprojektuj strukturę danych umożliwiającą ustalanie w czasie O(1), czy istnieje pole p, w którym aktualne etykietowanie nie jest dobre dla Bolka, oraz poprawianie wartości etykietowania w polu p i aktualizację struktury danych w czasie O(d), gdzie d jest sumą liczb, następników pola p oraz jego ,,poprzedników'', tj. pól dla których p jest następnikiem.

Ciekawy problem:
Przyjmijmy, że liczba zielonych pól wynosi . Czy istnieje algorytm rozwiązujący gry w zielone działający w czasie ? W szczególności, czy istnieje algorytm rozwiązujący gry w zielone działający w czasie O(m)?

Testy

Ocena rozwiązań zadania ``Gra w zielone'', przedstawionych przez uczestników olimpiady, została oparta na zachowaniu się programów na kolekcji jedenastu testów, tj. jedenastu plików wejściowych zawierających opisy plansz różnych gier w zielone:

• gra0.in: Plik z treści zadania.
• gra1.in, gra2.in: Niewielkie plansze, zaprojektowane głównie z myślą o sprawdzaniu, czy program poprawnie rozwiązuje zadanie, nie wymagające - ze względu na mały rozmiar - aby algorytm był bardzo wydajny.
• gra3.in: Niewielka plansza o kilkudziesięciu polach z losowo dobranymi następnikami.
• gra4.in^*: Plansza o umiarkowanej wielkości, z losowo dobranymi następnikami; mała średnia liczba następników.
• gra5.in^*: Plansza o umiarkowanej wielkości, z losowo dobranymi następnikami; duża średnia liczba następników.
• gra6.in^*: Plansza o dużej wielkości z losowo dobranymi następnikami.
• gra7.in^*: Plansza o umiarkowanej wielkości, w której wszystkie pola przeciwnika o większych numerach niż numer danego pola są następnikami tego pola.
• gra8.in^*: Plansza o bardzo dużej wielkości, z losowo dobranymi następnikami; mała średnia liczba następników.
• gra9.in^*: Plansza o bardzo dużej wielkości, z losowo dobranymi następnikami; duża średnia liczba następników.
• gra10.in^*: Plansza o umiarkowanej wielkości, na której przedstawione rozwiązania działają w czasie równym pesymistycznemu oszacowaniu, tj. .