363

Mesterséges Intelligencia Csató Lehel

Mesterséges Intelligencia Csató Lehel Matematika-Informatika Tanszék Babe¸s–Bolyai Tudományegyetem, Kolozsvár

2010/2011

1/363

˝ Az Eloadások Témái Mesterséges Intelligencia

˝ mi a mesterséges intelligencia ... Bevezeto:

6

„Tudás”–reprezentáció

Csató Lehel

Gráfkeresési stratégiák

Jatekelmelet

Szemantikus hálók / Keretrendszerek

Kétszemélyes játékok NIM

Játékok modellezése

Tic–Tac–Toe Nyero Strat.

Bizonytalanság kezelése

Strat. keresés Minimax alg. Negamax

Fuzzy rendszerek

Alfabéta Játékprogramok

Grafikus modellek

˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

Tanuló rendszerek

Példa

Szimulált kifutés, ˝ Genetikus algoritmusok

Összefoglaló

A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 110/363

Admin ...

http://www.cs.ubbcluj.ro/~csatol/mestint

Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet

... trívia

Vizsga Szóbeli (60%) + Gyakorlat (40%)

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

Laborgyakorlatok:

Strat. keresés Minimax alg.

1

Gráfok ábrázolása - dedukciós algoritmus

18%

2

Játékelmélet

10%

3

Matlab - tanulási algoritmus

12%

4

Opcionális feladatok - max. 3/személy

Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Bemutatók (5–20 pont) Alkalmazások bemutatása, melyek adaptív, gépi tanulásos vagy mestint módszereket alkalmaznak. 111/363

sok%

Játékelmélet Mesterséges Intelligencia

6

Futó, pp. 215

... problems arising when we try to plan ahead in presence of hostile agents ... Russell&Norvig, pp. 122

Csató Lehel Jatekelmelet

Babbage (1846) - gépet tervez, mely Tic-tac-toe-t játszik,


Leonardo Torres y Quevedo (1890) - sakk végjáték,


von Neumann & Morgenstern (1944) - Theory of games and Economic Behaviour Shannon és Turing (1950) - sakkprogram, mert

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

1

Példa Összefoglaló

2 3

„intelligencia” szükséges a játékhoz, egyszeru˝ szabályok, teljes informáltság,

McCarthy (1956) - vágások. 112/363

Játékok és keresés Mesterséges Intelligencia

„Ismeretlen” ellenfél:

6

Nem ismerjük a lépéseit,

Csató Lehel

Feltételezzük, hogy nyerni akar.

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

Válasz: egy stratégia, mely az ellenfél minden lehetséges lépését figyelembe veszi.

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ Sakk-program esetében: nincs lehetoség az összes ˝ lehetoség vizsgálatára ⇒ szükségesek a közelítések.

Mit közelítünk? 113/363

Játékok típusai Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

Teljes információs Részleges információs

determinisztikus sakk, go

valószínuségi ˝ Dáma, Monopoly

battleship

bridge, póker

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

?? Kupacos játék - Maya.

114/363

Kétszemélyes játékok Mesterséges Intelligencia

Kétszemélyes teljes információs játékok:

6

két játékos lép felváltva, adott szabályok szerint;

Csató Lehel

a játékosok minden információval rendelkeznek;

Jatekelmelet

minden állapotban véges számú lépés létezik;

Kétszemélyes játékok NIM

véges a játszma ideje;

Tic–Tac–Toe Nyero Strat.

az egyik játékos mindig nyer (esetenként lehetséges döntetlen...)

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Ezzel a játékosztállyal foglalkozunk.

115/363

I

Kétszemélyes játékok Mesterséges Intelligencia

6

Formális definíció:

Csató Lehel

Két játékos, legyen MAX illetve MIN;

Jatekelmelet Kétszemélyes játékok NIM

MAX kezd;

Tic–Tac–Toe Nyero Strat. Strat. keresés

˝ ismert kezdoállapot;

