Cutcake (Çözüm)

Önce basit durumları ele alalım. 1x1 oyun için oyuna başlayan kaybeder çünkü yapılabilecek hamle yoktur. $Mx1$ boyutlu oyunları her zaman R kazanır, çünkü L'nin yapacak hamlesi yoktur. Benzer şekilde $1xN$ boyutlu oyunları da her zaman L kazanır, çünkü R'nin yapacağı hamle yoktur.

Oyunda ortaya çıkan poziysonların sayısal değerlerini nasıl hesaplandığını göstermeye çalışacağım. Bu sayısal değerler ile oyunu kimin kazanacağını hesaplayabileceğiz ama bu yazıda kazanmak için hangi algoritmanın kullanılacağını vermeyeceğim.

Oyuna başlayan oyuncunun kaybettiği pozisyonlara 0 (sıfır) pozisyonu diyelim. Eğer oyuna kim başlarsa başlasın L kazanıyorsa pozisyonun değeri pozitif olsun. Oyuna kim başlarsa başlasın R kazanıyorsa da pozisyonun değeri negatif olsun. 

Bu giriş sonucunda 1x1 pozisyonunun değeri 0 olur. $1xN$ boyutlu pozisyonun değerini de $N-1$ ile gösterelim, sonuçta L oyuncusunun $N-1$ hamlesi var, buna karşı R oyuncusunun hiçbir hamlesi yok. Ayrıca $N>1$ olduğu sürece bu pozisyonun değeri de pozitiftir. Benzer mantıkla $Mx1$ pozisyonunun değeri de $-(M-1)$ olacaktır.

Genelde verilen bir pozisyonda oyuna iki oyuncu da başlayabileceği için pozisyonun değerini başka bir notasyonla gösterelim:

$\left\{a|b\right\}$ notasyonu ile yapılacak hamlenin pozisyonu hangi değere taşıdığını gösteriyoruz. Eğer hamle sırası L'de ise yapacağı hamle ile pozisyonu $a$ değerine, hamle sırası R'de ise $b$ değerine getirebiliyor. Bu notasyon aynı zamanda sürreel sayıların da notasyonudur ve bu sayılar oyunları incelemede önemli bir yer tutar. Bu problemin çözümünde bu sayıların oldukça basit özelliklerine ihtiyaç duyacağız. Bu özelliklerin doğruluklarını göstermeye çalışmayacağım.

Oyun sırasında pozisyonun değerini alt oyunların pozisyonlarının toplamı şeklinde yazabiliriz. Alt oyundan kastedilen şu: Örneğin $2x2$ şeklinde bir oyuna başlayalım. L ilk hamleyi (yapacak tek hamlesi vardır) yaptığında elimizde iki tane $2x1$ şeklinde parça olur. Bu pozisyonu iki tane ayrı oyunmuş (alt oyunlar) gibi değerlendirebiliriz. Sırası gelen oyuncu istediği alt oyunu seçer ve orada kurallara uygun bir hamle yapar.

Bu tanıma göre iki alt oyundan oluşan pozisyonun değerini $\left\{a|b\right\} + \left\{c|d\right\}$ şeklinde gösterebiliriz.

Tabii ki verilen bir pozisyonda bir oyuncunun birden fazla hamlesi olabilir. Her bir hamle farklı değerlerdeki pozisyonlara yol açabilir. Bunu aynı notasyonda şöyle gösteriyoruz:

$\left\{a, b, c, ...|d, e, f, ...\right\}$

Yani verilen pozisyonda L yapacağı hamleye göre pozisyonu $a$, $b$, $c$ ... değerli pozisyonlarından birine dönüştürebilir. Aynı şekilde R de hamle kendisindeyse pozisyonu $d$, $e$, $f$ ... değerli bir pozisyona getirebilir.

Şimdi bu en genel notasyona göre pozisyonun değerinin nasıl hesaplandığını görelim. Bu değer kısaca soldaki değerlerin hepsinden büyük olan ve sağdaki değerlerin hepsinden küçük olan en "basit" sayıdır. En basit sayıyı bulmak için de iki kural kullanıyoruz:

