15 bulmaca, 1960'lardan beri yapay zekâ arama algoritmaları için bir kıyaslama ölçütü. Her algoritma kuşağı, bir öncekinin tosladığı duvarı aşmak için icat edildi. Bu makale onları icat sırasıyla anlatıyor — her birinin neye yaradığını ve bir sonrakini neyin zorunlu kıldığını göstererek.
1960'lar — Genişlik öncelikli arama (BFS)
Herkesin ilk denediği algoritma. Durumları seviye seviye keşfet: 1. derinlikte 4 durum, 2. derinlikte 16, 3. derinlikte 64 ve böyle devam eder. Hedefi bulana kadar keşfe devam et.
8 bulmaca için BFS hızla biter — en kötü derinlik 31 olduğundan en fazla 4³¹ durum (tekrar ziyaretler sayesinde pratikte çok daha az). 15 bulmaca içinse en zor derinlik 80, yani 4⁸⁰ durum. Bu, gözlemlenebilir evrendeki atom sayısından fazladır. BFS bitmez.
Duvar: üstel patlama. Bilgisiz aramayla çözmek 3×3'ün ötesinde umutsuzdur.
1968 — A* araması
Hart, Nilsson ve Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths makalesini yayımlar. Fikir: durumları başlangıca uzaklık sırasıyla keşfetmek yerine, f = g + h sırasıyla keşfet; burada h, kalan mesafenin bir alt sınır tahminidir.
15 bulmaca için h, Manhattan mesafesidir — her taşın hedefine olan satır+sütun mesafelerinin toplamı. Manhattan kabul edilebilirdir (asla abartmaz) ve tutarlıdır (bir üçgen eşitsizliğini sağlar). Bu özelliklerle A* optimal çözümü bulur.
15 bulmacadaki performansı: her tahtayı çözer, ama en zor örneklerde milyonlarca durum keşfeder ve yüzlerce megabayt bellek tüketir. Duvar: bellek.
1985 — IDA*
Richard Korf'un Depth-first iterative-deepening: An optimal admissible tree search makalesi. Fikir şu: A*'ın (keşfedilen tüm durumları tutan) öncelik kuyruğu yerine, derinlik sınırı derinlik değil f-maliyeti olan yinelemeli derinleştirmeli DFS yap.
IDA*, A*'ın keşfedeceği durumları yaklaşık aynı sırayla keşfeder ama yinelemeler arasında onları hatırlamadan. Her "derinlemesine tarama", O(keşfedilen durum) yerine O(derinlik) bellek kullanır.
15 bulmacadaki performansı: 1985 donanımında her tahtayı saniyeler içinde çözer, kilobaytlarca belleğe sığar. Duvar: sezgisel hâlâ Manhattan'dır. Aramayı hızlandırmak daha sıkı bir sezgisel gerektirir.
1990'lar — Doğrusal çakışma
Hansson, Mayer ve Yung'un Criticizing solutions to relaxed models yields powerful admissible heuristics makalesi. Manhattan sezgiseli taşların birbirinin içinden geçebildiğini varsayar. Geçemezler.
Doğrusal çakışma (linear conflict), aynı satırda bulunan, ikisi de o satıra ait olan ama yanlış sırada duran her taş çifti için sezgisele 2 hamle ekler — birinin geçmesi için diğerinin satırdan çıkarılması gerekecektir. Sütunlar için de aynısı geçerlidir.
Etkisi: zor 15 bulmacalarda genişletilen düğüm sayısında tipik olarak %5–15 azalma. Düz Manhattan'a göre katı bir iyileştirme; kayda değer bir bedeli yok.
1996 — Yürüme mesafesi
Bulmacanın yapısını daha derinden yakalayan bir sezgisel. Taş diziliminin yalnızca satırlara izdüşümü için (satır içi konumları yok sayarak), her taşı doğru satırına götürmek için gereken minimum satır-takası sayısını önceden hesapla. Aynısını sütunlar için yap.
Yürüme mesafesi kabul edilebilirdir ve Manhattan + doğrusal çakışmadan hatırı sayılır ölçüde sıkıdır — tipik olarak Manhattan değerinin 1,5–2 katı; bu da IDA*'ın çok daha az düğüm genişletmesi demektir.
Uygulama maliyeti: küçük bir ön hesaplama tablosu (4×4 için ~500 KB). 15 bulmaca için tatlı nokta.
2002 — Toplamsal ayrık örüntü veritabanları
Korf ve Felner'in Disjoint pattern database heuristics makalesi. Kayan bulmacalar için bilinen en güçlü sezgisel.
Fikir: taşları ayrık gruplara böl (15 bulmaca için 7+8'lik bölme standarttır). Her grup için, diğer tüm taşları yok sayarak yalnızca o grubun taşlarını hedef konumlarına götürmenin optimal maliyetini önceden hesapla. Grubun her olası dizilimini tabloya dök.
Arama sırasında her grubun katkısını tablodan al ve topla. Gruplar ayrık olduğundan ve her grup için gereken hamleler (dikkatli bir argümana bağlı olarak) çakışmadığından, toplam kabul edilebilirdir.
Bellek maliyeti: 15 bulmaca için yaklaşık 1 GB. Performans: en zor 15 bulmacayı birkaç bin düğüm genişletmesiyle — yani milisaniyelerde — çözer.
2005+ — daha büyük bulmacalar için daha büyük örüntü veritabanları
Aynı teknik 24 bulmacaya (5×5) ve ötesine ölçeklenir. 24 bulmaca için 5+5+5+9'luk bir bölme yaklaşık 4 GB'dir. Onunla herhangi bir rastgele 24 bulmaca saniyeler içinde çözülür.
35 bulmaca (6×6) çözülebilirliğin sınırındadır. En zor 6×6 örnekleri 2026 itibarıyla hâlâ açık araştırma konusudur.
2010'lar+ — sinir ağı sezgiselleri
Kayan bulmacalar için Manhattan-mesafesi-benzeri niceliği tahmin etmek üzere sinir ağları eğitildi ve bunlar bazen elle tasarlanmış sezgisellerden daha sıkı sonuçlar üretiyor. Sorun şu: sinir ağı sezgiselleri genellikle kanıtlanabilir biçimde kabul edilebilir değildir, dolayısıyla üzerlerine kurulan çözücüler garantili-optimal değil muhtemelen-optimal cevaplar verir.
Araştırma makaleleri için bu ilginçtir. Optimalliğin önemli olduğu yazılımlar içinse (oyunlarda zorluk kalibrasyonu gibi) klasik örüntü veritabanları doğru araç olmaya devam ediyor.
Bu tarih neden önemli
Kayan bulmaca algoritması araştırmalarının her dalgasını aynı baskı sürükledi: bulmaca, algoritmaların kıyaslanabileceği kadar küçük, kötü algoritmaların süre aşımına uğrayacağı kadar büyüktür. 15 bulmaca; A*, IDA* ve örüntü veritabanları gibi bugün rota planlamadan teorem kanıtlamaya birçok alanı çalıştıran sezgisel arama ilerlemelerinin test alanı olmuştur.
Bir uygulamada ipucu düğmesine basarak 15 bulmaca çözdüğünüzde, tam da bu oyun için geliştirilmiş ve sonra her yere genellenmiş algoritmaları kullanıyorsunuz.
Özet tablo
| Yıl | Algoritma | Zor 15 bulmacayı çözme süresi | Bellek | Bunu mümkün kılan |
|---|---|---|---|---|
| 1960'lar | BFS | Bitmez | Devasa | — |
| 1968 | A* + Manhattan | Dakikalar | Yüzlerce MB | Sezgisel arama |
| 1985 | IDA* + Manhattan | Saniyeler | KB | Yinelemeli derinleştirme |
| 1996 | IDA* + yürüme mesafesi | < 1 sn | + 500 KB ön hesap | Daha iyi sezgisel |
| 2002 | IDA* + 7+8 örüntü VT | Milisaniyeler | + 1 GB ön hesap | Alt küme sayımı |
Her satır marjinal bir iyileştirme değil, gerçek bir nitel sıçramadır. 15 bulmacayı çözmenin tarihi, aynı zamanda modern sezgisel aramanın tarihidir.