Minimax alg. Negamax Alfabéta

muveletek, ˝ melyek leírják a lehetséges lépéseket;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

játék végének a tesztje;


nyereség-függvény; Stratégia: szabály az egyik – MAX – játékos optimális lépéseinek megadására. 116/363

II

Nim játék Mesterséges Intelligencia

Nim = „nip” + „muster”

6 Csató Lehel

Játék: gyufaszálak több sorban;

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

adott gyufaszál minden sorban;

[n1 , . . . , nm ]

lépés = egy sorból valahány gyufaszál elvétele;

i 0 ≤ ni0 < ni

Alfabéta

játék vége: elfogynak a gyufaszálak;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok

m

∀i; ni = 0

veszít az a játékos, mely már nem tud gyufaszálat felvenni.

Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ nem Változatok: vesztes az utolsó gyufaszálat felvevo; ˝ lehet tetszoleges számú elemet felvenni, etc. 117/363

Nim játék Mesterséges Intelligencia


A játék állásai: Nyero˝ – ha a játékos tud úgy lépni, ˝ függetlenül hogy az ellenfél lépéseitol nyer; Veszto˝ – ha nincs nyero˝ lépés.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Nyero˝ stratégia:

Minimax alg. Negamax

0 0 1 1


0 1 0 1

1 0 0 1

1 = 3 1 = 5 0 = 8 0 (XOR)

˝ melyekre az Állítás: azon állások vesztok, XOR csupa nullát eredményez. 118/363

Nim játék tulajdonságai Mesterséges Intelligencia


˝ melyekre az XOR csupa Állítás: azon állások vesztok, nullát eredményez. 1. Lemma Ha egy állásban az XOR nem csupa nullát eredményez, akkor van lépés, mely az XOR szerint nullát eredményez.

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok

2. Lemma Ha egy állapotban az XOR csupa nulla, akkor nincs lépés, mely eredményeként az XOR nulla lesz.


Nyero˝ stratégia Ha XOR nem nulla, akkor le tudjuk nullázni és az ellenfél nem tud olyat lépni, hogy számunkra megint nulla legyen. =⇒ nyero˝ stratégia. 119/363















Nim játék példa Mesterséges Intelligencia

Kezdeti állapot:

6 0 0 1 1

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe

0 1 0 1

1 0 0 1

1 = 3 1 = 5 0 = 8 0 (XOR)

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok

Válasszuk az utolsó (8 elemes) sort. Ahhoz, hogy mindenhol 0 legyen

˝ o˝ játékok Ismétlod Null-összegu˝ játékok

0 1 1 0 = 6


kell maradjon, tehát 2 elemet kell elvenni. Az új pozíció vesztes. 120/363

Nim játék gráfja Mesterséges Intelligencia

1, 2 A lép

6 Csató Lehel

játék gráfja véges mélységu; ˝

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

0, 2 B lép

1, 1 B lép

1, 0 B lép

0, 1 A lép

0, 0 A lép

1, 0 A lép


Nyero˝ stratégia:

Alfabéta

mindig van legalább egy olyan ˝ gyozni ˝ lépés, melybol tud;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

függetlenül attól, hogy az ellenfél mit lép;


0, 0 B lép 121/363

˝ Tic-Tac-Toe – amoba MAX(X) Mesterséges Intelligencia

6 Csató Lehel

MIN(O)

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

MAX(X)

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

MIN(O)


Vég Jutalom: 122/363

A játék gráfja −1

0

1

Nyero˝ stratégia létezése Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

Tétel Egy teljes információjú kétszemélyes játék esetén mindig létezik egy játékos számára nyero˝ stratégia (ha nincs döntetlen).

.

MAX


Bizonyítás: ˝ Az élek címkézése lentrol felfelé. Ha B lép, ∃ ág, mely B-vel van címkézve, akkor B, ellenkezo˝ esetben A. 123/363

.

B

.

B

A

.

B

A

MIN

A

MAX

Majdnem NIM Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok

