puck
Založen: 24. 06. 2010
Příspěvky: 4
|
 Zaslal: 19. listopad 2012, 22:30:57 Předmět: minmax/maxmin |
 |
|
Zdravim, muj dotaz by se mozna spis hodil do nejakeho matematickeho fora, ale myslim ze je to takova banalita ze najdu odpoved i tady, a treba se to nekomu bude hodit.
Moje uvaha, o ktere nejsem vubec nejak skalopevne presvedcen, je takova, ze minmax a maxmin dojdou vzdy ke stejnemu vysledku pokud pouzivame "pure strategy", plati to same i pro "mixed strategy" ?
A mohou nastat nejake dalsi okolnosti kdy minmax dava jiny vysledek nez maxmin? Jake?
Diky. |
|
mar
Založen: 16. 06. 2012
Příspěvky: 610
|
| Zaslal: 20. listopad 2012, 09:35:57 Předmět: Re: minmax/maxmin |
|
|
| puck napsal: |
Zdravim, muj dotaz by se mozna spis hodil do nejakeho matematickeho fora, ale myslim ze je to takova banalita ze najdu odpoved i tady, a treba se to nekomu bude hodit.
Moje uvaha, o ktere nejsem vubec nejak skalopevne presvedcen, je takova, ze minmax a maxmin dojdou vzdy ke stejnemu vysledku pokud pouzivame "pure strategy", plati to same i pro "mixed strategy" ?
A mohou nastat nejake dalsi okolnosti kdy minmax dava jiny vysledek nez maxmin? Jake?
Diky. |
Čau,
no já bych se upřímně vybodnul na minimax a další teoretické pindy a zkusil rovnou alpha-beta pruning a přepsat to na nega-max, to je mnohem lepší. Než s minimaxem dosáhneš nějakou hloubku tak uběhnou věky, záleží samozřejmě na typu hry a average branching factoru.
Jakmile dostaneš principal variation, tak použiješ negascout/pvs (zero-window, kde alpha+1=beta), tím rychle vyloučíš horší tahy.
Alpha-beta funguje nejlíp, pokud zkusíš nejlepší tah jako první, protože pokud ti už první tah udělá cutoff, tak další tahy nemusíš řešit. Vetšinou to pak vypadá tak, že se ti během hledání střídají all/cut nodes, pv nodes jsou poměrně vzácné.
Takže samozřejmě iterative deepening a zkusit nejlepší tah z předchozí iterace, ale pokud máš už hash table, tak nějdřív tah odsud (pokud ne, tak tah z PV).
U šachů pak můžeš zkusit nullmove a late move reductions, tyhle věci fungují dobře. No a samozřejmě naprostá nezbytnost v tomhle případě je quiescence search. Ten opakuješ tak dlouho, dokud jedna strana nemůže stand pat, tzn., že vyhodnocení pozice je lepší, než beta a tím pádem nemá smysl dál hledat. Plus tam pomůže static exchange evaluation (SEE), případně (nebo v kombinaci s) most valuable victim/least valuable attacker (MVV/LVA). Samozřejmě strategii určuje vyhodnocovací funkce.
U her jako je Go je potřeba uvažovat jinak, tam se nedá spoléhat na taktiku, protože BF je obrovský.
U her pro víc hráčů je to pak ještě větší legrace. |
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
