Go-Moku i Threat-Space Search

Na podstawie opracowania:

Go-Moku and Threat-Space Search

L.V. Allis, H. J. van den Herik, M. P. H. Huntjens

Cel gry Go-Moku

W grze bierze udział dwóch graczy. Jeden dysponuje pionkami białymi a drugi czarnymi. Umawiamy się, że czarny kolor zaczyna rozgrywkę. Na planszy 15x15 pól (najczęściej pola to przecięcia 15 pionowych i 15 poziomych linii) należy ułożyć 5 swoich pionków obok siebie w jednej linii. Linia może być pozioma, pionowa lub ukośna.

Rysunek 1. Wygrana grającego czarnymi pionami przez ukośną linię pięciu pionków.

Jeśli żadnemu z graczy nie uda się ułożyć współliniowej piątki pionków swojego koloru i plansza będzie całkowicie zapełniona, gra kończy się remisem.

Inne warianty gry

A. Plansza 19x19 (to jeszcze zwiększa przewagę czarnego koloru)

B. Tylko ciąg dokładnie pięciu pionów wygrywa, linie złożone z 6 lub więcej nie wygrywają (popularna wersja Go-Moku)

C. Czarny kolor ma narzucone ograniczenie na drugi ruch: nie może postawić pionka w kwadracie o boku 5, którego środkiem jest pierwszy czarny pionek (redukuje przewagę czarnego koloru, ale nie likwiduje jej całkowicie).

D. Renju – profesjonalny wariant

– biały kolor nie ma żadnych ograniczeń

– czarny nie może utworzyć linii dłuższej niż 5, a także dwóch trójek lub dwóch czwórek, gdyż jeśli to zrobi uznaje się go za przegranego w grze

(to również niweluje przewagę czarnego koloru ale nadal wygląda na to, że jest to kolor uprzywilejowany, powoduje to również konieczność stosowania różnych strategii gry w zależności od koloru gracza)

E. Renju z możliwością zamiany koloru przez białego gracza – polega to na tym, że po pierwszym ruchu czarnego koloru koniecznie w środku planszy, biały musi postawić swojego pionka na jednym z ośmiu sąsiednich pól, gracz czarny wykonuje drugi ruch a następnie biały przed swoim drugim ruchem decyduje czy chce pozostać przy swoim kolorze czy zamienić się kolorami z czarnym graczem. Prowadzi to do tego, że w optymalnej sytuacji czarny tak postawi drugiego pionka, żeby teoretycznym wynikiem gry był remis.

Wprowadzenie

Przez dziesięciolecia japońscy mistrzowie gry Go-Moku byli przekonani, że zaczynający gracz ma pewną wygraną.

Jednak nie było to wcześniej udowodnione matematycznie ani też żaden program komputerowy nie okazał się niepokonany kiedy grał czarnymi pionkami.

Zauważono dużą rozbieżność między sposobem w jaki aktualną sytuację na planszy analizują najlepsi gracze i jak wybierają kolejny ruch, a tym jak robią to algorytmy przeszukiwania stosowane powszechnie w grach. Stąd postanowiono przyjrzeć się bliżej grze Go-Moku i spróbować znaleźć lepsze techniki przeszukiwania.

Definicje

Do dalszego rozpatrywania problemu potrzebne będą następujące definicje:

Threat – zagrożenie, groźba, (tu: szach) będziemy rozumieć jako sytuację, w której przeciwnik jest zmuszony do wykonania ruchu z pewnego małego zbioru ruchów (jeśli nie chce przegrać od razu). Główne typy zagrożeń mają swoje nazwy (rozpatrujemy z pozycji koloru czarnego):

a) four - czwórka – jest zdefiniowana jako linia pięciu pól, z których gracz atakujący ma zajęte dowolne cztery a piąte pole jest wolne

b) straight four - czwórka w linii – to sekwencja czterech pionków gracza atakującego ograniczona z obu końców przez wolne pola

c) three – trójka – linia siedmiu pól, z których trzy środkowe są zajęte przez atakującego a pozostałe wolne

d) three – trójka - linia sześciu pól, z których trzy z czterech środkowych są zajęte przez gracza atakującego a trzy pozostałe są wolne

e) broken three – rozbita trójka – linia sześciu pól, z których trzy (nie tworzące sekwencji) z czterech wewnętrznych są zajęte przez atakującego, a pozostałe są wolne

Rysunek 2. Rodzaje zagrożeń.

