Napisałem grę w kółko i krzyżyk w Javie i moją obecną metodę określania kont zakończenia gry dla następujących możliwych scenariuszy zakończenia gry:
- Plansza jest pełna i żaden zwycięzca nie został jeszcze wyłoniony: Gra kończy się remisem.
- Krzyż wygrał.
- Circle wygrał.
Niestety, aby to zrobić, czyta wstępnie zdefiniowany zestaw tych scenariuszy z tabeli. To niekoniecznie jest złe, biorąc pod uwagę, że na planszy jest tylko 9 miejsc, a zatem stół jest nieco mały, ale czy istnieje lepszy algorytmiczny sposób określania, czy gra się skończyła? Ustalenie, czy ktoś wygrał, czy nie, jest sednem problemu, ponieważ sprawdzenie, czy 9 miejsc jest pełnych, jest trywialne.
Metoda tabeli może być rozwiązaniem, ale jeśli nie, to co nim jest? A co by było, gdyby tablica nie miała odpowiedniego rozmiaru n=9
? Co gdyby był znacznie większy deska, powiedzmy n=16
, n=25
i tak dalej, powodując szereg kolejno wprowadzanych elementów do wygrania będzie x=4
, x=5
itp? Ogólny algorytm dla wszystkich n = { 9, 16, 25, 36 ... }
?
źródło
3
). Możesz więc śledzić liczbę każdego z nich i zacząć sprawdzać wygrane tylko wtedy, gdy są wyższe.Odpowiedzi:
Wiesz, że wygrywający ruch może nastąpić dopiero po tym, jak X lub O wykonał ostatni ruch, więc możesz przeszukiwać tylko wiersz / kolumnę z opcjonalną diagą zawartą w tym ruchu, aby ograniczyć przestrzeń poszukiwań podczas próby określenia zwycięskiej planszy. Ponieważ w grze w kółko i krzyżyk jest ustalona liczba ruchów, po wykonaniu ostatniego ruchu, jeśli nie był to ruch wygrywający, domyślnie jest to gra remisowa.
edytuj: ten kod dotyczy planszy n na n z n z rzędu, aby wygrać (3x3 wymagania na planszy 3 z rzędu itp.)
edycja: dodano kod do sprawdzania antydiag, nie mogłem wymyślić sposobu bez pętli, aby określić, czy punkt był na antydiag, dlatego brakuje tego kroku
źródło
możesz użyć magicznego kwadratu http://mathworld.wolfram.com/MagicSquare.html, jeśli którykolwiek wiersz, kolumna lub diag sumują się do 15, to gracz wygrał.
źródło
A co z tym pseudokodem:
Po tym jak gracz kładzie figurę na pozycji (x, y):
Użyłbym tablicy char [n, n], z O, X i spacją dla pustych.
źródło
i==1
in==3
,rdiag
musi być zaznaczone na(1, 3)
i(1, 3-1+1)
jest równe poprawnym współrzędnym, ale(1, 3-(1+1))
nie.Jest to podobne do odpowiedzi Osamy ALASSIRY , ale zamienia stałą przestrzeń i czas liniowy na przestrzeń liniową i czas stały. Oznacza to, że po inicjalizacji nie ma pętli.
Zainicjuj parę
(0,0)
dla każdego wiersza, każdej kolumny i dwóch przekątnych (przekątnych i przeciw przekątnych). Te pary przedstawiają zgromadzone(sum,sum)
elementy w odpowiednim rzędzie, kolumnie lub po przekątnej, gdzieKiedy gracz umieszcza pionek, zaktualizuj odpowiednią parę rzędów, parę kolumn i pary po przekątnych (jeśli są na przekątnych). Jeśli wszystkie nowo zaktualizowanego wiersza, kolumna lub ukośnie pary albo równa
(n,0)
lub(0,n)
następnie albo A i B wygranych, odpowiednio.Analiza asymptotyczna:
Do wykorzystania pamięci używasz
4*(n+1)
liczb całkowitych.Ćwiczenie: Czy widzisz, jak sprawdzić remis w czasie O (1) na ruch? Jeśli tak, możesz zakończyć grę wcześniej po remisie.
źródło
O(sqrt(n))
czas, ale trzeba to zrobić po każdym ruchu, gdzie n jest rozmiarem planszy. Więc kończysz zO(n^1.5)
. W przypadku tego rozwiązania maszO(n)
ogólny czas.Oto moje rozwiązanie, które napisałem dla projektu, nad którym pracuję, w javascript. Jeśli nie przeszkadza Ci koszt pamięci kilku tablic, jest to prawdopodobnie najszybsze i najprostsze rozwiązanie, jakie znajdziesz. Zakłada, że znasz pozycję ostatniego ruchu.
źródło
Właśnie napisałem to dla mojej klasy programowania w C.
Publikuję to, ponieważ żaden z innych przykładów tutaj nie będzie działał z żadną prostokątną siatką i każdą liczbą N w rzędzie kolejnych znaków, aby wygrać.
Znajdziesz mój algorytm, taki jaki jest, w
checkWinner()
funkcji. Nie używa magicznych liczb ani niczego wymyślnego do sprawdzenia zwycięzcy, po prostu używa czterech dla pętli - Kod jest dobrze skomentowany, więc myślę, że będę mówił sam za siebie.źródło
Jeśli plansza jest n × n, to jest n wierszy, n kolumn i 2 przekątne. Sprawdź każdy z nich dla wszystkich X lub all-O, aby znaleźć zwycięzcę.
Jeśli do wygrania potrzeba tylko x < n następujących po sobie kwadratów, to jest to trochę bardziej skomplikowane. Najbardziej oczywistym rozwiązaniem jest sprawdzenie, czy każdy kwadrat x × x jest zwycięzcą. Oto kod, który to potwierdza.
(I faktycznie nie przetestować ten * Kaszel *, ale nie kompilacji przy pierwszej próbie, yay mnie!)
źródło
Nie znam tak dobrze Javy, ale znam C, więc wypróbowałem pomysł magicznego kwadratu adk (wraz z ograniczeniami wyszukiwania Hardwareguy'a ).
Dobrze się kompiluje i testuje.
To było fajne, dzięki!
Właściwie, myśląc o tym, nie potrzebujesz magicznego kwadratu, wystarczy policzyć dla każdego wiersza / kolumny / przekątnej. Jest to trochę łatwiejsze niż uogólnienie magicznego kwadratu na macierze
n
×n
, ponieważ wystarczy policzyć don
.źródło
W jednym z wywiadów zadano mi to samo pytanie. Moje przemyślenia: Zainicjuj macierz wartością 0. Zachowaj 3 tablice 1) sum_row (rozmiar n) 2) sum_column (rozmiar n) 3) przekątna (rozmiar 2)
Dla każdego ruchu o (X) zmniejsz wartość pola o 1, a dla każdego ruchu o (0) zwiększaj ją o 1. W dowolnym momencie, jeśli wiersz / kolumna / przekątna, który został zmodyfikowany w bieżącym ruchu, ma sumę -3 lub + 3 oznacza, że ktoś wygrał grę. W przypadku remisu możemy zastosować powyższe podejście, aby zachować zmienną moveCount.
Myślisz, że czegoś mi brakuje?
Edycja: to samo można zastosować dla macierzy nxn. Suma powinna wynosić nawet +3 lub -3.
źródło
niepętlowy sposób określenia, czy punkt znajdował się na antydiag:
źródło
Spóźniłem się na przyjęcie, ale chciałem wskazać jedną korzyść, jaką znalazłem przy użyciu magicznego kwadratu , a mianowicie, że można go użyć do uzyskania odniesienia do kwadratu, który spowodowałby wygraną lub przegraną w następnej turze, zamiast po prostu używane do obliczania zakończenia gry.
Weź ten magiczny kwadrat:
Najpierw skonfiguruj
scores
tablicę, która jest zwiększana za każdym razem, gdy wykonywany jest ruch. Zobacz tę odpowiedź, aby uzyskać szczegółowe informacje. Teraz, jeśli nielegalnie zagramy X dwa razy z rzędu w [0,0] i [0,1], toscores
tablica wygląda tak:Tablica wygląda tak:
Następnie wszystko, co musimy zrobić, aby uzyskać odniesienie do pola, na którym wygrać / zablokować, to:
W rzeczywistości implementacja wymaga kilku dodatkowych sztuczek, takich jak obsługa numerowanych klawiszy (w JavaScript), ale wydało mi się to całkiem proste i podobała mi się rekreacyjna matematyka.
źródło
Dokonałem optymalizacji w wierszach, kole, przekątnych. O tym, czy musimy sprawdzić konkretną kolumnę lub przekątną, decyduje głównie w pierwszej zagnieżdżonej pętli. W ten sposób unikamy sprawdzania kolumn lub przekątnych, oszczędzając czas. Ma to duży wpływ, gdy rozmiar płytki jest większy, a znaczna liczba komórek nie jest wypełniona.
Oto kod java do tego.
źródło
Podoba mi się ten algorytm, ponieważ wykorzystuje on reprezentację planszy 1x9 vs 3x3.
źródło
Inna opcja: wygeneruj tabelę z kodem. Jeśli chodzi o symetrię, są tylko trzy sposoby na wygraną: rząd skrajny, rząd środkowy lub przekątna. Weź te trzy i obracaj nimi w każdy możliwy sposób:
Te symetrie mogą mieć więcej zastosowań w twoim kodzie do gry: jeśli dojdziesz do planszy, na której już widziałeś obróconą wersję, możesz po prostu wziąć wartość z pamięci podręcznej lub buforowany najlepszy ruch z tego (i cofnąć zwrot z powrotem). Zwykle jest to znacznie szybsze niż ocena poddrzewa gry.
(Przerzucanie w lewo i w prawo może pomóc w ten sam sposób; nie było to potrzebne, ponieważ zestaw obrotów zwycięskich wzorów jest lustrzano-symetryczny).
źródło
Oto rozwiązanie, które wymyśliłem, zapisuje symbole jako znaki i używa wartości int znaku, aby dowiedzieć się, czy wygrał X lub O (spójrz na kod sędziego)
Tutaj są również moje testy jednostkowe, aby sprawdzić, czy faktycznie działa
Pełne rozwiązanie: https://github.com/nashjain/tictactoe/tree/master/java
źródło
Co powiesz na następujące podejście do 9 slotów? Zadeklaruj 9 zmiennych całkowitych dla macierzy 3x3 (a1, a2 .... a9), gdzie a1, a2, a3 reprezentują wiersz-1, a a1, a4, a7 utworzą kolumnę-1 (masz pomysł). Użyj „1”, aby wskazać gracza-1, a „2”, aby wskazać gracza-2.
Istnieje 8 możliwych kombinacji wygranych: Win-1: a1 + a2 + a3 (odpowiedź może wynosić 3 lub 6 w zależności od tego, który gracz wygrał) Win-2: a4 + a5 + a6 Win-3: a7 + a8 + a9 Win-4 : a1 + a4 + a7 .... Win-7: a1 + a5 + a9 Win-8: a3 + a5 + a7
Teraz wiemy, że jeśli gracz jeden przekroczy a1, musimy ponownie oszacować sumę 3 zmiennych: Win-1, Win-4 i Win-7. Które z „wygranych”? zmienna osiągnie 3 lub 6 jako pierwsza wygrywa grę. Jeśli zmienna Win-1 osiągnie 6 jako pierwsza, wtedy Gracz-2 wygrywa.
Rozumiem, że tego rozwiązania nie da się łatwo skalować.
źródło
To naprawdę prosty sposób na sprawdzenie.
}
źródło
Jeśli masz na przykład pole granicy 5 * 5, zastosowałem następną metodę sprawdzenia:
Myślę, że jest to bardziej przejrzyste, ale prawdopodobnie nie jest to najbardziej optymalny sposób.
źródło
Oto moje rozwiązanie wykorzystujące dwuwymiarową tablicę:
źródło
Rozwiązanie ze stałym czasem, działa w O (8).
Zapisz stan płytki jako liczbę binarną. Najmniejszy bit (2 ^ 0) znajduje się w lewym górnym rzędzie planszy. Następnie idzie w prawo, a potem w dół.
TO ZNACZY
Każdy gracz ma swój własny numer binarny reprezentujący stan (ponieważ kółko i krzyżyk) ma 3 stany (X, O i puste), więc pojedyncza liczba binarna nie będzie działać, aby reprezentować stan planszy dla wielu graczy.
Na przykład tablica taka jak:
Zauważ, że bity gracza X są rozłączne od bitów gracza O, jest to oczywiste, ponieważ X nie może umieścić figury, w której O ma bierkę i odwrotnie.
Aby sprawdzić, czy gracz wygrał, musimy porównać wszystkie pozycje objęte przez tego gracza z pozycją, o której wiemy, że jest wygrana. W tym przypadku najłatwiejszym sposobem byłoby bramkowanie ORAZ pozycji gracza i zwycięskiej pozycji oraz sprawdzenie, czy te dwie pozycje są równe.
na przykład.
Uwaga:
X & W = W
więc X jest w stanie wygranej.Jest to rozwiązanie oparte na stałym czasie, zależy tylko od liczby zwycięskich pozycji, ponieważ zastosowanie bramki AND jest operacją o stałym czasie, a liczba zwycięskich pozycji jest skończona.
Upraszcza również zadanie wyliczenia wszystkich prawidłowych stanów tablicy, tylko ich wszystkich liczb reprezentowanych przez 9 bitów. Ale oczywiście potrzebujesz dodatkowego warunku, aby zagwarantować, że liczba jest prawidłowym stanem tablicy (np.
0b111111111
Jest prawidłową liczbą 9-bitową, ale nie jest to prawidłowy stan tablicy, ponieważ X właśnie wykonał wszystkie tury).Liczbę możliwych zwycięskich pozycji można wygenerować w locie, ale tutaj i tak są.
Aby wyliczyć wszystkie pozycje tablicy, możesz uruchomić następującą pętlę. Chociaż pozostawię ustalenie, czy liczba jest prawidłowym stanem tablicy do kogoś innego.
UWAGA: (2 ** 9 - 1) = (2 ** 8) + (2 ** 7) + (2 ** 6) + ... (2 ** 1) + (2 ** 0)
źródło
Nie jestem pewien, czy to podejście zostało jeszcze opublikowane. Powinno to zadziałać dla każdej planszy m * n, a gracz powinien zajmować kolejne pozycje „ zwycięzcaPos ”. Pomysł opiera się na uruchomionym oknie.
źródło
Opracowałem kiedyś algorytm do tego w ramach projektu naukowego.
Zasadniczo rekurencyjnie dzielisz planszę na kilka nakładających się prostokątów 2x2, testując różne możliwe kombinacje wygranej na kwadracie 2x2.
Jest powolny, ale ma tę zaletę, że działa na płytach o dowolnej wielkości, z dość liniowymi wymaganiami dotyczącymi pamięci.
Żałuję, że nie mogę znaleźć mojej realizacji
źródło