Kółko i krzyżyk, AI dla planszy 5x5

Witam,

Mam do napisania dla kolegi gre kolko i krzyzyk. Plansza ma miec rozmiar 5x5(zasady takie sam, tyle ze do wygrania potrzeba 5, a nie 3 sasiadujacych ze soba tych samych znakow) Probowalem uzyc funkcji minmax, ale mam problem z tym. Znalazlem w necie kolko i krzyzyk na 3, korzystajace z tej funkcji(http://edu.i-lo.tarnow.pl/inf/utils/002_roz/p012.php). Probowalem przystosowac ten algorytm do wersji 5x5, ale nie wiem dlaczego aplikacja wpada w nieskonczona petle podczas wywolanie rekurencyjnego funkcji minimax. W algotymie poprawilem zasade wygrywania i zwiekszylem wielkosc planszy. Nie wrzucam tutaj mojego kodu, poniewaz ma to byc na zaliczenie. Prosze o podpowiedz czy da sie ten algorytm przystosowac do wersji 5 na 5. Jesli nie to jaki algorytm uzyc i jesli mozna prosze o jakis przyklad.W ostatecznosci zrobie to na if'ach, ale to zadne rozwiazanie

założę się, że wcale nie wpada w nieskończoną pętle, ale ty tracisz cierpliwość.
Pamiętaj, że w 3 na 3 masz tylko 9 ruchów i niewielką ich kombinację.
dla 5 na 5 nasz już 25 ruchów, więc możliwości jest więcej.
Ktoś kto pisał 3 na 3 nie przejmował się optymalizacją kodu (bo i po co) i przy konwersji na głupa masz właśnie takie problemy.
Wprowadź ograniczenie przewidywania 4 ruchów do przodu i powinno pomóc (dodaj też inne optymalizacje).

Niestety to nie pomaga. Po zmianie na 4 rowniez nie moge sie doczekac konca obliczen. Dziala tylko gdy zmienie na 3. To raczej nie mozliwe, aby tak dlugo trwaly obliczenia. O jakie usprawnienia chodzi? Jakies pomysly?

Przeanalizuj kod, to zobaczysz. Czego się spodziewasz, skoro nawet nie widzieliśmy tego twora.

Bazuje sie na kodzie wersji 3 na 3, do ktorej podalem linka w pierwszym poscie.

a my się mamy domyśleć co poprawiłeś a co nie! Szukasz pomocy czy telepaty?

Algorytm ma złożoność wykładniczą. Dla 3 x 3 nie jest to problemem, gdyż ilość obiegów wynosi:

9 x 8 x 7 = 504

Ale dla 25 x 25 mamy już:

25 x 24 x 23 x 22 x 21 = 6375600

Jeśli jeden obieg zajmuje 0.001 (tysięczną sekundy), to znalezienie ruchu wymaga:

6375,6[s] = 106,26 [min] = 1 godz 40 min.

Stąd efekt "zablokowania"

Po prostu minimax w czystej formie nie nadaje się dla bardziej rozbudowanych gier - trzeba stosować różne "obcięcia" drzewa poszukiwań. Na przykład dla planszy 5 x 5 można eliminować niektóre ruchy, co zmniejszy istotnie złożoność obliczeń. Pierwsze ruchy mogą pochodzić z tzw. książki otwarć, ewentualnie można je wyliczać wg pewnego algorytmu kombinatorycznego.

Pozdrawiam

JW z edu.i-lo.tarnow.pl

Poza tym podany link prowadzi do starego artykułu. Tutaj jest nowszy

http://edu.i-lo.tarnow.pl/inf/utils/001_2008/0415.php

Pozdrawiam

JW z edu.i-lo.tarnow.pl