Jeśli gracz tworzy czwórkę (przypadek a) to zagraża wygraną w następnym ruchu. Dlatego ruch ten musi zostać odparowany natychmiast przez drugiego gracza.

Jeśli tworzona jest czwórka w linii (przypadek b) oznacza to przegraną dla gracza broniącego, gdyż na obronę jest już za późno.

Jeśli gracz ustawi trójkę stwarza zagrożenie utworzenia czwórki w linii w następnym ruchu. Dlatego mimo tego, że zagrożenie rozkłada się na dwa ruchy musi zostać odparowane przez gracza broniącego już w tym posunięciu. Jeśli mamy do czynienia z przypadkiem trójki bez ograniczeń (przypadek c) z obu stron, są dwa ruchy obronne. Jeśli z trójką nieograniczoną z jednej strony (przypadek d) wtedy broniący może wykonać jeden z trzech ruchów.

W przypadku rozbitej trójki również gracz broniący musi wybrać w kolejnym posunięciu jeden z trzech ruchów (przypadek e).

Aby WYGRAĆ gracz musi doprowadzić do podwójnego zagrożenia:

· przez czwórkę w linii

· przez dwa rozłączne zagrożenia

Wtedy gracz broniący nie może obu naraz odparować i przegrywa.

Sekwencja zagrożeń (threat sequence) w większości przypadków występuje jako seria ruchów, z których każdy kolejny jest zagrożeniem i powoduje konieczność odparowania ataku przez gracza broniącego, przed wystąpieniem podwójnego zagrożenia (double threat). Gracz broniący ma bardzo ograniczone możliwości wyboru pola na kolejny ruch (jedynie pola, które odparują zagrożenie).

Sekwencję prowadzącą do wygranej (do podwójnego zagrożenia) nazywamy sekwencją zwycięstwa.

Przykładowe sekwencje:

Rysunek 3. Przykładowa rozgrywka.

Na rysunku 3 przedstawiona jest przykładowa sekwencja zagrożeń dzięki której kolor czarny wygrywa. Składa się ona z zagrożeń tylko typu czwórka. W związku z tym, że odpowiedź na tego typu zagrożenie jest tylko jedna cała sekwencja ruchów białego koloru jest wymuszona i jednoznacznie wyznaczona.

Rysunek 4. Przykładowa rozgrywka.

Na rysunku 4 jest pokazany przykład rozgrywki, w której zwycięstwo dla czarnego koloru jest osiągnięte przez sekwencję dwóch trójek.

W międzyczasie pojawiają się dwie czwórki ze strony białego koloru. Mimo tego jego przegrana jest nieunikniona (jest jedynie trochę odwleczona w czasie).

W tym przypadku jednak dokładna sekwencja zwycięstwa dla czarnego koloru jest zależna od reakcji przeciwnika na dwie trójki. W takich przypadkach będziemy stosować termin drzewo zwycięstwa. W praktyce w sekwencji zwycięstwa takie czwórki ze strony przeciwnika są pomijane.

Analiza mistrzów Go-Moku

Podczas obserwacji dwóch rosyjskich graczy mających stopnie piąty dan w GoMoku okazało się, że mają oni dużą łatwość w znajdowaniu obszaru na planszy gdzie można skonstruować sekwencję zwycięstwa i nie ma przy tym znaczenia ile trójek na nią się składa. Długość takiej sekwencji waha się w granicach 5 do 20 ruchów.

Wyodrębniono kolejne kroki w znajdowaniu zwycięskich sekwencji przez najlepszych graczy:

1. Wybierana jest najlepsza część planszy, która wydaje się najkorzystniejsza dla atakującego. Następnie decyduje się czy wystarczająco dużo pionków tworzy układ, w którym warto jej szukać. Opiera się to na „odczuciach” gracza, biorących się z dużego doświadczenia w osądzaniu stanu gry.

2. Rozpatrzone zostają zagrożenia, szczególnie te powiązane z innymi atakującymi pionkami będącymi już na planszy. Ruchy obronne przeciwnika są zwykle lekceważone.

3. Jeśli zostanie znaleziony wariant, w którym atakujący może stworzyć podwójne zagrożenie sprawdza się jaki wpływ na taką sekwencję mogą mieć ruchy obronne przeciwnika. Jeśli ma on jakiś wybór przy obronie sprawdza się czy wszystkie ścieżki prowadzą do wygranej. Sprawdza się także czy przeciwnik może uformować w międzyczasie jedną lub więcej czwórek neutralizując atak.