• Eğer yukarıdaki şartı sağlayan bir tam sayı varsa, o zaman en basit sayı bu sayılar içinde sıfıra en yakın olanıdır.
• Eğer yukarıdaki şartı sağlayan bir tamsayı yoksa o zaman en basit sayı bu şartı sağlayan ve paydası 2'nin en küçük kuvveti olan rasyonel sayıdır.

Örnekler:

$\left\{0|1\right\}  = \frac {1}{2}$

$\left\{-5|2 \frac {5}{8} \right\}  = 0$

$\left\{ \frac {1}{4} | \frac {5}{16} \right\} = \frac {9}{32}$

Sanırım cutcake için çözüm tablosunu oluşturmaya yetecek araç ve gereçlerimiz var artık.

$1x1$ için pozisyon değeri : $\left\{|\right\}  = 0$

$1xN$ için pozisyon değeri: $\left\{N-2|\right\}  = N-1$

$Mx1$ için pozisyon değeri: $\left\{|M-2\right\}  = -(M-1)$

$2x2$ için pozisyon değeri: $\left\{-2|2\right\}  = 0$

$2x3$ için pozisyon değeri: $\left\{-1|4\right\}  = 0$ (L oynayınca $2x1$ ve $2x2$ pozisyonları bırakır. $2x2$ 0 değerine sahiptir, $1x2$ de -1. R oynarsa iki tane $1x3$ alt oyunu yapacaktır. Bunların toplam değeri de $2 + 2 = 4$ olacaktır.)

$3x2$ için pozisyon değeri: $\left\{-4|1\right\} = 0$ (L oynayınca iki tane $3x1$ alt oyun pozisyonları bırakır. Bunların toplam değeri de $(-2) + (-2) = -4$ olacaktır. R oynarsa $2x1$ ve $2x2$ pozisyonları bırakır. $2x2$ 0 değerine sahiptir, $1x2$ de 1.)

$3x3$ için pozisyon değeri: L oyuna başlarsa bir tane $3x1$ ve bir tane $3x2$ alt oyunu bırakır. Bunların değeri de sırasıyla -2 ve 0 olacaktır. Bu poziszonların toplam değeri de $-2 + 0 = -2$'dir.  Eğer oyuna R başlarsa bir tane $1x3$ ve bir tane $2x3$ alt oyunu bırakacaktır. Bunların da değeri sırasıyla 2 ve 0'dır. Bu pozisyonlar da $2 + 0 = 2$ toplamını vermektedir. O zaman ilk pozisyonun değeri $\left\{-2|2\right\}= 0$ olur.

$4x2$ için pozisyon değeri: L oyuna başlarsa yapabileceği iki hamle var. Ya oyunu $2x1$ ve $2x3$ pozisyonlarına getirecek ya da iki adet $2x2$ alt oyunu yaratacak. Oyuna R başlarsa tek hamlesi var ve iki adet $1x4$ pozisyonu yaratmak zorunda. Bu pozisyonların değerlerini daha önce hesaplamıştık. Bunları kullanarak başlangıç pozisyonunun değerini şöyle yazabiliriz. $\left\{-1 + 0, 0 + 0|3+3\right\}= 1$

Bu adımları daha büyük oyunlara uyguladığımızda aşağıdaki gibi bir tablo elde ederiz. Tabloda kalın yazılmış sayılar oyunun kaç satır ve sütundan oluştuğunu gösteriyor. Normal yazılmış sayılar da bu oyunun değerini.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
2	-1	0		1		2		3		4		5		6
3	-2
4	-3	-1		0				1				2
5	-4
6	-5	-2
7	-6
8	-7	-3		-1				0
9	-8
10	-9	-4
11	-10
12	-11	-5		-2
13	-12
14	-13	-6
15	-14

Çözümde kullanılan yöntemi ve tabloyu kaynakçada belirtilen kitaptan aldım.

Kaynakça: 

Winning Ways for your Mathematical Plays, Elwyn R. Berlekamp, John H. Conway, Richard K. Guy