Vytváram tic tac toe s min / max, takže môžemrozbaľte ho na alfa-beta prerezávanie. Takže počas môjho min / max zisťujem, či má cesta s vedením +1 (X win) -1 (O win) alebo 0 (Draw) pre konfiguráciu dosiek ako je táto:
Počas 0 otočení vyberie spodnú ľavú odtento krok vedie k jeho víťazstvu. Mala by som skontrolovať každú tabuľku pre blok, potom by to nebolo tak rýchlo a ja si nemyslím, že by sa mala implementovať min / max.
0 | x | 0 - | x | - - | - | -
Môže niekto vysvetliť, prečo min / max nie je dostatočne chytrý, aby to zistilo. Aj keď som sa pozrel na ľavé uzly a vrátil +1 / -1 / 0.
odpovede:
2 pre odpoveď č. 1edit: Zmiešal som "čistý" minimax s minimax + heuristickým. Upravil som svoju odpoveď na vyriešenie tohto problému.
Možno by to pomohlo definovať minmax. z Článok študenta UC Berkeley:
minimax(player,board)
if(game over in current board position)
return winner
children = all legal moves for player from this board
if(max"s turn)
return maximal score of calling minimax on all the children
else (min"s turn)
return minimal score of calling minimax on all the children
S minimaxom sa snažíte minimalizovať straty, nie maximalizovať svoje zisky. Takže "vaša" je min"s obrátiť. S touto definíciou, ak by ste mohli niekedy stratiť výberom štvorca, potom bude označený -1, Ak by si mohol niekedy kravatu, ale nikdy nestratí, bude označená 0, Iba v prípade, že je zaručená výhra, bude označená 1.
Mal by som skontrolovať každú tabuľku pre blok
Ak definujete skóre a algoritmussprávne (priradenie pravých hráčov k správnej logike), nemusíte "skontrolovať blok". Akýkoľvek podsúbor hry, v ktorom by hráč nebol blokovaný, by sa implicitne mal hodnotiť -1, pretože v určitom okamihu (pravdepodobne veľmi rýchlo) to vyhodnotí na stratu a táto strata bude bublina.
Skutočný problém s týmto algoritmom (a kdemôžete dosiahnuť výsledky, ktoré neočakávate), keď všetky sub-stromy vedú k možným stratám.V tomto bode budete musieť použiť heuristiku, aby ste získali lepšie informácie o pohybe, ktorý by ste mali vziať.Tak budete potrebovať niečo lepšie ako jednoducho {-1, 0, 1}, pretože niektoré pohyby vám môžu umožniť vyhrať, ale vy by ste ich zablokovali, pretože by ste mohli tiež prehrať.
0 pre odpoveď č. 2
Nie som si celkom istý, aký je váš problém. Ako už bolo spomenuté vyššie, min / max má problémy, keď viac ako jedna cesta vedie k výhre alebo všetky cesty vedú k strate. V takom prípade je matematicky správne vybrať akúkoľvek alebo víťaznú cestu alebo akúkoľvek cestu na stratu. Avšak ak hráte s neperfémným protivníkom, je často rozumnejšie vybrať najkratšiu víťaznú cestu a najdlhšiu voľnú cestu (ako dúfať, že protivníka nebude hrať perfektný a vyberie nesprávnu voľbu).
Toto správanie je docela ľahké implementovaťmin / max použitím rozkladu pre každú rekurziu. Tj. kedykoľvek vrátite niečo z rekurzívneho hovoru, vynásobte výsledok o 0,9 alebo niečo podobné. Toto povedie k vyšším skóre pre dlhšie negatívne cesty a menšie skóre pre dlhšie pozitívne cesty.
To však vedie k problémom, akonáhle začnete používať heuristiku, aby ste vybuchli.