Ugrás a tartalomhoz

combinatorial game theory

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

combinatorial game theory (tsz. combinatorial game theories)

  1. (informatika) Combinatorial Game Theory (CGT), magyarul kombinatorikus játékelmélet, a játékelmélet egyik ága, amely olyan kétjátékos játékokat vizsgál, amelyek:
  • teljes információval rendelkeznek (nincs rejtett adat),
  • nincs véletlen elemük (pl. kockadobás),
  • és zéróösszegűek (ami az egyik játékos nyeresége, az a másik vesztesége),
  • ahol a játék véges számú lépés után biztosan véget ér.

Ez az elmélet matematikai szempontból elemzi, hogy melyik játékos nyerhet biztosan egy adott állásból, tökéletes stratégiával játszva.


🧩 Példák klasszikus kombinatorikus játékokra

Játék Leírás
Nim Halmazokból (kupacokból) vehetünk el elemeket
Sprouts Kézzel rajzolható topológiai játék
Domineering Dominók lerakása váltakozó irányban
Chomp Csokoládétábla-evés tiltott mezővel
Hackenbush Színes gráf alapú játék
Hex Területösszekötés hatszögrácson


🧠 Alapfogalmak

🎯 Játékállapot (game position)

A játék aktuális állása, amit matematikai objektumként értelmezünk.

🔁 Lépés (move)

A szabályok szerinti változtatás egy állapoton, amellyel a játékos a következő állásba juttatja a játékot.

🔚 Terminális állapot

Olyan állás, ahonnan már nincs érvényes lépés – az utolsó játékos nyer.

🔁 Játék összege (disjunktív összeg)

Több játék kombinálása úgy, hogy minden lépésnél csak egy játékban lehet lépni.


🏁 Játékos típusok

  • Left és Right játékos (általános CGT terminológia)
  • A játékosok váltakozva lépnek
  • Az utolsó lépő nyer (“normal play”) – ez az alapértelmezett verzió


🔢 Sprague–Grundy tétel

Ez a tétel a “Nim-értékekkel” (vagy Grundy-számokkal) dolgozik:

  • Minden játékállapothoz hozzárendelhető egy nemnegatív egész szám (nimber).
  • Két játék kombinált értéke a nim-összegük (XOR).
  • A játékos, aki nulla Grundy-értékkel kezd, veszített, ha az ellenfél tökéletesen játszik.


📐 Példa: Nim játék

Tételezzük fel, hogy 3 kupac van: A = 3, B = 4, C = 5

Nim-összeg:

3 ⊕ 4 ⊕ 5 = 011 ⊕ 100 ⊕ 101 = 010 (azaz 2)

Ha a nim-összeg ≠ 0 → nyerhető állás Ha a nim-összeg = 0 → vesztes állás


🛠️ CGT felépítése

A CGT nemcsak a győztes meghatározására szolgál, hanem strukturált algebrai műveleteket is definiál a játékokon, pl.:

  • összeadás (játékhalmazok kombinálása)
  • negáció (játékosok szerepcseréje)
  • értékelés (játék nehézsége, előny értékelése)

Ezek segítségével algebrai struktúrákat hoz létre (pl. nimber mező).


🧮 Alkalmazási területek

Terület Használat
🎲 Játéktervezés Játékmechanika kiegyensúlyozása
🎓 Oktatás Kombinatorikai gondolkodás fejlesztése
🧠 AI kutatás Tökéletes játékstratégiák modellezése
🧩 Matematikai logika Végesállapotú rendszer analízise
🧬 Informatika Algoritmusok optimalizálása, pl. XOR műveletek


📚 Fontos nevek

  • John H. Conway – a CGT megalapítója, On Numbers and Games (1976)
  • Elwyn Berlekamp, Richard Guy – Winning Ways for Your Mathematical Plays (1982)
  • Sprague & Grundy – a nevükkel fémjelzett tétel


🧩 TL;DR

A kombinatorikus játékelmélet matematikai módszerekkel elemzi a teljes információval rendelkező, véges, kétszemélyes, zéróösszegű játékokat. Segítségével meghatározható, hogy melyik játékos tud biztosan nyerni adott állásból – tökéletes játék mellett.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=combinatorial_game_theory&oldid=3498390”