Példa

Kuglizás – ahol az összes bábú egy sorban van, tehát csak egy vagy két – egymásmelletti – bábút tudunk leütni. ˝ Vesztes, akinek eloször nem marad bábúja. Feladat:

NIM Tic–Tac–Toe

Határozzuk meg a játék állapotterét k = 3 egymásmelletti bábúra;

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Határozzuk meg, hogy az kezdo˝ játékos nyer vagy veszít.

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Számítsuk ki, hogy a kezdo˝ játékos nyertes-e k = 5 egymás-melletti bábú esetén.

Összefoglaló

Írjunk programot, mely meghatározza, hogy a kezdo˝ ˝ játékos nyer-e tetszoleges konfigurációnál. 124/363

Stratégiák keresése Mesterséges Intelligencia

Stratégia nem keresheto˝ mert a teljes gráf nem fér el a memóriában;


túl sok állapot.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Sakk:


≈ 45 lépés tehát 90 mélységu˝ fa, ˝ ≈ 35 lehetoség; 3590 = 10139 levél. 1080 összes elektron


Deep Blue – 32CPU × 8 dedikált sakk-processzor (13-30 mélységig; 30 milliárd lépés/perc) 125/363

Minimax algoritmus Mesterséges Intelligencia

Minimax algoritmus:

6 Csató Lehel

bonyolultabb játékok esetén használják;

Jatekelmelet Kétszemélyes játékok NIM

nem építheto˝ meg a teljes játékfa;

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

nem talál biztosan nyero˝ stratégiát;


˝ vagy „elég jó” lépés; „eros”


˝ Közelítéseket adunk a nyero/vesztes értékelés helyett. 126/363

Minimax algoritmus játékfákon Mesterséges Intelligencia

Játékfa építése adott mélységig;

6

3

MAX

Levelek címkézése: kiértékelo˝ függvény

Csató Lehel Jatekelmelet Kétszemélyes játékok

Értékek visszaterjesztése lásd Nyero˝ stratégia ;

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg.

3

2

MIN

2

Negamax

A gyökér-címke értéku˝ lépés megtétele;


3

127/363

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

127/363

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

127/363

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

127/363

12

8

2

4

6

14

5

2

MAX

Negamax algoritmus Mesterséges Intelligencia

6

A minimax algoritmusnál a különbözo˝ játékosok lépéseinél minimumot vagy maximumot kerestünk;


A negamax algoritmus egyesíti a kétfajta optimális lépést:

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

minden lépésben maximumot számol,


˝ o˝ szint negált értékei szerint. ellenben az eloz


a javasolt lépés a csúcs negált értéku˝ utódjába történo˝ lépés;

128/363

Negamax algoritmus muködése ˝ Mesterséges Intelligencia

6

3

-MAX

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

-3

Alfabéta

-2

-MAX

-2

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

3 129/363

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 129/363

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 129/363

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 129/363

12

8

2

4

6

14

5

2

-MAX

Minimax/Negamax tulajdonságok Mesterséges Intelligencia

Tulajdonságok:

6

Teljesség – megtalálja az optimális lépést, ha ilyen létezik? Ha a játékfa véges. igen


Optimalitás – a legjobb lépést találja meg? Ha az ellenfél is racionális.

Nyero Strat. Strat. keresés Minimax alg.

igen

Negamax Alfabéta

Bonyolultság: O(bm )

Játékprogramok

kimeno˝ élek – b kiértékelés mélysége – m


Memóriaigény: O(bm)


Sakk-program: b ≈ 35, 90

35

m ≈ 100, ⇒ 3590 = 10139 levél v.ö: 1080 összes elektron

Hatékonyság növelése: VÁGÁSOK 130/363


Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35



Alfa-béta vágás Mesterséges Intelligencia

I

Minimax/negamax algoritmus költséges mert nagyon sok csúcsot kell generálni; azonban

6

Tudjuk, hogy az értékelés a minimax szabály szerint történik;


