Bu yazımızda 1942’de Piet Hein tarafından bulunan ve 1947’de bağımsız olarak John Nash tarafından tekrar keşfedilen Hex oyununu inceleyeceğiz.
Hex, hücreleri altıgen olan eşkenar dörtgen biçimindeki bir tahtada oynanan bir masaüstü oyunu. Oyun tahtası geleneksel olarak 11 x 11 boyutunda olsa da 13 x 13 ve 19 x 19 boyutundaki çeşitlemeler de mevcut.
Hex iki oyuncu ile oynanıyor ve her oyuncu bir renge sahip. Bu blog yazısı için oyuncuların renkleri mavi ve kırmızı olsun. Hex tahtasının her bir kenarı karşılıklı kenarlar aynı renk olmak üzere mavi ve kırmızı renkleriyle işaretleniyor.
Oyunun kuralları basit. Her oyuncu sırası geldiğinde tahtaya kendi renginde bir taş yerleştirerek o renge sahip kenarlar arasında (bağlantılı) bir yol oluşturmaya çalışıyor. Mesela aşağıda mavi oyuncunun kazandığı bir Hex oyunu görüyoruz.
Oyunu özümsemek için bilgisayara karşı Hex oynamak isterseniz şu adreste bir uygulama mevcut. Bu yazıda şunları kanıtlayacağız
- Hiçbir Hex oyunu berabere bitemez.
- Hex’te birinci oyuncunun bir kazanma stratejisi vardır.
Birinci oyuncunun bir kazanma stratejisi olduğunu okuyunca oyunun bir anlamı kalmadığını düşünebilirsiniz. Öte yandan bilmenizde fayda var ki birinci oyuncunun kazanma stratejisinin ne olduğu bilinmiyor, sadece böyle bir strateji olduğu biliniyor. Sanıyorum ki bu durum yapıcı olmayan kanıtlara aşina olmayan pek çok okuyucu için şaşırtıcı bir durum. Nasıl oluyor da birinci oyuncunun bir kazanma stratejisi olduğunu böyle bir stratejiyi açık açık bulmadan gösterebiliyoruz? Yazının ilerleyen bölümlerinde bunun John Nash tarafından yapılmış basit ve zarif bir kanıtını göreceğiz ancak şimdiden anahtar kelimeyi vermek istiyorum: Strateji çalmak.
Birinci oyuncunun -henüz ne olduğunu bilmesek de- bir kazanma stratejisi olduğunu öğrendiğimize göre bu noktada Hex’e bazen dahil edilen bir değişim kuralından bahsetmekte fayda var. Bu kurala göre birinci oyuncu ilk hamlesini yaptıktan sonra ikinci oyuncuya renkleri değiştirme fırsatı verilir. Böylece, ikinci oyuncu birinci oyuncunun ilk hamlesinde çok stratejik bir pozisyonu ele geçirdiğini düşünürse renkleri değiştirerek bu avantajı kendisi ele geçirebilir.
Hex Teoremi
Yazının bu bölümünde Hex’in berabere bitemeyeceğini kanıtlayacağız. Bu teoremi daha sonra birinci oyuncunun bir kazanma stratejisi olduğunu kanıtlamakta kullanacağız. Okuduğum kadarıyla John Nash bu teoremin kanıtını 1952’de yapmış ancak bu kanıta ne yazık ki erişemedim. Bu yazıda Nash’in kanıtı yerine David Gale’ın ilgili 1979 makalesindeki kanıtı yapacağız.
- Teorem: Hex tahtası sırasıyla mavi ve kırmızı taşlarla doldurulursa oyunu mavi oyuncu veya kırmızı oyuncu kazanır. Yani Hex oyunu berabere bitemez.
- Kanıt (Taslak): Hex tahtasına aşağıda görüldüğü gibi dört nokta ve dört kenar ekledikten sonra oluşturduğumuz düzlemsel çizgedeki ilgili dört bölgeyi ilgili kenarların renklerine aşağıdaki gibi boyayalım.
Diyelim ki mavi ve kırmızı oyuncular oyunu oynayıp tahtayı kırmızı ve mavi taşlarla doldurdular. Her hücrenin rengini o hücreye konan ilgili taşın rengi olarak atayalım. Şimdi yapacağımız şey yukarıdaki çizgenin bir alt çizgesini oluşturmak. Oluşturacağımız alt çizgenin noktalar kümesi aynı olsun, kenarları da şu kurala uygun biçimde seçelim.
- Asıl çizgedeki bir kenar alt çizgeye dahildir ancak ve ancak bu kenarın ayırdığı iki bölgenin renkleri farklı ise.
Örneklemek açısından, aşağıdaki şekilde doldurulmuş bir tahta üzerinde oluşturduğumuz alt çizge turuncu ile işaretlenmiş kenarları içeren çizge olacak.
Şimdi kanıtlarını okuyucuya egzersiz olarak bırakacağım iki önsav göreceğiz.
Önsav 1: Oluşturduğumuz alt çizgedeki noktaların dereceleri 0, 1 ya da 2 olabilir.
Önsav 2: Noktalarının dereceleri en fazla 2 olan sonlu bir çizge
- izole noktaların (yani derecesi 0 olan noktaların),
- basit döngülerin (yani kendini kesmeyen döngülerin) ve
- basit yolların (yani kendini kesmeyen yolların)
ayrık birleşimi olarak yazılabilir.
Biraz uğraşla kolayca gösterilebilir ki oluşturduğumuz alt çizgede derecesi 1 olan noktaların ilk başta eklediğimiz dört noktadan ibarettir. Dolayısıyla, Önsav 2’nin bir sonucu olarak, oluşturduğumuz alt çizgede bu noktaları birbirine bağlayan basit yollar olmak zorunda.
(Eğer Jordan eğri teoremi gibi şeylerden haberdarsanız, bu basit yolların eklediğimiz noktalardan karşılıklı olanları birbirine bağlayamacağını da kanıtlayabilirsiniz.)
Ne elde ettik? Hex tahtası mavi ve kırmızı taşlarla doldurulduğu zaman yukarıdaki prosedürle elde ettiğimiz alt çizge, ilk başta eklediğimiz dört noktayı ikili olarak birbirine bağlayan iki basit yol içeriyor. Bu basit yolların kenarlarının üzerinde olduğu altıgen hücreler takip edilerek de karşılıklı kenarları birbirine bağlayan bir altıgen hücre zinciri olmak zorunda olduğu kanıtlanabilir. (Mesela sağ aşağıdaki noktayı sağ üstteki noktaya bağlayan bir yol varsa oyunu kırmızı kazanmıştır, aksi halde sağ aşağıdaki noktayı sol alttaki noktaya bağlayan bir yol varsa oyunu mavi kazanmıştır vs.)
Yukarıda taslağını verdiğimiz kanıt Gale’in orijinal makalesinden ya da şuradaki ders notlarından da okunabilir. Kanıtın fikri basit ve şık. Tabii matematiksel kesinlikten ödün vermemek adına kanıtı olabildiğince biçimselleştirmek istersek, özellikle kanıtın sonlarına doğru, bir miktar hammallık yapmak zorunda kalacağız. Bu yüzden her yeri sembol yığınına boğmak yerine kanıtın taslağını vermeyi tercih ettim -aynı Gale’ın yaptığı gibi!
Yukarıdaki teoremdeki veya ifadesini ya ya da ifadesine çevirebiliriz. İki oyuncunun aynı anda kazanamayacağı, yani karşılıklı kenarları bağlayan hem kırmızı hem de mavi taşlar zinciri olamayacağı, sezgisel olarak açık olmalı. Öte yandan bunu matematiksel olarak kanıtlamak için Jordan eğri teoremini kullanmak zorundayız. (Aslında Gale’ın makalesinin ikinci bölümünde yazana göre bunun Lichtenstein tarafından yapılan tamamen kombinatoriyel bir kanıtı da mevcutmuş.)
Bu noktada belirtmeliyim ki fazladan iş yükü çıkarttığından dolayı ilgili teoremin ya ya da çeşitlemesini kanıtlamayacağız ve kanıtsız kabul ederek yazıya devam edeceğiz.
Hex’in Belirliliği
Hex’in berabere bitemeyeceğini kanıtladığımıza göre şimdi birinci oyuncunun bir kazanma stratejisi olduğunu gösterebiliriz.
Önsav: Hex’te ya birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi vardır.
Kanıt: Göstermek istediğimiz önerme şu önermeye denk: Eğer ikinci oyuncunun bir kazanma stratejisi yoksa, o zaman birinci oyuncunun bir kazanma stratejisi vardır.
Bunu kanıtlayabilmek için küçük bir tanıma ihtiyacımız var. Oyundaki bir pozisyona birinci oyuncu için kaybeden pozisyon diyelim ancak ve ancak bu pozisyondan itibaren ikinci oyuncunun bir kazanma stratejisi varsa, yani tahta bu pozisyona geldiğinde ikinci oyuncu kazanmayı garantileyen bir strateji bulabiliyorsa.
Şimdi önemli bir gözlem yapalım. Bir pozisyon birinci oyuncu için kaybetmeyen bir pozisyonsa, birinci oyuncu öyle bir hamle yapabilir ki ikinci oyuncu ne hamle yaparsa yapsın ortaya çıkan pozisyon birinci oyuncu için gene kaybetmeyen bir pozisyon olacaktır. Aksi halde ilk başta içerisinde bulunduğumuz pozisyon birinci oyuncu için kaybetmeyen bir pozisyon olmazdı! Demek ki birinci oyuncu kaybetmeyen bir pozisyondaysa, kendini tekrar kaybetmeyen bir pozisyona sokacak bir hamle yapabiliyor.
Şimdi kanıtın ilk satırında yazdığımız önermeyi kanıtlamaya hazırız. Diyelim ki ikinci oyuncunun bir kazanma stratejisi yok. Bu durumda birinci oyuncunun bir kazanma stratejisi olduğunu göstermek istiyoruz.
İkinci oyuncunun bir kazanma stratejisi olmadığına göre boş tahta birinci oyuncu için kaybetmeyen bir pozisyondur. Yukarıda yaptığımız gözlem gereği de birinci oyuncu öyle bir hamle yapabilir ki (ikinci oyuncu ne yaparsa yapsın) kendini tekrar kaybetmeyen bir pozisyona sokabilir. Benzer şekilde birinci oyuncu her hamlesinde kendini kaybetmeyen bir pozisyona sokacak bir hamle yapsın, ki böyle bir hamle yapabileceğini biliyoruz.
Birinci oyuncu için (tümevarımla) inşa ettiğimiz bu strateji bir kazanma stratejisi olmak zorundadır. Aksi halde, eğer birinci oyuncu oyun sonunda kaybetseydi, ikinci oyuncunun kazanmayı garantilediği bir pozisyon bulabilirdik ve bu da tümevarım hipotezimizle çelişirdi.
Demek ki Hex’te ikinci oyuncunun bir kazanma stratejisi yoksa birinci oyuncunun bir kazanma stratejisi olmak zorunda. Dolayısıyla Hex’te ikinci oyuncunun veya birinci oyuncunun bir kazanma stratejisi vardır. İki oyuncunun aynı anda kazanma stratejisi olamayacağına göre bir önceki cümledeki veya bağlacını ya da olarak değiştirebiliriz.
(Yukarıda yaptığımız şey aslında tam bilgili sonlu iki kişilik oyunlar için geçerli olan Zermelo’nun teoremini Hex için kanıtlamak. Yaptığımız kanıt da sonsuz oyunlardaki Gale-Stewart teoreminin kanıtının ta kendisi.)
Şimdi yazının ana teoremini kanıtlayabiliriz.
- Teorem: Hex’te birinci oyuncunun bir kazanma stratejisi vardır.
- Kanıt (Nash): Önceki yazdıklarımızın bir sonucu olarak birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi olması gerektiğini biliyoruz.
Diyelim ki ikinci oyuncunun bir kazanma stratejisi var. Bu durumda birinci oyuncu bu kazanma stratejisini kolayca çalabilir:
İlk hamle olarak rastgele bir hamle yapsın. Daha sonra ikinci oyuncu sanki birinci oyuncu, kendisi de ikinci oyuncuymuş gibi davranarak ikinci oyuncunun kazanma stratejisini uygulasın. Eğer bu strateji herhangi bir noktada ilk başta rastgele yaptığı hamlenin yapılmasını gerektiriyorsa (o hamle zaten ilk başta yapıldığı için) başka bir hamle yaparak devam etsin.
Dikkat edilmesi gereken nokta Hex’te yapılan fazladan bir hamlenin bir oyuncuyu içerisinde bulunduğu durumdan daha kötü bir pozisyona sokamayacağı. Yani bir oyuncu bir hücre boşken oyunu kazanmayı garantileyebiliyorsa o hücreye fazladan bir taş koyarak da oyunu kazanmayı garantileyebilir. Dolayısıyla yukarıda birinci oyuncunun ikinci oyuncunun stratejisini çalarak geliştirdiği strateji kendisi için bir kazanma stratejisidir.
Demek ki ikinci oyuncunun bir kazanma stratejisi varsa birinci oyuncu bunu çalıp kendisi için bir kazanma stratejisi üretebiliyor. İki oyuncunun aynı anda kazanma stratejileri olamayacağına göre ikinci oyuncunun bir kazanma stratejisi olamaz. Demek ki birinci oyuncunun bir kazanma stratejisi olmak zorunda.
Birinci Oyuncu Oyunu Nasıl Kazanır?
Hex’te birinci oyuncunun bir kazanma stratejisinin var olması gerektiğini biliyoruz. Öte yandan, 2016 itibariyle 11 x 11’lik standart tahtalar için bir kazanma stratejisi açık açık bulunmuş değil. Bununla birlikte tahta boyutunu küçültüp 9 x 9’luk Hex ile ilgilenirsek, bilgisayarlar yardımıyla birinci oyuncunun stratejisi bulunmuş durumda.
Yazıyı noktalamadan önce birkaç küçük not ekleyim. Hex’te verilen bir pozisyonun kazanan bir pozisyon olup olmadığını anlamak PSPACE-tam bir problemmiş. Son olarak, matematikçilerin ilgisini çekebilecek bir bilgi. Hex’in belirliliği (yani ya birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi olması) kullanılarak Brouwer sabit nokta teoremi, daha doğrusu bu teoremin birim kare üzerindeki özel hali, kanıtlanabiliyor. Bunun tersi de doğru, Brouwer’in sabit nokta teoremiyle Hex’in belirliliğini kanıtlamak da mümkün. Bu kanıtları görmek isteyenler Gale’ın bağlantısını verdiğim 1979 makalesini inceleyebilir.
Not: Bu yazı Can Numan müstear ismiyle kaleme alınmıştır. Yazardan izin alınarak sitemize Taner Beyter tarafından uyarlanmıştır.
