Sztuczna inteligencja gier planszowych: algorytm Minimax: 8 kroków

2024 Autor: John Day | [email protected]. Ostatnio zmodyfikowany: 2024-01-30 11:29

Czy kiedykolwiek zastanawiałeś się, jak zbudowane są komputery, z którymi grasz w szachy lub warcaby? Nie szukaj dalej niż ten Instruktaż, ponieważ pokaże Ci, jak stworzyć prostą, ale skuteczną sztuczną inteligencję (AI) za pomocą algorytmu Minimax! Korzystając z algorytmu Minimax, sztuczna inteligencja wykonuje dobrze zaplanowane i przemyślane ruchy (lub przynajmniej naśladuje proces myślowy). Teraz mógłbym po prostu podać kod sztucznej inteligencji, którą stworzyłem, ale to nie byłoby zabawne. Wyjaśnię logikę wyborów dokonywanych przez komputer.

W tym Instruktażowym przeprowadzę Cię przez kroki, jak stworzyć sztuczną inteligencję dla Othello (AKA Reversi) w Pythonie. Powinieneś mieć pośrednie zrozumienie, jak kodować w Pythonie, zanim zajmiesz się tym projektem. Oto kilka dobrych stron internetowych, na które warto spojrzeć, aby przygotować Cię do tego Instructable: w3schools lub learnpython. Pod koniec tej instrukcji powinieneś mieć sztuczną inteligencję, która wykona obliczone ruchy i powinna być w stanie pokonać większość ludzi.

Ponieważ ten Instructable będzie przede wszystkim zajmował się tworzeniem sztucznej inteligencji, nie będę wyjaśniał, jak zaprojektować grę w Pythonie. Zamiast tego podam kod do gry, w której człowiek może grać przeciwko drugiemu człowiekowi i zmodyfikować go tak, abyś mógł grać w grę, w której człowiek gra przeciwko sztucznej inteligencji.

Nauczyłem się tworzyć tę sztuczną inteligencję podczas letniego programu w Columbia SHAPE. Dobrze się tam bawiłem, więc zajrzyj na ich stronę internetową, aby zobaczyć, czy byłbyś zainteresowany.

Teraz, gdy usunęliśmy już logistykę, zacznijmy kodować!

(Na zdjęciach umieściłem kilka notatek, więc koniecznie na nie spójrz)

Kieszonkowe dzieci

To jest łatwe:

1) Komputer ze środowiskiem Pythona, takim jak Spyder lub IDLE

2) Pobierz pliki do gry Othello z mojego GitHub

3) Twój mózg z zainstalowaną cierpliwością

Krok 1: Pobierz niezbędne pliki

Kiedy wejdziesz na mój GitHub, powinieneś zobaczyć 5 plików. Pobierz wszystkie 5 i umieść je wszystkie w tym samym folderze. Zanim uruchomimy grę, otwórz wszystkie pliki w środowisku spyder.

Oto, co robią pliki:

1) othello_gui.py ten plik tworzy planszę do gry, na której gracze mogą grać (czy to człowiek, czy komputer)

2) othello_game.py ten plik gra dwa komputery przeciwko sobie bez planszy i pokazuje tylko wynik i pozycje ruchów

3) ai_template.py to miejsce, w którym umieścisz cały swój kod, aby stworzyć swoją sztuczną inteligencję

4) randy_ai.py to predefiniowana sztuczna inteligencja, która losowo wybiera ruchy

5) othello_shared.py zestaw gotowych funkcji, których możesz użyć do stworzenia sztucznej inteligencji, takich jak sprawdzenie dostępnych ruchów, wyniku lub stanu planszy

6) Trzy inne pliki: Puma.py, erika_5.py i nathan.py, stworzone przeze mnie, Erikę i Nathana odpowiednio z programu SHAPE, to trzy różne AI z unikalnymi kodami

Krok 2: Jak otworzyć i grać w Pythona Othello

Po otwarciu wszystkich plików w prawym dolnym rogu ekranu wpisz „run othello_gui.py” i naciśnij enter w konsoli IPython. Lub w terminalu Mac wpisz „python othello_gui.py” (oczywiście po tym, jak znajdziesz się we właściwym folderze). Następnie na ekranie powinna pojawić się tablica. Ten tryb to tryb człowiek kontra człowiek. Światło przechodzi jako drugie, a ciemność jako pierwsze. Spójrz na mój film, jeśli jesteś zdezorientowany. iNa górze znajduje się wynik każdego kolorowego kafelka. Aby zagrać, kliknij odpowiednie pole ruchu, aby umieścić tam płytkę, a następnie daj komputer przeciwnikowi, który zrobi to samo i powtórzy.