4. Jeśli tylko kilka wariantów obrony nie prowadzi do wygranej atakującego, są one badane czy w nich nie da się znaleźć w nich innej zwycięskiej sekwencji.

5. W praktycznej grze zwykle sekwencja zwycięstwa ma jeden wariant czyli ruchy obronne są nieznaczące.

6. Rozmiar przestrzeni przeszukiwania jest poważnie zmniejszony przez analizę jednostronną (atakującego). Tylko jeśli znajdzie się sekwencję zwycięstwa badane są możliwe przypadki ruchów obronnych przeciwnika.

Na pozycjach bez wygrywających sekwencji wykonuje się ruchy zwiększające potencjalne możliwości tworzenia zagrożeń lub w przypadku obronnych ruchów zmniejszenia tej możliwości u przeciwnika. Człowiek ocenia te możliwości na podstawie dwóch aspektów:

· Bezpośrednich kalkulacji np. jeśli oponent nie reaguje w tej części planszy

· Tzw. dobrego kształtu, czyli konfiguracji, w której pionki dobrze współgrają ze sobą

Strategie programów komputerowych

Najlepsze programy korzystają z wariantów algorytmu alfa-beta. Na każdej pozycji jedynie ograniczona liczba ruchów jest sprawdzana – ogranicza się tylko do tych najlepiej rokujących (wybór opiera się na heurystyce). Niektóre stosują dodatkowo przycinanie liści, dla których ewaluacja daje nikłe nadzieje na sukces. Najsilniejsze programy przeszukują do 16 ruchów. W fazie początkowej korzystają z tzw. książki otwarć, czyli bazy danych układów początkowych.

Pomiędzy programami są różnice. Na przykład program Polygon (1992) najpierw szuka wygranej w drzewie bez użycia funkcji oceniającej. Wykorzystując tablice transpozycji sięga czasem nawet 20 do 30 poziomów (lub nawet więcej). Jeśli nie znajdzie wygrywającej ścieżki przeprowadza n-poziomowe przeszukiwanie z użyciem funkcji oceny. Następnie symuluje wykonanie ruchu i sprawdza czy przeciwnik nie ma teraz wygrywającej ścieżki. Jeśli ma to ruch jest cofany i wybierany jest nowy przez n-poziomowe przeszukiwanie.

Kolejny przykład to Vertex (1991) nie używa tablic transpozycji, ani specjalnych technik przeszukiwania. Standardowo przegląda na głębokość 16 ruchów. Wybiera 14 najbardziej obiecujących ruchów dla każdego stanu planszy. Wraz z użyciem rozwiniętej księgi otwarć cechy te spowodowały, że był mistrzem w 1991.

Człowiek vs. komputer

Człowiek stosuje metody przeszukiwania optymistycznego, programy konwencjonalne algorytmy przeszukiwania stanów (drzewiaste). Moc obliczeniowa komputerów stara się pokryć duże narzuty na rozgałęzienia i kosztowną funkcję oceny (znacznie gorszą niż ludzka ocena). Stąd dążenie do symulowania myślenia ekspertów.

Zaprezentujmy interesujący ekstremalny przypadek:

Rysunek 5. Przykład stanu planszy.

Czarny gracz może utworzyć czwórkę przez jeden z 16 ruchów (np. a4, a5, a11, a12 itd.). Ma zatem

8!x2⁸ ≈ 10.000.000

możliwości przeprowadzenia 8 ruchów (z 8 wymuszonymi reakcjami przeciwnika).

Jeśli zostaną użyte tablice transpozycji (zapamiętujemy wszystkie stany planszy i nie liczymy ich wielokrotnie) wciąż jest do obsłużenia 6.000 możliwych kombinacji. To musi przeszukać komputer.

Człowiek po spojrzeniu na taką planszę od razu wie, że nie ma sensu przeprowadzać żadnego z tych ruchów, a już tym bardziej nie ma znaczenia kolejność ich wykonania.

Zmodyfikowana sytuacja z poprzedniego rysunku:

Rysunek 6. Przykład stanu planszy z zagrożeniami.

W sytuacji z rysunku 6 czarny kolor ma sekwencję zwycięską ale algorytmy będą niepotrzebnie rozszerzać drzewo stanów przez badanie posunięć w tych częściach planszy, w których nie ma wartościowych ruchów (prowadzących do wygranej).

Konkluzja jest taka, że konwencjonalne algorytmy nie symulują ludzkiego procesu myślowego w przypadku tej gry.

Threat-Space Search

