Kółko i krzyżyk na Arduino z AI (algorytm Minimax): 3 kroki

2025 Autor: John Day | [email protected]. Ostatnio zmodyfikowany: 2025-01-23 15:03

W tej instrukcji pokażę, jak zbudować grę Tic Tac Toe z AI za pomocą Arduino. Możesz grać przeciwko Arduino lub oglądać, jak Arduino gra przeciwko sobie.

Używam algorytmu zwanego „algorytmem minimax”, który może być użyty nie tylko do zbudowania sztucznej inteligencji do gry w kółko i krzyżyk, ale także do wielu innych gier, takich jak Cztery w rzędzie, warcaby, a nawet szachy. Gry takie jak szachy są bardzo złożone i wymagają znacznie bardziej dopracowanych wersji algorytmu. W naszej grze w kółko i krzyżyk możemy użyć najprostszej wersji algorytmu, która jest jednak dość imponująca. W rzeczywistości sztuczna inteligencja jest tak dobra, że nie da się pokonać Arduino!

Gra jest łatwa do zbudowania. Potrzebujesz tylko kilku komponentów i szkicu, który napisałem. Dodałem również bardziej szczegółowe wyjaśnienie algorytmu, jeśli chcesz zrozumieć, jak to działa.

Krok 1: Buduj i graj

Do zbudowania gry w kółko i krzyżyk potrzebne będą następujące elementy:

• Arduino Uno
• 9 diod LED RGB WS2812
• 9 przycisków
• trochę przewodów i kabli rozruchowych

Połącz komponenty, jak pokazano na szkicu Fritzing. Następnie prześlij kod do swojego Arduino.

Domyślnie Arduino wykonuje pierwszą turę. Aby było trochę ciekawiej, pierwszy ruch wybierany jest losowo. Po pierwszym ruchu Arduino wykorzystuje algorytm minimax do określenia najlepszego możliwego ruchu. Nową grę rozpoczynasz, resetując Arduino.

Możesz oglądać „myślenie” Arduino, otwierając Monitor szeregowy. Dla każdego możliwego ruchu algorytm oblicza ocenę, która wskazuje, czy ten ruch doprowadzi do wygranej (wartość 10), czy przegranej (wartość -10) dla Arduino lub remisu (wartość 0).

Możesz także zobaczyć, jak Arduino gra przeciwko sobie, odkomentowując linię „#define DEMO_MODE” na samym początku szkicu. Jeśli prześlesz zmodyfikowany szkic, Arduino wykona pierwszy ruch losowo, a następnie użyje algorytmu minimax, aby określić najlepszy ruch dla każdego gracza w każdej turze.

Pamiętaj, że nie możesz wygrać z Arduino. Każda gra kończy się remisem lub przegrywasz, jeśli popełnisz błąd. Dzieje się tak, ponieważ algorytm zawsze wybiera najlepszy możliwy ruch. Jak zapewne wiesz, gra w kółko i krzyżyk zawsze kończy się remisem, jeśli obaj gracze nie popełnią błędu. W trybie demo każda gra kończy się remisem, bo jak wszyscy wiemy, komputery nigdy nie popełniają błędów;-)

Krok 2: Algorytm Minimax

Algorytm składa się z dwóch elementów: funkcji oceny i strategii wyszukiwania. Funkcja oceny to funkcja, która przypisuje wartości liczbowe do pozycji na planszy. Jeśli pozycja jest pozycją końcową (tj. Pozycją, w której wygrał niebieski lub czerwony gracz lub w której żaden z graczy nie wygrał), funkcja oceny jest bardzo prosta: powiedzmy, że Arduino gra na niebiesko, a człowiek gra na czerwono. Jeśli pozycja jest zwycięską pozycją dla koloru niebieskiego, funkcja przypisuje tej pozycji wartość 10; jeśli jest to wygrywająca pozycja dla czerwonego, funkcja przypisuje tej pozycji wartość -10; a jeśli pozycja jest remisem, funkcja przypisuje wartość 0.

Kiedy przychodzi kolej Arduino, chce wybrać ruch, który maksymalizuje wartość funkcji oceny, ponieważ maksymalizacja wartości oznacza, że woli wygraną nad remisem (10 jest większe niż 0) i preferuje remis niż przegraną (0 jest większe niż -10). Analogicznym argumentem przeciwnik chce grać w taki sposób, aby minimalizować wartość funkcji oceny.

