Nim Oyunu ve Sprague-Grundy Teoremi: Her Tarafsız Oyunun Bir Sayısı Vardır

Nim oyunu

Kurallar basit:

1. Masada birkaç yığın kibrit (veya taş, çakıl, jeton).
2. İki oyuncu sırayla oynar.
3. Her hamlede bir oyuncu tek bir yığından, en az 1 nesne alır (istediği kadar).
4. Son nesneyi alan kazanır (normal kural) veya alan kaybeder (misère kural).

Örnek başlangıç: yığınlar (3, 4, 5). İlk oyuncu hangi hamleyi yapmalı?

Cevap: XOR ile çözülür

Charles Leonard Bouton 1901'de Harvard'da matematik dergisinde tarihi makalesini yayımladı: Nim, a Game with a Complete Mathematical Theory. Çözümü olağanüstüydü.

Bouton'un teoremi: Nim pozisyonunda yığın boyutlarını ikili gösterimde XOR'layın. Sonuç 0 ise mevcut hamleyi yapan oyuncu kaybeder (kayıp pozisyon); 0 değilse kazanır (kazanan pozisyon).

Örnek (3, 4, 5):

• $3 = 011_2$
• $4 = 100_2$
• $5 = 101_2$
• XOR: $011 \oplus 100 \oplus 101 = 010 = 2$

Sonuç 2 ≠ 0, dolayısıyla ilk oyuncu kazanır. Kazanma hamlesi: XOR'u 0'a indirecek yığını bul. $5 \oplus 2 = 7$ — yığın 5'ten almak istesek 7'ye çıkarması gerekir, imkânsız. $4 \oplus 2 = 6$ — yığın 4'ten 6'ya çıkmamız gerekir. $3 \oplus 2 = 1$ — yığın 3'ten 1'e indir (yani 2 al). Sonra yığınlar (1, 4, 5), XOR = 0. Rakip artık kayıp pozisyondadır.

Bu zarif çözüm, basit ikili aritmetikle oyunun tüm strateji ağacını çözer.

Sprague-Grundy teoremi: genelleştirme

Nim sadece bir özel oyundur. Roland Sprague (Almanya, 1935) ve Patrick Michael Grundy (Britanya, 1939) birbirinden bağımsız olarak Bouton'un fikrini muazzam genelleştirdiler:

Sprague-Grundy teoremi: Her tarafsız sonlu oyun Nim oyununa eşdeğerdir. Yani her oyun pozisyonunun bir Grundy sayısı (Nim değeri) vardır; iki oyunun toplamı, Grundy sayılarının XOR'una sahip bir Nim yığınına eşittir.

Tarafsız oyun: her iki oyuncunun aynı hamleleri olduğu, şans içermeyen, sonlu oyun (Nim, Hackenbush, Wythoff oyunu, Northcott oyunu, vb).

Önemi: her tarafsız oyunu, tek bir sayıya indirgemek. Birden fazla oyunu paralel oynuyorsanız (örneğin iki Nim masası), toplam strateji = Grundy XOR'u.

Grundy sayısı hesaplanması

Bir oyun pozisyonunun Grundy sayısı (veya mex değeri):

$G(P) = \text{mex}\{G(P') : P \to P' \text{ geçerli hamle}\}$

Burada mex = "minimum excludant" — kümede olmayan en küçük sayı.

Örnek: $\text{mex}\{0, 1, 3\} = 2$, $\text{mex}\{1, 2, 3\} = 0$.

Nim yığını $n$ taşının Grundy sayısı = $n$. Bunu kanıtlayalım: $n$ taşlık yığından gidebileceğimiz pozisyonların Grundy sayıları $\{0, 1, ..., n-1\}$. Mex = $n$.

Oyunların toplamı

İki oyun $A$ ve $B$'yi paralel oynamak (her oyuncu sırasında istediği oyunda hamle yapar) ile oyun toplamı denilen yeni bir oyun elde edilir.

Sprague-Grundy: $G(A + B) = G(A) \oplus G(B)$ (XOR).

Bu temel formül, çoklu oyunları analiz etmeyi mümkün kılar.

Wythoff oyunu — bir başka klasik

İki yığın taş. Bir hamlede: bir yığından istediğin kadar AL veya her iki yığından eşit sayı al. Son alan kazanır.

Kayıp pozisyonlar (yığın çiftleri): $(0,0), (1,2), (3,5), (4,7), (6,10), \ldots$

Bu sayılar Beatty dizisi ile verilir; altın oran $\phi$ ile ilgili:

$a_n = \lfloor n \phi \rfloor, \quad b_n = \lfloor n \phi^2 \rfloor$

Wythoff oyununun "Nim değeri" ile XOR yöntemi de uygulanır.

Conway'in Surreal Numbers (1976)

John Horton Conway, Sprague-Grundy'yi olağanüstü bir genelleştirmeye götürdü: Surreal sayılar (sürreal sayılar). Her kısmi taraf (partisan) oyun, bir sayı veya benzer cebirsel nesne ile ifade edilir. Surreal Numbers ve sonra Winning Ways for Your Mathematical Plays (Berlekamp-Conway-Guy, 1982) bu çerçeveyi sundu.

Conway, Go ve diğer oyunların bitiş aşamalarını sayısal toplamlar olarak analiz etti — günümüzde Go uzmanları bu teoriyi kullanır.

Modern uygulamalar

1. Bilgisayar oyun yapay zekası: Nim ve türevleri, AI eğitiminde "saf strateji" örneklerdir.
2. Kombinatoryal optimizasyon: bazı çizelgeleme problemleri tarafsız oyunlara çevrilir.
3. Şifreleme: bazı oyun-teorik protokollerde Sprague-Grundy.
4. Yapay zeka — pekiştirme öğrenme: optimal politika bulmanın matematiksel arka planı.
5. Matematik olimpiyatları: her yıl Nim varyantları sorulur.

Cevap: orijinal soru

Başlangıç (3, 4, 5) — ilk oyuncu kazanır. Hamle: 3'lük yığını 1'e indir (2 al). Geri (1, 4, 5), XOR = $001 \oplus 100 \oplus 101 = 000$. Rakip artık kazanamaz; mükemmel oynanırsa siz kazanırsınız.

Sonuç

Nim ve Sprague-Grundy teoremi, basit oyunların derin matematik gizlemesinin muhteşem bir örneği:

• Kurallar ilkokul seviyesi.
• Strateji ikili XOR ile çözülür.
• Tüm tarafsız oyunları kapsayan bir teoremle birleşir.
• Modern AI ve algoritma teorisinin alt yapısında.

Matematik bazen "oyun" değildir, bütün oyunların ardındaki yapıdır.