Jak wdrożyć sztuczną inteligencję w warcaby / warcaby?

Widziałem tę grę w warcaby i zastanawiałem się, jak zaimplementowano sztuczną inteligencję.

Jak powinienem wdrożyć AI dla warcabów (wersje robocze, dama, dama)? Czy są jakieś znane algorytmy?

Bardzo dziękuję wszystkim. Bardzo się cieszę, widząc ten post na blogu z samouczkami o grze Tic Tac Toe .

Tak, chcę kod dama algorytmu gry open source i post na blogu .. Czy jest jakiś pomocny link lub jakiś plik doc ..? proszę daj mi znać..

Och, uwielbiam te gry!

Po pierwsze, aby komputer mógł grać, potrzebuje:

1. struktura do pracy
2. zasady gry
3. 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: /

W dowolnym momencie gry liczba możliwych ruchów gracza jest dość niska * (około 5), co oznacza, że ​​można myśleć o kilku ruchach do przodu, oceniać każdy możliwy ruch i wybrać najlepszy ruch.

Takie podejście nazywa się minimax (wikipedia) .

Aby wdrożyć minimax, potrzebujesz funkcji oceny, która zwraca wynik dla danego układu planszy i odtwarzacza. W przypadku przeciągów naiwną implementacją byłaby funkcja, która zwraca jeden punkt za każdy kawałek, który gracz ma przy życiu.

Wizualizacja drzewa decyzyjnego minimax (z artykułu na Wikipedii). Po lewej stronie znajduje się numer zakrętu. Każdy węzeł liścia ma oceniany wynik, który jest przekazywany z powrotem do drzewa w celu podjęcia decyzji.

*jednak przeciągi to gra o najwyższym współczynniku rozgałęzienia, która została całkowicie rozwiązana .

Przycinanie alfa-beta jest algorytmem wyszukiwania, którego celem jest zmniejszenie liczby węzłów ocenianych przez algorytm minimax w drzewie wyszukiwania. Jest to przeciwny algorytm wyszukiwania używany powszechnie do automatycznej gry w gry dwuosobowe (Kółko i krzyżyk, Szachy, Go itd.). Przestaje on całkowicie oceniać ruch, gdy znaleziono co najmniej jedną możliwość, która dowodzi, że ruch jest gorszy niż wcześniej zbadany ruch. Takie ruchy nie wymagają dalszej oceny. Po zastosowaniu do standardowego drzewa minimax zwraca taki sam ruch, jak minimax, ale przycina gałęzie, które nie mogą wpłynąć na ostateczną decyzję.