6.Kétszemélyes játékok

Question 1

Hogyan kapcsolhatóak a kétszemélyes játékok a keresési problémákhoz

Answer 1

kiismerhetetlen ellenfél -> megoldás egy stratégia
meg kell határozni a válaszlépést az ellenfél minden lehetséges lépésére

időkorlát -> a célkereséstől eltérően közelítő megoldás kell

Question 2

Min max keresés

Answer 2

Teljes információjú determinisztikus játék tökéletes játszása

ötlet: lépjen oda ahol a legmagasabb a minimax érték, legjobb elérhető érték a legjobb ellenfél ellen

Tulajdonságok:
teljes, optimális

Question 3

Használható-e a minimax keresés akkor, amikor a játékfa nem fér el egyszerre a memóriában? Milyen módon?

Answer 3

Használható:
-cutoff-test
-mélységi korlát

Nem építjük fel az egész fát előre hanem mélységi bejárást alkalmazunk és csak a szükséges részeit generáljuk dinamikusan

Alfa béta nyeséssel kizárhatunk állapotokat és ezzel kevesebb állapotot kell megnéznünk

Question 4

Mit jelöl az alfa és béta az alfa-béta nyesés esetén?

Answer 4

alfa: maximalizáló játékos eddig legjobb talált érték az aktuális útvonalon
alsó korlát: ennél rosszabb érték már biztosan nem kell a maxnak

Béta: a minimalizáló játékos számára eddig talált legjobbb érték
Felső korlát: ennél nagyobb érték már biztosan nem kell

Question 5

Hogyan kezelhetjük a véletlent is tartalmazó játékokat?

Answer 5

Expectiminimax algoritmus

3 csomópont:

1.Max
2.Min
3.Véletlen csomópont

Véletlen csomópont az utódállapotok súlyozott átlagát (várható értékét) számolja:

Question 6

Hogyan kezelhetjük a nem teljesen informált játékokat?

Answer 6

Rendszerint minden lehetséges leosztás valószínűségét kiszámoljuk

MMintha egy sok oldalú kockát dobtunk volna

Ötlet: számoljuk ki a minimax értékét az összes lépésnek és válaszuk azt amelynek a legmagasabb várható értéke az összes elosztást tekinve