AlegsaOnline.com

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.

Szerző: Leandro Alegsa

28-03-2026

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.

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 misè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} $L$ azok a játékok, amelyekre a bal játékos léphet. R {\displaystyle R} $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 \}} $\{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.