Och, uwielbiam te gry!
Po pierwsze, aby komputer mógł grać, potrzebuje:
- struktura do pracy
- zasady gry
- warunek wygranej do pracy
Zajmijmy się tym jednym kawałkiem na raz.
Struktura
Ponieważ plansza jest siatką 8x8 (ale można ją łatwo skalować), a każda przestrzeń siatki może istnieć tylko w jednym z pięciu stanów, zdefiniujmy te stany:
[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]
Odpowiednio ENUM chciał:
[0, 1, 2, 3, 4]
Teraz, gdy wiemy, czym może być każde pole, potrzebujemy jakiegoś sposobu na przedstawienie wszystkich pól lub tablicy, jeśli wolisz. Prawie każdy silny język będzie obsługiwał tablicę wielowymiarową (tablicę, w której każdy element jest tablicą przechowującą dane). Więc weź następujący kod slack do zdefiniowania naszej tablicy:
BOARD_ARRAY = array(8, 8)
To da nam tablicę 8 x 8, w której możemy przechowywać liczby całkowite (nasze wyliczenia wcześniej):
(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)
Teraz możesz już zobaczyć, jak to zaczyna wyglądać jak deska! Nigdy nie grałem w wariant wspomniany w filmie na youtube, ale wydaje się, że zaczyna się od 2 rzędów białych kawałków jeden rząd od dołu i 2 rzędów czarnych kawałków jeden rząd od góry. Co oznaczałoby, że kiedy zaczynamy grę, nasza tablica powinna wyglądać następująco:
(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)
(Pamiętaj, że 2 oznacza „BLACK_PIECE”, a 1 oznacza „WHITE_PIECE”)
Więc teraz komputer ma strukturę do pracy. Krok 1 ukończony!
Zasady
Wyobraźmy sobie, że masz przed sobą prawdziwą planszę, grając przeciwko mistrzowi. Gdybyś próbował przenieść jeden z jego elementów, uderzyłbyś się w rękę. Gdybyś spróbował poruszyć kawałek w sposób, który nie byłby możliwy, uderzyłbyś rękę. Jeśli próbowałeś oszukiwać dobrze ... masz pomysł. Problem w tym, że komputery nie. Naszym zadaniem jest zapewnienie ścisłych zasad gry.
Musimy stworzyć sposób na sprawdzenie, czy dany ruch jest „legalny”. Co oznacza, że najpierw potrzebujemy jakiegoś sposobu na przedstawienie „ruchu”. Jednym ze sposobów byłoby użycie pozycji tablicy; Na przykład, aby przenieść element z [0, 0] na [0, 1], możemy stworzyć funkcję, która zaktualizuje planszę po tym ruchu. Wróćmy do luzu:
MY_MOVE = array( [0, 0], [0, 1] )
Powyższe przedstawia jeden element, przesuwający się o jedno pole w dół od górnego rogu planszy (zakładając 0, 0 to lewy górny róg). Możesz także zauważyć, że zdecydowałem się na użycie wielowymiarowej tablicy do przenoszenia. Wynika to z tego, że pionki teoretycznie mogą poruszać się wiele razy w jednej turze (do „skakania” innych kawałków). Udawajmy, że na 0, 1 był kawałek przeciwnika, co oznacza, że wylądowalibyśmy na 0, 2:
MY_MOVE = array( [0, 0], [0, 2] )
Całkiem proste eh. Program powinien zrozumieć, że jeśli pomijamy miejsce, przeskakujemy o kolejny kawałek (w przeciwnym razie jest to nielegalny ruch i powinien wyrzucić błąd). Teraz przeskoczmy dwa kawałki:
MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )
To pozwala nam opisać każdy ruch na planszy. Tak! Teraz, ponieważ nie do końca rozumiem zasady gry, o której mowa (chociaż grałem kiedyś w kanadyjskie warcaby), dokładna legalność ruchów będzie musiała zostać przez Ciebie określona. Dobry przepływ do tego momentu wyglądałby następująco:
FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn
Powyższe zakłada, że możesz przewijać każdy kawałek, aby znaleźć wszystkie legalne ruchy, a następnie biorąc pod uwagę zbiór wszystkich legalnych ruchów, wybierz jakoś najlepszy (strategia tutaj). Ruch zostaje następnie zastosowany na planszy lub zgłasza błąd. Następnie następny gracz wykonuje swoją turę. Mamy więc AI, która umie grać! Radość! Iść dalej.
Zwycięski
Proste gry są wspaniałe, ponieważ wygraną określa bardzo prosty stan. Czy na planszy nie ma białych elementów? Myślę, że wygrałeś! Jest to realizowane w kroku 2, gdy wybieramy najlepszy ruch, aby zbliżyć nas do warunków wygranej.
Aby stworzyć bardzo inteligentną sztuczną inteligencję, możesz przechowywać bazę danych, która przechowuje każdą możliwą tablicę jako stan, z każdym możliwym ruchem z każdego możliwego stanu, aby znaleźć łańcuchy do zwycięstwa.
Możesz także tworzyć strategie, takie jak: jeśli istnieje element, który BĘDZIE skoczył, zapisz ten element lub jeśli element jest w stanie skoczyć więcej niż jeden inny element, wykonaj ten skok.
To powinno dać ci dobry punkt wyjścia, to tylko jedna metoda dosłownie nieograniczonych możliwości. Możesz teoretycznie zbudować gigantycznego robota do rysowania kredkami, a następnie przeprowadzić analizę spektralną na rysunku, aby wybrać ruchy ... ale nie działałoby to zbyt dobrze ani szybko. Ten sposób działał w przeszłości i działał dobrze (: Mam nadzieję, że to pomaga!
Kilka słów o implementacji
Warcaby to tak zwana „rozwiązana” gra, w której możemy obliczyć każdy ruch bez żadnych niewiadomych. Ale to cała masa ruchów! Więc nie ma sposobu, aby zrobić to wszystko ręcznie ... gdyby tylko było ... och, prawda, jesteśmy programistami. pompa pięści
SQL jest wspaniałym narzędziem do przechowywania tych pozornie niekończących się ruchów. Dla osób bez doświadczenia w SQL, mySQL jest darmowym (dość łatwym w użyciu) i otwartym serwerem SQL. SQL jest używany do zarządzania bazami danych, podobnie jak arkusz kalkulacyjny na sterydach. Jest również w stanie przechowywać bardzo duże ilości danych i pracować z nimi bardzo szybko.
Jak więc możemy tego użyć? Ponieważ wiemy, że jeśli plansza jest w dokładnym stanie (każdy element w określonej pozycji), możemy obliczyć wszystkie dostępne ruchy i je zapisać. Na przykład:
+Board State+ +All Possible Moves+ +Best Move+
([0,0,1,2,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([7,6],[7,7])
([0,0,2,2,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([5,5],[5,4])
([0,0,1,3,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([4,4],[4,3])
etc...
Więc kiedy komputer musi wykonać ruch, po prostu sprawdza stan płyty (przechowywany jako klucz podstawowy) w bazie danych i może albo wybrać najlepszy ruch (powinien być nie do pobicia), albo jeden z pozostałych ruchów, aby uczynić bardziej przyjaznym AI.
Świetnie teraz zbudujmy tę bazę danych. Najpierw musimy obliczyć każdy stan tablicy. Można to zrobić za pomocą dużej, paskudnej pętli, jeśli ktoś chce spędzić trochę czasu i wypracować to, co byłoby niesamowite. Spójrz na tablicę jako jedną dużą liczbę, a następnie policz w górę, z wyjątkiem bazy 5 (0, 1, 2, 3, 4) i pod warunkiem, że każdy gracz może mieć tylko 16 sztuk.
W tym momencie powinniśmy przechowywać każdy stan planszy i możemy przejść przez obliczanie wszystkich możliwych ruchów.
Po obliczeniu wszystkich możliwych ruchów przychodzi czas na znalezienie najlepszych możliwych ruchów. W tym momencie moja wiedza zaczyna brakować, a takie rzeczy jak Minimax lub A * zaczynają się pojawiać. Przykro mi, ale nie mogę w tym pomóc: /
