Satranç oyunu üzerine kurulu en ilginç bulmacalardan biri matematikçi Euler’in çalışmalarının ardından popülerlik kazanmış At Turu problemidir.
Satranç taşlarından yalnızca bir atı bırakıp diğerlerinin hepsini kaldırın. Atı da satranç tahtasındaki 64 kareden herhangi birine yerleştirin. Şimdi soru şu: Atla 63 kez kurallı hamle yaparak tahtadaki her kareye tam bir kez uğrayabilir misiniz?
At Turu Problemi İle İlgili Sorun Nedir?
Hatırlatmak gerekirse, at satranç tahtasında L harfi şeklinde hareket eder (2 adım bir yöne, sonra 1 adım buna dik olacak yöne). Bu yüzden, boş bir satranç tahtasının ortasında bulunan bir at, aşağıda gördüğünüz 8 farklı hareketten birini yapacaktır.
At turu problemi ilk bakışta basit görünür. Ancak Leonhard Euler bu soruyu analiz edilmesi zor, ilginç bir problem olarak tanımlamıştı. Buna rağmen onu sistemli biçimde inceleyen ilk kişi oldu. Problemin kökeni ise MS 9. yüzyıla kadar uzanır.
Amaç yalnızca bir tur bulmak değildir. Asıl mesele, bu turların kaç farklı şekilde oluştuğunu belirlemektir. Eğer 63 hamleyi tamamladıktan sonra bulunduğunuz kareden tek bir yasal hamleyle başlangıç karesine geri dönebiliyorsanız, buna kapalı tur denir. Bu koşulu sağlamayan düzenlemelere ise açık tur denir.
Matematikçiler kapalı turların sayısını uzun süre inceledi. Elde edilen sonuç 26 trilyondan fazladır. Açık turların sayısı ise bundan çok daha büyüktür ve kesin değeri hâlâ bilinmemektedir.
Karıncalar Bir Satranç Problemini Nasıl Çözer?
Karıncalar, yiyecek ararken belirli bir desen ya da algoritma izler. Bu davranışı Gezgin Satıcı Problemi ve araç rotalama gibi birçok farklı probleme uygulamak mümkündür. Karınca kolonisi optimizasyonu yaklaşımının atın turu problemini çözmede de kullanılıp kullanılamayacağı araştırılmıştır. Algoritmanın işleyişi şu şekildedir:
Karıncalar, yiyecek kaynaklarına ulaşmak için dolaşırken arkalarında feromon adı verilen çekici bir kimyasalın küçük izlerini bırakır.
Diğer karıncalar bu kimyasalın cazibesine kapılarak izi takip eder ve ilerledikçe kendi feromonlarını ekler. Hansel ve Gretel’in ekmek kırıntılarıyla iz bırakmasına benzer şekilde, karıncalar da yuvalarına geri dönmek için bu izleri kullanır.
Daha başarılı karıncalar (sorunu daha etkili çözenler), düşük performans gösterenlere kıyasla daha fazla feromon bırakır. Bu süreç çok sayıda kez, hatta milyonlarca kez tekrarlanır. Zamanla, iyi çözümler üzerindeki feromon yoğunluğu artarken, zayıf çözümler üzerindeki izler buharlaşma nedeniyle azalır.
Karınca koloni optimizasyonu algoritması da benzer bir prensiple çalışır. Olası çözüm yollarını keşfederek, deneme-yanılma ve işaretleme mekanizmaları aracılığıyla daha iyi çözümlere ulaşacak bir yol haritası oluşturur. Bu süreç, gerçek karıncalar yerine karınca popülasyonunu simüle eden bir bilgisayar programı tarafından gerçekleştirilir.
Geçtiğimiz yıllarda araştırmacılar at turu problemini çözmek için karınca kolonisi optimizasyon algoritmasını kullanmaya karar verdiler. Simülasyonda, karıncaların yalnızca satranç tahtasındaki bir at gibi hareket etmesine izin verildi. Ayrıca karıncalar satranç tahtasının sınırları içinde kalmak zorundaydı. Sonucunda, bu algoritmayı kullanarak araştırmacılar yaklaşık yarım milyon tur buldular.
Sonuç Olarak
At turu problemi çözümsüz bir satranç problemi değildir. Ancak kaba kuvvetle ( yani deneme yanılma ile) çözmek de olası değildir. Bilgisayar kullanarak belirli bir tahtada at turunu bulmanın birkaç yolu vardır. Konu ilginizi çektiyse sizin de bu algoritmalardan birini kullanarak denemeler yapmanız olasıdır. Daha fazlası için göz atınız.
Kaynaklar ve ileri okumalar
- How to get ants to solve a chess problem. Yayınlanma tarihi: 30 Ocak 2014. Kaynak site: Conversation. Bağlantı: https://doi.org/10.64628/AB.mngynx6gf
- Rezvanian, Alireza & Vahidipour, S Mehdi & Sadollah, Ali. (2023). An Overview of Ant Colony Optimization Algorithms for Dynamic Optimization Problems. 10.5772/intechopen.111839.
Size Bir Mesajımız Var!
Matematiksel, matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
