Keresőeljárások kétszemélyes játékokhoz Összeállította : Vályi Sándor Prof. Dr. Heiner Stuckenschmidt (Universität Mannheim) előadása nyomán http://www.google.hu/url?sa=t&source=web&ct=res&cd=5&ved=0CBcQFjAE&url=http%3A%2F%2Fki.informatik.uni-mannheim.de%2Ffileadmin%2Fteaching%2Fki%2F2009%2F6Spielbaumsuche.ppt&rct=j&q=minimax+negamax+filetype %3Appt&ei=bn4FS7rpBp_cmgPWwMTICg&usg=AFQjCNFg9LosMFOWOrO3dA7XLNlGN-iTmg Letöltve: 2009. nov. 19.
Játéktípusok Determinisztikus
Sztochasztikus
Teljesen megfigyelhető
Sakk, Go
Backgammon, Monopoly
Parciálisan megfigyelhető
Torpedó
Bridzs, Póker
Adatbázis-módosítható keresési eljárások • •
ToDoListe := [Startzustand] LOOP –
IF ToDoLista üres THEN fail
– – –
Csomópont := Select(ToDoLista) IF MEGOLDÁS(Csomópont) THEN succeed Rand := BESZÚR(KITERJESZT(Knoten), ToDoListe)
Mehadia
Rimnicu Vilcea Craiova
Zerind
Sibiu
Timisoara
Lugoj
Arad
Fagaras
Pitesti
Oradea
Oradea
Zerind
Sibiu
Bucharest
Faragas Drobeta
Drobeta
Pitesti
Bucharest
Craiova
Arad
Rimnicu Vilcea
Arad Bucharest
Játékok mint keresési problémák • Formalizálás állapottérként – Operátorok: lehetséges lépések – Célállapot: nyerő, ill. vesztő állások – Költség: Pontnyereség ill. -veszteség – Keresési tér: “Játék-fa”
• Probléma: – Az ellenfél lépései nem tervezhetők
Példa: Tic-tac-toe
2 játékos: o und x Determinisztikus Teljesen megfigyelhető Nullaösszegű játék
Játékok, mint ÉS/VAGY fák 1 Játék nyerve 0 Játék vesztve
∨ saját lépés ∧ ellenfél lépése
∨
∧
∧
∨
0
∨
1
1
∨
∨
0
Nyerni fogunk?
0
0
1
0
Játékok, mint ÉS/VAGY fák 1 Játék nyerve 0 Játék vesztve
∨ saját lépés ∧ ellenfél lépése
∨
∧
∧ ∨
∨
0
1
1
∨
∨
0
0
0
1
Igen, ha helyes stratégiát választunk?
0
Gondok a játékfában való kereséssel • Meghatározhatjuk, mely lépések vezetnek győzelemhez • Gond: – a keresési fa túl nagy ahhoz, hogy teljesen végigkeressük
• Megoldás: – Mélységkorlátozott keresés olyan mélységig, amit meg tudunk valósítani
• Gond: – Honnan tudhatjuk, hogy tényleg nyerünk egy bizonyos állásban?
• Megoldás: – A köztes állapotokra értékelő heurisztikát alkotunk
Részleges játékfák ∨ ∧
∧
∨
?
∨
?
?
∨
∨
?
?
?
?
?
Részleges játékfák ∨ ∧
∧
∨
h(n)
2
∨
5
9
∨
∨
3
1
Figyelem: h(n) a heurisztikát jelenti, nem a költséget !!
4
7
8
Részleges játékfák A legnagyobb várható haszont ígérő lépést tesszük meg
Az ellenfél azt a lépést választja, amely számunkra a legkisebb hasznot hozza
min
max
max
h(n)
2
max
5
9
min
max
3
1
max
4
7
8
Részleges játékfák 5
5
5
h(n)
2
4
min
9 max
max
5
max
9
4
3
1
min
8
max
4
7
max
8
Részleges játékfák A többet ígérő ágat választjuk és ott majd újra végrehajtjuk a keresést. 5
5
5
h(n)
2
4
min
9 max
max
5
max
9
4
3
1
min
8
max
4
7
max
8
Feltételezések • Racionális magatartásból indultunk ki: – Minden játékos a saját nyereségét próbálja maximalizálni – Az ellenfél húzásai csökkenteni próbálják a saját játékos hasznát
minmax(n) =
h(n) , ha n VÉGÁLLAPOT max{ minmax(h(s))| s n után jövő állás}, ha mi következünk min{minmax(h(s))| s n után jövő állás} ellenséges lépésnél
A Minimax algoritmus tulajdonságai • Teljesség:: IGEN/NEM: teljes, véges játékfák esetén
• Optimalitás: IGEN/NEM: felttételezvez, hogy az ellenfél is optimálisan játszik
• Időbonyolultság: O(bn): mint mélységkorlátozott keresés.
• Speicherkomplexitaet: O(bn): mint mélységkorlátozott keresés.
Kompakt reprezentáció • A Min és a Max csomópontok megkülönböztetése megnehezíti az implementációt • Tiszta maximalizálási problémaként való megfogalmazása: – Alap: min(a,b) = -max(-a,-b) – A negatív nyereségi várakozás definíciója:
negamax(n) = hasznosság(n), ha n maxim. mélységű max{-negamax(s) | s n rákövetkezője} hasznosság(n) = h(n) saját lépésnél -h(n) ellenfél lépésénél
Negamax játékfák negamax(n) = max{-u(n)}
5 max
-5 max
5
u(n)
-2
-4 max
9 max
max
-5
-9
4
-3
-1
8
max
-4
-7
max
-8
A NegaMax rekurzív kiszámítása int Negamax (Csomópont n) int value; succ = KITERJESZT(n); if (succ üres) return u(n) ; value := -∞; foreach ( s in succ) value := max(value, -Negamax(s)); return value;
Használhatóság • Az időbonyolultság nagy gond: A valódi játékok óriási játékfával bírnak: • Dáma: 1078, Sakk 10120, Go 10761
– Sakk: • Kb. 40 lépés minden állásban • Azaz, kb 2 Mio csomópont, ha 2 lépést előre tervezünk • Kezdők 3-4 lépést terveznek, Profik kb. 10-ig
• Megoldás: A keresési tér korlátozása (levágás, pruning) – Ötlet: ágak, amelyek jobb megoldást nem tartalmazhatnak, kihagyjuk a keresésből – A Branch&Bound (ág-és-korlát) algoritmus alkalmazása
Honnan jönnek a kiértékelő függvények? • •
Nehéz játtékoknál nem a végigjátszásból Alternatíva: mélységkorlátozás és empirikus heurisztikus értékelések
•
sakk: – gyalog: 1, huszár és futó 3, bástya 5, királynő 9
Végállási adatbázisok • Minden olyan pozíció esetén teljse stratégia tárolása, ahol pl. már csak N darab bábu van a táblán. • Ha ilyen pozíciót érünk el a játékfában, akkor nem becslünk, hanem pontos hasznosságot tudunk számolni Fehér lép, matt 3 féllépésben
Lehet bonyolult is •
matt 262 lépésben !!
Probléma a végállás-adatbázissal • Még az automatikus létrehozása is extrém módon erőforrás-igényes – Persze az imént említett keresési módszereket használhatjuk
• A tárigény: – 5 figurával: 7 GB – 6 figurával: 1.2 TB – 7 figurás végállásokat a közeli jövőben biztos nem lehet tárolni
• Gyorsabb lehet az állásra egy keresőt indítani – Kivétel? Mint az utolsó fólián
Nem-Determinisztikus játékok • Példa: Backgammon • A lehetséges lépések koczkadobástól függnek • Minimax-fát nem lehet építeni
Várhatóérték-minimax • A kockadobásokat mint plusz csomópontokat bevonni a fába • A Minimax-értékbe a különböző csomópontok értékei a kockadobás érintett kimenetének valószínűségével súlyozva, várható értékként kerül be.
Egy egyszerű példa • Játék pénzfeldobással:
Backgammon:
Költségszámítás • Várhatóérték-számítással