Az alfa-béta vágások módszere figyelembe veszi a már kiszámított csúcsok értékét (McCarthy 1956 – sakk)

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

és csak olyan csúcsokat nem értékel ki, ahova racionális játék során eljutunk.

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Kiértékelés során bevezetett változók:

α – MAX szint utódjainak maximuma;

Összefoglaló

csak növekedhet.

β – MIN szint utódjainak minimuma; csak csökkenhet. 131/363

Alfa-béta vágás Mesterséges Intelligencia

6 Csató Lehel

II

Vágás: muvelet, ˝ melynek eredményeként nem értékeljük ki egy csúcshoz tartozó többi utódcsúcsot. Vágási kritériumok:

Jatekelmelet

˝ MIN csúcs alatt vágunk, ha az egyik oséhez rendelt

Kétszemélyes játékok

α érték nagyobb, mint a csúcs β értéke.

NIM Tic–Tac–Toe Nyero Strat.

alfa vágás

Strat. keresés Minimax alg.

˝ MAX csúcs alatt vágunk, ha az egyik oséhez rendelt

Negamax Alfabéta

β érték kisebb, mint a csúcs α értéke.


béta vágás


Egy kiértékelést abba lehet hagyni, ha:

α≥β 132/363

Alfa-béta vágás – példa Mesterséges Intelligencia

≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

3


2

2<3

X

X

MIN


3

133/363

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN


3

133/363

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN


3

133/363

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN

< 14


3

133/363

12

8

2

14

5

2

MAX


≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

<5

Strat. keresés

3


2

2<3

X

X

MIN


3

133/363

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN

2


3

133/363

12

8

2

14

5

2

MAX


3

≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

<5 < 14

Strat. keresés

3


2

2<3

X

X

2

MIN


3

133/363

12

8

2

14

5

2

MAX

Alfa-béta algoritmus tulajdonságai Mesterséges Intelligencia

6 Csató Lehel

˝ a vágások nem módosítják a megoldások minoségét;

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

hatékony vágások (elso˝ eset) megvalósítása a ˝ csúcsok rendezésével: ido-komplexitás: O(bm/2 )

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Fontos a tudás – hol lehet „jó csúcsokat” találni – kódolása.

134/363

Létezo˝ játékprogramok: Dáma – Chinook program 40 éves nyerési sorozatot szakított meg ...


6

Sakk – Deep Blue 1997-ben megverte Kasparov-ot.

Csató Lehel

Reversi – nem játszanak: gép ... mindig nyer.

Jatekelmelet

Go – nem játszanak: gép ... mindig veszít.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

135/363

Játékelmélet Mesterséges Intelligencia

Neumann János

˝ Jellemzok:

6

két játékos van: a sor illetve az oszlop játékos.

Csató Lehel

a sor-játékos a számára elérheto˝ m stratégia közül pontosan egyet választ.

Jatekelmelet Kétszemélyes játékok

az oszlop-játékos a számára elérheto˝ n stratégia közül pontosan egyet választ.


A választások egymástól függetlenek.

Negamax Alfabéta

Ha a sor játékos az i opciót, az oszlop játékos a j opciót választotta, a sor játékos nyeresége aij .


˝ Stratégia: szabályrendszer, mely eloírja, hogy egy játékos mit kell lépjen. Neumann János tétele - kevert stratégiákra null-összegu˝ játékokon. 136/363

Stratégia játékokban Mesterséges Intelligencia

6

Példa

Két játékos, mindegyiknek van valahány stratégiája, melyek közül választhat (A → 3, illetve B → 4).


Nyereségmátrix az A számára; veszteség B-nek.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

A.1 A.2 A.3


B.1 −1 5 8

B.2 3 4 −2

B.3 2 −2 6

B.4 9 6 −2


Ha A nem tudja, hogy B mit fog lépni, melyik a legjobb lépés? ?

137/363

Minimax tulajdonság Mesterséges Intelligencia