Jeśli nie wiesz, jak grać w Othello, przeczytaj poniższe zasady na stronie ultra boardów:

Czarne zawsze poruszają się jako pierwsze. Ruch jest wykonywany poprzez umieszczenie krążka w kolorze gracza na planszy w pozycji, która „oskrzydla” jeden lub więcej krążków przeciwnika. Krążek lub rząd krążków jest oskrzydlany, gdy jest otoczony na końcach krążkami o przeciwnym kolorze. Dysk może oskrzydlać dowolną liczbę dysków w jednym lub kilku rzędach w dowolnym kierunku (poziomym, pionowym, ukośnym)…. (dokończ czytanie na ich stronie internetowej)

Różnica między oryginalną grą a tą grą w Pythona polega na tym, że gdy nie ma żadnych ważnych ruchów dla jednego gracza, gra się kończy

Teraz, gdy możesz grać w tę grę ze znajomym, stwórzmy sztuczną inteligencję, z którą możesz grać.

Krok 3: Algorytm Minimax: Generowanie scenariuszy

Zanim porozmawiamy o tym, jak napisać to w kodzie, przyjrzyjmy się logice, która za tym stoi. Algorytm minimax jest algorytmem podejmowania decyzji, śledzenia wstecznego i jest zwykle używany w grach turowych dla dwóch graczy. Celem tej sztucznej inteligencji jest znalezienie następnego najlepszego ruchu i kolejnych najlepszych ruchów, dopóki nie wygra gry.

Jak algorytm określi, który ruch jest najlepszy? Zatrzymaj się i pomyśl, jak wybrałbyś następny ruch. Większość ludzi wybrałaby ruch, który dałby im najwięcej punktów, prawda? Albo gdyby myśleli z wyprzedzeniem, wybraliby ruch, który stworzyłby sytuację, w której mogliby zdobyć jeszcze więcej punktów. Ten ostatni sposób myślenia to sposób, w jaki myśli Algorytm Minimax. Wybiega w przyszłość na wszystkie przyszłe konfiguracje plansz i wykonuje ruch, który prowadzi do uzyskania największej liczby punktów.

Nazwałem to algorytmem wycofywania, ponieważ zaczyna się od utworzenia i oceny wszystkich przyszłych stanów tablicy wraz z powiązanymi z nimi wartościami. Oznacza to, że algorytm będzie grał w grę tyle, ile potrzebuje (wykonując ruchy dla siebie i przeciwnika), aż każdy scenariusz gry zostanie rozegrany. Aby śledzić wszystkie stany planszy (scenariusze), możemy narysować drzewo (patrz na zdjęcia). Drzewo na powyższym obrazku jest prostym przykładem gry w Connect 4. Każda konfiguracja planszy nazywana jest stanem planszy, a jej miejsce na drzewie nazywa się węzłem. Wszystkie węzły na dole drzewa są końcowymi stanami planszy po wykonaniu wszystkich ruchów. Oczywiście niektóre stany planszy są lepsze dla jednego gracza niż dla drugiego. Więc teraz musimy sprawić, by sztuczna inteligencja wybrała stan planszy, do którego chce się dostać.

Krok 4: Minimax: ocena konfiguracji płytek

Aby nadać wartości stanom planszy, musimy nauczyć się strategii gry, w którą gramy: w tym przypadku strategii Otella. Ponieważ ta gra to bitwa polegająca na odwracaniu dysków przeciwnika i twoich, najlepsze pozycje dysków to te, które są stabilne i nie można ich odwrócić. Na przykład róg to miejsce, w którym po umieszczeniu dysku nie można go zmienić na inny kolor. Tak więc to miejsce byłoby niezwykle cenne. Inne dobre pozycje to boki planszy, co pozwoliłoby na zabranie dużej ilości kamieni. Na tej stronie jest więcej strategii.

