Trochę tła: jako sposób na nauczenie się drzew wielosystemowych w C ++, postanowiłem wygenerować wszystkie możliwe tablice TicTacToe i zapisać je w drzewie tak, że gałąź zaczynająca się w węźle to wszystkie plansze, które mogą podążać z tego węzła, a dzieci z Węzeł to płyty, które następują po jednym ruchu. Potem pomyślałem, że fajnie byłoby napisać sztuczną inteligencję do gry w TicTacToe, używając tego drzewa jako drzewa decyzyjnego.

TTT to rozwiązywalny problem, w którym doskonały gracz nigdy nie przegra, więc wydawało mi się, że łatwe jest kodowanie po raz pierwszy, aby wypróbować sztuczną inteligencję.

Teraz, kiedy po raz pierwszy zaimplementowałem AI, wróciłem i dodałem dwa pola do każdego węzła podczas generowania: liczba razy X wygra i liczba razy O wygra we wszystkich dzieciach poniżej tego węzła. Pomyślałem, że najlepszym rozwiązaniem będzie po prostu posiadanie mojego AI przy każdym ruchu i zejście w dół poddrzewa, gdzie wygrywa najwięcej razy. Potem odkryłem, że podczas gdy gra doskonale przez większość czasu, znalazłem sposoby, w które mogę go pokonać. To nie był problem z moim kodem, po prostu problem ze sposobem, w jaki AI wybrał ścieżkę.

Następnie zdecydowałem się wybrać drzewo z maksymalnymi wygranymi dla komputera lub maksymalnymi stratami dla człowieka, w zależności od tego, co było większe. To sprawiło, że działał LEPIEJ, ale wciąż nie był doskonały. Nadal mogę go pokonać.

Mam więc dwa pomysły i mam nadzieję na wkład, który jest lepszy:

1) Zamiast maksymalizować wygrane lub straty, zamiast tego mogę przypisać wartości 1 dla wygranej, 0 dla remisu i -1 dla przegranej. Wtedy wybór drzewa o najwyższej wartości będzie najlepszym posunięciem, ponieważ ten następny węzeł nie może być ruchem powodującym stratę. Jest to łatwa zmiana w generowaniu kart, ale zachowuje tę samą przestrzeń wyszukiwania i wykorzystanie pamięci. Lub...

2) Podczas generowania planszy, jeśli istnieje plansza, która wygra X lub O w następnym ruchu, tylko dziecko, które uniemożliwi wygraną, zostanie wygenerowane. Żadne inne węzły potomne nie będą brane pod uwagę, a następnie generowanie będzie przebiegać normalnie po tym. Zmniejsza rozmiar drzewa, ale potem muszę zaimplementować algorytm, aby ustalić, czy wygrana jest jeden ruch, i myślę, że można to zrobić tylko w czasie liniowym (myślę, że generowanie płyty jest dużo wolniejsze?)

Co jest lepsze, czy jest jeszcze lepsze rozwiązanie?