Yazan : Şadi Evren ŞEKER

Bu yazının amacı, hırsız oyunu (game of nim) isimli oyun üzerinden asgari-azami ağaçları (minimax trees) açıklamaktır. Öncelikle oyunu kısaca anlatalım.

Oyun iki kişi tarafından karşılıklı olarak sırayla oynanmaktadır. Oyun sayılabilir varlıklar üzerinden oynanır. Örneğin boncuk, çubuk, kalem gibi sayılabilir varlıklar oyun için kullanışlıdır. Bu yazı boyunca çubuk kullanıldığını düşünerek konuyu izah edelim.

Başlangıçta n miktarda çubuk ile oyuna başlanır. Bu n sayısı imkanlar dahilinde değişmekle birlikte mümkünse asal sayı almak daha iyidir ki taraflardan birisi hızlı bir hesaplama ile hile yapamasın 🙂

Bu örnekte 7 olarak kabul edelim.

Oyuna 7 adet çubuk ile başlıyoruz. Sıra kendisinde olan taraf çubukları iki gruba ayırıyor. Grupların büyüklüğüne kendisi karar veriyor. Örneğin 7 çubuğu, 1+6, 2+5, 3+4 şeklinde gruplara ayırabilir.

Ardından sıra diğer oyuncuya geçiyor ve bu oyuncu da gruplardan istediğini iki gruba bölüyor ve oyun böylelikle sürüp gidiyor. En sonunda taraflardan birisi artık iki gruba ayıramayacak hale gelince oyunu diğer taraf kazanmış oluyor. Oyunda gruplara ayırma sırasında bir de istisna bulunuyor. Buna göre eşit sayıda iki gruba bölemiyoruz. Örneğin 6 çubuk olması halinde 3+3 şeklinde iki gruba bölmek yasak. Dolayısıyla 2 çubuk kalması halinde oyun bitiyor çünkü oyuncu 1+1 şeklinde bölemez.

Oyunun örnek hamle ağacını aşağıdaki şekilde çizebiliriz:

Yukarıdaki ağaçta görüldüğü üzere, oyun 7 adet çubuk ile başlamış ve bütün ihtimaller ağaçta gösterilmiştir. Ağaçta görüldüğü üzere oyunun 3 farklı bitiş koşulu bulunmaktadır. Bu bitişler aşağıdaki şekilde işaretlenmiştir:

Bitişler, aynı zamanda kazananı da belirlemektedir. Yukarıdaki bu ağaç üzerinde asgari-azami ağacı işaretleyecek olursak, aşağıdaki şekli elde ederiz:

Yukarıdaki şekilde, ağaçta gösterilen değerler, hamlelere karar verme sırasında kullanılmaktadır. Örneğin yukarıdaki şekle bakıldığında her durumda 1 sonucuna ulaşılabilecek hamleler yapılacağı görülmektedir. Diğer bir deyişle 1 sonucu, bizim kazanma durumumuzu göstermekte ve %100 ihtimal ile oyunu kazanmaktayız.

İlk hamleyi Rakip oyuncu yapıyor ve ilk hamlede bütün ihtimaller üzerinde 1 değeri olduğu için ne oynadığının hiç önemi yok. Diyelim ki 5+2 ihtimalini oynadı. Bu durumda mecburen 5 grubunu böleceğiz (2 grubunu bölemez çünkü bölmesi halinde iki eşit grup oluşacaktır). 5 grubunu ise iki farklı şekilde bölünebilir: 4+1 veya 3+2.

Bu hamlelerden bizim için karlı olanı, 4+2 şeklinde bölmek çünkü bu hamle bize oyunu kazandıracak (3+2+2 kolunda 0 değeri olduğuna dikkat ediniz)

Sıra tekrar rakibe geçince yapabileceği tek hamle 4+2+2 grubundaki 4 değerini 3+1 şeklinde bölmek olacaktır.

Biz ise son hamleyi yapıp 3 grubunu 2+1 olarak bölüyor ve oyunu kazanıyoruz.

Yukarıda görüldüğü üzere oyunun bütün hamlelerini minimax ağacı üzerinde hesaplayarak bir sonuca eriştik ve oyunu kesin olarak kazanacağımızı biliyoruz. Ayrıca yukarıdaki ağaçta dinamik programlama (dynamic programming) kullanılmıştır. Yani, örneğin 4+2+1 sonucuna iki farklı yerden ulaşılabilmektedir. (6+1 veya 5+2’den) Ağaçta bu değerler ayrı ayrı gösterilmek yerine tek bir düğümde gösterilmiştir. Bu sayede ağacın karmaşıklığı indirgenmiştir.

Yukarıdaki oyunun minimax ağacını daha da verimli hale getirebiliriz. Bunun için alfa beta budaması (alfa beta prunning) kullanmayı deneyelim. Konu hakkında bilgisi olmayanlar ilgili yazıyı, linke tıklayarak okuyabilirler.

Yukarıdaki ağaçta, iki dal budanmıştır. Bunun sebebi, ağacın dolaşılması sırasında, azami değerin alınacağı seviyede 1 değerine ulaşılmış olması ve sonrasında gelen değerlerin bir önemi olmamasıdır. Örneğin 5+2 düğümüne, 1 değeri 4+2+1 düğümünden taşındıktan sonra diğer koldan ne geldiğinin artık bir önemi yoktur çünkü azami değere ulaşılmıştır. Bu sayede bazı kolların altındaki değerlerin hesaplanmasına gerek kalmadan sonuca daha hızlı bir şekilde ulaşılmış olunur.


Yorumlar

  1. Şeyma

    merhabalar hocam çok teşekkür ederiz çok güzel anlatmışsınız zor bir soruydu birde şu 1 ve 0 ların yerleştirilmesini anlamadım neye göre azami asgari belirliyoruz bir de 1. ve 3. soruların cevaplarını yazarsanız çok seviniriz???

  2. Şadi Evren ŞEKER Article Author

    şekildeki 1 ve 0’lar kazanma ve kaybetme durumlarıdır. Azami ve asgari değerler alınırken bizim için yapılabilecek en iyi ihtimalleri (kazanma) ve rakibin yapabileceği, rakip için en iyi (bizim için en kötü (kaybetme) ) ihtimallerini hesaplıyoruz.

    Diğer soruların cevapları zaten site üzerinde yayınlanmıştır.

    Başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir