Türk'ün LittleAlchemy'yle İmtihanı

Bundan hemen önce yazdığım Unrar kütüphanesi serisinde, işlerden zaman buldukça yazmaya devam edeceğimi yazmıştım ancak durumlar hiç de benim beklediğim gibi olmadı. Aslında iş yoğunluğu normale döndü ancak çalışma saatleri dışında oyun oynamaktan ötürü yazmaya zaman ayıramadım. Ben de madem oyun oynuyorum, oyunla ilgili birşeyler yazmaya karar verdim.

Üzerinde konuşacağım oyun Little Alchemy. Aslında 2010 yada 2011'de çıkmış eski bir oyun ama ben keşfedeli çok zaman olmadı. Bilmeyenler olabileceğini düşünerek özetlenirse; oyun 4 temel elementle başlıyor: Hava, Su, Ateş, Toprak. Amaç, bu temel elementleri birleştirerek diğer maddeleri oluşturmak. Bu yazıyı yazmamdan 3 gün öncesine kadar veritabanında 420 element vardı, şu anda 430 tane var. Birkaç ayda bir kullanıcılardan gelen geri beslemeye göre element listesi güncelleniyor. Little Alchemy çok basit bir oyun ancak RSA şifrelemesi gibi tamamlamak için çok fazla olasılık var ki oyunu asıl zor hale getiren de bu. Bütün farklı kombinasyonları tek tek denemeye çalışmak pratikte imkansız gibi.

Element birleştirme işlemi sağ taraftaki elementler listesinden elementleri sol tarafa sürükleyip birbirlerinin üstüste çakıştırmak biçiminde. Örneğin Ateş + Toprak = Lav, Lav + Hava = Taş, Hava + Toprak = Toz, Toz + Ateş = Barut ... biçiminde ilerliyor. Element sayısı az olduğu zaman birleştirmek kolay ama element sayısı arttıkça elementlerin arasında gezinirken genelde neyi neyle birleştirdiğinizi unutup bir yerden sonra olduğunuz yerde saymaya başlıyorsunuz. Dolayısıyla elle hiçbir yardım olmadan denemek bir yerden sonra etkili olmuyor. Bunu fark ettikten sonra yaptığım işlemleri Excel tablosuna aktarmaya başladım. Bir yerden sonra sonuçlar tabloya da sığmaz hale geldi, üstelik hem daha önce denediğim bazı kombinasyonları tekrar denememi önlemiyordu hem de tabloda sürekli arama yapmak pratik değildi.

Oturup çözüm için basit bir algoritma geliştirdim ve MATLAB'de kodladım. Mantığı basit ve büyük olasılıkla da en optimal algoritma değil. Sadece beni aynı şeyleri tekrar denemekten kurtarsın diye yazdım. Yazıyı uzatmamak için sadece pseudokodu ekleyeceğim. Kodun içerisinde dört sütundan oluşan bir tablo tutuyorum. En başta satır sayısı elimdeki element sayısına eşit yani dört. İlk sütun elementin adı. İkinci ve üçüncü sütunlar elementin bileşenleri (ilk 4 element için sıfır.) Son sütun da elementin başka elementler verip vermeyeceğine dair bir flag. Dikkat edilirse bazı elementlerin üstüne gelince arkaplan hafif kırmızı oluyor. Bu elementler başka elementlerle daha fazla etkileşime girmiyorlar, ağacın yaprakları gibi en uçta bulunuyorlar. Örneğin 'Obsidian' gibi (water + lava). Dolayısıyla yeni element ararken zamandan kazanmak için bunları tekrar etkileşime sokmaya gerek yok. Elementlerin kodları da listeye eklendiği sıra sayıları oluyor. Bir de etkileşim tablosu tutuyorum. Bu, o anda bildiğim element sayısı kadar dereceye sahip bir kare matris. Yani ilk adımda 4x4 bir matris. Matrisin i. satır ve j. sütun elemanının değerine göre, i. elementle j. element etkileşime girmiş mi giremiş mi bunu tutuyorum. Henüz denememişsem değeri -1, etkileşim olmuyorsa 0, etkileşim oluyorsa 1. İlk değeri -1'lerden oluşan 4x4'lük bir matris. Elbette ki değişme özelliği bulunduğundan i. ile j.'yi karıştırmakla j. ile i.'yi karıştırmak arasında herhangi bir fark yok. Yani aslında  sadece matrisin üst yada alt üçgen kısmını tutmak yeter ancak kafa karıştırıcı olmaması açısından ben her ikisini de tutacağım. Bu matrisin bütün çalışma süresince simetrik olacağı açık.

