Kayar Noktalı Sayılar ve Kesme Hataları

Merhaba. Bu konuda uzun zamandır yazmak istiyordum ama zaman bulamıyordum. Konu, geniş olduğundan kafamda toparlamak ve yazmak uzun zaman aldı. Aynı nedenden yazıyı iki parça olarak böldüm. Bu yazılarda tek değerlikli (single precision) sayılar üzerinden bilgisayarda ondalıklı (floating point) sayıların nasıl tutulduğunu ve bunun ne tür hatalara yol açtığını anlatacağım. Öncesinde iki ilginç ekran görüntüsü ekledim. İlki Excel 2007'den ama daha güncel sürümlerde de benzer sonuçlar elde edilebilir:

A sütununda formüllerin sonuçları var. B sütununda, A sütunundaki formülleri metin olarak yazdım. Yani A1'de =1-0.2-0.2-0.2-0.2-0.2, A2'de =1-0.1-0.1...-0.1 (10 tane 0.1) var. A2 ve A3'teki sonuçlar ilginç. Sıfır olması gereken iki sonucun da sıfırdan saptığı görülüyor. Bu neden oldu? İkinci sorulması gereken aynı ilginçlik A4 veya A5'te neden tekrarlanmıyor? Aşağıda görüleceği gibi Octave/Matlab'le de aynı sonuçlar alınıyor.

Bu davranışla ilgili bir ipucu vereceğim. Octave'da varsayılan veri türü çift değerlikli (double) sayı. Tamsayı olduğu halde 1 bile çift değerlikli olarak işlem görüyor (yandaki ekran görüntüsüne bakınız). Sayıları 0.2 yerine single(0.2) verip (tek duyarlıklı sayıya dönüştürüp), bunları ardarda 1'den çıkardığımda hata artıyor. Örn. 0.2 için hata 10^-17 mertebesinden 10^-8 mertebesine yükseldi ama single(0.0625) için hata yine 0.

Sayıların Bilimsel Gösterimi
Hatanın nedenlerine inmeden önce okul yıllarına dönüp normalleştirilmiş sayı ve sayıların bilimsel gösterimini hatırlamak gerekiyor: Çok büyük veya çok ondalıklı sayılar yazılırken sayının anlamlı basamakları yazılıp yanına 10ⁿ gibi bir çarpan eklenir. Sıfıra yakın sayılar için n, negatif ve büyük sayılar için n pozitif olur.

Örn.
6 720 000 000 = 6.72 * 10⁹
0.000 000 007 51 = 7.51 * 10^-9

m, bir gerçel sayı ve n bir tamsayı olmak üzere, onluk tabandaki bilimsel gösterim, m * 10ⁿ olarak genellenir. m'e katsayı, n'e üs diyelim. m'i gerçel sayı seçtim ama bunun üzerine bazı kısıtlamalar daha koymak gerekir. d_i'ler rakamlar {0, 1, ..., 9} ve d₀, sıfır olmamak üzere m aşağıdaki gibi yazılabilir:

d₀'ın sıfır olduğunu düşünelim: Örn. 0.672 * 10¹⁰ = 6.72 * 10⁹
d₀'ın 10dan büyük bir değer olduğunu düşünelim: 67.2 * 10⁸ = 6.72 * 10⁹

Dolayısıyla her sayı yukarıdaki gibi tek bir şekilde yazılabilir. Yukarıda onluk tabanın altını çizdim çünkü herhangi bir sayı sistemine genellersem yukarıdaki ifade şöyle olur:

İkilik sayı sistemi için b = 2 seçilir ve kısıtlar gözönüne alınırsa ikilik sayı sisteminde d₀'ın yalnızca 1 olabileceği görülür.

İkilik Sayı Sisteminde Ondalıkların Gösterimi
Bu konu lise matematiğinin dışında ama mantığı basit. Onluk sistemde basamak değerleri şöyle:

İkilik sayı sistemine genellendiğinde basamak değerleri 2⁰, 2¹, 2²... olarak gidiyorsa noktadan sonraki basamak değerleri de benzer biçimde 2^-1, 2^-2, 2^-3... şeklinde devam eder.

Yukarıdaki sayı 2³ + 2¹ + 2⁰ + 2^-2 + 2^-3 = 11.375'dir. Kısacası ikilik sayı sisteminde de sayılar bilimsel gösterimle tekil olarak yazılabilir. Katsayının tamsayı kısmının her zaman 1 olacağını yazmıştım. Bu gösterimde tamsayılar aşağıdaki gibidir:

