Kétszemélyes, teljes információjú, véges és determinisztikus, zéró összegű, játékok
V. Játékok
Gregorics Tibor
Mesterséges intelligenc ia
Két játékos lép felváltva adott szabályok szerint, amíg a játszma véget nem ér. Mindkét játékos ismeri a maga és az ellenfele összes múltbeli és jövőbeli lépéseit és lépési lehetőségeit, és azok következményeit. Minden lépés véges számú lehetőség közül választható, és minden játszma véges lépésben véget ér. Egy lépés determinisztikus, a véletlennek nincs szerepe. Amennyit a játszma végén az egyik játékos nyer, annyit veszít a másik. (Legegyszerűbb változatban: egyik nyer, másik veszít, esetleg lehet döntetlen is) Gregorics Tibor
1
Mesterséges intelligenc ia
Állapottér-reprezentáció
2
Grundy mama játéka
állapot ‒ állás + soron következő játékos művelet ‒ lépés kezdő állapot ‒ kezdőállás + kezdő játékos végállapot ‒ végállás + játékos célfüggvény ‒ mindkét játékosnak van célfüggvénye pA, pB : végállapot⟶ ℝ o o
Zéró összegű kétszemélyes játék esetén: pA(t) + pB(t) = 0 Speciális zéró összegű kétszemélyes játék esetén: • • •
pA(t) = +1 ha t állapotban az A játékos nyer (célállapot, nyerő állás A-nak) pA(t) = ‒1 ha t állapotban az A játékos veszít (vesztő állás A-nak) pA(t) = 0 ha t állás döntetlen
Gregorics Tibor
Mesterséges intelligenc ia
Gregorics Tibor
3
Mesterséges intelligenc ia
Grundy mama játékgráfja
Grundy mama játékfája
7; A 6,1; B 5, 1, 1 ; A
A
5, 2 ; B
4, 2, 1 ; A
4, 1, 1, 1 ; B
4, 3 ; B
3, 2, 2 ; A
7
B 3, 3, 1 ; A
2, 2, 2, 1 ; B
3, 2, 1, 1 ; B
4
A nyer
6, 1
A
5, 1, 1
B
4, 1, 1, 1
3, 2, 1, 1
5, 2
4, 3
4, 2, 1
4, 2, 1
3, 2, 2
4, 2, 1
3, 3, 1
3, 2, 1, 1
3, 2, 1, 1
2, 2, 2, 1
3, 2, 1, 1
3, 2, 1, 1
A 3, 1, 1, 1, 1 ; A
2, 2, 1, 1, 1 ; A
A
B nyer
B 2, 1, 1, 1, 1, 1 ; B Gregorics Tibor
A nyer
3,1,1,1,1
2,2,1,1,1
2,2,1,1,1
2,2,1,1,1
2,2,1,1,1
2,2,1,1,1
B
B
B
B
B
2,1,1,1,1,1
A Mesterséges intelligenc ia
5
Gregorics Tibor
Mesterséges intelligenc ia
6
1
Játékfa
csúcs szint él gyökér levél ág
‒ ‒ ‒ ‒ ‒ ‒
Hogyan tud a B játékos biztosan nyerni?
állás (egy állás több csúcs is lehet) játékos (felváltva az A és B szintjei) lépés (szintről szintre) kezdőállás (kezdő játékos) végállások játszma
B A
Mesterséges intelligenc ia
7
6, 1
5, 2
A 5, 1, 1
4, 2, 1
3, 2, 2
4, 2, 1
3, 3, 1
2, 2, 2, 1 A
3, 2, 1, 1
3, 2, 1, 1
2,2,1,1,1 B
2,2,1,1,1 B
A 4, 1, 1, 1 B 3, 2, 1, 1
3, 2, 1, 1
3, 2, 1, 1
A
A 3,1,1,1,1
2,2,1,1,1 B
2,2,1,1,1 B
2,2,1,1,1 B
Egy győztes játszmához az ellenfél játéka is kell.
2,1,1,1,1,1 A Gregorics Tibor
7
Mesterséges intelligenc ia
Nyerő stratégia
A nyerő stratégia NEM egyetlen győztes játszma, hanem olyan győztes játszmák összessége, amelyek közül az egyiket biztos végig tudja játszani az a játékos, aki rendelkezik a nyerő stratégiával.
Mesterséges intelligenc ia
9
A nyerő (nem-vesztő) stratégia egy megfelelő ÉS/VAGY fa részfájával ábrázolható. Ez a részfa az ÉS/VAGY fa olyan hiper-útja, amely a kezdő állás csúcsából (startcsúcs, gyökércsúcs) vezet a nyerő (nem-vesztő) végállások csúcsaiba. A nyerő stratégia keresése tehát egy ÉS/VAGY gráfbeli hiper-út keresési probléma.
Gregorics Tibor
Nyerő stratégia keresése a B játékos ÉS/VAGY fájában
B B B B
A A B
A A A B B B
8
Megjegyzés
Egy játékos nyerő (vagy nem-vesztő) stratégiája egy olyan elv, amelyet betartva az ellenfél minden lépésére tud olyan választ adni, hogy megnyerje (ne veszítse el) a játékot.
Gregorics Tibor
4, 3
4, 2, 1
B
B Gregorics Tibor
A győztes stratégia garantál egy győztes játszmát.
A
Mesterséges intelligenc ia
10
Nyerő stratégia keresése az A játékos ÉS/VAGY fájában
A
A
B
B
A
A
B
B B B B
A A B
A A A B B B
B
Nincs nyerő stratégia. Csak az egyik játékosnak lehet nyerő stratégiája. Gregorics Tibor
Mesterséges intelligenc ia
11
Gregorics Tibor
Mesterséges intelligenc ia
12
2
Tétel
Ha a döntetlen nem megengedett, akkor bármelyik kétszemélyes játékban az egyik játékos számára biztosan létezik nyerő stratégia. Döntetlen esetén pedig nem vesztő stratégia.
B
B
A B
A
A
B B A B
A
A nyerő stratégia megkeresése egy nagyobb játékfa esetében reménytelen. Az optimális lépés helyett a soron következő jó lépést keressük. •
A
A
B
Részleges játékfa-kiértékelés
A
Legyen a bennünket képviselő játékos neve mostantól MAX, az ellenfélé pedig MIN.
Ehhez az aktuális állapotból indulva kell a játékfa néhány szintjét felépíteni, ezen a részfa leveleinek számunkra való hasznosságát megbecsülni, majd ez alapján a soron következő lépést meghatározni.
A B AA A A
B B B
Gregorics Tibor
Mesterséges intelligenc ia
Gregorics Tibor
13
Kiértékelő függvény
Minden esetben szükségünk van egy olyan heurisztikára, amely a mi szempontunkból becsüli meg egy állás hasznosságát. Sokszor ez egy f : Állások [-1000 .. 1000] függvény.
A játékfának az adott állás csúcsából leágazó részfáját felépítjük néhány szintig. A részfa leveleit kiértékeljük aszerint, hogy azok számunkra kedvező, vagy kedvezőtlen állások. Az értékeket felfuttatjuk a fában:
1.
2.
A saját (MAX) szintek csúcsaihoz azok gyermekeinek maximumát, Az ellenfél (MIN) csúcsaihoz azok gyermekeinek minimumát.
• •
4.
Mesterséges intelligenc ia
Soron következő lépésünk ahhoz az álláshoz vezet, ahonnan a gyökérhez felkerült a legnagyobb érték. Gregorics Tibor
15
Példa
7
7
MIN MAX
7
6 8
6
– –
MIN -2 7 2 -4
Gregorics Tibor
8 -1 -2
6 5 6 12 23 10
Mesterséges intelligenc ia
–
17
16
Az algoritmust minden alkalommal, valahányszor mi következünk, megismételjük, hiszen lehet, hogy az ellenfél nem az általunk várt legerősebb lépésekkel válaszol, mert: –
23
Mesterséges intelligenc ia
Megjegyzés
MAX
14
Minimax algoritmus
3.
Gregorics Tibor
Mesterséges intelligenc ia
eltérő mélységű részfával dolgozik, más kiértékelő függvényt használ, nem minimax eljárást alkalmaz, hibázik.
Gregorics Tibor
Mesterséges intelligenc ia
18
3
Átlagoló kiértékelés
Az (m,n) átlagolás célja a kiértékelő függvény esetleges tévedéseinek simítása. A MAX szintjeire a m darab legnagyobb, MIN szintjeire az n legkisebb értékű gyerek átlaga kerül.
6.5 9 MAX
Váltakozó mélységű kiértékelés
m=2,n=2
6.5
9
4
7.5 8 6
9
4
8
MIN MAX
8
7
MIN
8 0
5 6
8
7 4 8 8 4 -1 9
Gregorics Tibor
Célja, hogy a kiértékelő függvény minden ágon reális értéket mutasson. Nem megbízható ez az érték abban a csúcsban (f(aktuális)), amelynek gyerekénél a kiértékelő függvény lényegesen eltérő értéket (f(gyerek)) mutat. Ezekben az esetekben a részfát tovább kell építeni ezen csúcsokból addig, amíg nem teljesül a nyugalmi teszt: f(aktuális) ‒ f(gyerek) K. Ha a nyugalmi teszt nem felel meg egy csúcs, de vannak olyan gyerekei, amelyekre f(aktuális) ‒ f(gyerek)< K, akkor ezekre a gyerekekre nem kell a nyugalmi tesztet megismételni, ezek levélcsúcsok lesznek.
-1 -2
Mesterséges intelligencia
Gregorics Tibor
19
Mesterséges intelligenc ia
Példa 8
MAX
Szelektív kiértékelés
7 7
9 10 7
min mélység=2 max mélység=5 nyugalmi teszt = 3 Gregorics Tibor
MIN
23
MAX
9 8
8
-4
4 3
8 7
7
21
3 77
-5 6
2
20
Célja a memória-igény csökkentése. Elkülönítjük a lényeges és lényegtelen lépéseket, és csak a lényeges lépéseknek megfelelő részfát építjük fel. Ez a szétválasztás heurisztikus ismeretekre épül.
MIN MAX MIN
7
Mesterséges intelligenc ia
21
Gregorics Tibor
Mesterséges intelligenc ia
22
Példa
Negamax algoritmus
20
Negamax eljárást könnyebb implementálni.
7 MAX
– –
Az ellenfél szintjén levő levelek értékének vesszük a ( ‒1)szeresét, majd minden szinten szülő:= max(‒gyerek1,..., ‒gyerekn)
-7
MIN MAX
-6 8
7 5
MIN -2 7 2 -4 2 -7 -2 4 -5
Gregorics Tibor
Mesterséges intelligenc ia
23
Gregorics Tibor
-3
6
-8
23 12 23 10 -12 -23 -10
6 3 7 12 8
Mesterséges intelligenc ia
24
4
Alfa-béta algoritmus
Visszalépéses algoritmus segítségével járjuk be a részfát (mélységi bejárás). Az aktuális úton fekvő csúcsokat ideiglenes értékekkel látjuk el: – a mi szintünkön értékkel (ennél rosszabb értékű állásba innen már nem juthatunk), – az ellenfelén értékkel(ennél jobb értékű állásba onnan már nem juthatunk) látjuk el. Lefelé haladva =-, és =+. Ezek visszalépéskor a felhozott értékre változnak, ha az nagyobb, mint az , illetve kisebb, mint a . Vágás: ha az úton van olyan és , hogy .
Gregorics Tibor
Mesterséges intelligenc ia
Példa
=
Gregorics Tibor
Mesterséges intelligenc ia
27
-2
2
74 +
7 8 4
22 +
-1 -1 +
-1
2
Mesterséges intelligenc ia
26
Kétszemélyes játékot játszó program
Ugyanazt a kezdőlépést kapjuk eredményül, amit a minimax algoritmus talál. (Több egyforma kezdőirány esetén a „baloldalit” választjuk.) Memória igény: csak egy utat tárol. Futási idő: a vágások miatt sokkal jobb, mint a minimax módszeré. – Átlagos eset: egy csúcs alatt, két belőle kiinduló ág megvizsgálása után már vághatunk. – Optimális eset: egy d mélységű b elágazású fában kiértékelt levélcsúcsok száma: b d – Jó eset: A részfa megfelelő rendezésével érhető el.
- -1 2 -2 + -2
Gregorics Tibor
25
44 -
2 -
= + 282 8
22 +
2 +
=
Elemzés
22 -
=
Váltakozó mélységű, szelektív, (m,n) átlagoló, negamax alfa-béta kiértékelést végez. Keretprogram, amely váltakozva fogadja a felhasználó lépéseit, és generálja a számítógép lépéseit. Kiegészítő funkciók (beállítások, útmutató, segítség, korábbi lépések tárolása, mentés stb.) Felhasználói felület, grafika Heurisztika megválasztása (kiértékelő függvény, szelekció, kiértékelés sorrendje)
Gregorics Tibor
Mesterséges intelligenc ia
28
5
