This is the translation. The original web-page (oryginalna strona): https://wilson.engr.wisc.edu/boxes/method/
David Wilson
Spojrzenie na każdą możliwą sekwencję ruchów daje n! czas na analizę. Zamiast tego mój program sprawdza każdą możliwą pozycję, co daje 2n czasu na analizę. Chociaż 2n szybko się powiększa, nie jest tak duże jak n!.
Praca wstecz
Dla każdej pozycji program przechowuje najlepszy wynik gracza w ruchu dla przyszłych pudełek. Pudła już otoczone są ignorowane. Zatem każda pozycja jest jednoznacznie identyfikowana przez obecne linie. Żadne dane o punktacji do tego ruchu nie są przechowywane.
Analiza działa wstecz od pozycji z wypełnionymi wszystkimi liniami. Pozycji tej przypisywana jest wartość podana w pierwszym wierszu pliku danych (zwykle zero). Następnie program przetwarza pozycje z wypełnioną jedną linią mniej. Gdy te są gotowe, przetwarza pozycje z inną linią mniej. W końcu wraca do pierwotnej pozycji.
Dla każdej takiej pozycji program bierze pod uwagę wszystkie możliwe ruchy i zachowuje wynik z najlepszym wynikiem dla gracza będącego w ruchu.
Dla każdego możliwego ruchu program najpierw sprawdza, czy powstało zero, jedno lub dwa nowe pola. Jeśli nowe pola nie zostały utworzone, wynik za ruch jest ujemny w stosunku do wyniku za wynikową pozycję, ponieważ pozycja ma najlepszy wynik dla drugiego gracza. Jeśli utworzono jedno lub dwa nowe pola, wynikiem za ruch jest wynik za wynikową pozycję plus liczba nowych pól, ponieważ gracz pozostaje w ruchu.
Znajdowanie pozycji z podaną liczbą wierszy
Pozycja jest reprezentowana przez liczbę binarną z jednym miejscem bitowym (cyfrą binarną) przypisanym do każdego wiersza. Bit ma wartość 0, jeśli linia jest obecna i 1, jeśli linia jest nieobecna. (Odwróciłem zwykłą konwencję, aby ułatwić sprawdzanie nowych pól).
Dzielę linie na grupy. Każda grupa wierszy jest reprezentowana przez kolejne bity w liczbie binarnej pozycji. Bity te można skopiować i umieścić w osobnej liczbie reprezentującej stan linii w grupie. Na przykład w grze 3×3 są łącznie 24 linie. Program używa dwóch grup linii po 12 linii każda. Dla każdej możliwej liczby linii dla grupy (od 0 do 12) program tworzy listę liczb reprezentujących grupę z taką liczbą linii. Następnie, aby znaleźć pozycje z ustawionymi n wierszami, łączę cały pierwszy stan grupowy z ustawionymi i liniami ze stanem drugiej grupy z ustawionymi ni linie, gdzie i zmienia się we wszystkich możliwych wartościach, co nie skutkuje niemożliwą liczbą wierszy dla żadnego z nich Grupa. Na przykład, aby znaleźć wszystkie pozycje z 15 liniami w grze 3×3, program łączy wszystkie stany pierwszej grupy z 3 liniami ze wszystkimi stanami drugiej grupy z 12 liniami (jest tylko jeden z nich), a następnie wszystkie pierwsze stany grupy z 4 liniami z wszystkie stany drugiej grupy mają 11 linii,… i wreszcie wszystkie stany pierwszej grupy mają 12 linii (znowu, tylko jeden możliwy), wszystkie stany drugiej grupy mają 3 linie.
Sprawdzanie nowych pudełek
Każda linia otrzymuje numer indeksu, który odpowiada swojemu bitowi w liczbie binarnej pozycji. Program ma dwa zestawy wartości testu pudełkowego, do których odwołuje się numer indeksu nowej linii. Jeden zestaw sprawdza, czy nad lub po lewej stronie nowej linii znajduje się nowe pole. Drugi sprawdza pole poniżej lub po prawej stronie nowej linii. Te wartości służą do sprawdzenia, czy pozostałe 3 wiersze są już obecne. Bity odpowiadające tym 3 liniom są ustawione na 1; wszystkie inne bity są ustawione na 0. Test jest wykonywany przy użyciu operacji logicznych „i” między liczbą binarną pozycji a wartością testową. Operacja “i” dla każdej pozycji bitu daje 1, jeśli odpowiednie bity w obu wartościach są ustawione; 0 inaczej. Ponieważ liczba binarna pozycji ma bity ustawione na 0, jeśli linia jest obecna, „i” tego i wartości testowej daje wynik zerowy wtedy i tylko wtedy, gdy te trzy wiersze są już obecne.
Jeśli pole nie istnieje, ponieważ linia znajduje się na krawędzi, wartość testowa ma ustawione wszystkie bity, testując w ten sposób wszystkie obecne linie. Ponieważ test jest wykonywany przed umieszczeniem nowej linii w liczbie binarnej pozycji, co najmniej jedna linia nie została ustawiona, a test z tą wartością powie, że nie ma nowego pola.
Korzystanie z wielu grup linii
Gdy analiza islandzka trwała zaledwie pół godziny, zdałem sobie sprawę, że czas obliczeń nie będzie problemem dla analizy gry 3×5. Islandzka gra ma 30 otwartych linii, podczas gdy gra 3×5 ma 38 otwartych linii, co czyni ją 256 (28) razy trudniejszą. 256 razy pół godziny to 128 godzin lub około 5 dni. Ponieważ mogłem skonfigurować program tak, aby zaczynał się od miejsca, w którym został przerwany po przerwaniu lub ponownym uruchomieniu, 5 dni można łatwo zrobić w nocy i w weekendy. Problem stał się więc wymyśleniem, jak dopasować go do mojego komputera z 256 MB pamięci RAM i 16 GB wolnego miejsca na dysku.
Na początku nie wydawało się to możliwe. Przechowywanie analizy wymagałoby 238 bajtów lub 256 GB miejsca na dysku. Przestrzeń potrzebna w pamięci RAM przy obliczaniu wartości dla pozycji z ustawionymi 19 wierszami w odniesieniu do wyników dla pozycji z ustawionymi 20 wierszami wynosiłaby 56 GB, a nie więcej niż jedna czwarta GB pamięci RAM.
Zakładając, że linie zostały podzielone na dwie grupy po 19 linii każda, mógłbym mieć w pamięci RAM tylko wartości odpowiadające danej liczbie linii dla każdej z dwóch grup. Na przykład, robiąc pozycje z 19 wierszami, mógłbym oceniać pozycje z 9 wierszami w pierwszej grupie i 10 wierszami w drugiej grupie. Nazwę je pozycjami 9/19 10/19. Aby obliczyć te wartości, musiałbym odwołać się do dwóch zestawów pozycji z 20 wierszami: 10/19 10/19 i 9/19 11/19. Nie potrzebowałem jednocześnie obu tych 20 zestawów linii w pamięci; można ich używać pojedynczo, zapisując najlepsze wyniki, biorąc pod uwagę tylko nowe linie w pierwszej grupie dla wszystkich pozycji 9/19 10/19, a następnie sprawdzając, czy można poprawić wyniki z nową linią w drugiej Grupa. Dwa bufory zajęłyby tylko 16 GB.
Wtedy zdałem sobie sprawę, że mogę podzielić te linie na więcej niż dwie grupy. Używając 6 grup, mogłem zmniejszyć potrzebną pamięć RAM do zaledwie 426 MB. Dalsze cięcie za pomocą symetrii (patrz poniżej) sprawiło, że był dopasowany. Oczywiście, aby znaleźć np. Wyniki dla pozycji 4/8 3/6 3/6 3/6 3/6 3/6, program musiał czytać w sześciu różnych zestawach punktacji po 20 wierszy – każdy mając jeszcze jedną linię w jednej z sześciu grup.
Symetria
Gra 3×5 jest symetryczna w pionie i poziomie, więc korzystając z symetrii, mógłbym podzielić wymagania przestrzenne przez 4 (właściwie przez 3 w mojej ostatecznej implementacji). Paul Stevens zgłosił błąd w teście symetrii na przekątnej na kwadratowej planszy.
Aby obliczyć wynik dla pozycji, program sprawdza wcześniej obliczone wyniki dla pozycji, które wynikają z dodania jeszcze jednej linii. Jednak dodanie linii może spowodować, że pozycja musi zostać symetrycznie przekształcona, zanim będzie można znaleźć jej wynik. Aby upewnić się, że wynik dla pozycji wynikającej z transformacji symetrycznej jest natychmiast dostępny, konieczne jest, aby transformacja odwzorowała wszystkie linie na tę samą grupę. W ten sposób liczba linii w każdej grupie pozostaje taka sama po transformacji.
Zanim program przypisze linie do grup, najpierw szuka linii, które są ze sobą powiązane poprzez transformację symetryczną. W grze 3×5 istnieje siedem zestawów po 4 linie i pięć zestawów po 2 linie. Następnie program przypisuje zestawy linii do grup. W przypadku gry 3×5 z 256 MB pamięci RAM, sześć grup (każda z dwoma zestawami linii) o rozmiarach 8 6 6 6 6 6.
Aby określić, czy pozycja powinna być transformowana symetrycznie, program sprawdza tylko linie z pierwszej grupy. Podczas fazy konfiguracji program przeszukuje wszystkie możliwe konfiguracje linii w pierwszej grupie linii. Do każdej konfiguracji stosuje odbicie pionowe, odbicie poziome i odbicie poprzez transformacje pochodzenia. Jeśli w wyniku jednej z tych transformacji liczba stanu przewodów w grupie jest numerycznie mniejsza niż liczba stanu przewodów oryginalnych, to (1) konfiguracja NIE jest uwzględniona na połączonej liście konfiguracji z zadana liczba wierszy jest zapisywana i (2) zapisywana jest informacja, która transformacja symetryczna jest potrzebna, aby uzyskać pozycję, której wynik został obliczony – czyli jak dostać się do odpowiedniej konfiguracji o najniższej wartości liczbowej dla stan jego linii.
Mimo że tylko pierwsza grupa jest używana do sprawdzenia, czy transformacja powinna zostać wykonana, po dokonaniu transformacji ma ona wpływ na linie we wszystkich grupach.
Oszczędzanie miejsca na dysku
Wyniki za pozycje z określoną liczbą wierszy w każdej grupie są przechowywane w jednym pliku dyskowym. Na przykład wyniki za pozycje 4/8 3/6 4/6 2/6 3/6 3/6 są przechowywane w pliku: \Boxes\3×5\19\4\3\4\2\3.bin
Odwrotne ukośniki oddzielają nazwy zagnieżdżonych folderów. 3×5 to nazwa analizowanej gry. 19 to całkowita liczba wierszy na pozycji. Pozostałe nazwy folderów i nazwa pliku pochodzą od liczby wierszy w grupach. Liczba wierszy w ostatniej grupie nie jest używana, ponieważ jest ustalana przez inne liczby. .Bin oznacza, że jest to plik binarny – jego zawartość nie może być bezpośrednio przeglądana. Używane są foldery zagnieżdżone, ponieważ system Windows bardzo wolno przetwarza foldery z dużą liczbą plików.
Transformacje symetryczne zmniejszają wymaganą przestrzeń dyskową z 256 GB do 85 GB. Jednak nie jest konieczne przechowywanie całości wyników analizy. Gdy tylko program został zakończony z pozycjami z 19 wierszami, wyniki dla pozycji z 20 wierszami można było usunąć. Mając tylko 16 GB wolnego miejsca na dysku, program zachowuje wyniki dla pozycji z 15 lub mniej wierszami. W rezultacie powstaje „książka otwierająca” dla gry 3×5.
Jednak przechowywanie tylko wyników dla 20 pozycji liniowych i 19 pozycji liniowych nadal zajmuje 22 GB. Rozwiązuje się to poprzez usunięcie części plików pozycji z 20 wierszami, ponieważ nie są one już potrzebne do dalszego obliczania wyników dla pozycji z 19 wierszami. Gdy program przejdzie przez wszystkie możliwe kombinacje zliczeń wierszy dla grup, które w sumie składają się na 19 wierszy, liczba dla pierwszej grupy wierszy nigdy się nie zmniejsza. Tak więc, gdy licznik dla pierwszej grupy linii wzrośnie, na przykład, od 0 do 1, wszystkie pliki zaczynające się od \Boxes\3×5\20\0\ mogą zostać usunięte. Dzięki tej zmianie analiza mieści się w dostępnych 16 GB.
Więzy
W tym momencie program był nadal niewystarczający do rozwiązania problemów 5×5 w rozdziale 12 z of The Dots-and-Boxes Game by Elwyn Berlekamp (A. K. Peters, 2000). Jeśli komputery nadal podwajają swoją pojemność co 18 miesięcy, powinniśmy być w stanie przeanalizować całą grę 5×5 w 2034 roku, ponieważ ma ona o 22 więcej linii niż gra 3×5, która była analizowana w 2001 roku. Program może teraz obsłużyć pozycje do 36 otwartych linii, w których pozycja nie ma symetrii i dostępne jest 14 GB miejsca na dysku. Oznaczało to, że można było zająć się tylko pozycjami 5×5 z 24 lub więcej liniami (z 60). Żaden z problemów z rozdziału 12 nie miał tylu wierszy.
Łańcuch to ciąg jednego lub więcej pól z wypełnionymi dwiema stronami. Założyłem, że gdy jeden z graczy wybierze linię w łańcuchu, co najmniej jedna z najlepszych linii gry obejmuje wszystkie pozostałe linie w łańcuch jest wypełniany przez jednego lub drugiego gracza, zanim zostaną wypełnione jakiekolwiek wiersze w innym miejscu. Każdy zestaw łańcuchów jest reprezentowany przez pojedynczą „pseudolinie”. Reprezentacja pozycji w programie ma tylko jeden bit mówiący, czy łańcuch został całkowicie wypełniony, czy też nadal jest całkowicie pusty. Na przykład, oto miejsce na zadanie 12.18 (przed przesunięciem linii przerywanej):
+ + + . + + +
| . |
| . |
| . |
+ + . + . + + +
| . | .
| . | ....
| . |
+ + . +-----+-----+-----+
| . |
| . | ..........
| . | .
+ + . + . +-----+ . +
| | .
| .... | ....
| . |
+ + + . + . +-----+
| .
| ....
|
+ + +-----+ + +
Kropki oznaczają łańcuchy, z których każdy jest reprezentowany przez pojedynczą pseudolinie. Z 60 wierszy 15 jest wypełnionych, 30 jest pustych, a 15 jest zaangażowanych w 6 łańcuchów. Pozycje, które mogą powstać z tej pozycji początkowej, są reprezentowane przez 36 bitów – 30 dla pustych linii i 6 dla 6 łańcuchów. W związku z tym ta pozycja ledwo mieści się w obecnych możliwościach programu.
W wielu pozycjach wynikających z danej pozycji początkowej łańcuchy początkowe staną się częścią dłuższych łańcuchów. Program nie zmienia schematu reprezentacji pozycji w tej sytuacji. Pseudolinie nadal reprezentują tylko początkowe łańcuchy. Dzieje się tak, ponieważ reprezentacja pozycji jest używana jako „adres” w celu uzyskania dostępu do wcześniej obliczonych wyników.
Oceniając, czy przejście do początkowego łańcucha jest dobrym pomysłem dla gracza będącego w ruchu, program udostępnia wynik netto z najlepszą grą dla przyszłych pól dla gracza będącego w ruchu po zapełnieniu całego początkowego łańcucha. Następnie program musi sprawdzić pola wokół łańcucha, aby zobaczyć, który gracz będzie miał pierwszą szansę na zabranie pudeł w łańcuchu, aby zobaczyć, czy ten gracz skorzystałby na poświęceniu się, aby uniknąć przeniesienia się po zapełnieniu łańcucha i sprawdzić, czy łańcuch nie został wydłużony, a nawet nie był częścią pętli.
Jeśli początkowy łańcuch ma 3-stronne pudełko po obu stronach, tuż za łańcuchem, wówczas gracz w ruchu może wejść do łańcucha poprzez bicie i ma możliwość zabrania pudeł w łańcuchu. W przeciwnym razie to drugi gracz ma opcję w łańcuchu. Do osoby, która ma możliwość zabrania pudeł w łańcuchu, zadzwonię do „łańcuszka”.
Jeśli początkowy łańcuch został wystarczająco wydłużony, aby gracz w łańcuchu mógł później poświęcić się, wtedy wynik po całkowitym zapełnieniu łańcucha już odzwierciedla tę opcję, a gracz łańcuchowy bierze wszystkie pudełka z początkowego łańcucha. W przeciwnym razie program sprawdza, czy jest wystarczająco dużo miejsca na poświęcenie, zakładając najlepszy ruch w łańcuchu gracza pierwotnie będącego w ruchu i patrząc na początkowy łańcuch i wszelkie rozszerzenia. Jeśli nadal nie ma miejsca na ofiarę, gracz łańcuchowy bierze wszystkie pudełka. W przeciwnym razie program sprawdza, czy ofiara jest opłacalna, a jeśli tak, ocenia przejście do łańcucha dla gracza, który był pierwotnie w ruchu, zakładając, że gracz łańcuchowy złoży ofiarę.
Kara za ostatni ruch
Program umożliwia nałożenie kary na wynik gracza wykonującego ostatni ruch. Jeśli ta kara jest wystarczająco duża, ruchy wybrane jako najlepsze będą takie same, jak te wybrane w analizie nimstring. Na przykład przeanalizowałem problem 11.16 z karami o coraz większej skali. Program nie zezwala na ułamkowe kary, ponieważ nie dostarczałyby żadnych dodatkowych informacji:
- Jeśli przeprowadzisz analizę przy dwóch różnych karach, wynik za ruch nie może się zmienić o więcej niż plus lub minus różnica w karach.
- W przypadku kolejnych kar za liczby całkowite jedna analiza daje wszystkie wyniki w postaci liczb parzystych całkowitych, a druga – wszystkie wyniki w postaci liczb całkowitych nieparzystych.
- Tak więc w przypadku kolejnych kar całkowitych wyniki zawsze zmieniają się o +1 lub -1… maksimum możliwe.
- W związku z tym można uzyskać wynik dowolnej kary ułamkowej, interpolując między wynikami sąsiednich kar całkowitych.
Głupie posunięcia
Ostateczna wersja programu zawiera analizę ruchów wariatów. Na wyjściu wynik jest dodawany przez v, jeśli gracz A musi wykonać następny ruch wariata, lub przez ^, jeśli gracz B musi. Jeśli żaden z graczy nie może wykonać szalonego ruchu, nie używa się przyrostka. Podczas analizy dwa bity bajtu używanego do przechowywania partytury są używane do podtrzymania szalonego stanu ruchu. To pozostawia tylko 6 bitów na wyniki. Zatem można przechowywać tylko wyniki od -32 do +31. To sprawia, że wersja programu do analizy ruchów zwariowanych jest niewiarygodna na planszach większych niż 5 na 6. Dlatego mam dostępną wersję, która nie wykonuje analizy ruchów wariatów do użytku z większymi płytkami.
Aby znaleźć ruchy wariatów w rozsądnym czasie komputera, program sprawdza premię zwariowaną, ilekroć jest to możliwe, aby złapać pudełko. Jeśli pole po drugiej stronie rozpatrywanej linii ma już wypełnione dokładnie dwie inne strony, program stwierdza, że poprzedni ruch przeciwnika był szalony.
Rogi
William Fraser napisał: „Czy bierzesz pod uwagę fakt, że [ab] i [ba] odnoszą się do równoważnych linków? Zatem (jeśli umieścisz osiem linków narożnych w ostatniej grupie 8 linii) możesz zapisać tylko 3^4=81 wpisy zamiast 2^8=256. Byłoby to całkowicie niezależne od obrotu/odbicia. Zmniejsza użycie dysku o 75%, a użycie pamięci średnio o 75%.”
Wdrożyłem tę sugestię, co umożliwiło analizę gry 4×4.