Dla pozycji nieostatecznej algorytm oblicza wartość funkcji oceny za pomocą rekurencyjnej strategii wyszukiwania. Zaczynając od aktualnej pozycji, naprzemiennie symuluje wszystkie ruchy, które mogą wykonać niebieski gracz i czerwony gracz. Można to zwizualizować w postaci drzewa, tak jak na diagramie. Kiedy osiągnie końcową pozycję, zaczyna się wycofywać, przenosząc wartość funkcji oceny z niższego poziomu rekurencji na wyższy poziom rekurencji. Przypisuje maksimum (jeśli w odpowiednim kroku rekurencji jest to tura gracza niebieskiego) lub minimum (jeśli w odpowiednim kroku rekurencji jest to tura gracza czerwonego) wartości funkcji oceny z dolnego poziomu rekurencji do pozycji na wyższy poziom rekurencji. Wreszcie, gdy algorytm zakończy cofanie się i ponownie osiągnie bieżącą pozycję, wykonuje ruch (lub jeden z ruchów), który ma maksymalną wartość funkcji oceny.

Może to zabrzmieć nieco abstrakcyjnie, ale w rzeczywistości nie jest to takie trudne. Rozważ pozycję pokazaną na górze diagramu. W pierwszym kroku rekurencji, niebieski może wykonać trzy różne ruchy. Niebieski próbuje zmaksymalizować wartość funkcji oceny. Na każdy ruch, który może wykonać niebieski, są dwa ruchy, które może wykonać czerwony. Czerwony próbuje zminimalizować wartość funkcji oceny. Rozważ ruch, w którym niebieski gra w prawym górnym rogu. Jeśli czerwony gra w polu środkowym, wygrywa czerwony (-10). Jeśli natomiast czerwony zagra w środkowym dolnym polu, niebieski wygra w następnym ruchu (10). Tak więc, jeśli niebieski gra w prawym górnym rogu, czerwony zagra w środkowym polu, ponieważ minimalizuje to wartość funkcji oceny. Analogicznie, jeśli niebieski zagra w środkowym dolnym polu, czerwony ponownie zagra w środkowym polu, ponieważ minimalizuje to funkcję oceny. Jeśli natomiast niebieski zagra w środkowym polu, nie ma znaczenia, który ruch wykona czerwony, niebieski zawsze wygra (10). Ponieważ niebieski chce zmaksymalizować funkcję oceny, zagra w polu środkowym, ponieważ ta pozycja daje większą wartość funkcji oceny (10) niż pozostałe dwa ruchy (-10).

Krok 3: Rozwiązywanie problemów i dalsze kroki

Jeśli naciśniesz przycisk i zaświeci się inna dioda LED niż odpowiadająca temu przyciskowi, prawdopodobnie masz pomieszane przewody na pinach A0-A2 lub 4-6, albo diody LED zostały podłączone w złej kolejności.

Należy również pamiętać, że algorytm niekoniecznie zawsze wybiera ruch, który pozwoli Arduino wygrać tak szybko, jak to możliwe. W rzeczywistości spędziłem trochę czasu na debugowaniu algorytmu, ponieważ Arduino nie wybrało ruchu, który byłby zwycięskim ruchem. Zajęło mi trochę czasu, zanim zdałem sobie sprawę, że zamiast tego wybrał ruch, który gwarantował, że wygra jeden ruch później. Jeśli chcesz, możesz spróbować zmodyfikować algorytm tak, aby zawsze preferował wygrywający ruch od późniejszej wygranej.

Możliwym rozszerzeniem tego projektu byłoby wykorzystanie algorytmu do zbudowania sztucznej inteligencji dla koła 4x4 lub nawet 5x5 Tic Tac Toe. Należy jednak pamiętać, że liczba pozycji, które algorytm musi zbadać, rośnie bardzo szybko. Będziesz musiał znaleźć sposoby, aby funkcja oceny była bardziej inteligentna, przypisując wartości do pozycji, które nie są ostateczne, w oparciu o prawdopodobieństwo, że pozycja jest dobra lub zła dla danego gracza. Możesz również spróbować uczynić wyszukiwanie bardziej inteligentnym, zatrzymując rekurencję wcześniej, jeśli ruch okaże się mniej wart dalszej eksploracji niż ruchy alternatywne.

Arduino prawdopodobnie nie jest najlepszą platformą dla takich rozszerzeń ze względu na ograniczoną pamięć. Rekurencja umożliwia wzrost stosu podczas wykonywania programu, a jeśli stos rozrośnie się zbyt mocno, może uszkodzić pamięć programu, prowadząc do awarii lub nieprawidłowego zachowania. Wybrałem Arduino do tego projektu głównie dlatego, że chciałem sprawdzić, czy da się to zrobić i w celach edukacyjnych, a nie dlatego, że jest to najlepszy wybór dla tego rodzaju problemu.