Wyzwanie polega na napisaniu solvera do klasycznej ołówkowej i papierowej gry Dots and Boxes . Twój kod powinien przyjmować dwie liczby całkowite m
i n
jako dane wejściowe określające rozmiar tablicy.
Zaczynając od pustej siatki kropek, gracze na zmianę dodają pojedynczą poziomą lub pionową linię między dwoma niepołączonymi sąsiednimi kropkami. Gracz, który ukończy czwartą stronę pola 1 × 1, zdobywa jeden punkt i wykonuje kolejną turę. (Punkty są zazwyczaj rejestrowane poprzez umieszczenie w polu identyfikatora gracza, takiego jak inicjał). Gra kończy się, gdy nie można już umieścić więcej linii. Zwycięzcą gry jest gracz z największą liczbą punktów.
Możesz założyć, że albo n = m
albo n = m - 1
i m
wynosi co najmniej 2.
Wyzwanie polega na solve
jak największej grze w kropki i pudełka w niecałą minutę. Rozmiar gry jest po prostu n*m
. Wyjście kodzie powinno być win
, draw
lublose
co powinno być wynikiem dla pierwszego gracza zakładając obaj gracze grać optymalnie.
Twój kod musi być kompilowalny / uruchamialny na Ubuntu przy użyciu łatwo instalowalnych i bezpłatnych narzędzi. Podaj swój wynik jako największy obszar, jaki możesz rozwiązać na komputerze w ciągu 1 minuty wraz z czasem. Następnie przetestuję kod na moim komputerze i utworzę uporządkowaną tabelę wpisów.
W przypadku remisu zwycięzca będzie najszybszym kodem na planszy największego rozmiaru, który może rozwiązać w niecałą minutę.
Byłoby lepiej, gdyby kod generował nie tylko wygraną lub przegraną, ale także faktyczny wynik. To powoduje sprawdzenie poprawności poprawności poczytalności.
Odpowiedzi:
C99 - tablica 3x3 w 0,084s
Edycja: Zmodyfikowałem kod i przeprowadziłem głębszą analizę wyników.
Dalsze zmiany: Dodano przycinanie przez symetrie. To sprawia, że 4 konfiguracje algorytmów: z lub bez symetrii X z przycinaniem alfa-beta lub bez
Najdalsze edycje : Dodano zapamiętywanie za pomocą tabeli skrótów, w końcu osiągnięcie niemożliwego: rozwiązanie planszy 3x3!
Główne cechy:
#define HASHTABLE_BITWIDTH
). Gdy ten rozmiar jest większy lub równy liczbie ścian, gwarantuje to brak kolizji i aktualizacji O (1). Mniejsze tablice skrótów będą miały więcej kolizji i będą nieco wolniejsze.-DDEBUG
wydrukamiPotencjalne ulepszenia:
naprawić mały wyciek pamięcinaprawiony podczas pierwszej edycjiprzycinanie alfa / betadodano w 2. edycjiprzycinamy symetriedodane w 3. edycji (zauważ, że symetrie nie są obsługiwane przez zapamiętywanie, więc pozostaje to osobną optymalizacją).zapamiętywaniedodane w 4. edycjiKod
Z powodu braku organizacji liczba plików wymknęła się spod kontroli. Cały kod został przeniesiony do tego repozytorium Github . W edycji notatki dodałem plik makefile i skrypt testowy.
Wyniki
Uwagi na temat złożoności
Podejścia brutalnych sił do kropek i pudełek bardzo szybko się komplikują .
Rozważ tablicę z
R
rzędami iC
kolumnami. IstniejąR*C
kwadraty,R*(C+1)
ściany pionowe iC*(R+1)
ściany poziome. To w sumieW = 2*R*C + R + C
.Ponieważ Lembik poprosił nas o rozwiązanie gry z minimaxem, musimy przejść do liści drzewa gry. Na razie zignorujmy przycinanie, ponieważ liczy się rząd wielkości.
Istnieją
W
opcje pierwszego ruchu. Dla każdego z nich następny gracz może zagrać w dowolną zW-1
pozostałych ścian itp. To daje nam pole przeszukiwaniaSS = W * (W-1) * (W-2) * ... * 1
, lubSS = W!
. Czynniki są ogromne, ale to dopiero początek.SS
to liczba węzłów liści w przestrzeni wyszukiwania. Bardziej istotna dla naszej analizy jest całkowita liczba decyzji, które musiały zostać podjęte (tj. Liczba gałęziB
drzewa). Pierwsza warstwa gałęzi maW
opcje. Dla każdego z nich następny poziom maW-1
itp.Spójrzmy na kilka małych rozmiarów stołu:
Te liczby stają się śmieszne. Przynajmniej wyjaśniają, dlaczego kod brutalnej siły wydaje się zawieszać na zawsze na płycie 2x3. Przestrzeń wyszukiwania na tablicy 2x3 jest 742560 razy większa niż 2x2 . Jeśli wykonanie 2x2 zajmuje 20 sekund, zachowawcza ekstrapolacja przewiduje ponad 100 dni czasu wykonania dla 2x3. Oczywiście musimy przycinać.
Analiza przycinania
Zacząłem od dodania bardzo prostego przycinania przy użyciu algorytmu alfa-beta. Zasadniczo przestaje szukać, czy idealny przeciwnik nigdy nie dałby mu obecnych możliwości. „Hej, spójrz - dużo wygrywam, jeśli mój przeciwnik pozwala mi zdobyć każdy kwadrat!”, Pomyślał, że nie ma AI.
edytuj Dodałem również przycinanie oparte na symetrycznych tablicach.
Nie używam metody zapamiętywania, na wszelki wypadek, gdy pewnego dnia dodam zapamiętywanie i chcę oddzielić tę analizę od siebie. Zamiasttego działa to tak: większość linii ma „parę symetryczną” gdzieś na siatce. Istnieje do 7 symetrii (pozioma, pionowa, obrót o 180 stopni, obrót o 90 stopni, obrót o 270 stopni, przekątna i druga przekątna). Wszystkie 7 dotyczą desek kwadratowych, ale ostatnie 4 nie dotyczą desek kwadratowych. Każda ściana ma wskaźnik do „pary” dla każdej z tych symetrii. Jeśli wchodząc w zakręt, plansza jest symetryczna poziomo, wówczas należy zagrać tylko jedną z każdej pary poziomej .edytuj edytuj Zapamiętywanie! Każda ściana ma unikalny identyfikator, który wygodnie ustawiam jako bit wskaźnikowy; n-ta ściana ma identyfikator
1 << n
. Skrót tablicy jest więc tylko salą wszystkich granych ścian. Jest to aktualizowane w każdym oddziale w czasie O (1). Rozmiar tablicy hashtable jest ustawiony na#define
. Wszystkie testy zostały przeprowadzone z rozmiarem 2 ^ 12, ponieważ dlaczego nie? Gdy jest więcej ścian niż bitów indeksujących tablicę mieszającą (w tym przypadku 12 bitów), najmniej znaczące 12 jest maskowane i używane jako indeks. Kolizje są obsługiwane za pomocą połączonej listy w każdym indeksie tablicy mieszającej. Poniższa tabela to moja szybka i brudna analiza wpływu wielkości tabeli mieszającej na wydajność. Na komputerze z nieskończoną pamięcią RAM zawsze ustawialiśmy rozmiar stołu na liczbę ścian. Tablica 3x4 miałaby tablicę mieszającą o długości 2 ^ 31. Niestety nie mamy tego luksusu.Ok, wracając do przycinania. Zatrzymując wyszukiwanie wysoko w drzewie, możemy zaoszczędzić dużo czasu, nie schodząc do liści. „Czynnik przycinania” to ułamek wszystkich możliwych gałęzi, które musieliśmy odwiedzić. Brute-force ma współczynnik przycinania równy 1. Im jest mniejszy, tym lepiej.
źródło
rows columns
określające rozmiar planszyPython - 2x2 w 29s
Publikowanie postów z puzzli . Niezbyt zoptymalizowany, ale może stanowić przydatny punkt wyjścia dla innych uczestników.
źródło
JavaScript - płyta 1x2 w 20ms
Demo online dostępne tutaj (ostrzeżenie - bardzo wolne, jeśli większe niż 1x2 z pełną głębokością wyszukiwania ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html
Został opracowany dla oryginalnych kryteriów wygranych (kod golfa), a nie dla prędkości.
Testowane w Google Chrome v35 na Windows 7.
źródło