Nim

A nim egy kétszemélyes stratégiai játék, melyben több kupacban kavicsok vannak és a játékosok felváltva vesznek el a megfelelő szabályok szerint. Alapvetően az nyer, aki az utolsó kavicsot vagy kavicsokat elveszi, de van olyan változat is, amelyben éppen azt kell elkerülni, hogy az utolsó kavicsot elvegyük.

Az emberiség vélhetően nagyon régóta játssza ezt a játékot. Azt lehet sejteni, hogy az ókori Kínában lehet a játék ősét megtalálni, de bizonytalanok az erre utaló adatok. A játék első európai említése a 16. századból való. A játék nevének eredete is bizonytalan, egy elég valószínűnek tűnő verzió, hogy a német nimm (vegyél el) szó szolgáltatta az alapot az elnevezéshez. De érdemes észrevenni, hogy ha a NIM szót 180 fokkal elforgatjuk, akkor a WIN (angolul nyerni) szót kapjuk.

Alain Resnais Tavaly Marienbadban című filmje tette híressé. A film címére utalva marienbadi játéknak is hívják.

Egyike az első játékoknak, amiket számítógép is tudott játszani. 1952-ben Herbert Koppel, Eugene Grant és Howard Bailer építettek egy 25 kilogrammos gépet, mely tudott szabályosan játszani és rendszeresen megverte az ellene kiálló embereket.

A játék

A játékot két játékos játssza, a legegyszerűbb esetben két kupac kaviccsal. Ennél kicsit elterjedtebb a három kupacos verzió. A két játékos felváltva vehet el kavicsokat, mégpedig egy kupacból annyit, amennyit jónak lát. Akár az összeset is. Az nyer, aki az utolsó kavicsokat elveszi. De speciális változatban épp ennek ellenkezője a cél, vagyis, hogy az veszít, aki elveszi az utolsó kavicsot.

Az alábbi példa egy lehetséges játék lefolyását mutatja, amit Anna és Béla játszik egymással. Kezdetben három kupac kavics van, rendre 3, 4 és 5 kaviccsal.

Kupacokban      A lépés
lévő kavicsok
száma
A B C
 
3 4 5           Anna elvesz 2 kavicsot A-ból
1 4 5           Béla elvesz 3 kavicsot C-ből
1 4 2           Anna elvesz 1 kavicsot B-ből
1 3 2           Béla elvesz 1 kavicsot B-ből
1 2 2           Anna elveszi a teljes A kupacot
0 2 2           Béla elvesz 1 kavicsot B-ből
0 1 2           Anna elvesz 1 kavicsot C-ből
0 1 1           Béla elvesz 1 kavicsot B-ből
0 0 1           Anna elveszi a teljes C kupacot és nyer.
0 0 0

Nyerő stratégia

A nim játéknak ismert a nyerő stratégiája tetszőleges számú kupaccal és azokban tetszőleges számú kaviccsal.

A legegyszerűbb verzióban két kupac kavics van. Itt a kezdő tud nyerni, ha kezdetben különböző számú kavics van a két kupacban, és a nyerő lépés az, ha a két kupacban lévő kavicsok darabszámát egyenlőre állítja. Ha kezdetben ugyanannyi kavics van a két kupacban, akkor át kell engedni a kezdést. Könnyen látható, hogy a két kupac egyenlővé tétele győzelmet eredményez.

A nyerő stratégia kulcsa a kettes számrendszerbeli, átvitel nélküli összeadás. A játék miatt ezt nim-összegnek is szokták nevezni. Ennek lényege, hogy kettes számrendszerben felírjuk az összeadandó tagokat, majd minden helyiértéken 1-est írunk, ha a számok között páratlan 1-es van, és 0-t, ha páros számú(0 vagy 2 db 1-es van). A nim-összeget megkülönböztetendő a szokásos összeadástól így szokás jelölni: x ⊕ y. Egy konkrét példán nézve:

100 ⊕ 50 =

1 100 100
⊕ 110 010
---------
1 010 110

Vagyis 100 ⊕ 50 = 86.

A nyerő stratégia pedig a következő: úgy kell lépni, hogy a lépés után létrejövő helyzetben a kupacokban lévő kavicsok számának nim-összege 0 legyen. Látható, hogy ha nem 0 ez az összeg, akkor mindig el lehet érni, hogy 0 legyen ez az összeg, és ha 0 összegnél kell lépnünk, akkor feltétlenül úgy fogunk lépni, hogy a lépés után nem lesz 0 az összeg. A véghelyzet az, hogy minden kupacból elfogytak a kavicsok, vagyis minden kupacban 0 kavics van. Vagyis a végső nyerő helyzetben a nim-összeg 0, így követve a fenti stratégiát, el fogjuk ezt érni.

Az előzőekből nem látszik világosan, hogy hogyan kell megtalálni a nyerő lépést hatékonyan. Legyen az i-edik kupacban $a_{i}$ darab kavics. Legyen $b=a_{1}\oplus a_{2}\oplus \dots \oplus a_{n}$. Minden kupac kavicsszámához adjuk hozzá nim-összegzéssel b-t. Figyeljük, hogy melyik kupacnál lesz az így kapott összeg kisebb, mint az eredeti kavicsszám volt. Abból a kupacból kell elvennünk, ahol ez megtörténik, úgy hogy annyi kavics maradjon amennyi a nim összegzéssel kijött.

Nézzük ezt meg egy konkrét példán. Legyen $a_{1}=3,a_{2}=4,a_{3}=5$. Ekkor $b=a_{1}\oplus a_{2}\oplus a_{3}=3\oplus 4\oplus 5=2$.

$a_{1}\oplus b=3\oplus 2=1$

$a_{2}\oplus b=4\oplus 2=6$

$a_{3}\oplus b=5\oplus 2=7$

Csak az első kupac esetében fordul elő, hogy a nim-összeg kisebb, mint az eredeti szám. Emiatt az első kupacból kell elvennünk úgy hogy 1 maradjon, vagyis 2-t.