Nyereségmátrix: (a sor játékos számára)

6 −1 5 8

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

3 4 −2

2 −2 6

9 6 −2

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Azon stratégiát válassza, mely a legkisebb nyereségek maximumát adja.


Minimax játékos: max min Mij ≤ min max Mij i

Összefoglaló

j

j

azaz: az A legalább min max-ot nyer.

138/363

i

Minimax tulajdonság Mesterséges Intelligencia

Nyereségmátrix: (a sor játékos számára)

6 −1 5 8

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

3 4 −2

2 −2 6

9 6 −2

−1 −2 −2

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Azon stratégiát válassza, mely a legkisebb nyereségek maximumát adja.


Minimax játékos: max min Mij ≤ min max Mij i

Összefoglaló

j

j

i

azaz: az A legalább min max-ot nyer. A sor-játékos az elso˝ sort választja −1 nyereséggel 138/363

Kevert stratégia Mesterséges Intelligencia

Nyereségmátrix:

6

−1 5 8

Csató Lehel Jatekelmelet

3 4 −2

2 −2 6

9 6 −2

−1 −2 −2

Kétszemélyes játékok NIM Tic–Tac–Toe

De: vannak a nyereségmátrixnak sokkal nagyobb elemei is, tehát kell legyen jobb választás; Kevert stratégiával játszunk: a sorjátékos válassza:

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok

x1 valószínuséggel ˝ az elso˝ sort; x2 valószínuséggel ˝ a második sort; x3 valószínuséggel ˝ a harmadik sort (x3 = 1 − x1 − x2 );

˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Az oszlop játékos ugyanígy választhat. Feltételezzük, hogy sokszor játsszuk ugyanazon mátrix szerint. 139/363

Kevert stratégia létezési tétele Mesterséges Intelligencia


Neumann-tétel Minden nulla-összegu˝ játék esetén létezik egy olyan keveréke a stratégiáknak, mely minimax tulajdonsággal rendelkezik.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

Bizonyítás: y Átlagnyereség: x T My

x = [x1 , . . . , xn ] ∈ Π n

y ∈ Πm

Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

y= max min x T My

Összefoglaló

x∈Πn m∈Πm

V=V | {z }

y = min max x T My m∈Πm x∈Πn

teljes biz. Finta - operációs kutatások

140/363

Kevert stratégia létezési tétele Mesterséges Intelligencia


Neumann-tétel Minden nulla-összegu˝ játék esetén létezik egy olyan keveréke a stratégiáknak, mely minimax tulajdonsággal rendelkezik.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

Bizonyítás: y Átlagnyereség: x T My

x = [x1 , . . . , xn ] ∈ Π n

y ∈ Πm

Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

y= max min x T My

Összefoglaló

x∈Πn m∈Πm

V=V | {z }

y = min max x T My m∈Πm x∈Πn

teljes biz. Finta - operációs kutatások

140/363

Minimax tétel Mesterséges Intelligencia

6

Példa:

0 2

T 1 x y Arányokkal: M 1−x 1−y 0

XMAPLE KÓD

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ A nyeresége maximális, ha 2/3 valószínuséggel ˝ az elso, 1/3-dal a második stratégia szerint játszik. 141/363

Olló – papír – ko˝ Mesterséges Intelligencia

6 Csató Lehel

Szabályok: két játékos játszik egyszerre mutatnak egy ... papírt követ ollót

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe

papír: becsomagolja a követ;


0 1 −1 −1 0 1 1 −1 0

˝ kicsorbítja az ollót; ko:

Negamax Alfabéta

olló: elvágja a papírt


Teljes szimmetria ⇒ nincs optimális stratégia. „Optimális” kevert stratégia: [1/3, 1/3, 1/3]. 142/363

Egy paradoxon

–

Stratégiák

Székely J.G.: Paradoxonok a véletlen matematikájában. Mesterséges Intelligencia

Ketten játszanak: Q és R. Egy vagy két ujjat mutatnak fel;

