Minimax Algoritmus Výhody / nevýhody - algoritmus, minimax

Nevýhodou algoritmu minimax je, že každý štát má dosky navštíviť dvakrát: raz nájsť svoje deti a druhýkrát vyhodnotiť heuristickú hodnotu.

Existujú nejaké iné nevýhody alebo výhodyna minimax algoritmus? Hovorte o hre ako šach, by existovali nejaké lepšie alternatívy? (Samozrejme minimax s alfa-beta prerezávaním, ale niečo iné?)

odpovede:

Minimax má tendenciu byť príliš pomalý pre hry, ako je šach. Pre každú otočku má prehrávač veľa možností rozhodnúť sa faktor rozvetvenia hra šachu je obrovská, a preto čím hlbšie ideme, tým pomalšie. V priemere faktor vetvenia pre šachy má tendenciu k 30. To znamená, že 30 subtrees na otáčku sú vytvorené.

Pred uvedením konkrétnych algoritmov všetci používajú to, čo nazývame prerezávanie alfa beta. Alpha beta znižuje počet uzlov, ktoré sa majú rozšíriť, a preto znižujeme faktor rozvetvenia.

Majte na pamäti, že existuje mnoho rôznych variantov minimax a alfa beta, ale najdôležitejšie algoritmy sú:

• Negamax: Myšlienkou je, že skóre pre pohyb pre jedného hráča je vždy - podľa toho druhého hráča, ale rovnakej veľkosti, ktorá umožňuje vypočítať max (a, b) = -min (-a, -b).

Jednoduchá interpretácia:

score = -negamax(depth-1,-player)
best = max(score,best)

Algoritmy vyhľadávania okien

Nasledujúce algoritmy používajú okno na zmenšenie vyhľadávacieho priestoru. Okno by malo spočiatku nadobudnúť hodnotu pre alfa a beta.

• Metóda hlavnej variácie: Táto metóda znižuje počet uzlov navštívených "hádaním" počiatočného alfa a beta. Robí to tak, že preskúma len jednu vetvu a vyberie ju kandidát hodnota. Pomocou tejto hodnoty prerezávame. Ak nájdeme rozpor, je to hodnota, ktorá prináša vyššie skóre ako kandidát, ktorý začneme opäť kandidovať.

• MTD (f) Ďalšia variácia minimaxu. Používa vyhľadávanie v nulovom okne. To znamená, že po nájdení kandidáta (napríklad "v") predpokladáme, že hodnoty alfa beta budú (v-1, v) a preto je možné len riešenie v. Ak nájdeme rozpor, zmente kandidáta a zopakujte.

Tiež najlepší a najpoužívanejší algoritmus pre šachové počítačové programy je MTD (f) s niektorými variáciami / heuristikou.

zdroj:Konverzia Minimaxu na Negamax (python)