Her güzel oyun bir NİM oyununa eşdeğerdir

Ali NESİN

Doktora yaptığım okulun en büyük odası "toplumsal etkinliklere" ayrılmıştı. Bu odanın hemen yanında küçücük bir çay ocağı vardı. Matematikçiler çalışmaktan bunaldıklarında, sohbet etmek istediklerinde o odaya gelip dinlenirlerdi. Kimi bütün gününü o odada geçirirdi. Doktora tezlerini o odada yazanlar bile vardı. Oysa her öğrenciye ayrı bir çalışma odası verilmişti. Ama çay odasının ayrı bir havası, kendine özgü bir kokusu vardı; kitap, çay, kahve ve tebeşir tozu alaşımı, doyum olmaz bir koku...

Çay odasının başlıca iki etkinliği matematik ve oyundu. Dans partileri düzenlediğimiz, doğum günlerini kutladığımız, bayramlarda yemek yediğimiz, içki içtiğimiz olurdu ama gene de bu etkinliklerin hiçbiri matematik ve oyun denli bu odanın karakterini belirlememiş, havasına yerleşmemişti. Araştırma konularında ilginç ya da zor problemlerle karşılaşan öğrenciler problemlerini öbür matematikçilere anlatırlar, onlara danışırlardı. Duvarı boydan boya kaplayan 5-6 metre genişliğinde ko- caman bir karatahta vardı. O karatahtada onu aşkın matematikçinin çalıştığı olurdu. Kimi zaman aynı problem üzerine... Kimileyin, bir matematikçi ilgisini çeken bir bilimsel yazıyı öbürlerine anlatırdı. Okula yeni girmiş doktora öğrencileri bitirmek üzere olanlara sorular sorarlardı. Ya da bir profesörün dersi tartışılır, zor bölümler aydınlığa kavuşurdu. Haftada bir gece de o odada aramızdan biri araştırma konusunu anlatırdı. Sanırım biz öğrenciler öğrendiklerimizin çoğunu o odada öğrendik. Hergün akşamüstü saat dörtte o odada çay, kahve ve kek ve- rilirdi. İşte o zaman odanın keyŞne doyum olmazdı. Elliye yakın öğrenci ve hoca odaya doluşurdu. Büyük matematikçilerin çay içişlerini, kek yiyişlerini seyrederdik. Nedense onların çayları ve kekleri bizimkilerden çok daha lezzetliymiş gibi gelirdi bize.

Odanın ikinci önemli etkinliği oyundu. Aslında matematikle oyunu birbirinden ayırmak pek doğru değil ya... Matematikçilerin büyük çoğunluğu oyunbazdır, hiç oyun oynamayanların bile araştırmalarına yaklaşımı bir oyuncunun oyuna yaklaşımından pek farklı değildir çoğu zaman. Her türden oyun oyna- nırdı o odada: satranç, briç, tavla, go, poker (geceleri ve gizli gizli, ama az parasına, zaten paramız mı vardı!) sık oynadığımız klasik oyunlardı. Bu oyunların dışında az bilinen ilginç oyunlar da oynardık. Örneğin "negatif satranç".

Negatif satrançta kaybeden kazanır, kazanan kaybeder. Almak zorunlu, şah alındığında oyun bitmez (dolayısıyla şah çe- kildiğinde "şah" demenin anlamı ve gereği yok) ve hiç askeri kalmayan oyuncu oyunu kazanır.

Oynadığımız bu tür oyunlarda amacımız oyun oynamak değildi. Gerçek amacımız oyunun çözümlemesini (analizini) yapmak, hangi oyuncunun kazanacağını, yani hangi oyuncunun kazanan stratejisinin olduğunu, bunu bulamasak bile en iyi oyun stratejisini bulmaktı. Örneğin, negatif satrançta, beya- zın, şimdi anımsayamadığım1 bir hamleyle oyuna başladığında, oyunu kaybedeceğini aşağı yukarı kanıtlamıştık (siyah akıllıca oynarsa elbet.)

