Five-guess algoritması ile sözlükten kelime bulmak

Merhabalar,

Algoritmalar dersinde yaptığımız ödevi paylaşmak istedim. Algoritmaya geçmeden nereden çıktığını anlamak için Mastermind oyununu açıklamakta fayda var. Mastermind iki kişi(grup) tarafından oynanan tahmine dayalı bir oyundur bir grup belli sayıda deliklere belli renkleri istediğince dizer ve diğer grup da bunu tahmin etmeye çalışır. Tahmin eden grup renk sıralamasını da doğru bilmek zorundadır. Her tahminden sonra diğer gruptan bir dönüt alınmasını isterler ve cevaplar şu şekilde olur:

Hem doğru renk hem de delik için bir siyah delik ● ,

Sadece doğru renk için bir beyaz delik ○ cevabını alır.

Örneğin 6 renk  ve 4 delikli bir mastermind oyunu için renkler ve sıralamaları (1. renk 2.renk gibi) 123123 olursa ve tahmin eden grup da 11112 gönderirse alacağı cevap : ●●○ olacaktır (siyahlar 1’den beyaz ise 2 den geliyor).

Umarım oyun kısmını anlamışsınızdır. Şimdi 1977’de Donald Knuth hocamızın geliştirdiği Five-guess algoritmasına bakabiliriz.

Bu arada şu kaynaklardan daha detaylı öğrenebilirsiniz:

Bu hocamız demiş ki eğer aldığımız doğru renk sayısını ve tahminimizi geriye kalan olasılıklarla karşılaştırırsak ve aynı sayıda olmayanları kümeden silersek kümemiz hızla küçülecek ve doğru sonucu bulmamız o kadar hızlanacaktır.(Bunu anlaması biraz güç farkındayım şimdi bir örnekle daha iyi açıklamaya çalışacağım, bu örneği yazılan kod üzerinden vereceğim.)

Tahmin Uzayı (Bu kelimeleri renk sıralaması gibi de düşünebilirsiniz):

[Muzaffer, Kadir, Yılmaz, Abaküs, Sürat, Demlik]

Tahmin edilmesi gereken kelime: Demlik

İlk Tahmin edilen kelime: Muzaffer

İlk Tahmin rastgele olabilir eğer kritik harfleri içeren yani kullanım frekansı az olan  kelimeleri seçmek avantajlı bir başlangıç doğurabilir. Örneğin J, F, V, Ğ gibi harfleri içeren bir tahmin olabilir.

Demlik ile Muzaffer kelimelerinin arasında m, e harfleri ortak olarak bulunur yani karşı takımın dönütü 2(benzerlik) olacaktır.

İkinci aşama olarak sözlükteki tüm kelimeler ile Muzaffer kelimesi karşılaştırılır ve Muzaffer kelimesi sözlükten silinir.

Muzaffer – Kadir = 2(benzerlik) a,r

Muzaffer – Yılmaz = 3 a,z,m

Muzaffer – Abaküs = 1 a

Muzaffer – Sürat = 2 a,r

Muzaffer – Demlik = 2 m,e

Burada benzerliklere bakarken kartezyen olarak bakmadık yani mesela Abaküs kelimesindeki a harfi 2 tane olduğu için Muzaffer kelimesindeki a harfiyle çarpılarak toplanmaz birbirini götürür. Kartezyen olarak bakarsak her harf için ayrı ayrı bakıp sonuca giderdik ve böylece Muzaffer ve Abaküs arasındaki benzerlik 2 olurdu. Tüm karşılaştırmaları kartezyen olarak yaparsak da algoritma doğru çalışacaktır.

Benzerlik sayısı 2 olmayanları listeden sildiğimizde listemiz:

[Kadir, Sürat, Demlik] olacaktır.

Şimdi rastgele seçtiğimiz kelime Kadir olsun.

Kadir – Demlik arasında 3 harf benzerdir böylece karşı takımın vereceği cevap da 3 olacaktır. Aynı işlemleri yaparsak:

Kadir – Sürat = 2 a,r

Kadir – Demlik = 3 d,i,k

olacaktır Kadir ve Sürat kelimelerini silersek sadece Demlik kelimesi kalır ve cevabımız olur.

Koda geçecek olursak mastermind oyununa benzer bir yapıda olsa da hangi harfin hangi noktada doğru yerleşip yerleşmediği hakkında bir bilgi alamıyoruz yani ● cevabını hiç alamıyoruz. Sadece kaç tane ○ cevabına sahibiz biliyoruz bu da benzer harf sayısına denk geliyor.

Koda buradan ulaşabilirsiniz:

https://github.com/muzafferkadir/findingWordsWithMasterMind

65binlik bir sözlük kullandık siz de farklı modlardan birini seçip deneyebilirsiniz.

1 Yorum

Yorum Bırak...