Oyun Teorisi · 1612'den Bugüne
Masada birkaç sıra taş var. Sırayla, bir sıradan istediğiniz kadar taş alıyorsunuz; son taşı alan kazanıyor. Şans yok, gizli bilgi yok, kart yok. Yine de bu oyunu kusursuz oynayan bir bilgisayara karşı neredeyse hiç kazanamazsınız. Neden mi? Çünkü 1901'de bir matematikçi, kazanmanın sırrının sayıları ikili sistemde yazmakta saklı olduğunu kanıtladı. Önce aşağıda birkaç el oynayın, sonra sırrı birlikte açalım.
Engin Dikkulak
Çekirgeler Eğitim ve Sigma Olympics Kurucu Ortağı
Önce Temel Kavramlar
Nim, kombinatoryal oyunlar (combinatorial games) ailesindendir: iki oyuncu sırayla oynar, iki taraf da her şeyi görür, zar ya da kart gibi şans unsuru yoktur ve oyun sonlu sayıda hamlede biter. Nim'de ayrıca iki oyuncunun da aynı hamleleri yapabildiği için oyun tarafsızdır (impartial): satrançta beyaz yalnızca beyaz taşları oynar, Nim'de ise taşlar kimseye ait değildir.
Böyle bir oyunda her konum iki türden biridir. Sıra kendisindeyken oyuncunun ne yaparsa yapsın kaybettiği konumlara kaybeden konum (P-konumu, "previous player wins": bir önceki hamleyi yapan kazanır), en az bir kazandıran hamlesi olan konumlara kazanan konum (N-konumu, "next player wins") denir. İki basit kural her şeyi belirler:
(1) Kaybeden konumdan yapılan her hamle, kazanan bir konuma götürür. (2) Kazanan konumdan, kaybeden bir konuma götüren en az bir hamle vardır. Hiç taş kalmamış masa, sırası gelen için kaybeden konumdur (son taşı rakip almıştır). Strateji de buradan çıkar: rakibinize her zaman kaybeden bir konum bırakın.
Yığınlardaki taş sayılarını ikili sistemde (binary) yazıp alt alta dizin. Her basamak sütununda kaç tane 1 olduğuna bakın. Bir sütundaki 1'lerin sayısı tekse o sütuna 1, çiftse 0 yazın. Bu işleme XOR (dışlayıcı veya, "exclusive or") ya da Nim toplamı denir ve \(\oplus\) ile gösterilir. 3, 4 ve 5 taşlı üç yığın için:
| Yığın | 4'ler | 2'ler | 1'ler |
|---|---|---|---|
| 3 taş | 0 | 1 | 1 |
| 4 taş | 1 | 0 | 0 |
| 5 taş | 1 | 0 | 1 |
| \(3\oplus4\oplus5\) | 0 | 1 | 0 |
Charles Bouton'un 1901'de kanıtladığı teorem şudur: Nim toplamı 0 olan konumlar kaybeden, 0'dan farklı olanlar kazanan konumlardır. Yukarıdaki örnekte toplam \(010_2 = 2\), yani sıradaki oyuncu kazanabilir. Kazandıran hamle, toplamı yeniden 0'a indiren hamledir: 3 taşlı yığından 2 taş alırsanız yığınlar 1, 4, 5 olur ve \(1\oplus4\oplus5=0\).
\(x \oplus 0 = x\), \(x \oplus x = 0\), sıra önemli değildir (\(x\oplus y = y\oplus x\)) ve gruplama önemli değildir. Bu yüzden aynı büyüklükteki iki yığın birbirini "sıfırlar": 7 ve 7 taşlı iki yığından oluşan bir masa kaybeden konumdur, çünkü rakip hangi yığından ne alırsa, siz diğer yığından aynısını alarak onu taklit edebilirsiniz. XOR, bilgisayar biliminin en temel işlemlerinden biridir; Sezar'dan RSA'ya yazısındaki Vernam'ın tek kullanımlık şeridi de tam olarak bu işlemle çalışır.
Bu sürüme misère (Fransızca "sefalet") Nim denir. Şaşırtıcı biçimde strateji neredeyse aynıdır: normal Nim gibi oynayın, ta ki bir hamleniz masada 2 ya da daha fazla taşlı yığın bırakmayacak duruma gelene kadar. O anda, tek taşlı yığınların sayısı tek kalacak şekilde oynayın. Hero'daki oyunda "son taşı alan kaybeder" kuralını seçip deneyin. Ama dikkat: bu kolaylık yalnızca Nim'e özgüdür. Başka oyunların misère sürümleri, Derinlemesine bölümünde göreceğimiz gibi, çok daha zordur.
Taş Yığınlarından Yapay Zekâya
Taş alma oyunları muhtemelen çok eskidir; ama ne zaman ve nerede doğdukları belirsizdir. Nim'in matematiksel hikâyesi ise 17. yüzyılın bir bulmaca kitabıyla başlar ve bugün yapay zekâ araştırmalarının bir sınama alanına uzanır.
Bir yığından sırayla nesne alma oyunları birçok kültürde oynanır. Nim'in Çin'den geldiği sık sık söylenir ama bunu destekleyen güçlü bir belge yoktur. Kesin olan şu: oyunun matematiksel incelemesi, onu bir bulmaca olarak gören Avrupalı yazarlarla başladı.
İki oyuncu sırayla 1 ile 10 arasında bir sayı söyler, sayılar toplanır; toplamı 100'e ulaştıran kazanır. Bachet, kazanmak için hangi ara toplamları "ele geçirmek" gerektiğini gösterdi: 89, 78, 67, …, 12 ve 1. Yani ilk oyuncu 1 diyerek başlarsa ve her seferinde toplamı bir sonraki "güvenli" sayıya taşırsa kaybetmez. Bu, kaybeden konumlar fikrinin bilinen ilk açık örneklerinden biridir. Laboratuvarda deneyebilirsiniz.
Bouton, istenen sayıda yığın ve taşla oynanan Nim'in tam çözümünü verdi: ikili toplam 0 ise sıradaki oyuncu kaybeder. Oyunun adını da o koydu; muhtemelen Almancadaki "nimm!" (al!) ya da eski İngilizcedeki "nim" (çalmak, aşırmak) kelimesinden. Misère sürümünün çözümü de aynı makalededir. Bir oyunun bütünüyle, kanıtlanmış biçimde çözülmesinin ilk örneklerinden biri.
Wythoff, iki yığınlı bir sürüm önerdi: bir yığından istediğiniz kadar ya da iki yığından eşit sayıda taş alabilirsiniz. Kaybeden konumlar beklenmedik bir yerden çıktı: \(\big(\lfloor n\varphi \rfloor, \lfloor n\varphi^2 \rfloor\big)\), burada \(\varphi\) altın orandır. Yani (1, 2), (3, 5), (4, 7), (6, 10), … Özel Sayılar yazısındaki altın oran, bir taş oyununun içinden çıkıp geliyor.
Küme kuramcısı Zermelo, satranç üzerine yazdığı kısa bir makalede, beraberliğin mümkün olduğu sonlu ve tam bilgili bir oyunda taraflardan birinin kazanmayı ya da en azından berabere kalmayı garantileyen bir stratejisi olduğunu gösterdi. Ama hangisi olduğunu söylemedi: satrancın "doğru" sonucu bugün hâlâ bilinmiyor. Nim'in güzelliği, bu varlık kanıtının ötesine geçip stratejiyi açıkça vermesidir.
Birbirinden habersiz iki matematikçi, şaşırtıcı bir sonuç kanıtladı: her sonlu tarafsız oyunun her konumu, belirli büyüklükte tek bir Nim yığınına denktir. Bu büyüklüğe bugün Grundy sayısı (ya da nimber) diyoruz. Böylece birbirinden çok farklı görünen oyunlar, aynı dille çözülebilir hâle geldi. Derinlemesine bölümünde bu teoremin nasıl çalıştığını göreceğiz.
Fizikçi Condon'un tasarladığı Nimatron, rölelerle çalışan, bir tondan ağır bir makineydi; her biri yedi lambadan oluşan dört sırayla Nim oynuyordu. Fuarda yaklaşık 100.000 kez oynandı ve bunların 90.000 kadarını kazandı. Elektromekanik bir makinenin bir oyunu kusursuz oynayabilmesi, Bouton'un kuralının ne kadar "mekanik" olduğunu gösteriyordu.
Ferranti'nin Nimrod'u, Londra'daki Britanya Festivali'nde ziyaretçilere karşı Nim oynadı. Yalnızca bir oyunu oynamak için tasarlanmış ilk dijital bilgisayar olarak anılır. Amacı eğlence değil, bilgisayarların mantıksal işlemleri ne kadar hızlı yapabildiğini halka göstermekti.
Guy ve Smith, Sprague–Grundy kuramını onlarca oyuna uyguladı ve şaşırtıcı düzenlilikler buldu: birçok "çıkarma oyununun" Grundy değerleri bir noktadan sonra periyodik olarak tekrar ediyordu. Bazı oyunlar için bu periyodun var olup olmadığı ise bugün hâlâ açık bir sorudur.
Fransız yönetmen Resnais'nin filminde bir karakter, 1, 3, 5 ve 7 kibritten oluşan dört sırayla misère Nim oynar ve hiç kaybetmez. Film oyunu bir gizem simgesi olarak kullanır; hero'daki "Marienbad" dizilimi bu sahneden gelir. \(1\oplus3\oplus5\oplus7=0\): ilk hamleyi yapan, kusursuz bir rakibe karşı kaybeder.
Conway, tarafsız olmayan oyunları da kapsayan genel bir kuram kurdu ve bu kuramın içinden, tam sayıları, gerçek sayıları ve sonsuz büyüklükleri tek bir yapıda birleştiren yeni bir sayı sistemi çıkardı. Donald Knuth 1974'te bu sayılara "gerçeküstü sayılar" (surreal numbers) adını verdi. 1982'de yayımlanan iki ciltlik "Winning Ways", kombinatoryal oyun kuramının temel kitabı oldu. Conway, Nisan 2020'de hayatını kaybetti; Kollatz yazısındaki "karar verilemez" genelleme de onundur.
Berlekamp ve Wolfe, Conway'in kuramını Go oyununun son aşamalarına uyguladı. Tahtayı birbirinden bağımsız küçük bölgelere ayırıp her bölgeyi bir "oyun" olarak hesapladılar. Ortaya çıkan yöntem, profesyonel oyuncuların bile zorlandığı bazı oyun sonlarını kesin olarak çözebiliyordu.
Sprague–Grundy kuramı misère oyunlarda çalışmaz; bu oyunlar on yıllarca kuramın "karanlık köşesi" olarak kaldı. Plambeck ve Siegel, her misère oyuna özel bir cebirsel yapı (misère bölüm) eşleyerek birçoğunu çözmeyi mümkün kıldı. Genel bir çözüm yöntemi ise hâlâ yok.
AlphaZero, kendi kendine oynayarak birkaç saatte satranç, şogi ve Go'da ustalaştı. Zhou ve Riis aynı yöntemi Nim'e uyguladı: beş yığınlı masada iyi oynayan sistem, yığın sayısı arttıkça hızla bozuldu ve yedi yığında konumları neredeyse rastgele değerlendirdi. Nedeni, kazanmanın anahtarı olan XOR işleminin bir tür eşlik (parity) fonksiyonu olması; sinir ağları bu tür fonksiyonları örneklerden öğrenmekte zorlanıyor. Bir sekizinci sınıf öğrencisinin bir öğleden sonrada öğrenebileceği bir kural, en güçlü oyun yapay zekâlarından birini zorluyor.
Kendi Elinizle
Aşağıdaki üç araç, Nim'in akrabası olan oyunlarda kaybeden konumları bulmayı öğretiyor. Her birinde önce kendiniz bir kural tahmin edin: hangi sayılar, hangi konumlar "güvenli"? Sonra aracın gösterdiği desenle karşılaştırın.
Sırayla 1 ile \(k\) arasında bir sayı ekleyin; toplamı hedefe tam olarak ulaştıran kazanır. Bilgisayar "usta" oynuyor. Birkaç el oynadıktan sonra "güvenli sayıları göster" kutusunu açın ve desenin \(k+1\) ile ilişkisine bakın.
Wythoff oyununu bir satranç tahtasında düşünebilirsiniz: bir vezir, sola, aşağıya ya da sol-aşağı çaprazda istediği kadar ilerliyor; sol alt köşeye (0, 0) ulaştıran kazanıyor. Her kare iki yığındaki taş sayılarına karşılık gelir. Aşağıdaki tablo, kaybeden konumları işaretliyor. Bir kareye tıklayın: araç o konumun türünü ve varsa kazandıran hamleyi göstersin.
Bir çıkarma oyununda (subtraction game) yalnızca belirli miktarlarda taş alınabilir; örneğin her seferinde 1, 3 ya da 4 taş. Aşağıya izin verilen miktarları yazın. Araç, her yığın büyüklüğü için Grundy sayısını hesaplıyor; 0 olanlar kaybeden konumlardır. Değerlerin bir süre sonra periyodik olarak tekrar etmeye başladığına dikkat edin.
Araştırmacının Pusulası
Aşağıdaki sekiz başlık, Bouton'un kuralının kanıtından Sprague–Grundy teoremine, oradan bugün hâlâ çözülemeyen oyunlara uzanıyor. Her başlıkta bir durum etiketi var: kanıtlanmış, açık soru, varlık kanıtı ya da araç-veri.
Temellerdeki iki kuralı Nim toplamı için göstermek yeter.
(1) Toplam 0 iken her hamle toplamı 0'dan farklı yapar. Bir yığını \(a\)'dan \(a'\)'ne indirdiğinizde (\(a' < a\)) yeni toplam \(s' = s \oplus a \oplus a'\) olur. \(s=0\) ise \(s' = a\oplus a'\), ve \(a\ne a'\) olduğu için bu 0 olamaz.
(2) Toplam 0'dan farklıyken, toplamı 0 yapan bir hamle vardır. \(s\)'nin ikili yazılışındaki en soldaki 1'in sütununa bakın. Bu sütunda 1 olan bir yığın mutlaka vardır (yoksa toplamda o sütun 0 olurdu). O yığını \(a\)'dan \(a\oplus s\)'ye indirin. \(a\oplus s\), \(a\)'nın o sütundaki 1'ini 0 yapar ve daha sağdaki sütunları değiştirir; bu yüzden \(a\)'dan küçüktür, yani hamle yasaldır. Yeni toplam \(s\oplus a\oplus(a\oplus s)=0\) olur.
İki kural birlikte stratejiyi verir: toplamı 0 olmayan bir konumdaysanız toplamı 0'a indirin; rakibiniz ne yaparsa yapsın toplamı bozacak, siz yeniden 0'a indireceksiniz. Taşlar her hamlede azaldığı için oyun biter ve son taşı siz alırsınız. Hero'daki "usta" rakip tam olarak bu kuralı uyguluyor.
Bir konumun Grundy sayısı, ondan gidilebilen konumların Grundy sayılarında bulunmayan en küçük doğal sayıdır. Bu işleme "mex" (minimum excludant) denir:
Hiç hamle kalmayan konumun Grundy sayısı \(\operatorname{mex}\{\}=0\)'dır. Teoremin iki parçası var: (a) bir konum ancak ve ancak Grundy sayısı 0 ise kaybeden konumdur; (b) birbirinden bağımsız oyunlar yan yana oynandığında (her hamlede yalnızca birinde oynanır), toplam oyunun Grundy sayısı, tek tek Grundy sayılarının Nim toplamıdır:
Nim'de \(a\) taşlı tek bir yığının Grundy sayısı \(a\)'nın kendisidir; Bouton'un teoremi bu genel kuralın özel bir hâlidir. Laboratuvardaki hesaplayıcı, mex kuralını her yığın büyüklüğü için sırayla uyguluyor.
Alınabilecek miktarlar sonlu bir küme olduğunda, Grundy değerlerinin bir noktadan sonra periyodik olduğu kanıtlanmıştır: her değer, kendinden önceki sınırlı sayıda değerden belirlendiği için dizi eninde sonunda tekrar etmek zorundadır. Ama daha karmaşık oyunlarda durum farklı. Örneğin Grundy'nin kendi oyununda (bir yığını, eşit olmayan iki yığına bölmek) değerler bilgisayarlarla çok büyük yığınlara kadar hesaplanmış, ama periyodik olup olmadıkları bilinmiyor. Richard Guy'ın "oktal oyunların hepsi sonunda periyodiktir" konjektürü de hâlâ açıktır.
Nim'in misère sürümü, normal sürümden yalnızca son hamlelerde ayrılır. Bu kolaylık bir istisnadır. Genel olarak misère oyunlarda iki bağımsız oyunun toplamı, parçaların değerlerinden hesaplanamaz; yani Sprague–Grundy teoreminin (b) parçası çöker. Conway'in kuramında bile misère oyunlar çok daha karmaşık bir yapıya sahiptir. 2008'den bu yana geliştirilen "misère bölüm" yöntemi birçok somut oyunu çözdü, ama bütün misère oyunlar için Nim toplamı gibi basit bir anahtar bilinmiyor.
David Gale'in 1974'te tanıttığı Chomp oyununda dikdörtgen bir çikolata tableti vardır; sol alt karesi zehirlidir. Sırayla bir kare seçilir ve o karenin sağında ve üstünde kalan her şey yenir; zehirli kareyi yiyen kaybeder. İlk oyuncunun her boyuttaki tablette kazandığı şık bir argümanla kanıtlanır: ilk oyuncu yalnızca sağ üst köşedeki kareyi alsın. Bu hamle kaybettiriyorsa, ikinci oyuncunun bir "cevap" hamlesi vardır; ama ilk oyuncu o cevabı en baştan kendisi oynayabilirdi. Yani ilk oyuncu ikinci oyuncunun stratejisini "çalar".
Bu kanıt, kazandıran hamlenin ne olduğunu söylemez. Kare ve iki sıralı tabletler için strateji bilinir; genel dikdörtgenler için bilinmez. John Nash'in 1949'da Hex oyunu için verdiği kanıt da aynı türdendir. Matematikte "var olduğunu bilmek" ile "bulmak" arasındaki farkın en somut örneklerinden biri.
Nim'de kazandıran hamleyi bulmak çok kolaydır: yığın sayısıyla orantılı bir işlem yeter. Ama bu bir istisnadır. Bilgisayar bilimi, oyunları çözmenin ne kadar zor olduğunu karmaşıklık sınıflarıyla ölçer:
| Oyun (genelleştirilmiş) | Zorluk | Kanıt |
|---|---|---|
| Nim | kolay (doğrusal zaman) | Bouton, 1901 |
| Coğrafya oyunu (Geography) | PSPACE-tam | Schaefer, 1978 |
| \(n\times n\) satranç | EXPTIME-tam | Fraenkel ve Lichtenstein, 1981 |
| \(n\times n\) Go (Japon kuralları) | EXPTIME-tam | Robson, 1983 |
"PSPACE-tam" ve "EXPTIME-tam", kabaca, tahta büyüdükçe çözüm süresinin üstel biçimde büyüyeceğinin (ya da büyümesinin çok olası olduğunun) göstergesidir. Nim'in basitliği, ikili sistemdeki gizli yapısından gelir.
XOR, bir eşlik (parity) fonksiyonudur: sonucu, girdideki bitlerin tamamına bağlıdır; tek bir bitin değişmesi sonucu tersine çevirir. Satranç ya da Go'da benzer konumlar genellikle benzer değerlere sahiptir ve sinir ağları bu "benzerliği" öğrenerek başarılı olur. Nim'de ise tek bir taşın farkı, kazanan konumu kaybedene çevirir. Zhou ve Riis'in deneyleri, AlphaZero tarzı sistemlerin bu yüzden büyük Nim masalarında ustalaşamadığını gösteriyor. Bu sonuç, yapay zekânın "örüntü tanıma" ile "kural kavrama" arasındaki farkını tartışan araştırmalarda sıkça anılıyor.
Nim'i bir kez kavrayan bir öğrenci, 50 yığınlı bir masada da kusursuz oynar; çünkü öğrendiği şey örnekler değil, bir kanıttır. Matematik eğitiminin gücü tam da burada: bir kuralın neden doğru olduğunu bilen, onu hiç görmediği durumlara da güvenle taşır.
Tarafsız olmayan oyunlarda (her oyuncunun kendi taşları vardır) bir konumun değeri tek bir Nim yığınıyla ifade edilemez. Conway bu oyunlar için bir değer sistemi kurdu ve bazı oyunların değerlerinin tam olarak sayılar gibi davrandığını fark etti: bir oyuncuya "bir hamle avantaj" sağlayan konum 1, "yarım hamle" sağlayan \(1/2\) değerindeydi. Kural genişletildiğinde ortaya, gerçek sayıları ve Cantor'un sonsuzluklarını aynı çatı altında toplayan bir sayı sistemi çıktı. Nim yığınları ise bu sistemde "sayı olmayan" yeni nesnelerdir: \(*1, *2, *3, \dots\) diye yazılır ve \(*a + *a = 0\) kuralına uyar. Bir çocuk oyunundan çıkan bir sayı kuramı.
Terim Sözlüğü
Kombinatoryal oyun kuramı üzerine kaynakların neredeyse tamamı İngilizce. Aşağıdaki terimler, bu yazıdan sonra okuyacağınız kitap ve makalelerde aradığınızı bulmanızı kolaylaştırmak için hazırlandı.
| Türkçe | İngilizce | Kısaca |
|---|---|---|
| Kombinatoryal oyun kuramı | combinatorial game theory (CGT) | Şanssız, tam bilgili, sıra tabanlı oyunların matematiği |
| Tarafsız / tarafgir oyun | impartial / partizan game | İki oyuncunun aynı hamleleri yapabildiği / yapamadığı oyun |
| Tam bilgili oyun | game of perfect information | Her iki oyuncunun da her şeyi gördüğü oyun |
| Kaybeden / kazanan konum | P-position / N-position | Sırası gelenin kaybettiği / kazanabildiği konum |
| Normal oyun / misère oyun | normal play / misère play | Son hamleyi yapan kazanır / kaybeder |
| Nim toplamı | nim-sum, bitwise XOR | Taşıma yapılmadan ikili toplama, \(\oplus\) |
| İkili sistem | binary numeral system | Sayıları yalnızca 0 ve 1 ile yazma |
| Grundy sayısı | Grundy number, nimber, nim-value | Bir konuma denk gelen Nim yığınının büyüklüğü |
| Bulunmayan en küçük değer | mex (minimum excludant) | Bir kümede olmayan en küçük doğal sayı |
| Oyunların toplamı | disjunctive sum of games | Her hamlenin bileşenlerden yalnızca birinde yapıldığı birleşik oyun |
| Çıkarma oyunu | subtraction game | Yalnızca belirli miktarlarda taş alınabilen oyun |
| Oktal oyunlar | octal games | Kurallarının sekizlik bir kodla yazılabildiği taş oyunları ailesi (Kayles gibi) |
| Strateji çalma argümanı | strategy-stealing argument | Kazanan stratejinin varlığını, onu bulmadan kanıtlama yöntemi |
| Belirlenmişlik | determinacy | Oyunda bir tarafın kazanan stratejisi olması |
| Oyun ağacı | game tree | Bütün olası hamle dizilerinin dallanan gösterimi |
| Eşlik fonksiyonu | parity function | Girdideki 1'lerin sayısının tek mi çift mi olduğunu veren fonksiyon |
| Pekiştirmeli öğrenme | reinforcement learning | Deneme ve ödülle öğrenen yapay zekâ yöntemi |
| Gerçeküstü sayılar | surreal numbers | Conway'in oyunlardan türettiği, gerçek ve sonsuz sayıları kapsayan sistem |
Buradan Nereye?
Aşağıdaki sorular, bir kitapta, bir ders notunda ya da bir yapay zekâ sohbetinde bu yazının bir adım ötesine geçmeniz için seçildi. Her birinde, cevabı küçük örneklerle (iki, üç taşlı konumlarla) kendiniz denetlemeyi unutmayın; oyunlar, kendi elinizle denemenin en kolay olduğu matematik dalıdır.
Fibonacci Nim'de kazanmak için neden Zeckendorf gösterimi gerekir?
Anahtar kelimeler: Fibonacci Nim, Whinihan (1963), Zeckendorf representation. Her sayının, ardışık olmayan Fibonacci sayılarının toplamı olarak tek biçimde yazılabildiği teoremle başlayın.
Kayles oyununun Grundy değerleri neden bir noktadan sonra 12'lik bir periyotla tekrar eder?
Anahtar kelimeler: Kayles, octal games, Guy ve Smith (1956). Laboratuvardaki hesaplayıcının mantığını, bir sıradaki labutları devirme oyununa genişletmeyi deneyin.
Chomp'ta 2 × n ve kare tabletler için kazandıran ilk hamle nedir?
Anahtar kelimeler: Chomp, Gale (1974), strategy stealing. Kare tablette simetri fikri işe yarar; genel dikdörtgen için cevabın neden bilinmediğini de sorun.
Hackenbush'ta bir konumun değeri nasıl 1/2 ya da 3/4 olabilir?
Anahtar kelimeler: Red-Blue Hackenbush, partizan games, "Winning Ways" birinci cilt. Conway'in gerçeküstü sayılarına en kolay giriş kapısı.
Bir oyunun "PSPACE-tam" olması, onu oynayan biri için pratikte ne anlama gelir?
Anahtar kelimeler: generalized geography, PSPACE-complete games, Schaefer (1978). Karmaşıklık sınıflarına oyunlar üzerinden giriş yapan ders notları iyi bir başlangıç.
Sinir ağları neden eşlik fonksiyonunu öğrenmekte zorlanır; bu sorun nasıl aşılabilir?
Anahtar kelimeler: parity function learning, neural network inductive bias, Zhou ve Riis (2022). Yapay zekâ ile matematiksel akıl yürütme arasındaki farkı tartışan güncel bir alan.
Bu Sayfada
Nim'in hikâyesi, matematiğin en sevdiğimiz yanlarından birini gösteriyor: oyun gibi görünen bir soru, doğru bakış açısıyla bütünüyle çözülebiliyor ve bu çözüm başka sorulara da kapı açıyor. Bachet'nin yüze ulaşma bulmacası, Bouton'un ikili toplamı, Sprague ve Grundy'nin "her oyun bir Nim yığınıdır" teoremi, Conway'in gerçeküstü sayıları ve bugün yapay zekânın sınandığı deneyler aynı zincirin halkaları. Çekirgeler Eğitim'in Türkiye Zekâ Ligi sorularında karşılaşılan strateji oyunlarının arkasında da bu düşünme biçimi var: rakibe her zaman kaybeden bir konum bırakmak. Asal sayıların ve şifrelerin dünyasındaki ikili düşünce için Sezar'dan RSA'ya, altın oranın başka yüzleri için Özel Sayılar yazılarına bakabilirsiniz.
Nim'in normal ve misère sürümleri tamamen çözüldü (Bouton 1901). Her sonlu tarafsız oyun bir Nim yığınına denktir (Sprague–Grundy). Sonlu çıkarma kümeli oyunların Grundy değerleri sonunda periyodiktir. Chomp'ta ilk oyuncu her zaman kazanır.
Bütün oktal oyunlar sonunda periyodik mi? Misère oyunlar için genel bir yöntem var mı? Genel dikdörtgen Chomp'ta kazandıran hamle nedir? Yapay zekâ, Nim gibi "kural tabanlı" oyunlarda bir öğrenci gibi ustalaşabilir mi?
Bir sonraki taş oyununda kazanmak için bir kâğıt kalem yeterli. Belki de bir gün, hâlâ çözülemeyen bu oyunlardan birinin anahtarı da böyle bir kâğıtta, bu sayfayı okuyan birinin elinde ortaya çıkacak.
Kaynakça
Sayfadaki tarihler ve açıklamalar aşağıdaki özgün çalışmalara ve standart kaynaklara dayanmaktadır. Sayısal örnekler hesaplanarak doğrulanmıştır.