1 = 1 * 2⁰
2 = 1 * 2¹
3 = 1.5 * 2¹
4 = 1 * 2²
5 = 1.25 * 2²
6 = 1.5 * 2²
7 = 1.75 * 2²
8 = 1 * 2³
...

Ondalıklı sayıları bilgisayarda göstermek için, Hexpert adında bir Hex düzenleyici (editör) kullanacağım. Bu düzenleyiciyi bilgisayarla tanıştığım zamandan beri kullanıyorum. En sevdiğim düzenleyici ama artık geliştirilmiyor. İkinci sevdiğim düzenleyici HxD ve aktif olarak geliştiriliyor. Bu yazıyı hazırlarken baktığımda HxD'nin yeni sürümünün çıktığını farkettim. Son sürümde dosya düzenleme daha yetenekli duruma gelmiş ve bu düzenleyici de kullanılabilir. Ben ekran görüntülerini Hexpert'den aldım. Aşağıda küçük bir dosyanın ekran görüntüsü var. İçinde boşluklar olan bir metin dosyası oluşturup bunu açmak yeterli.

Yanda dosyanın byte'ları, alttaki kutularda imlecin olduğu yerdeki 8, 16 ve 32 bitlik değerler var. S'ler işaretli U'lar işaretsiz değerler. İşaretli sayılarda sayının ilk biti işaret (birse negatif, sıfırsa pozitif) biti. İşaretsiz sayılarda bu bit sayıya katılıyor. Alttaki kutular değerleri elle girmeye olanak veriyor. Örn. 30h ofsetindeki 8 bit (00h) ve 16 bit (00h 00h) değer sıfır. Gösterim Little Endian olduğundan 32 bitlik değerin byte'ları tersine okunduğunda (3fh 80h 00h 00h) 63 * 256³ + 128 * 256² + 0 * 256 + 0 = 1 065 353 216 değerini alıyor. Asıl ilgilendiğim FP32 hücresi. Ondalıklı sayılar bilgisayarda her zaman işaretli olarak ele alındıklarından bunların işaretsizi yok. FP32, 32 bit floating point yani tek değerlikli anlamına geliyor. FP64 ise 64-bit floating point (çift değerlikli). Buna şimdilik değinmeyeceğim. Yalnızca 40h offsetinde FP64 1.0 değeri var.

Bu gösterim IEEE-754 standardıyla belirleniyor. 1985'teki standartta 'single' ve 'double' ifadeleri geçerken 2008 revizyonunda bunlar binary32 ve binary64 olarak anılıyor. Standarda göre 32 bitlik ondalıklı sayının ilk biti işaret, sonraki 8 bit [30-23] üs ve geri kalan 22 bit [22-0] katsayı. 1.0'ı buna göre ayrıştıralım:

3F 80 00 00 = 0|011 1111 1|000 0000 0000 0000 0000 0000