Yukarıda bahsettiğim iki tablo kodun kritik değişkenleri. Öyle ki bu değerleri belli aralıklarla diske yazıyorum, çalışmaya ara vermem gerektiğinde sadece bu iki tabloyu yükleyerek çalışmaya kaldığım yerden devam edebiliyorum. İki tablonun içeriği oluşturulduktan sonra sürekli olarak kullanıcıya şununla (i. element olsun) şunu (j. element olsun) karıştır sonucu yaz diyor. Eğer bir sonuç varsa bunu listeye ekleyip etkileşim matrisinin (i, j) ve (j, i) elemanlarını 1 yapıyor. Bütün karşılıklı etkileşimleri denedikten sonra yeni eklenenler kadar etkileşim matrisini genişletiyor ve yeni baştan yeni eklenen elementlerle denemeler yapıyor.

Pseudokod şöyle:

ilk 4 elementle veritabanini ve etkilesim matrisini olustur.

while(toplam < 430)
  eleman_sayisi = veritabani.size;
  toplam = eleman_sayisi;
  for k1 = 1:eleman_sayisi
  . k1. eleman tepkime veriyorsa;
  . for k2 = 1:eleman_sayisi
  . . k2. eleman tepkime veriyor ve k1 ile k2'nin etkilesimi bilinmiyorsa;
  . . sonuc = input( element(k1) + element(k2) = ? );
  . . eger sonuc yoksa etkilesim(k1, k2) = etkilesim(k2, k1) = 0;
  . . sonuc varsa
  . .   ayni element daha once listeye girilmemisse 
  . .     adini gir, onculler k1 ve k2 gir
  . .     baska etkilesime giriyorsa 4. sutun true, degilse false
  . .     etkilesim(k1, k2) = etkilesim(k2, k1) = 1;
  . .     toplam = toplam + 1;
  . .   daha once girilmisse
  . .     etkilesim(k1, k2) = etkilesim(k2, k1) = 0;
  . endfor
  endfor

  eklenen = toplam - eleman_sayisi;
  etkilesim matrisinin sagina (eleman_sayisi x eklenen) boyutlu -1'lerden olusan matrisi ekle
  etkilesim matrisinin altina (eklenen x (elesay + eklenen) boyutlu -1'lerden olusan matrisi ekle

end

Programı çalıştırınca while döngüsünün ilk adımında sırayla şu yeni elementler oluşacak:

1. Su + Su = Deniz
2. Su + Ateş = Buhar
3. Su + Toprak = Çamur
4. Su + Hava = Yağmur
5. Ateş + Toprak = Lav
6. Ateş + Hava = Enerji
7. Toprak + Toprak = Basınç
8. Toprak + Hava = Toz
9. Hava + Hava = Basınç

9. adımdaki basınç 7. adımda bulunduğundan listeye toplam 8 element eklenecek. Bazı elementler birden fazla biçimde yapılabildiği için kodda elementin daha önceden listeye eklenip eklenmediğine dair bir kontrol gerekiyor. Ayrıca bazı elementlerin birleşimi sonucunda birden fazla yeni element oluşabiliyor. Bu durumda da tablolara elle müdahale etmek gerekiyor.

Yukarıdaki kodun ne kadar çalışacağını kestirmek için bir elementin derecesi diye bir kavram ortaya attım. while'in ilk adımında ortaya çıkan (yani yukarıda saydığım) elementlere birinci derece elementler diyelim. Bir sonraki adımda bunlarla etkileşime girince oluşacaklar ikinci derece elementler olsun. En başta elimizde olan dört element sıfırıncı derece elementler olsun. Sıfırıncı dereceden birinci dereceye geçişte element sayısı 3 katına artıyor. Bu durumda ikinci derecede 36 element, üçüncü derecede 108, dördüncü derecede 324 element ve 430 element bulunduğundan bütün elementler en fazla beşinci derecede bitecektir diye kaba bir hesap yaptım. Başka tahmin modelleri de uygulanabilir ancak bulduğum diğer modeller de elementlerin yaklaşık beşinci derecede biteceğini öngörüyor. Elle beşinci dereceye kadar gelebilmek 1-1.5 saatimi aldı fakat evdeki hesap çarşıya uymadı. Beşinci derece elementlerle birlikte sadece 110 elemente ulaşabildim. Bu algoritmaya uymadan rastgele denemelerle, 180'e yakın element ürettiysem de bir sistematiğe oturtmadan bütün elementleri bulmak bence imkansız. Yaklaşık 2-2.5 saat sonra bütün altıncı derece elementleri de tamamladım fakat 164 tane oldu. 200'ü bile bulamadım.

Yedinci derece elementleri taramaya başladıktan sonra bu işin elle de yapılamayacağını fark ettim. Öyle ki bütün elementleri bulmak için işten 3-5 gün izin almayı bile düşündüm. Sonra bir ihtimal diyerek sayfanın kaynağını incelemeye başladım. Bütün java scriptleri indirip inceledim (ki hiç java script yazmamış bir insan olarak anlayabildiğim, Macarca bir diyalogda sadece arada geçen Michael Jackson kelimesini anlayıp sevinmek eylemine benzetilebilir). Kodların içinde, elementlerin ad ve birleşim tablolarını tutan iki listenin adına rastladım. Bunları oyunu yapanların haklarına saygısızlık olacağı gerekçesiyle burada ilan etmeyeceğim ancak ilgilenen ve yeteneğine güvenenler varsa kodları kendi inceleyebilir. Yalnız bir ipucu vereyim, tablolar JSON biçiminde saklanıyor. Bunları indirip, Notepad'in karakter değiştirme işleviyle bile halledilebilecek ufak birkaç değişiklikle MATLAB'in anlayacağı biçime dönüştürdüm ve tek bir for döngüsünden oluşan bir sorguyla bütün çözümleri buldum. Veritabanıyla ilgili bir not daha: Oyunun sanıyorum paralı sürümü var ve bedava sürümünden 30 element fazlası var. Veritabanında bu elementler görünüyor ancak bileşenleri anlamsız girdilerden oluşuyor. Veritabanını indirenler ne dediğimi anlayacaklardır.

Ömrümü yedin.

Gelelim tahminin hatasına. İlk 4 element birbirleriyle yoğun olarak tepkimeye giriyorlar, sonraki derece elementler bu kadar yoğun olarak etkileşmiyorlar. Dolayısıyla ilk adımlarda yapılan tahminler her şekilde iyimser kalıyor. Her derecedeki element sayısını görselleştirince aşağıdaki grafik çıkıyor:

Aslında artış üstel olarak devam etmesi gerekirken element sayısının sınırlı olması nedeniyle 9. dereceden sonra artış çok azalıyor. Bir de elbette ki benim tüm tahminlerim etkileşimin sınırsız olması üzerine ancak derece ilerledikçe elementler karmaşıklaşıyor ve birbiriyle etkileşimi zorlaşıyor. Basit elementlerin birbiriyle etkileşimi daha kolay. Vampirle çalar saatin veya aslanla şarabın etkileşime girmesi sanırım imkansız.

Bütün elementleri bulduktan sonra kafam biraz rahatladı ve işten izin almama gerek kalmadı ama tam olarak değil. Bu sefer benim yaklaşımımı incelemek için yukarıda yalancı kodunu verdiğim programı çok az değiştirip oyunun veritabanını kullanarak bir denemeye tuttum. Yaptığım çok basit; elle girdiğim girdileri veritabanına bakarak olup olmayacağını deniyor. Kodu yine çabucak MATLAB'de yazdım. Veritabanı zaten MATLAB matris biçimindeydi. Bazı elementleri elde etmenin birden fazla yolu olduğundan sorgulama uzun sürdü ancak sorgulamanın asıl uzun sürmesinin nedeni MATLAB'de yazdığım halde find'la halledilmesi gereken yerlerde fazlaca for döngüsü kullanmış olmam. Zaten algoritma da en optimal halinde değil. Bütün bu olumsuzluklar birleşince elementlerin tamamını sayıp dökmesi 2-3 saatini alıyor. Benim yaklaşımımla çözünce, en fazla 16. dereceden iki tane element var ( meteor = atmosphere + meteorid , solar system = sun + planet ). Toplam karşılaştırma sayısı 92665 ( = 430 * 431 / 2 ). Bir günün 86400 sn olduğunu gözönüne alınca dikkate değer bir sayı, üstelik her saniyede bir karşılaştırma yapmak olanaksız. Liste çok uzadığında gerekli elementi bulmak bile zaman kaybettiriyor. Uzun lafın kısası, bütün elementleri tek tek denemek yazının başında RSA şifrelemesiyle ilgili yaptığım benzetmeyi haklı çıkardı.

Elementler üzerinde kafa yorulacak başka bir problem de bütün elementlerin temel dört element cinsinden yazılmasıyla ilgili. En başta bunun elementin derecesiyle birebir aynı olacağını düşünüyordum ama değil. Şöyle bir örnek vereyim eruption ( = energy + volcano ) üçüncü derece element ama temel elementler cinsinden yazıldığı zaman eruption = ( earth +( earth + fire ))+( air + fire ) halinde 5 temel element ile yazılabiliyor. Sonradan düşünce bunun nedenini anlamak zor değil. Belki biraz cebir bilgisi gerekirebilir.

Bütün elementlerim en fazla üçüncü dereceden elementler olsalardı dediğim doğru olurdu. Şöyle açıklanabilir; ilk başta elimde sadece 1 sayısı ve kural olarak toplama işlemi var. Bununla sadece 2 elde edebilirim. İkinci adımda elimde {1, 2} kümesi oldu. Bunlarla 1+2 = 2+1 = 3 elde edebilirim. Üçüncü adımda {1,2,3} kümesinden elde edebileceklerim artık kümenin en büyük elemanından bir fazlası değil çünkü 2+3=5. Başka bir yaklaşıma göre de, elimdeki n. derece elementlerden n+1. derece elementleri elde ederken yalnızca dört temel elementi eklemeye iznim olsaydı (yani bir önceki örnek üzerinden gidersek, kümenin bir sonraki elemanını elde ederken, keyfi bir eleman değil yalnızca 1'i alma hakkım var diyelim) o zaman yine doğru olacaktı.

Eruption'da da benzer şey geçerli, birinci derece bir elementle ikinci derece bir element etkileşime giriyor. Tabi derecelendirme sıfırdan başladığından yaptığımız 2+3 işlemi oluyor.

Tüm elementleri temel elementler türünden yazma sorununu ele alırken yine MATLAB kullandım. Önce element veritabanını basitleştirdim. Bazı (yaklaşık 200 tane) elementlerin birden fazla biçimde oluşturulabildiğini söylemiştim. Bunları gözönüne almadan, veritabanında karşıma ilk çıkanı aldım ve üç sütunluk bir tablo oluşturdum. Elementin adı, bileşen1, bileşen2. İlk dört element için bileşen1 ve bileşen2 değeri 0. Sonra basit özyinelemeli (recursive) bir fonksiyon yazdım.

function cozumle(element)
// negatif sayilar ozel karakterler: -9='+', -6='(', -3=')'
bil1 = veritabani(element).bilesen1;
bil2 = veritabani(element).bilesen2;

if( (bil1 <= 4) && (bil2 <= 4) )
  return [ -6, bil1, -9, bil2, -3 ];
elseif( (bil1 <= 4) && (bil2 > 4) )
  return [ -6, bil1, -9, cozumle(bil2), -3 ];
elseif( (bil1 > 4) && (bil2 <= 4) )
  return [ -6, cozumle(bil1), -9, bil2, -3 ];
else
  return [ -6, cozumle(bil1), -9, cozumle(bil2), -3 ];
end

Bundan sonrası gelen sayıları temel element adlarına yada (, ), + karakterlerine çevirip ekrana yazdırmak. Buna göre en fazla sayıda temel elementle yazılabilen 'ghost' var ( = night + graveyard ), tam 163 tane. Bunu takip eden 158 ile 'constellation' ve 'galaxy' var. Bazı elementlerin birleşimi sonucu birden fazla element çıktığını söylemiştim. Bu iki element de aynı şekilde 'star + star' sonucu ortaya çıkıyor. Bunlardan sonra üçüncülük 139 elementle 'pigeon'da ( = bird + city ). Bir de son olarak bunların dağılımına bakarsak asıl kümelenme 2 ile 20 arasında fakat 60'a kadar ciddi bir miktar var. 

Son olarak, bütün bu yazdıklarıma ek birşey daha kaldı. O da oyundaki elementlerin çizgesini (graph) daha doğrusu ağacını çıkartmak ancak buna uygun bir program bulamadığım için onu şimdilik yapmayacağım. 

Sonuç olarak sanıyorum ki bu yazıda dünyanın en basit oyunu üzerine dünyanın en uzun incelemesini yaptım. Yeri geldi sevdiklerime ayırmam gereken zamanda deli gibi MATLAB kodu yazdım, yeri geldi işe 4 saat uykuyla gittim. Sonunda da elime oyunu bitirmiş olmaktan başka birşey geçmedi. Böyle de duygusal bir kapanış oldu.