Trzeba położyć nacisk na ograniczenie rozmiaru drzewa przeszukiwania i jak najefektywniejsze przeszukiwanie pozostających gałęzi.

Znaczna oszczędność przychodzi wraz ze zdeterminowaniem ruchów obronnych przeciwnika. Gdy weźmiemy pod uwagę różne możliwości obrony w przypadku trójki (2 pola lub 3 pola, na które broniący może postawić pionka) okaże się, że przestrzeń bardzo nam się powiększy. Dlatego przyjmiemy, że gracz broniący wykonuje wszystkie ruchy odparowujące atak naraz. Jeśli mimo tego nadal jesteśmy w stanie znaleźć wygrywającą sekwencję to możemy mieć pewność, że ruchy przeciwnika nie miały znaczenia. Wadą jest to, że faktycznie możemy nie znaleźć jakiejś sekwencji zwycięskiej mimo, że takowa istnieje.

Zatem zredukowaliśmy przestrzeń do ruchów atakujących.

Wprowadzamy 6 nowych pojęć:

1. gain square – zdobyte pole – pole na które atakujący stawia pionka

2. cost squares – pola stracone – pola na które broniący stawia pionki w odpowiedzi na atak

3. rest squares – pozostałe pola – pola należące do zagrożenia (z wykluczeniem pola zdobytego)

4. Zagrożenie A jest zależne od zagrożenia B jeśli zdobyte pole B jest jednym z pozostałych pól A.

5. Drzewo zależności A jest zakorzenione w A i składa się jedynie z zależnych węzłów. Tzn. potomkowie węzła J są zagrożeniami zależnymi od J („zagrożenie w synu wykorzystuje pionka postawionego w ojcu”).

6. Drzewa zależności P i Q są w konflikcie jeśli w drzewie P istnieje zagrożenie A i w drzewie Q zagrożenie B, w taki sposób, że zdobyte pole w A jest straconym w B lub odwrotnie, lub pokrywa się choć jedno pole stracone w A i w B.

Przykład:

Rysunek 7. Przykład definicji.

Na rysunku 7 zagranie e15 tworzy czwórkę (zdobyte pole to e15, stracone d15, pozostałe pola a15,b15,c15).

Następnie (po czarny e15, biały d15) rozważmy ruch atakującego na i11.

Rysunek 8. Przykład zależności zagrożeń.

Widać, że czwórka z polem zdobytym i11 jest zależna od czwórki z polem zdobytym e15.

Drzewo zależności zagrożenia i11 ma korzeń w czwórce i11, którego jedynym dzieckiem jest czwórka e15 (ta czwórka jest zależna tylko od pionków już będących na planszy więc nie ma potomków w drzewie zależności).

Przykładem drzew w konflikcie są ruchy e15 z obroną d15 i atak d15 z obroną e15. Nie mogą one zajść w tym samym przebiegu więc są w konflikcie. Przy większych drzewach zależności przeszukiwanie czy węzły nie są w konflikcie jest dość czasochłonne.

Dwa pomocne stwierdzenia:

1. Zagrożenie A niezależne od B nie ma prawa wystąpić w drzewie przeszukiwania B.

2. W drzewie threat-space search występują tylko zagrożenia powodowane przez atakującego. Po znalezieniu potencjalnej sekwencji zwycięskiej jest sprawdzane czy oprze się każdemu kontratakowi.

Drzewo przeszukiwania dla rysunku 6.

Istnieje 18 niezależnych zagrożeń w stanie początkowym. 16 czwórek w rogach i dwie trójki w zakresie i7-i12. W 15 czwórkach i 1 trójce zdobyte węzły nie biorą udziału w kolejnych zagrożeniach, zatem są to węzły końcowe. Pozostałe: czwórka i trójka są wykorzystywane w następujących po nich zagrożeniach.

W przypadku czwórki e15:

Tracimy d15, dwie nowe czwórki mogą być utworzone:

- h12 (strata i11) nie ma następnych zagrożeń

- i11 (strata h12) powoduje możliwość utworzenia czwórki w linii (wygranej) przez zajęcie i8

Pozwoliło to znaleźć sekwencję wygrywającą.

W przypadku trójki i11:

Tracimy i7,i8,i12. Dwie nowe czwórki mogą być utworzone:

- h12 (strata e15) nie ma następnych zagrożeń

- e15 (strata h12) prowadzi do utworzenia piątki przez zajęcie d15.

Druga sekwencja wygrywająca została znaleziona.