[ Hexpert'te Alt+B ile ikilik taban görünümüne geçilebilir. ]

Tamsayı kısmı her zaman 1 olduğundan bu saklanmaz, her hesaplamada kendiliğinden eklenir. Dolayısıyla burada katsayı 0 + 1 = 1. Üs 0111 1111b = 127 ve standart gereği üsten 127 çıkarılır. Yani gerçek üs 127 - 127 = 0. İşaret biti 0 olduğundan pozitif. Hesaplandığında 1 * 2^(127-127) = 1 bulunur.

2 = 1 * 2¹ olarak yazılır. Katsayıdan bir çıkarılırsa 1 - 1 = 0 ve üsse 127 eklenirse 1 + 127 = 128. O halde 2 şöyle ifade edilir: 0|100 0000 0|000 0000 0000 0000 0000 0000 = (40 00 00 00)₁₆. Tabii Little endian olduğundan byte'ların tersine yazılması gerekir.

Katsayı bitlerinin ondalıklı ikilik sayılar olduğuna dikkat edilmelidir. Örn. 200 = 128 + 64 + 8 = 2⁷ + 2⁶ + 2³. Üs olarak en büyük üssün değeri seçilmeli. O halde 200 = 2⁷ * (1 + 2^-1 + 2^-4) = 1.1001b * 2⁷ = 1.5625 * 2⁷. Katsayıdan 1'i atınca kalan .1001 ve üs 7 + 127 = 134 = 1000 0110b. Hepsini toparlayınca sayı: 0|100 0011 0|100 1000 0000 0000 0000 0000 = (43 48 00 00)₁₆.

Ondalıklı sayıları ifade etmek için hiçbir engel kalmadı:

Örn. 0.25 = 1 * 2^-2. Üs -2 + 127 = 125 olur : 0|011 1110 1|000 0000 0000 0000 0000 0000

Şimdi periyot seyreden sayıları hatırlayalım. Bölmeleri kesirler yerine ondalıkla ifade etmeye kalktığımızda bölünen bölene tam bölünmüyorsa bölümde ondalıklar birbirini tekrar eder. Örn: 7 / 90 = 0.0707... Ondalık sayının bilgisayarda gösteriminde sürekli ikiye bölme ve ikilik kesirlerle ifade etme var. Peki ondalıklı sayılarda böyle bir periyot durumu olur mu? 0.1'i ele alalım. Bunun karşılığı: 0|011 1101 1|100 1100 1100 1100 1100 1101. Üs 123 - 127 = -4. Katsayıları ayırıp toplarsak aşağıdaki gibi oluyor:

Eğer en düşük değerli 2^-23 olmasaydı 0.599 999 904 632 568 359 15. Tam 0.6 (aslında 1.6) hiçbir zaman olmuyor. Sayıya 1 ekleyip 2^-4 ile çarpınca elde edilen sayı 0.100 000 001 490 116 119 370 703 125 ama Hexpert, Excel, Matlab ve Octave bu sayının ilk 6-7 basamağını gösterdiklerinde 0.1 görüyoruz (elbette şimdilik Matlab'de sayıların double olmasını görmezden geldim). Bu küçük fark her -0.1 işleminde birikerek artıyor ve sonuç sıfıra yaklaşıkça önem kazanıyor.

Not: Bu durum ikilik sistemin eksikliği olarak görülmemeli. Bilgisayarlar 10'luk sistemi kullanabilseydi ama insanlık 12'lik sayı sistemini kullanıyor olsaydı aynı durum yine yaşanacaktı.

Yukarıdaki sayıda dokuzuncu ondalıktan sonra sıfırdan farklı değerler görüldü ama 10 kere çıkarma yapıldığında aslında yapılan işlem "1-1.000 000 014 901 161 193 707 031 25" olup hata birikerek sekizinci ondalığa taşar. Octave'da tek değerlikli sayılarla aynı işlem tekrarlandığında hatanın 10^-8 mertebesinde olduğunu yazmıştım.

>> X=single(0.1)
X =  0.10000
>> 1-X-X-X-X-X-X-X-X-X-X
ans =  -7.4506e-008
>>

Bilgisayardaki katsayının son bitinin bir olması ve olmaması arasındaki fark, bilgisayarın iki ondalıklı sayı arasındaki anlayabileceği en küçük farktır. Eğer bu 1 ile kendisinden büyük ilk sayı arasındaysa bilimsel yazında makina epsilonu (machine epsilon) denir. Matlab'de eps işlevi bu değeri döndürür:

>> eps
ans =   2.2204e-016
>> eps('single')
ans =   1.1921e-007

Wikipedia'daki örneklerde aynı değerler karşılaştırılabilir:
Single-precision floating-point format
0|011 1111 1|000 0000 0000 0000 0000 0001₂ = 3f80 0001₁₆ = 1 + 2^-23 ≈ 1.0000001192
(smallest number larger than one)

Double-precision floating-point format

0|011 1111 1111 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001₂ ≙ 1 + 2-⁵² ≈ 1.0000000000000002, the smallest number > 1

Peki neden 0.0625'te hata olmadı? Çünkü 0.0625 aslında 0.0001₂ olduğundan işlemcide tam değeriyle ifade edilebiliyor. Haliyle hata olmuyor.

Yazının ikinci bölümünde ortaya çıkabilecek hataları detaylandırıp başka örnekler vereceğim.

Calculator the Game ve Çözümü (Function Pointers)

Merhaba. Bu yazı uzunca bir aradan sonra yine bir oyunla ilgili. Bir miktar yazılımdan bahsedeceğim ve Matlab kullanacağım. 

Yaz başında telefonuma "Calculator: The Game" adında bir oyun indirmiştim. Oyunun amacı bir sayıyla başlayıp verilen işlemler aracılığıyla ve sınırlı sayıda işlemle hedef sayıya ulaşmak. Oyunun videosu: https://www.youtube.com/watch?v=w5yyY341-4A Oyun, Google Play'de 5 milyondan fazla indirilmiş yani bilindik bir oyun olduğunu varsayıyorum.

Yandaki ekran görüntüsü ilk bölümden. Bu bölüm sıfırla başlıyor. Verilen işlem +1 ve amaç iki hamlede 2 elde etmek. Açık ki, başka da işlem olmadığından yapılması gereken iki kere +1'e basmak.

Bölüm 30

İlerleyen seviyelerde, dört işlem dışında işlemler ekleniyor. Örn. kaydırma '<<' işlemi 4321'i 432 yapıyor. Sayı ekleme, üzerinde sayı olan yan görüntüdeki gibi mor tuşlar. Mor 5, 432'den 4325 yapıyor. Yine yanda görülen dönüşüm tuşları sırayla sayının içindeki 1'leri 2 ( 1 => 2 ) ve 2'leri 3 yapıyor ( 2 => 3 ). Yandaki bölümün çözümü: 1, 2, 2=>3, 1=>2, 2, 1. SUM düğmesi sayının basamak değerlerinin toplamı olan sayıyı veriyor. Inv10 her basamağı 10'dan çıkarıyor. [+]1 bütün tuşların değerine 1 ekliyor. Store, aynı sayıyı birden fazla kullanmak için hafızaya alıyor. Shift, assembly'deki rotation'a karşılık geliyor. Mirror, sayının ayna görüntüsünü sayının sonuna ekliyor.

Örnekler:
4325 (SUM) -> 14 (SUM) -> 5
4325 (Inv10) -> 6785
4325 (Shift>) -> 5432 (<Shift) -> 4325
25 (Mirror) -> 2552 -> (Mirror) 25522552

Portallar, bir tuş olmayıp şunu yapıyor: Yüzler basamağından birler basamağına bir portal, işlem sonucu çıkan sayı 100'den büyükse yüzler basamağındaki sayıyı birler basamağına ekler.

Bölüm 60

Bu oyunu uzunca zaman oynadım. Oynarken bazı bölümlerin çözümü için bütün olasılıkları denemenin daha pratik olduğunu farkettim. Örneğin yukarıdaki ekran görüntüsü (Bölüm 30) ele alındığında, çözüm zor olmasa da denemek için 4 tuşa 6 kere basmak, 4⁶ = 4096 farklı kombinasyon gerektirir. Altmışıncı bölüm daha zor görünüyor ama iki tuşa 5 kere basmanın 2⁵ = 32 farklı kombinasyonu var. Bazı bölümleri akıl yürüterek çözmek yerine denemek daha hızlı sonuç veriyor.

Deneyerek (brute force) çözerken, bilgisayar kullanmamak düşünülemez, öyle ki 4096 çokmuş gibi görünse de bilgisayarda bir kaç saniyede denenebilir. Önemli olan soruna doğru şekilde yaklaşmak.

İşlemler kodun içinde yazılırsa, doğrusal olarak çalışan bir kod farklı sıralarla çağırılamaz. Tuşlara ait işlemlerin fonksiyon olarak tanımlanması gerekir. Tuş sayısı kadar fonksiyon bulunmalı veya başka bir deyişle her tuş fonksiyon olarak yazılmalı.

Tuşlara nasıl basılabilir? Örneğin beş tane tuş da olsa birine ardarda basmak sorunu çözüyor olabilir veya önce ilkine sonra ikincisine vs. Tuşların numaralandırıldığını düşünelim. Şimdilik tuş sıralamasının önemi olmasın. Beş tuş için beş farklı rakam kullanılsın. İşlem sayısı üçse, birinci tuşa ardarda basmak 111'e, tuşlara sırayla basmak 123'e karşılık gelir. Genellenirse, tuş sayısı kadar rakam ve hamle sayısı kadar basamak olur. Bu örnekte, tüm dizilimler 5³ = 125 olduğundan burada hepsini saymaya gerek yok ama 125, 134, 225, 334, 415, 531, 555 şeklinde örneklendirilebilir. Bu arada tuşlar numaralandırılırken 5 yerine 0 kullanılsaydı problemin 5lik sayı sistemiyle olan bağlantısı fark edilebilir.

125, sırayla 1., 2. ve 5. tuşlara basmak veya 1., 2. ve 5. fonksiyonları çağırmak anlamına gelir. O halde sayının değerlerine göre fonksiyonlar belirli sıralarla nasıl çağırılmalı? Bunu yapmanın en kolay yolu fonksiyonların kendisiyle değil göstericileriyle (pointer) çalışmak. Bu biraz karışık gelebilir. Hazır karışık demişken, C'de bu aşağıdaki gibi yapılır: 

#include<stdio.h>

void fonk1(int i)    {
  fprintf(stdout, "Fonk1: %d\n", i);
}

void fonk2(int i)    {
  fprintf(stdout, "Fonk2: %d\n", i);
}

void fonk3(int i)    {
  fprintf(stdout, "Fonk3: %d\n", i);
}


int main(int argc, char* argv[])    {
  void (*fparray[3])(int i);
  int i;
 
  fparray[0] = fonk1;
  fparray[1] = fonk2;
  fparray[2] = fonk3;
 
  for(i = 0; i < 3; i++)    {
    (*fparray[i])(i);
  }
 
  return 0;
}

Yukarıda tamsayı argüman alan basit üç fonksiyon tanımlanıyor. main() içinde bu fonksiyonlar için üç elemanlı void fonksiyon pointer dizisi oluşturulup göstericiler bu diziye atanıyor. C'de fonksiyonun adı zaten o fonksiyonun göstericisi yani ilk komutunun adresi olduğu düşünülürse atamalar için herhangi bir operatöre (*, &) gerek olmadığı görülür. For döngüsünde dizinin elemanları sırayla i argümanıyla çağırılır.

Bölüm 192

C'de fonksiyon göstericileri biraz zor (en azından benim için). Hangi parantez nerede olmalı kafa karıştırıcı olabiliyor. Ben çözüm için C yerine Matlab kullandım. Matlab'de bunu kodlamak daha kolay. C'deki & operatörü benzeri, Matlab'de fonksiyon göstericiler için @ bulunuyor. Göstericiler için matris değişken yerine hücre (cell) değişken ve argümanların fonksiyona uygulanması için feval komutunu kullanmak gerekiyor. Ben kodda sayı sistemleriyle uğraşıp tek for döngüsünde halletmek yerine tuş sayısı kadar içiçe for döngüsü kullandım.

Örneğin 192. seviye zordu. Bunun için kod yazmam gerekti. Bu bölümde beş tuş ve altı hamle var yani çok sayıda dizilim var. Binler basamağından birler basamağına bir portal bulunuyor. Önce tuşlara fonksiyon yazmakla başladım. Hatırlatma: Matlab'de fonksiyonlar kendi adlarını taşıyan dosyalara kaydedilmeli. İlk fonksiyon tus1.m dosyasında, ikinci fonksiyon tus2.m dosyasında vb.

function deger = tus1(deger)
  % +8
  deger = deger + 8;
endfunction

function deger = tus2(deger)
  % *4
  deger = deger * 4;
endfunction

function deger = tus3(deger)
  % Inv10
  s_deger = int2str(deger); % Sayiyi string'e donustur
  for k1 = 1:length(s_deger)
    if (s_deger(k1) != '0')
      s_deger(k1) = int2str(10 - str2num(s_deger(k1))); % karakterleri 10dan cikar
    endif
  endfor

  deger = str2num(s_deger); % tekrar sayıya dönüştür.

endfunction

function deger = tus4(deger)
  % sonuna 9 ekle
  deger = deger * 10 + 9;
endfunction

function deger = tus5(deger)
  % 7 => 0
  if( floor(deger / 100) == 7 )
    deger = deger - 700;
  endif
 
  if( mod(floor(deger / 10), 10) == 7 )
    deger = deger - 70;
  endif
 
  if(mod(deger, 10) == 7)
    deger = deger - 7;
  endif
 
endfunction

Portalı, her fonksiyondan dönen değerin girdiği ayrı bir fonksiyon olarak düşündüm. Fonksiyonun sonucu portal fonksiyonuna giriyor ve düzenlenmiş olarak çıkıyor. Portal fonksiyonuna "girdicikti" adını verdim:

function deger = girdicikti(deger)
  if(deger > 999)
    binler = floor(deger / 1000);
    deger = mod(deger, 1000) + binler;
    if(deger > 999)
      girdicikti(deger)
    endif
  endif
endfunction

Ana fonksiyon aşağıdaki gibi:

ilkdeger = 189;

% Function array
f_a = { @tus1, @tus2, @tus3, @tus4, @tus5 };

for k1 = 1:5
  for k2 = 1:5
    for k3 = 1:5
      for k4 = 1:5
        for k5 = 1:5
          %for k6 = 1:5
           
            adim1 = girdicikti( feval (f_a{k1}, ilkdeger) );
            adim2 = girdicikti( feval (f_a{k2}, adim1) );
            adim3 = girdicikti( feval (f_a{k3}, adim2) );
            adim4 = girdicikti( feval (f_a{k4}, adim3) );
            adim5 = girdicikti( feval (f_a{k5}, adim4) );

            if(adim5 == 500)
              printf("%d %d %d %d %d\n", k1, k2, k3, k4, k5);
              break
            endif
          %endfor
        endfor
      endfor
    endfor
  endfor
endfor

ilkdeger değişkeni bir fonksiyona giriyor. Bir tuşa basılması (fonksiyon) sonucu adim1 değişkeni oluşuyor. Sonra adim1'den ikinci fonksiyonla adim2 oluşuyor... İlginç bir şekilde bu bölüm iki farklı şekilde ve 6 yerine 5 işlemle çözüldü. Benim bilgisayarımda çözüm ortalama 15.96 sn sürdü. Program iki farklı çıktı üretiyor:

Bölüm 199

2 5 4 1 5: 189 (x4) -> 756 (7 => 0) -> 056 (9) -> 569 (+8) -> 577 (7 => 0) -> 500
4 2 1 4 2: 189 (9) -> 900 (x4) -> 603 (+8) -> 611 (9) -> 125 (x4) -> 500

199. seviye için de bir kod yazdım. Bu bölümde 4⁶ = 4096 kombinasyon var. tus3 bir öncekiyle aynı olduğundan yazmadım.

function deger = tus1(deger)
  % sonuna 7 ekleme
  deger = deger * 10 + 7;
endfunction

function deger = tus2(deger)
  % 3 => 5
  deger = str2num(strrep(num2str(deger), '3', '5'));
endfunction

function deger = tus4(deger)
  % shift >          3002 => 2300
  if(deger > 999)
    deger = mod(deger, 10) * 1000  +  floor(deger / 10);
  elseif(deger > 99)
    deger = mod(deger, 10) * 100  +  floor(deger / 10);
  elseif(deger > 9)
    deger = mod(deger, 10) * 10  +  floor(deger / 10);
  endif
endfunction

Onbinler basamağından birler basamağına portal:

function deger = girdicikti(deger)
  if(deger > 9999)
    onbinler = floor(deger / 10000);
    % onbinler basamagini al
    deger = mod(deger, 1000) + onbinler;
    % birler basamagina ekle
    if(deger > 9999)
      girdicikti(deger)
    endif
  endif
endfunction

Ana fonksiyonda bir öncekinden farklı olarak tuş sayısını değişkene atayıp for'ları bu değişkene kadar çalıştırdım:

clc
clear

ilkdeger = 3002;

f_a = { @tus1, @tus2, @tus3, @tus4 };
lfa = length(f_a);

for k1 = 1:lfa
  for k2 = 1:lfa
    for k3 = 1:lfa
      for k4 = 1:lfa
        for k5 = 1:lfa
          for k6 = 1:lfa
            adim1 = girdicikti( feval (f_a{k1}, ilkdeger) );
            adim2 = girdicikti( feval (f_a{k2}, adim1) );
            adim3 = girdicikti( feval (f_a{k3}, adim2) );
            adim4 = girdicikti( feval (f_a{k4}, adim3) );
            adim5 = girdicikti( feval (f_a{k5}, adim4) );
            adim6 = girdicikti( feval (f_a{k6}, adim5) );
            if(adim6 == 3507)
              printf("%d %d %d %d %d %d\n", k1, k2, k3, k4, k5, k6);
              return
            endif
          endfor
        endfor
      endfor
    endfor
  endfor
endfor

Bu bölüm altı adımda çözüldü. Çözüm "1 1 2 3 4 1" ve ortalama 0.68 sn'de çözülüyor:

3002 (7) -> 30 (7) -> 307 (3 => 5) -> 507 (Inv10) -> 503 (Shift>) -> 350 (7) -> 3507

Bu bölümle birlikte oyun bitiyor ve oyun sonu videosu başlıyor. Bu yazıda anlattığım yaklaşım oyunun bir çok bölümüne uygulanabilir ama Store ve daha önemlisi [+]2 gibi tuşlara uygulamak zor. İkinci tuş için global bir artım değişkeni tanımlanarak her fonksiyondaki değerler buna göre düzenlenebilir. Benim zorlandığım sorularda bu tür tuşlardan bulunmadığından kodunu yazmam gerekmedi. 

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.