Kazanan strateji nedir? Örneğin Matematik ve Korku başlıklı yazıdaki birinci oyunda (sayfa 100-101), birinci oyuncunun kazanan stratejisi vardır. İkinci oyuncu ne oynarsa oynasın, bi- rinci oyuncuyu kazandıran bir oyun vardır. (Birinci oyuncunun hamleleri ikinci oyuncunun hamlelerine göre değişir elbet.)

Sonlu ve saklı bilgisi olmayan oyunlara değgin bildiğimiz bir teorem vardı. Bu teoremi açıklamadan önce teoremde kul- lanacağımız terimleri açıklayayım.

Eğer bir oyun her zaman sonlu sayıda hamlede bitiyorsa ve oyunun her evresinde, hamle sırası gelen oyuncunun sonlu ta- ne hamle seçeneği varsa, o oyuna sonlu oyun denir. Örneğin satranç sonlu bir oyundur. Çünkü satrancın her anında her oyuncunun sonlu tane seçeneği vardır ve her satranç oyunu ya iki oyuncudan birinin yengisiyle ya da beraberlikle biter. Pişti, poker gibi kâğıt oyunları biter, yani sonlu oyunlardır. Öte yandan tavla sonlu bir oyun değildir, her iki oyuncunun da bi- rer kırığı olabilir ve -kuramsal olarak, uygulamada olmasa bile- sonsuza değin gele atabilirler.

Eğer bir oyunda, her oyuncu kendisinin ve öbür oyuncunun gelecekte yapabileceği (ve yapamayacağı) bütün hamleleri bilebiliyorsa, o oyunun saklı bilgisi olmadığı söylenir. Satrançta saklı bilgi yoktur. Öte yandan tavlada saklı bilgi vardır. Atıla- cak zarı iki oyuncu da bilmez. Pokerde, piştide ve briçte de saklı bilgi vardır, öbür oyuncunun elindeki kâğıtları bilemeyiz.

Şimdi bildiğimiz teoremi yazabiliriz:

Teorem 1. Eğer iki kişi arasında oynanan bir oyun sonluysa ve oyunun saklı bilgisi yoksa ve oyun beraberliğe izin vermiyorsa, iki oyuncudan birinin kazanan stratejisi vardır.

Satrançta beraberlik olduğundan, satranca bu teoremi uygulayamayız. Öte yandan, beraberlik durumunda siyahın ka- zandığını varsayacak olursak, Teorem 1’den şu sonuç çıkar:

Teorem 1’in Bir Sonucu. Satrançta ya beyazın kazandığı ya da siyahın en az berabere kalabildiği bir strateji vardır.

Beyazın mı yoksa siyahın mı böyle bir stratejisi olduğu bi- linmiyor. Satranç öylesine karmaşık bir oyun ki bu varolduğu bilinen strateji bilgisayarlar yardımıyla bile bulunamıyor.

Bu teoremin kanıtı pek zor değildir. Yazının sonunda kanıtını bulabilirsiniz.

Bildiğimiz ikinci bir teorem daha vardı. Satrançta siyahlar beyaz askerlerle oynayamazlar. Beyazlar da siyah askerlere dokunamazlar. Yani satrançta bir oyuncunun yapabileceği, öbür oyuncunun (sıra kendisinde olsaydı) yapamayacağı hamleler vardır. Bir oyuncu için yasal olup da öbür oyuncu için yasal olmayan hamlelerin olmadığı oyunlara tarafsız oyun denir. Örneğin üç taş oyunu tarafsız bir oyundur.

Sonlu, tarafsız, beraberlikle bitmeyen ve saklı bilgisi olmayan oyunlara güzel oyun diyelim. Artık bildiğimiz teoremi açıklayabiliriz:

Teorem 2. Her güzel oyun bir NİM oyununa eşdeğerdir.

NİM oyunlarının ne olduğunu birazdan anlatacağım, ama önce "eşdeğer" teriminin anlamını açıklayayım. İkinci teoreme göre, bir "güzel oyun"da kazanan stratejisi olan oyuncuyu bul- mak, bir NİM oyununda kazanan stratejisi olan oyuncuyu bul- mak kadar zordur. Yani G bir güzel oyunsa, öyle bir NİM (oyunu) vardır ki, bu NİM’de kazanan strateji bulunduğunda, G oyununun da kazanan stratejisi bulunur.

