Kombinatorikus játékok és játékelmélet – definíció, alapok és példák
Kombinatorikus játékok és játékelmélet: részletes definíciók, alapok és szemléletes példák (Nim, játékértékek, játékösszeg) kezdőknek és haladóknak.
A kombinatorikus játékelmélet (röviden CGT) az alkalmazott matematika és az elméleti informatika olyan ága, amely a véges, determinisztikus, teljes információjú, kétjátékos kombinatorikus játékok szerkezetét és stratégiáit vizsgálja. Ezt a területet meg kell különböztetni a „hagyományos” vagy „gazdasági” játékelmélettől, mert itt nem a valószínűségek vagy a vegyes stratégiák, hanem a diszkrét lépések és azok kombinatorikus következményei állnak a középpontban. A CGT eredete különösen a pártatlan játékok — például a Nim nevű játék — elméletének elemzéséhez kötődik: sok eredmény az ilyen típusú játékok "megoldására" irányul.
Képgaléria
1 Kép
Milyen feltételek szükségesek egy kombinatorikus játékhoz?
Ahhoz, hogy egy játékról kombinatorikus játékként beszélhessünk, több feltételnek is meg kell felelnie. Ezeket röviden az alábbiakban foglaljuk össze:
- A játékban legalább két játékos vesz részt (többnyire pontosan kettő).
- A játék szekvenciális: a játékosok felváltva hoznak lépéseket.
- Tökéletes információjú: minden játékállapotot mindkét játékos teljesen ismer.
- Determinista: nincs benne véletlen elem; a szerencse nem része a játéknak.
- Véges számú lehetséges lépés és állapot (a játék időben véget ér).
- A játéknak előbb-utóbb véget kell érnie (nincs végtelen kör).
- A játék vége általában akkor következik be, amikor az egyik játékos már nem tud lépni.
Alapfogalmak és fontos eredmények
A kombinatorikus játékok leírására gyakran használunk játékt fákat: a gyökér a kezdőállapot, az élek a lehetséges lépéseket jelentik, a csúcsok pedig az azokat követő állapotokat. Minden állapothoz rendelhetünk kimeneteli információkat és értékeket, amelyek segítenek eldönteni, melyik játékosnak van nyerő stratégiája.
Alapvető kategorizálás:
- Pártatlan (impartial) játékok: mindkét játékosra ugyanazok a lépések vonatkoznak egy adott állapotban (példa: Nim).
- Partizán (partizan) játékok: a játékosoknak eltérő lépési lehetőségei lehetnek ugyanabban az állapotban (példa: Hackenbush, Domineering).
- Normál végződés (normal play): az nyer, aki az utolsó lépést tudja megtenni. (A misère szabály — „az utolsó veszít” — külön problémákat jelenthet.)
Fontos eredmények és eszközök:
- A Sprague–Grundy tétel (Sprague–Grundy theorem): minden pártatlan kombinatorikus játék megfeleltethető egy Grundy-számnak (más néven nimbernek), és két pártatlan játék összegének értéke a Grundy-számok xor-összegére vezethető vissza. Ez az eredmény a Nim optimalitási stratégiájának általánosítása.
- A játékelméletben definiálnak kimenetelosztási osztályokat (például N-pozíciók, ahonnan a következő játékos nyer; P-pozíciók, ahonnan a második játékos nyer), és ezek egymásra vezethetők vissza a fastruktúra alapján.
- Partizán játékok esetén Conway bevezette a surreális számok és általános játékszámok fogalmát, amelyek lehetővé teszik a játékok algebrai kezelését (összeg, negatív, relatív értékek, „meleg” és „hideg” játékok megkülönböztetése).
- Az összeg (diszjunktív összeg) jelentése: két vagy több komponensből álló játszmában a játékos egy lépést tesz pontosan egy komponensben, a többi komponens állapota változatlan marad; a komponensek értékének kombinációja adja a teljes játszma értékét.
Példák és gyakorlat
Gyakori, jól tanulmányozott példák:
- Nim: több kupac követ, egy lépésben egy kupacból tetszőleges pozitív számú követ vehetünk el. A Sprague–Grundy elmélet ezen játék teljes megoldását adja: a kupacok méretének bináris xor-összege határozza meg a pozíciót.
- Kayles, Wythoff és más pártatlan játékok: mindegyikhez tartozó Grundy-sorozat vizsgálata fontos kutatási irány.
- Hackenbush, Domineering, Go bizonyos egyszerűsített változatai: partizán játékok, ahol a Conway-féle elmélet és a surreális számok adnak elemzési lehetőséget.
- Hex: stratégiai, partizán játék, ahol fontos elméleti fogalom a „strategy stealing” (bizonyos állítások szerint az első játékosnak mindig van győztes stratégiája meghatározott táblaméretek mellett).
Számítási nehézség és alkalmazások
Sok kombinatorikus játék általánosított változata NP-teljes vagy PSPACE-teljes problémává válik; más szóval, a játékok optimális megoldása számításilag nehéz lehet nagy méretekben. Ennek ellenére a CGT módszerei gyakorlati stratégiák, algoritmusok és matematikai struktúrák feltárására szolgálnak, amelyek alkalmazhatók algoritmikus problémákra, mesterséges intelligenciára és játéktervezésre.
Történet és irodalom
A modern kombinatorikus játékelméletet nagyban meghatározta Elwyn Berlekamp, John Conway és Richard Guy, akik az 1960-as években kezdtek együtt dolgozni. Megjelent közös munkájuk a Matematikai játékok győztes útjai címet viselte, és ez a könyv alapművé vált a területnek (angol címe: "Winning Ways for Your Mathematical Plays").
Összefoglalva: a kombinatorikus játékelmélet erős kapcsolatban áll a diszkrét matematikával, a logikával és az algoritmusokkal. Habár sok alapvető játék jól megoldott (különösen a pártatlan játékok esetén a Sprague–Grundy-elv révén), a partizán játékok és a nagy, általánosított változatok még mindig aktív kutatási területet jelentenek.
Definíciók
Az elméletben két játékos van, akiket balnak és jobbnak hívnak. A játék olyan dolog, amely lehetővé teszi a bal és a jobb oldal számára, hogy lépéseket tegyen más játékokra. Például a sakkjátékban van egy szokásos kiinduló felállás. Azonban azt is gondolhatjuk, hogy a sakkjátszma az első lépés után egy másik játék, más felállással. Tehát minden egyes állást játéknak is nevezünk.
A játékok jelölése {L|R}. L {\displaystyle L}
azok a játékok, amelyekre a bal játékos léphet. R {\displaystyle R}
azok a játékok, amelyekbe a jobb játékos léphet. Ha ismered a sakkjelölést, akkor a szokásos sakkfelállás a következő játék
| { a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , b 5 , c 6 , c 5 , N c 6 , ... }. {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} |
A pontok "..." azt jelentik, hogy sok lépés van, ezért nem mindegyik látható.
A sakk nagyon összetett. Jobb, ha könnyebb játékokra gondolunk. A Nim például sokkal egyszerűbben gondolkodik. A Nim-et így játsszák:
- Nulla vagy több számlálóhalom van.
- Egy körben egy játékos annyi figurát vehet el egy kupacból, amennyit csak akar.
- Az a játékos, aki nem tud lépni, veszít.
A Nim legegyszerűbb játéka egyáltalán nem kezdődik számláló nélkül! Ilyenkor egyik játékos sem léphet. Ezt a jelzést {|} jelzi. Mindkét oldal üres, mert egyik játékos sem tud lépni. Az elsőként induló játékos nem tud lépni, így veszít. A CGT-ben az emberek gyakran írják a {|}-t 0 (nulla) szimbólumként.
A következő legegyszerűbb játékban csak egy halom van, egyetlen számlálóval. Ha a bal oldali játékos kezd, akkor el kell vennie a számlálót, a jobb oldali játékosnak pedig nincs lépése ({|}, vagy 0). Ha ehelyett a jobb játékos lép először, a bal játékosnak nem marad több lépése. Tehát mind a bal, mind a jobb oldal léphet a 0-ra. Ez a {{|}|{|}}}, vagy {0|0}. Aki először lép, az nyer. A {0|0}-vel egyenlő játékok nagyon fontosak. Ezeket a * (csillag) szimbólummal írjuk ki.
Kérdések és válaszok
K: Mi az a kombinatorikus játékelmélet?
V: A kombinatorikus játékelmélet (CGT) az alkalmazott matematika és az elméleti informatika egyik ága, amely a kombinatorikus játékokat tanulmányozza, és különbözik a "hagyományos" vagy "gazdasági" játékelmélettől.
K: Milyen feltételeknek kell megfelelnie egy játéknak ahhoz, hogy kombinatorikus játéknak lehessen tekinteni?
V: Ahhoz, hogy egy játékot kombinatorikus játéknak tekintsünk, legalább két játékosnak kell lennie, szekvenciálisnak kell lennie (azaz a játékosok váltják egymást), tökéletes információval kell rendelkeznie (azaz nincs rejtett információ), determinisztikusnak kell lennie (azaz nem lehet véletlen), a szerencse nem lehet része a játéknak, meghatározott számú lehetséges lépésnek kell lennie, a játéknak végül véget kell érnie, és a játéknak akkor kell véget érnie, amikor az egyik játékos már nem tud lépni.
K: Milyen típusú játékokra összpontosít a kombinatorikus játékelmélet?
V: A kombinatorikus játékelmélet nagyrészt olyan kétfős véges játékokra összpontosít, amelyeknek van nyertese és vesztese (azaz nem végződnek döntetlennel).
K: Hogyan ábrázolják az ilyen típusú játékokat?
V: Az ilyen típusú játékok fákkal ábrázolhatók, amelyek minden egyes csúcsa a fán közvetlenül alatta lévő lépésből eredő játékot képviseli.
K: Milyen célokat tűztek ki a CG-elméletírók?
V: A CG teoretikusok céljai közé tartozik az ilyen típusú játékok értékeinek megtalálása, valamint a "játék összeadás" fogalmának megértése, amely azt jelenti, hogy minden játékos csak egy lépést tesz két különböző játékban, és a másik játékost változatlanul hagyja a sora alatt.
K: Ki alapította a CGT-t?
V: Elwyn Berlekamp, John Conway és Richard Guy a CGT megalapítójaként tartják számon a Winning Ways for Your Mathematical Plays című, az 1960-as években megjelent munkájukban.
Kapcsolódó cikkek
Szerző
AlegsaOnline.com Kombinatorikus játékok és játékelmélet – definíció, alapok és példák Leandro Alegsa
URL: https://hu.alegsaonline.com/art/21870