Przeszukaliśmy zaledwie 24 węzły a wszystkie potencjalne sekwencje zagrożeń zostały przejrzane.

Czasem zdarza się tak, że w sekwencji zwycięskiej są węzły zależne od więcej niż jednego węzła (w powyższym przykładzie tak nie było). Innymi słowy w niektórych sytuacjach zdobyte pola dwóch lub trzech zagrożeń są włączone do stworzenia nowego zagrożenia. W takim przypadku niezależne węzły powinny być połączone. Przydatne jest jedynie łączenie tych węzłów, których zdobyte pola potencjalnie tworzą nowe zagrożenie, np. muszą leżeć w jednej linii i blisko siebie by móc utworzyć piątkę.

Oto przykład kiedy czarny może wygrać przez kombinację niezależnych zagrożeń (węzłów):

Rysunek 9. Przykład gry wygranej dla czarnego przez kombinację.

Drzewo przeszukiwania składa się z czterech czwórek. Nie znaleziono zagrożeń prowadzących do wygranej.

W czterema różnymi zdobytymi polami z drzewa (h9,h10,i9,j10) możemy utworzyć (⁴₂)=6 kombinacji dwóch pól zdobytych. W przypadku h9 i h10 oraz i9 i j10 drzewa są w konflikcie dlatego tych par nie bierzemy pod uwagę przy rozpatrywaniu drzewa threat-space search. Kombinacja h9 i j10 nie jest złożona z pól współliniowych więc również odpada. Zatem pozostają nam trzy sensowne kombinacje:

1. h10-i9

2. h10-j10

3. h9-i9

W każdym z tych przypadków rozwinęliśmy (jeśli to możliwe) nowe drzewo przeszukiwania zgodnie z zasadami tss.

Okazuje się, że kombinacja h10-i9 powoduje możliwość stworzenia czwórki w linii przez postawienie pionka na polu f12. Czyli tworzy potencjalną wygrywającą sekwencję.

Te dwa przykłady dobrze ilustrują zasadę działania algorytmu threat-space search:

1. Dla danego stanu planszy tworzone jest drzewo zagrożeń.

2. Każdorazowo kiedy gałąź kończy się piątką lub czwórką w linii sprawdza się czy sekwencja zwycięska może zostać obalona (przez ruchy przeciwnika).

3. Jeśli żaden przypadek nie prowadzi do zwycięstwa atakującego wtedy rozpatruje się kombinacje niezależnych węzłów (przy założeniu, że zdobyte pola leżą blisko siebie i na tej samej linii). Powtarza się to aż do znalezienia sekwencji zwycięstwa albo do momentu kiedy nie można już utworzyć wartościowych kombinacji.

Można by podsumować, że ogólnie threat-space search linearyzuje część procesu przeszukiwania.

Porównania i ulepszenia

Program implementujący Threat-Space Search nazwano Victoria TSS. Porównano go z jednym z najlepszych istniejących programów Polygon(1992). Porównanie wyszło na korzyść Victorii jeśli chodzi o wydajność – okazała się lepsza:

- przegląda średnio kilkukrotnie mniej węzłów

- i każdy z nich przegląda średnio 10 razy szybciej

od Polygona, który stosuje konwencjonalne metody przeszukiwania globalnego (TSS szuka lokalnie – potomek jest powiązany z ojcem przez swoje pole zdobyte). Polygon wykorzystuje tablice transpozycji i zasady wiedzy, które pozwalają obniżyć głębokość drzewa przeszukiwania.

Jeśli porównamy skuteczność znajdowania sekwencji wygrywającej w trzech przypadkach z dwunastu badanych rozgrywek Victoria nie znalazła sekwencji zwycięstwa ze względu na narzucone ograniczenia (wykonywanie wszystkich ruchów odparowujących atak naraz). Aby to poprawić powstała wersja Victorii używająca kombinacji threat-space search i proof-number search. To pomogło w tych trzech przypadkach.

Victoria najpierw uruchamia threat-space search i poszukuje wygrywającej sekwencji jak było to opisane wcześniej. Następnie jeśli nie znajdzie uruchamiany jest algorytm proof-number search.

Na procedure threat-space search można patrzeć jak na funkcję oceniającą.

Stąd, z użyciem tss i pns można skonstruować drzewo przeszukiwania, o takiej samej wartości(przydatności) dla wyboru kolejnego ruchu (czyli dla wyniku gry) jak pełne drzewo przeszukiwania.

