Windows Freecell oyununun kart karıştırma algoritması
(solitairelaboratory.com)Birçoğunuzun oynamış olduğu Windows Freecell, kartları rastgele dizer ve her kart dizilimine bir numara verir. Aynı numara seçildiğinde kartlar yine aynı şekilde dizilir.
Windows 2000 öncesine kadar 1 ile 32.000 arasında numaralar vardı, ancak XP’den sonra bu sayı 1.000.000’a çıktı.
Numara girildiğinde kart dizilimini oluşturan algoritma açık olarak yayımlanmıştır ve diğer Freecell programlarında da kullanılır.
Bu algoritma kısa bir C koduyla gerçekleştirilmiştir ve MS derleyicisinde uygulanan rand() işlevi ile srand() işlevine bağımlıdır.
8 yorum
Tag abi, oldukça iyisiniz.
Asıl rastgele sayı üretim algoritmaları random gibi görünse de, gerçekte öyle olmayan pseudo-random sayı dizileri üreten bir özyinelemeli formül kullanır. Her
rand()işlevinin uygulaması farklı olsa da, ilk seed aynıysa ardından gelen rastgele sayı dizisinin de aynı olması, neredeyse tüm algoritmaların ortak özelliğidir. Dolayısıyla kart dizilim algoritması deterministic ise, tüm kart dizilimleri de seed tarafından deterministic olarak belirlenmiş olur.Konudan biraz sapıyor ama ne kadar rastgele görünebilen pseudo-random sayı üretilebileceği de uzun süredir araştırılan konulardan biridir. TAOCP Vol.2'de de bu konuya kısaca değinilir.
Aslında bilgisayarda gerçek anlamda rastgelelik diye bir kavram yoktur.
Bu yüzden genelde insan davranışları milisaniye düzeyinde ölçülür ve bu değer rastgele seed olarak kullanılır.
Ben de rastgele sayının mevcut zaman damgasını kullandığını sanıyordum, meğer yanılıyormuşum haha. Paylaşım için teşekkürler.
Başlatırken seed olarak çoğu zaman zamanı kullanırlar. Sonuçta zaman sürekli değişir.
Referans olarak, Windows yardımında “kanıtlanmamış olsa da, burada oynadığınız tüm oyunların bir çözümü vardır” yazıyor; ancak birçok kişinin denemelerine göre 11982 numaralı oyunun şimdiye kadar çözülemez olduğu biliniyor.
32.000'in ötesinde de 146692, 186216, 455889, 495505, 512118, 517776 ve 781948 gibi çözülemez olduğu bilinen kart dizilimleri vardır.
Hayır, bunu nasıl not edip de çözememiş olduklarını nasıl anlamışlar acaba? Epey inatçı insanlar varmış!
Korkunç insanlar...!