Loginio žaidimo optimaliausio algortimo suradimas

Yra toks loginis žaidimas, kurį daugelis tikrai esate žaidę.

Į matricą NxN yra sudelioti spalvoti blokeliai, kurie sudaro blokų grupės (mažiausią grupę gali sudaryti du vienos spalvos blokeliai esantis vienas šalia kito). Tarp blokelių, matricoje yra įsiterpe monetos. Žaidimo tikslas naikinat blokelių grupes, padaryti taip, jog visos monetos pasiektų žemę. Jeigu sunaikinus blokelių grupę tarp grupių atsiranda tarpas blokelių grupės sustumiamos.

Žaidimo langas 10x10 iš trijų spalvų atrodytų taip:

http://adasu.info/game.png

Jeigu paspaude sunakintume parodytą blokelių grupę:

http://adasu.info/game3.png

Gautume tokį rezultatą:

http://adasu.info/game2.png

Man reikia rasti trumpiausią (kad reiktų kuo mažiau paspaudimų ir jeigu įmanoma sunakintų visus blokelius) algortimą žaidimo tikslui pasiekti. Tai gal kas esatę sprendę panašaus tipo uždavinį ir galite pasiūlyti optimaliausią alogritmą arba žinote, kur galėčiau rasti kodą kuris kažką panašaus nagrinėtų.

Vienas paprastesniu variantu, jei nerandi geresnio sprendimo, butu Alpha-beta pruning su Iterative deepening

Pirma kart rasant, nelabai atkreipiau demesio i problema, tai tik parasiau pirma dalyka, kas sove i galava. Perzvelgus vel, pastebejau, kad cia bus paprasciausias 'trumpiausio kelio' radimas, kuriam tiks paprastas heuristic search. Problema bus tik surasti geriausia heuristic algoritma.

Vienas paprastesniu variantu, jei nerandi geresnio sprendimo, butu Alpha-beta pruning su Iterative deepening

Pritariu. Tik svarbu gera evaluation funkcija tureti, kad rastu ko no.

A* algoritmas su heurisitika.

Kiekvienas A* node butu lenta ivykdzius atitinkama sunaikinima iš visų galimų.

Kelias, atliktu paspaudimu kiekis.

Heuristika galetu buti suma langeliu kiek truksta monetom pasiekti žemę.

Šis kursas gerai paaiškina kaip tokius algoritmus igyvendinti su python https://www.edx.org/course/artificial-intelligence-uc-berkeleyx-cs188-1x-0