Algoritma

Sözlükten kelime bulma algoritması

Mastermind oyununu bilenleriniz bilir (ben bilmiyorum). İki kişi oynanan bu oyunda taraflardan biri 6 farklı renkten bazılarını seçerek 4 renkten oluşan bir kombinasyon oluştur, diğer taraf ise bu renk sırasını tahmin etmeye çalışır. Her tahminden sonra kaç tane rengi doğru tahmin edildiği gibi bazı ipuçları verilir. Eğer tahmin eden taraf bu ipuçlarını takip eder ve en fazla 11 tahminde doğru renk kombinasyonunu bulursa oyunu kazanır.

Şimdi aynı oyunun bir benzerinin kelimeler üzerinden oynandığını düşünelim. Bu oyunda renklerin yerini karakterler, renk kombinasyonunun yerini de kelimeler alır. İlk olarak oyunculardan biri sözlükten bir kelimeyi seçer. Diğer oyuncu bu kelimeyi tahmin etmeye çalışır. Bunu da sözlükten bir kelime seçerek yapar. Eğer tahmini yanlışsa ilk oyuncu bu kelimenin tuttuğu kelime ile ne kadar benzerlik taşıdığına dair bir sayı söyler. İkinci oyuncu , bu ipucunu dikkate alarak tekrar bir tahminde bulunur ve oyun böyle devam eder.

İlk olarak işe ipucu olacak sayının nasıl elde edildiğini anlamakla başlayalım. İkinci oyuncunun tahmin ettiği kelimeye bakalım ve kendimize şu soruyu soralım : “Benim tuttuğum kelime, bu tahminin içindeki kaç karakteri içeriyor ?”. Aşağıdaki tablonun her satırında bir kelime, yanlış bir tahmin ve o tahminin kelimeye ne kadar benzer olduğuna dair ipucu değeri verilmiştir :

Artık ipucu değerlerinin nasıl elde edildiğini biliyoruz. Bir tahminde bulunduk ve tahminimiz tutmadı, oyuncu size ipucu değerini verdi. Peki şimdi ne olacak? İşte problemin kırılma noktasına geldik, evet sözlükte binlerce kelime var fakat bu kelimelerin arasında bir yerlerde tutulan kelime de var. Yani tahminimizdeki kelimeyi sözlükteki kelimelerle karşılaştırıp her biri için bir ipucu değeri elde edersek, sıra o kelimeye geldiğinde tekrardan ilk oyuncunun bize söylediği ipucu değerini elde edeceğiz. Sözlükteki kelimelerden aynı ipucu değerine sahip olmayan kelimeleri elersek tahmin uzayımız bir hayli daralacak. Unutmayın, sözlükten ipucu değerleri elde edilirken sözlükteki kelime tutulan kelimeymiş gibi düşünülmeli, tersi durumda farklı değerler elde edilir. Daha iyi anlaşılması için aşağıda bir örnek verilmiştir.

Resimde tutulan kelime “deniz”, ilk tahmin “demlik”tir. İpucu değerinin 3 olduğu öğrenildikten sonra tahmin edilen kelime tablodaki tüm kelimelerle karşılaştırılıp ipucu değeri 3 olmayanlar elenmiştir. Kalan kelimeler arasından rastgele bir kelime (dekan) seçilmiş, yeni seçilen kelime için de ilk oyuncudan yeni bir ipucu değeri alınmıştır ve aynı işlemler tekrar edilmiştir. İkinci tahmindeki ipucu değeri ile ilk tahmindeki ipucu değerinin aynı olması tesadüftür. Daha yüksek yada daha düşük bir ipucu değeri de çıkabilirdi. Burada amaç, tahmin uzayını olabildiğince daraltmak. İpucu değeri h() fonksiyonu ile temsil edilmiştir.

Son olarak yukarıda anlattığım algoritmayı kullanarak c dili ile yazdığım programın çıktısını görmektesiniz. Sözlük olarak içerisinde yaklaşık 380.000 kelime bulunan bir wordlist kullandım. Tuttuğum kelime “sea” idi. Tahmin uzayının ne kadar hızlı daraldığına dikkat edin.

1 thought on “Sözlükten kelime bulma algoritması

Leave a Reply

Your email address will not be published. Required fields are marked *