Głównym problemem jest nadal duży stopień rozgałęzienia drzewa (nawet ponad 200, szczególnie jeśli nie ma zagrożeń do odparowania).

Węzłem wewnętrznym nazwiemy węzeł, z którego nie znaleziono sekwencji wygrywającej. Aby zmniejszyć stopień rozgałęzienia zastosowano badanie tylko null-moves, czyli ruchów atakującego, po których jeśli następuje pusty ruch broniącego da się znaleźć sekwencję wygrywającą. To powoduje powstawanie tzw. ukrytych zagrożeń. Taka procedura zwykle zmniejsza liczbę możliwych ruchów obrony do kilku. Wybór takich ruchów (null-moves) jest raczej nieskomplikowany i może zostać wykonany przez heurystykę:

Victoria daje punkty za stworzenie schematów dwóch i trzech pionków w rzędzie. Potem N ruchów z najwyższą sumą punktów jest poddawana dalszemu rozwijaniu, żeby przekonać się czy skutkują znalezieniem sekwencji wygrywającej po pustym ruchu białego gracza. W testach okazało się, że N=10 jest rozsądnym wyborem.

Przy takim wyborze węzłów możemy mieć pewność, że każdy ruch czarnego koloru powoduje powstanie zagrożenia, większość ruchów białego może zostać pominięta w rozważaniach. Jednak musimy uważać, żeby nie utworzyć przez przypadek korzystnej sytuacji dla białego gracza zmuszając go do obrony. Dlatego został stworzony moduł, który po znalezieniu sekwencji wygrywającej dla czarnego gracza wybiera te ruchy białego gracza, które mają jakąś wartość obronną.

Są to ruchy zajmujące:

- stracone pole w sekwencji wygrywającej

- pole połączone z białymi pionkami na planszy

- pole połączone ze straconymi polami z sekwencji wygrywającej

Dzięki temu moduł redukuje liczbę potencjalnych ruchów białym kolorem z ponad 200 do 10-50 ruchów. Każdy z tych ruchów jest sprawdzany czy rzeczywiście obala sekwencję wygrywającą (sprawdzenie przez wykonanie tego ruchu i zapuszczenie threat-space search). Gdy czarny kolor ma więcej niż jedną sekwencję zwycięstwa liczba ruchów obronnych spada. Stan, w którym wszystkie ruchy białego gracza są wyeliminowane jest wygraną czarnego. Jeśli nie wszystkie ruchy białego są wyeliminowane wtedy przeszukiwanie jest wykonywane dla każdego jego ruchu.

W dużym stopniu udało się zniwelować problem znacznego rozgałęzienia drzewa. Zbadano, że tylko po pierwszych dwóch ruchach czarnego gracza i w niektórych przypadkach po trzecim i czwartym ruchu czarny gracz nie zagraża wygraną po pustym ruchu białego (tylko wtedy nie można stosować wyżej opisanego modułu). W tych przypadkach wszystkie (ponad 200) ruchów musi być rozpatrzone.

Przez zrobienie tego raz i zapamiętanie wyników w bazie danych rozwiązano grę Go-Moku!

Zastosowano praktyczne rozwiązania dla problemów:

- podział drzewa na mniejsze poddrzewa

- zapamiętywanie wyników w bazie danych

- łączenie wyników obliczeń w główne drzewo

- sprawdzenie spójności i pełności wykonanych obliczeń (wynikowego drzewa)

Szukano rozwiązania dla standardowego Go-Moku i dla wariantu odrzucającego linie dłuższe niż 5.

Oba zostały rozwiązane i znalezione drzewa zapamiętane w bazie danych.

Program przejrzał 5.3 (6.3 w drugim wariancie) miliona stanów planszy, wysokość drzewa rozwiązującego w obu przypadkach wyniosła 35.

Sposób gry (Victoria brała udział w turnieju programów grających w Go-Moku):

1. Najpierw korzysta z bazy danych stanów gry

2. Po przekroczeniu zasięgu bazy danych do akcji wkracza moduł threat-space search wspomagany w razie potrzeby przez proof-number search

Podsumowanie:

Victoria okazała się niepokonana gdy gra czarnym kolorem, threat-space search jest bardzo szybki w znajdowaniu sekwencji wygrywającej gdyż symuluje ludzką analizę problemu, ceną jaką się płaci za taką wydajność jest to, iż nie zawsze znajduje rozwiązanie ale wtedy może zostać wsparty przez proof-number search. Połączenie tych dwóch algorytmów może być także stosowane w innych grach jak i w dowodzeniu twierdzeń.