Teraz możemy przypisać wartości do pozycji dla każdej tablicy stanu tablicy. Kiedy pozycja jest zajęta przez pion AI, dajesz określoną liczbę punktów w zależności od pozycji. Na przykład stan planszy, w którym pion AI znajduje się w rogu, możesz dać bonus 50 punktów, ale jeśli był w niekorzystnym miejscu, pion może mieć wartość 0. Po uwzględnieniu wszystkich wartości pozycje, przypisujesz stanowi tablicy wartość. Na przykład, jeśli AI ma kawałek w rogu, stan planszy może mieć wynik 50, podczas gdy inny stan planszy z kawałkiem AI w środku ma wynik 10.

Można to zrobić na wiele sposobów, a ja mam trzy różne heurystyki do oceny kawałków planszy. Zachęcam do stworzenia własnego rodzaju heurystyki. Wrzuciłem na mój github trzy różne AI autorstwa trzech różnych twórców, z trzema różnymi heurystykami: Puma.py, erika5.py, nathanh.py.

Krok 5: Algorytm Minimax: wybór najlepszego ruchu

Teraz byłoby miło, gdyby sztuczna inteligencja mogła po prostu wybrać wszystkie ruchy, aby dostać się do stanu planszy z najwyższym wynikiem. Pamiętaj jednak, że sztuczna inteligencja również wybierała ruchy dla przeciwnika, gdy generowała wszystkie stany planszy, a jeśli przeciwnik jest sprytny, nie pozwoli AI uzyskać najwyższego wyniku na planszy. Zamiast tego sprytny przeciwnik wykonałby ruch, aby sztuczna inteligencja przeszła do najniższego stanu planszy. W algorytmie nazywamy dwóch graczy graczem maksymalizującym i graczem minimalizującym. Sztuczna inteligencja byłaby graczem maksymalizującym, ponieważ chce zdobyć jak najwięcej punktów dla siebie. Przeciwnik byłby graczem minimalizującym, ponieważ przeciwnik próbuje wykonać ruch, w którym sztuczna inteligencja zdobywa najmniej punktów.

Po wygenerowaniu wszystkich stanów tablicy i przypisaniu wartości do tablic algorytm rozpoczyna porównywanie stanów tablicy. Na zdjęciach stworzyłem drzewo, które ma reprezentować, w jaki sposób algorytm wybierałby swoje ruchy. Każdy podział w gałęziach to inny ruch, który może zagrać sztuczna inteligencja lub przeciwnik. Po lewej stronie rzędów węzłów napisałem, czy idzie gracz maksymalizujący czy minimalizujący. Dolny rząd to wszystkie stany planszy wraz z ich wartościami. Wewnątrz każdego z tych węzłów znajduje się liczba i są to wyniki, które przypisujemy każdej z plansz: im są wyższe, tym lepiej dla AI.

Definicje: węzeł nadrzędny - węzeł, który wynikuje lub tworzy węzły pod nim; pochodzenie węzłów potomnych - węzły pochodzące z tego samego węzła nadrzędnego

Puste węzły reprezentują ruch, który wykona sztuczna inteligencja, aby uzyskać najlepszy stan planszy. Zaczyna się od porównania dzieci skrajnego lewego węzła: 10, -3, 5. Ponieważ maksymalizujący wykonałby ruch, wybrałby ruch, który da mu najwięcej punktów: 10. Więc wybieramy i zapisujemy to przesuń się z wynikiem tablicy i zapisz go w węźle nadrzędnym. Teraz, gdy 10 znajduje się w węźle nadrzędnym, teraz kolej na graczy minimalizujących. Jednak węzeł, z którym porównalibyśmy 10, jest pusty, więc musimy najpierw ocenić ten węzeł, zanim gracz minimalizujący będzie mógł wybrać. Wracamy więc do tury gracza maksymalizującego i porównujemy dzieci sąsiedniego węzła: 8, -2. Maksymalizacja wybierze 8 i zapiszemy to w pustym węźle nadrzędnym. Teraz, gdy algorytm zakończył wypełnianie pustych miejsc dla dzieci węzła powyżej, gracz minimalizujący może porównać te dzieci - 10 i 8 i wybrać 8. Algorytm następnie powtarza ten proces, aż całe drzewo zostanie wypełnione. Na końcu tego przykładu mamy wynik 8. Jest to najwyższy stan planszy, jaki może zagrać sztuczna inteligencja, zakładając, że przeciwnik gra optymalnie. Tak więc AI wybierze pierwszy ruch, który prowadzi do stanu planszy 8, a jeśli przeciwnik gra optymalnie, AI powinna zagrać wszystkie ruchy, aby dostać się do stanu planszy 8. (Postępuj zgodnie z uwagami na moich zdjęciach)

