Neden çalışıyor, ne zaman başarısız oluyor, neden yeterli değil
Warnsdorff kuralı 1823'ten bu yana at turu probleminin pratik çözümünde kullanılır. İki yüzyıl sonra Yüz Yüze gibi modern bulmaca oyunlarında hâlâ geçerli. Ama nadiren açıkça incelenir: kural neden işe yarıyor, ne zaman tökezliyor, ve neden tek başına yeterli değil?
Warnsdorff kuralı tek cümlelik bir heuristiktir:
Sıradaki hamlede, kendisinden sonra en az geçerli devam seçeneğine sahip olan kareye git.
Eğer birden fazla kare aynı en az sayıda devam seçeneğine sahipse, aralarında rastgele veya başka bir tie-breaking kuralıyla seçim yapılır.
Kuralın altındaki sezgi şudur: oyunun ilerleyen safhalarında ziyaret edilebilen kare sayısı azalır, bazı kareler "izole" hale gelir. Az çıkışı olan kareler doğal olarak izolasyona daha yakındır. Onları erken ziyaret edersen, daha sonraki bir hamlede ulaşılamaz hale gelmeden işlerini bitirirsin.
Çok çıkışı olan kareler ise oyunun sonunda bile ulaşılabilir kalır. Onları "yedek" olarak saklamak güvenlidir.
Bu, satrancın klasik bir tavsiyesine benzer: köşeye sıkışan figürü kurtarma. Warnsdorff kuralı aynı sezgiyi sayısal hale getirir.
8x8 standart satrançtahtasında at turu için Warnsdorff kuralı, rastgele başlangıç karesi seçildiğinde %99'un üzerinde başarı oranıyla tam tur tamamlar. Bu sürpriz çıkar — saf bir heuristik genellikle bu kadar yüksek başarıya ulaşmaz.
Sebep şu: at turu probleminin grafik yapısı "düzenli" — her karenin out-degree (çıkış sayısı) sınırlı bir aralıktadır (2-8). Warnsdorff kuralı, bu düzenli yapıdaki "sıkışma noktalarını" erken tespit eder. Düzensiz veya yüksek varyanslı grafiklerde performansı düşer.
Yüz Yüze 10x10 grid üzerinde 3 düz / 2 çapraz hareketleriyle çalışır. Bu, satrançtahtasından farklı bir grafik yapısı yaratır:
Bu yapı at turuna kıyasla daha "asimetriktir". Köşe ve kenar kareleri çok kısıtlıdır. Warnsdorff kuralı bu yapıyı oldukça iyi yönetir — çoğu başlangıç karesinden 80-90 üzerinde skor üretebilir. Ama %100'e ulaşmak başlangıç karesine ve bulmacanın yapısına bağlıdır.
Warnsdorff kuralı bazı tipik durumlarda başarısız olur:
1. Eşit out-degree çatışması. Üç farklı kare aynı (örneğin 3) çıkışa sahipse, Warnsdorff hangisini seçeceğini söylemez. Yanlış seçim ileride çıkmaza yol açabilir.
2. Uzak parite tuzakları. Bazen "şimdi" güvenli görünen bir kare, 10-15 hamle sonra parite (renk dengesi) bozar ve son adımları imkansız kılar. Warnsdorff'un yerel görüşü bunu öngöremez.
3. Köprü kareler. Bir kare grid'in iki bölgesini birbirine bağlıyorsa, onu kullanmadan önce her iki tarafın da bitirilmiş olması gerekir. Warnsdorff'un saf hali köprü kareleri tanımaz.
Yüz Yüze'nin ipucu motoru saf Warnsdorff kuralını kullanmaz. Bunun yerine Monte Carlo simülasyonu ile desteklenmiş bir hibrit kullanır:
Bu yaklaşım iki dünyadan iyiyi alır:
Saf Warnsdorff'tan daha yavaş ama belirgin biçimde daha güçlü. Pratik sonuç: Yüz Yüze ipucusu çoğu pozisyonda gerçekten optimal hamleyi gösterir.
Warnsdorff'un nadiren tartışılan ama kritik yönü tie-breaking'dir. Birden fazla kare aynı out-degree'ye sahipse hangisi seçilmeli? Tarihsel olarak çeşitli ek kurallar önerilmiştir:
Yüz Yüze'de Monte Carlo simülasyonu doğal olarak bu eşitlikleri çözer — ortalamada hangi seçim daha uzun yol veriyorsa o kazanır.
Warnsdorff kuralı 200 yıllık bir başyapıt: tek cümlelik tanımıyla karmaşık bir matematik problemine pratik çözüm sağlıyor. Ama matematiksel olarak optimum değil ve bazı sınır durumlarda tökezleyebiliyor. Modern uygulamalar — Yüz Yüze dahil — kuralı simülasyon tabanlı yöntemlerle birleştirerek bu zaaflarını giderir.
Bir sonraki ipucu kullanışında, ekrana çıkan o sarı parıltının arkasında 120 simülasyonun ortalaması ve 200 yıllık bir matematiksel sezgi olduğunu hatırla.