Kombinatorikus játékelmélet

A kombinatorikus játékelmélet, más néven CGT az alkalmazott matematika és az elméleti informatika egyik ága, amely a kombinatorikus játékokat tanulmányozza, és megkülönböztethető a "hagyományos" vagy "gazdasági" játékelmélettől. A CGT a pártatlan játékok, különösen a Nim nevű kétjátékos játék elméletével kapcsolatban alakult ki, és a kombinatorikus játékok bizonyos típusainak "megoldására" helyezte a hangsúlyt.

Egy játéknak több feltételnek is meg kell felelnie ahhoz, hogy kombinatorikus játék legyen. Ezek a következők:

A játékban legalább két játékosnak kell részt vennie.
A játéknak szekvenciálisnak kell lennie (azaz a játékosok váltják egymást.)
A játéknak tökéletes információval kell rendelkeznie (azaz nincs rejtett információ, mint a pókerben).
A játéknak determinisztikusnak kell lennie (azaz nem lehet véletlenszerű). A szerencse nem része a játéknak.
A játéknak meghatározott számú lehetséges lépéssel kell rendelkeznie.
A játéknak végül véget kell érnie.
A játéknak véget kell érnie, amikor az egyik játékos már nem tud mozogni.

A kombinatorikus játékelmélet nagyrészt a kombinatorikus játékok egy részhalmazának tanulmányozására korlátozódik, amelyek két játékosból állnak, végesek, és van győztesük és vesztesük (azaz nem döntetlenre végződnek).

Ezek a kombinatorikus játékok fákkal ábrázolhatók, amelyek minden egyes csúcsa a fán közvetlenül alatta lévő játék egy adott lépéséből eredő játék. Ezekhez a játékokhoz játékértékek rendelhetők. Ezeknek a játékértékeknek a megtalálása nagy érdeklődésre tart számot a CG teoretikusok számára, ahogyan a játékadagolás elméleti fogalma is. Két játszma összege az a játszma, amelyben minden játékosnak a saját sorában csak a két játszma egyikében kell lépnie, a másikat változatlanul hagyva.

Elwyn Berlekamp, John Conway és Richard Guy az elmélet megalapítói. Az 1960-as években dolgoztak együtt. Megjelent munkájuk a Matematikai játékok győztes útjai címet viselte.

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.