NİM oyunlarının tanımını bir örnek- le verelim. İlk örneğimiz (1,0,2,0,0,1)’lik NİM oyunu. Bu oyunu oynamak için bir kâğıt parçasına yandaki şekli çizin.

Her oyuncu sırası geldiğinde aynı sı- radan ardarda gelen noktaları silebilir. Örneğin birinci oyuncu son sıranın sağ- dan ikinci, üçüncü ve dördüncü noktala- rını silebilir. Oyun o zaman yandaki du- rumu alır.

Şimdi sıra ikinci oyuncuda. İkinci oyuncu son sıranın soldan ikinci ve altıncı noktalarını bir çırpıda silemez. Çünkü bu noktalar artık ardarda gelmiyor, aradaki noktalar silinmiş. Aynı neden- den ikinci sıranın birinci ve üçüncü noktalarını da silemez. Ama ikinci sırayı tümden silebilir. Ya da ikinci sıranın sağındaki iki noktayı silebilir. Hiç nokta silmemezlik edemez, her oyuncu en az bir nokta silmeli (yoksa oyun sonlu olmazdı!) Diyelim ikinci oyuncu alttan ikinci sırayı tümüyle sildi. Oyun yandaki duruma gelir.

Şimdi sıra gene birinci oyuncuda...

En son hamleyi yapan, yani en son noktayı silen oyuncu oyunu kaybeder.

Yukardaki NİM oyununa (1, 0, 2, 0, 0, 1)’lik NİM oyunu demiştik, çünkü bu NİM oyununa ile başladık.

1 tane 1 noktalık sıra

0 tane 2 noktalık sıra

2 tane 3 noktalık sıra

0 tane 4 noktalık sıra

0 tane 5 noktalık sıra

1 tane 6 noktalık sıra

ile başladık.

Örneğin (3, 2, 0, 0, 1, 2)’lik NİM yandaki gibi başlar.

Görüldüğü gibi her NİM oyunu her hamleden sonra bir başka NİM oyununa dönüşüyor. Yukarda, örnek olarak sunduğumuz (1, 0, 2, 0, 0, 1)’lik NİM, birinci oyuncunun ilk hamlesinden sonra (2,1,2)’lik NİM’e dönüşmüş. İkinci oyuncunun hamlesinden sonraysa (2,1,1)’lik NİM’e dönüşmüş. Bu, genel olarak her oyun için geçerlidir. Her oyun, her hamleden sonra bir başka oyuna dönüşür.

NİM oyunlarının çözümlemesi pek kolay değildir. Ancak bazı kolay NİM’lerin analizini yapabiliriz.

(n)’lik bir NİM’i ele alalım. Bu oyunda n tane bir noktalı sı- ra vardır ve bu oyunu oynamak için zekâya gerek yoktur. Her oyuncunun ancak bir hamlesi vardır: bir noktayı (ya da bir sı- rayı, aynı şey) silmek. Eğer n çiftse birinci oyuncu, tekse ikinci oyuncu kazanır elbette. Bunu cebirsel olarak şöyle gösterelim:

K(2n) = 1 ve K(2n+1) = 0.

Bu, şu demektir: (2n)'lik NİM’leri birinci oyuncu, (2n+1)’lik NİM’leri ikinci oyuncu kazanır.

Şimdi (n, m)’lik NİM’lere bakalım. Bu oyunları kim kaza- nır? Daha doğrusu kimin kazanan stratejisi vardır? Bu oyunlar- da n tane 1 noktalı sıra ve m tane 2 noktalı sıra var. Yani ol- dukça kolay bir oyun. Ama herhangi bir NİM oyunu, oyunun bir aşamasında (n, m)’lik bir NİM oyununa dönüşebilir. Bu nedenden dolayı (n, m)’lik NİM’leri hangi oyuncunun kazanacağını bilmek önemlidir.

Eğer m = 0 ise, yani hiç iki noktalı sıra yoksa, bu aslında (n)’lik bir NİM’dir ve bu oyunların çözümlemesini yukarda yapmıştık.