6

Páros ujj-szám esetén Q fizet R-nek, ellenkezo˝ esetben fordítva;


annyit nyernek/veszítenek, ahány ujjat felmutattak.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Ismételt játékok esetén mi a nyero˝ stratégia?

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Nyereség–mátrix: Q.1 Q.2 R.1 2 −3 R.2 −3 4

Összefoglaló

T r M q = 2r1 q1 − 3r1 q2 − 3r2 q1 + 4r2 q2

Mindegyik játékos úgy játszik, hogy az eredmény ne függjön a másik játékostól, valamint tudva, hogy p2 = 1 − p1 és q2 = 1 − q1 , a játék értéke: V = (12r1 − 7)q1 + (4 − 7r1 ) R választása: 12r1 − 7 = 0. A megoldás: r1 = 7/12, r2 = 5/12, q1 = 7/12, q2 = 5/12 Átlagnyereség: −1/12

143/363

Tizenegyes-rúgások

Példa


Tizenegyes–rúgásn: a játékos rúg, a kapus véd.

6

˝ elmozdul. A kapus a lövés elott

Csató Lehel

˝ dönt. A játékos szintén a lövés elott Jatekelmelet

B K J

B 5 8 9

K 8 4 8

J 9 8 5


Milyen stratégiát kövessenek? ˝ Balra, Középre, vagy Jobbra lehet loni, ˝ a kapus is erre A buntet ˝ ot

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

˝ vetodhet.

Kevert stratégiákat keresünk. Játékos x = [x1 , x2 , 1 − x1 − x2 ] és kapus y = [y1 , y2 , 1 − y1 − y2 ].

Null-összegu˝ játékok

xT M y =

Neumann-tétel kevert stratégiákra Példa

−8y1 x1 − 4y1 x2 + 4y1 − 7y2 x2 + 3y2 + 4x1 − 4x1 y2 + 3x2 + 5 = −x1 (8y1 + 4y2 − 4) − x2 (4y1 + 7y2 − 3) + 4y1 + 3y2 + 5

Összefoglaló

Innen: y1 = 2/5 ; y2 = 1/5 ⇒ y3 = 2/5. (szimmetria okán a kapus ugyanígy kell eljárjon.) 144/363

Tizenegyes-rúgások

Példa


Tizenegyes–rúgásn: a játékos rúg, a kapus véd.

6

˝ elmozdul. A kapus a lövés elott

Csató Lehel

˝ dönt. A játékos szintén a lövés elott Jatekelmelet

B K J

B 5 8 9

K 8 4 8

J 9 8 5


Milyen stratégiát kövessenek? ˝ Balra, Középre, vagy Jobbra lehet loni, ˝ a kapus is erre A buntet ˝ ot

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

˝ vetodhet.

Kevert stratégiákat keresünk. Játékos x = [x1 , x2 , 1 − x1 − x2 ] és kapus y = [y1 , y2 , 1 − y1 − y2 ].

Null-összegu˝ játékok

xT M y =

Neumann-tétel kevert stratégiákra Példa

−8y1 x1 − 4y1 x2 + 4y1 − 7y2 x2 + 3y2 + 4x1 − 4x1 y2 + 3x2 + 5 = −x1 (8y1 + 4y2 − 4) − x2 (4y1 + 7y2 − 3) + 4y1 + 3y2 + 5

Összefoglaló

Innen: y1 = 2/5 ; y2 = 1/5 ⇒ y3 = 2/5. (szimmetria okán a kapus ugyanígy kell eljárjon.) 144/363

Játékok – összefoglaló Mesterséges Intelligencia

Játékok – fontos szemlélteto˝ eszközök:

6

Nincs tökéletes megoldás, tehát közelítenünk kell;

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

Formalizálás: „jó ötlet azon gondolkodni, hogy min kell gondolkodni”;

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Játékok: mint a Formula 1 az autók számára.

145/363

363

Recommend Documents