Chapter 3. Kétszemélyes stratégiai játékok és lépésajánló algoritmusok

Stratégiai játékok azok a játékok, melyekben játékosoknak a játék kimenetelére (ellenőrizhető módon) van befolyásuk. Ilyen játékok pl. a sakk, a bridzs, a póker, az üzleti „játékok” mint két vállalat konkurrencia harca, harci „játékok”.

Néhány a játékelméleti kutatásokban fontos név:

1921 E. Borel
1928 Neumann János
1944 Neumann János és O. Morgenstein
1994 Harsányi János (közgazdasági Nobel-díj)

Egy játék leírásához meg kell adni

Osztályozás

A továbbiakban játék alatt kétszemélyes, diszkrét, véges, teljes információjú, determinisztikus, zérusösszegű stratégiai játékot fogunk érteni.

3.1. A játékok reprezentációja

Jelölje a két játékost és , a játékállások halmazát . A játékot az kezdőállásban kezdje . Tegyük fel, hogy a játékosok a játék során felváltva lépnek, és ismerjük az egyes állásokban megtehető lépéseket: . Az lépés egy állásban akkor tehető meg, ha . A játék az állásban véget ér, ha . A szabályok leírják, itt ki a nyerő játékos: , ahol lenne az állásban soron következő játékos (). E játék állapottér-reprezentációja az az négyes, ahol

  • ,

A játék állapottér-repezentációját szemléltető gráf a játékgráf. „Egyenesítsük ki” a játékgráfot fává. A játékfában

  • páros szinteken lévő állásokban a kezdő játékos, páratlan szinteken lévőkben pedig az ellenfele léphet;

  • egy állást annyi különböző csúcs szemléltet, ahány különböző módon a játék során a kezdőállásból eljuthatunk hozzá;

  • véges hosszúságúak az utak, hisz véges játékokkal foglalkozunk.

Ha a játék során állapotból a játékosok valamelyik állapotba érnek, azaz , azt mondjuk lejátszottak egy játszmát. A játszmákat a játékfában a startcsúcsból a levélelemekbe vezető utak szemléltetik. Egy játék játékfája a játék összes lehetséges játszmáját szemlélteti a startcsúcsból induló, a különböző levelekben végződő útjaival.

Definíció

Az párt ÉS/VAGY gráfnak nevezzük:

  • nemüres halmaz, a gráf csúcsainak halmaza,

  • pedig az irányított hiperélek halmaza.

Definíció

Az ÉS/VAGY gráfban a gráf hiperéleinek egy olyan sorozata, ahol a gráf egy hiperútja.