Şimdi de (n, 1)’lik NİM’lere bakalım. n tane 1 noktalı sıra ve bir tane 2 noktalı sıra var. Bu durumda ilk oynayan kazanır. Neden? Şu nedenden: İlk oynayan oyuncu, ikilik sıradan bir ya da iki nokta silerek oyunu ister (n+1)’lik, ister (n)’lik NİM’e dönüştürebilir. Hangisini yapmalı? Eğer n çiftse, ikilik sıradan bir nokta silip oyunu (n+1)’lik NİM’e dönüştürür. n+1 tek ol- duğundan, bu durumda oyunu kazanır. Eğer n tekse, ikilik sı- rayı tümüyle silip ortadan kaldırmalı. Böylece oyun (n)’lik NİM’e dönüşür. n tek olduğundan gene oyunu kazanır.

Örneğin (5, 1)’lik NİM’de ikilik sıra tümüyle silinmeli. Öte yandan (6, 1)’lik NİM’de ikilik sıranın yalnızca bir noktası si- linmeli.

Böylece,

K(n, 1) = 1 (1)

eşitliğini bulmuş olduk. Daha önce de

K(2n, 0) = 1 (2)

ve eşitliklerini bulmuştuk.

K(2n+1, 0) = 0 (3)

Şu teoremi kanıtlayacağız:

Teorem 3. m > 0 olsun.

a) Eğer n ve m çiftse K(n, m) = 0’dır.
b) Eğer n ve m’den en az biri tekse K(n, m) = 1’dir.

Teoreme göre n ve m çiftse (m > 0), ikinci oyuncunun kaza- nan stratejisi vardır. Eğer n ve m sayılarından en az biri tekse, birinci oyuncunun kazanan bir stratejisi vardır. Yani K(n, m) sayısı n+m sayısının tekliğine ve çiftliğine göre değişir.

Görüldüğü gibi n ve m sayıları rastgele seçilirse, birinci oyuncu daha sık kazanacak.

Teorem 3’ün Kanıtı: m > 0 olsun. (n, m)’lik bir NİM’de hamle seçenekleri nelerdir? Sırası gelen oyuncunun üç seçeneği vardır:

1) Eğer bir noktalık bir sıra varsa, yani n > 0 ise, sırası ge- len oyuncu o bir noktalık sırayı silerek, oyunu (n–1, m)’lik NİM’e dönüştürebilir.

2) Sırası gelen oyuncu iki noktalık bir sırayı silerek, oyunu (n,m–1)’lik NİM’e dönüştürebilir.

3) Sırası gelen oyuncu iki noktalık bir sıradan bir nokta si- lerek oyunu (n+1, m–1)’lik NİM’e dönüştürebilir.

Eğer bu üç oyundan birinde ikinci oyuncu kazanıyorsa ilk hamleyi yapan oyunu kazanır. Bu dediğimi şöyle açıklamaya çalışayım. Birinci oyuncuya A diyelim, ikinci oyuncuya da B. Sıra A’da. Diyelim A, NİM oyununu ikinci oyuncunun kazanabileceği bir duruma getirdi. Bu yeni oyuna B başlayacağından, bu yeni oyunda ikinci oyuncu A’dır. Demek ki A’nın B’ye oy- nasın diye bıraktığı oyunu A kazanır.

Öte yandan bu üç oyunu da birinci oyuncu kazanıyorsa, ilk hamleyi yapan kaybeder. Çünkü ilk hamleyi yapan oyuncu, yani A, öbürüne kazanabileceği bir oyun bırakacaktır, başka se- çeneği yoktur.

Yani K(n–1, m) = 0 ise, ya da K(n, m–1) = 0 ise, ya da K(n+1, m–1) = 0 ise, (n, m)’lik NİM’i oyuna ilk başlayan oyun- cu kazanır: Yukardaki üç sayıdan hangisi 0 ise, birinci oyuncu oyunu o oyuna dönüştürür. Öte yandan bu üç sayıdan birinin 0 olması demek, bu üç sayının çarpımının 0 olması demektir. Bu üç sayıdan hiçbiri sıfır değilse, birinci oyuncunun yapabileceği pek bir şeyi yok demektir. İkinci oyuncu oyunu kazanır. Birinci oyuncunun yapabileceği tek şey, ikinci oyuncunun hata yapacağını umarak, oyunu çözümlemesi zor bir duruma sokmalıdır. Bu üç sayıdan hiçbirinin sıfır olmaması demek, yani hepsinin 1 olması demek, bu üç sayının çarpımının 1 olması demektir.

