Tanrının Sayısı 20 (ya da 26)

22 Nisan 2019

Hepimiz en az bir defa elimize Rubik Küpü almışızdır. Bir çoğumuz için eve alınan fakat çözülemeyen nesnelerdir Rubik Küpleri. Küpün bir yüzünü tamamladığınızda yüzünüzde oluşan o gülümsemeyi hatırlayın; ve daha sonra diğer yüzü yapmak için tamamladığınız yüzü bozmak zorunda kaldığınız için ne kadar üzüldüğünüzü.


Daha evvel buna kafa yormuş ve çözüm algoritmalarına hakim okurlarımız, siz bu tanımlama ve örneklemelerden muafsınız.

Rubik Küpü çok fazla değişik varyasyonda bulunabilen ve fakat çözümü için matematiksel hesaplama yapılabilen bir zeka oyunu. Çözümünün matematiğe dökülmesi hususunda (80'lerin başları) bir varyasyonun ne kadar zor olduğunun bir ölçütü olarak en az kaç hamlede çözülebildiği belirlendi. Ancak 1 hamlenin ne olduğu konusunda matematikçiler iki farklı görüş arasında anlaşamadılar. Bunlardan biri yalnızca 90° dönüşü (çeyrek tur sayımı) bir hamle sayarken, diğerleri bir yüzün ister 90°, ister 180° ya da isterse 270° dönüşünü (yarım tur sayımı) bir hamle sayıyorlardı. Bunlardan ilkini tercih edenler için 180° dönüş 2 hamleye tekabül ediyordu yani.

1981 Ocak ayında, çeyrek tur sayımı ile hesaplanmış çözüm için gerekli maksimum hamle sayısı 140 idi. Aynı yılın Temmuz Ayında yarım tur sayımı ile yeterli maksimum hamle sayısı 52 olarak hesaplandığından, çeyrek tur için üst limit de 104 olarak (2 katı) güncellendi. Algoritmayı iyileştirerek yapılan iyileştirmeler ile geçen zaman içerisinde daha az sayıda hamlenin yeterli olacağı ispatlanarak Temmuz 2010'da yarım tur sayımı için, Ağustos 2014'te de çeyrek tur sayımı için üst limitler, bu defa kesin olarak, belirlendi. Bunu başaranlar ise Tomas Rokicki, Herbert Kociemba, Morley Davidson ve John Dethridge adlarında matematikçi ve programcılar.

Hesaplanan Üst Limitin Gelişimi

Peki Rubik Küpünün toplamda 43.252.003.274.489.856.000 (43 quintillion) farklı pozisyonu içerisinde hepsinin en fazla 20 (ya da 26) hamle ile çözülebileceğini hesaplamak için neler yapılmış:
1- Önce bu varyasyonlar farklı gruplara ayrılmış.
2- Daha sonra bu varyasyonlar içerisinden birbirinin simetriği olanlar elenmiş.
3- 26 ve daha az sayıda hamle ile çözülebilecek varyasyonları bulmak için kod yazılmış.
4- Her grubun çözümü için 35 (ve diğer için de 29) CPU yılı (*) kullanılarak çözüm bulunmuş. (Bu 35 CPU yılı kadar bilgisayar gücü, programcı ve matematikçilerimize Google tarafından ücretsiz olarak sağlanmış.)

Çeyrek tur sayımında 26 hamlede çözülebilen yalnız 1 varyasyon varken, yarım tur sayımında 490.000.000 farklı varyasyon 20 hamlede çözülebiliyor. (Bence bu durum çeyrek tur sayımının daha doğru olduğunu gösteriyor.) Kullanılan algoritmaya göre çözümü en çok vakit alan (en zor) varyasyonu (ve çözümünü) buradan görebilirsiniz.

Bu noktada başlığı açıklamam gerekiyor sanırım. Deniyor ki; tanrı Rubik Küpü çözüyor olsaydı bunu mümkün olan en az hamlede yapardı. Bu sebeple de bu hamle sayısına Tanrının Sayısı adı verilmiş.

Bundan sonra Rubik Küpü çözmeye çalışırken 20 (ya da 26) hamleyi geçerseniz kendinize bir 20 (ya da 26) daha hak tanıyın. Yine olmuyorsa bir köşeye kaldırabilirsiniz.

(*) CPU Yılı: 1 FLOPS (Floating Point Operations Per Second) hesaplama gücünün bir ölçüsüdür. 1 GFLOP gücünde bir makine 1 saniyede 1 milyar işlem yapabilir. 1 GFLOP makine referans olarak alınarak hesaplanan CPU Yılı, bu makinenin 1 yılda yapabileceği işlem adedini ifade eder. Yarım tur sayımı için yazılan algoritma her bir grubu ortalama 20 saniyede çözerken, çeyrek tur sayımı için yazılan algoritma her bir seti 17 saniyede çözmüş (Intel Nehalem, 4 çekirdekli, 2.8GHz ile) . Elemeler sonrasında elde edilen grup sayısı 55.882.296 grup olduğundan (ki her biri 19.508.428.800 farklı varyasyon içeriyor) çözüm için gerekli süre hesaplanabiliyor. (Ben 30 yıl olarak hesapladım, siz de hesaplayabilirsiniz.). Google, kullandığı bilgisayar sistemi konusunda ayrıntılı bilgi vermemiş fakat 30 yıl değil, bir kaç hafta içerisinde çözümü sağlayabilmiş. Bu Google'ın yaklaşık 800 bilgisayar kullandığı anlamına geliyor olabilir mi?

Yorum yazmak için giriş yapın.
Giriş Yap