Wiem, że to dużo. Jeśli należysz do tych osób, które muszą z tobą porozmawiać, aby coś zrozumieć, oto kilka filmów, które obejrzałem, aby pomóc mi zrozumieć kryjącą się za tym ideę: 1, 2, 3.

Krok 6: Algorytm Minimax: pseudokod

Gdy zrozumiesz logikę algorytmu minimax, spójrz na ten pseudokod (funkcje, które są uniwersalne dla wszystkich kodów) z Wikipedii:

funkcja minimax(węzeł, głębokość, maximizingPlayer) is

jeśli głębokość = 0 lub węzeł jest węzłem końcowym, to

zwróć wartość heurystyczną węzła

jeśli maksymalizujesz Playera, to

wartość:= −∞

dla każdego dziecka węzła do

wartość:= max(wartość, minimax(dziecko, głębokość − 1, FAŁSZ))

wartość zwrotu

inny (* minimalizacja odtwarzacza *)

wartość:= +∞

dla każdego dziecka węzła do

wartość:= min(wartość, minimax(dziecko, głębokość − 1, PRAWDA))

wartość zwrotu

Jest to funkcja rekurencyjna, co oznacza, że wywołuje się w kółko, aż do osiągnięcia punktu zatrzymania. Po pierwsze, funkcja przyjmuje trzy wartości, węzeł, głębokość i czyją jest kolej. Wartość węzła to miejsce, w którym program ma rozpocząć wyszukiwanie. Głębokość określa, jak daleko program ma przeszukiwać. Na przykład w moim przykładzie z drzewem ma głębokość 3, ponieważ przeszukał wszystkie stany planszy po 3 ruchach. Oczywiście chcielibyśmy, aby sztuczna inteligencja sprawdziła każdy stan planszy i wybrała zwycięską wygraną, ale w większości gier, w których są tysiące, jeśli nie miliony konfiguracji plansz, twój laptop w domu nie będzie w stanie przetworzyć wszystkich tych konfiguracji. Ograniczamy więc głębokość wyszukiwania AI i każemy jej przejść do najlepszego stanu tablicy.

Ten pseudokod odtwarza proces, który wyjaśniłem w poprzednich dwóch krokach. Przejdźmy teraz o krok dalej i poprawmy to w kodzie Pythona.

Krok 7: Tworzenie sztucznej inteligencji za pomocą Ai_template.py

Zanim rzucisz okiem na mój kod Minimax AI, spróbuj stworzyć własną sztuczną inteligencję za pomocą pliku ai_template.py i pseudokodu, o którym mówiliśmy w ostatnim kroku. W szablonie ai znajdują się dwie funkcje: def minimax_min_node(tablica, kolor) i def minimax_max_node(tablica, kolor). Zamiast rekursywnego wywoływania funkcji minimax, mamy dwie różne funkcje, które wywołują się nawzajem. Aby stworzyć heurystykę do oceny stanów tablicy, będziesz musiał stworzyć własną funkcję. W pliku othello_shared.py znajdują się gotowe funkcje, których możesz użyć do zbudowania swojej sztucznej inteligencji.

Gdy już masz swoją sztuczną inteligencję, spróbuj z nią walczyć, randy_ai.py. Aby uruchomić dwa programy przeciwko sobie, wpisz „python othello_gui.py (wstaw nazwę pliku ai).py (wstaw nazwę pliku).py” w terminalu Mac lub wpisz „run othello_gui.py (wstaw nazwę pliku ai).py (wstaw nazwę pliku).py i upewnij się, że jesteś we właściwym katalogu. Również spójrz na mój film, aby zobaczyć dokładne kroki.

Krok 8: Czas na walkę AI

Teraz zdobądź grupę znajomych z komputera i spraw, by zaprojektowali własną sztuczną inteligencję! Następnie możesz zrobić zawody i sprawić, by Twoja sztuczna inteligencja go pokonała. Mam nadzieję, że nawet jeśli nie potrafiłeś zbudować własnej sztucznej inteligencji, udało ci się zrozumieć, jak działa algorytm minimax. Jeśli masz jakieś pytania, możesz je zamieścić w komentarzach poniżej.