Ne bulduk? Şunu bulduk:

Eğer K(n–1,m)K(n,m–1)K(n+1,m–1) = 1 ise, K(n,m) = 0’dır.

Eğer K(n–1,m)K(n,m–1)K(n+1,m–1) = 0 ise, K(n,m) = 1’dir. Burada küçük bir teorem kanıtladık:

K(n, m) = 1 – K(n–1, m)K(n, m–1)K(n+1, m–1) (4)

Ancak bu eşitlikte n > 0 varsaydığımızı unutmayalım. n = 0 ise, yukardaki formülü uygulayamayız, çünkü (–1, m)’lik NİM yok. Olmasın! Biz de

K(–1, m) = 1 (5)

olarak tanımlarız. Böylece (4) eşitliği bir anlam kazanır ve iyi bir anlam kazanır, yani formül n = 0 iken de doğrudur.

(1, 2, 3, 4, 5) formüllerini kullanarak K(n, m)’yi hesaplayabiliriz:

K(0,2) = 1 – K(–1,2)K(0,1)K(1,1) = 1 – 1´1´1 = 0

K(1,2) = 1 – K(0,2)K(1,1)K(2,1) = 1 – 0´1´1 = 1

K(2,2) = 1 – K(1,2)K(2,1)K(3,1) = 1 – 1´1´1 = 0

K(3,2) = 1 – K(2,2)K(3,1)K(4,1) = 1 – 0´1´1 = 1

K(4,2) = 1 – K(3,2)K(4,1)K(5,1) = 1 – 1´1´1 = 0 ...

Bu değerleri bulmak için bir önce bulduğumuz değerleri kul- landık. Örneğin, K(4, 2)’yi bulmak için K(3, 2)’yi, K(3, 2)’ yi bulmak için K(2, 2)’yi kullandık. Bu değerlere dikkatle bakıldığında, n çiftse K(n, 2) = 0, tekse K(n, 2) = 1 olduğu anlaşılır. Bu, tümevarımla kolaylıkla kanıtlanabilir. Bu da kanıtlamak istediğimiz ve kanıtlamak üzere olduğumuz teoremle uyumlu.

Şimdi K(n,3)’ü hesaplayalım. Teoreme göre sonuç hep 1 çıkmalı. Bakalım: (4) formülüne göre,

K(n, 3) = 1 – K(n–1, 3)K(n, 2)K(n+1, 2).

Burada ya n ya da n+1 çift sayıdır. Demek ki ya K(n, 2) ya da K(n+1, 2) sıfırdır. Dolayısıyla K(n, 3) = 1’dir.

Sıra K(n, 4)’ün hesaplanmasında. (4) formülünü uygulayalım:

K(n, 4) = 1 – K(n–1, 4)K(n, 3)K(n+1, 3).

Öte yandan

K(n, 3) = K(n+1, 3) = 1

eşitliklerini biliyoruz. Demek ki,

K(n, 4) = 1 – K(n–1, 4).

Bu son eşitliğe göre

K(n–1, 4) = 1 ise, K(n, 4) = 0’dır.

K(n–1, 4) = 0 ise, K(n, 4) = 1’dir.

Ama K(–1, 4) = 0 olduğundan, eğer n çiftse, K(n, 4) = 0’dır, eğer n tekse, K(n,4) = 1’dir. Bu sonuç da teoremimizle uyumlu.

Bundan sonrasını okur tümevarımla kanıtlayabilir.

Hangi (n, m)’lik NİM’leri kazanacağımızı gösterdik göster- mesine ama kazanacağımız oyunları nasıl kazanacağımızı ko- layca anlaşılır bir biçimde söylemedik. Diyelim hamle sırası bizde ve öbür oyuncu önümüze (n, m)’lik bir oyun sundu:

1) Eğer m = 0 ise, ne yapılacağı belli. Bir noktalık bir sırayı sileceksiniz. Eğer n tek ise kaybedeceksiniz, m çift ise kazana- caksınız.

2) Eğer m = 1 ise, iki noktalı sıradan oynayacaksınız. O sı- ranın ya bir noktasını ya da iki noktasını birden sileceksiniz. Bunu öyle yapacaksınız ki, geriye kalan noktaların sayısı tek olsun. Demek ki eğer n çiftse ikili sıradan bir nokta sileceksi- niz, eğer n tekse ikili sırayı olduğu gibi sileceksiniz. Bundan böyle m > 1 olduğunu varsayalım.

3) Eğer n çift, m tekse, iki noktalı bir sırayı silin. Böylece oyun (n, m–1)’lik bir NİM’e dönüşür.

4) Eğer n tek, m çiftse, bir noktalı bir sırayı silin. Böylece oyun (n–1, m)’lik NİM’e dönüşür.

5) Eğer hem n, hem de m çiftse, ne yaparsanız yapın, öbür oyuncu iyi oynadığında kazanamazsınız. Bir hata yapmasını beklemeniz gerekmektedir. Hata yapma olasılığını arttırmak için oyunu fazla kolaylaştırmayın, tek noktalı bir sırayı silin.

Birinci Teoremin Kanıtı: Söz verdiğimiz gibi birinci teoremi kanıtlayacağız. Sonlu bir oyunumuz var. Diyelim O oyunu.

A sonlu olduğundan, öyle bir n sayısı vardır ki, en fazla n hamlede oyun biter. Bu sayıların en küçüğüne O oyununun uzunluğu adını verelim. Yani O oyununun uzunluğu en uzun süren O oyununun hamle sayısı. Örneğin üç taş oyununun uzunluğu 9’dur.

Çünkü üç taş oyunu en fazla 9 hamle sonra biter ve gerçekten de 9 hamle sü- ren oyunlar olur. Yani üç taş oyunlarında en uzun oyun 9 hamledir.

Teoremimizi tümevarımla kanıtlayacağız. Ne üzerine tümevarımla? O oyununun uzunluğu üzerine tümevarımla.

Uzunluğu 0 olan oyunlar zaten bitmiş oyunlardır. Ya birinci oyuncu kazanmıştır ya da ikinci. Eğer birinci oyuncu kazanmış- sa, birinci oyuncunun kazanan stratejisi vardır. Eğer ikinci oyuncu kazanmışsa, ikinci oyuncunun kazanan stratejisi vardır. Kazanan stratejisi olan oyuncu kılını kıpırdatmadan kazanır.

Şimdi oyunumuzun uzunluğu 0’dan büyük olsun. Bu uzunuğa n diyelim. Tümevarım varsayımıyla, teoremimizin, uzunluğu n’den küçük olan oyunlar için doğru olduğunu biliyoruz. Anlatımda kolaylık sağlaması için oyunda ilk hamleyi bizim yapacağımızı varsayacağız. Kendimize A diyeceğiz, öbür oyuncuya B.

Her oyun gibi oyunumuz da bir hamleden sonra bir başka oyuna dönüşür, üstelik uzunluğu daha kısa olan bir oyuna. İlk hamle için k tane seçeneğimizin olduğunu varsayalım. Demek ki O oyununda ilk hamleyi yaptığımızda kendimizi k oyundan bi- rinde buluruz. Bu oyunlara O1, ..., Ok diyelim. Bir hamle yapıl- dığından, elde edilen bu k oyunun her birinin uzunluğu en faz- la n – 1’dir. Dikkat edilmesi gereken bir nokta var, o da şu: bu k oyundan her birine öbür oyuncu, yani B başlayacak. Eğer bu k oyundan birinde ikinci oyuncunun kazanan stratejisi varsa o oyunu üreten hamleyi yaparız. Böylece B oyunu kazanamaz ve kazanan bir stratejimiz olur. Eğer böyle bir hamle yoksa, yani türeyen k oyunun herbirinde birinci oyuncu kazanıyorsa, kaza- nan stratejimizi yoktur, B’nin vardır. Teorem kanıtlanmıştır.