Harvard’lı Bir Matematikçi 150 Yıllık Destansı Bir Satranç Problemini Temelde Çözdü

Bir düzeyde, satranç basit bir oyun gibi görünüyor: 64 ayrı siyah veya beyaz kare, her tarafta 16 parça ve fetih için çabalayan iki rakip.

Yine de biraz daha derine inin ve oyun inanılmaz derecede karmaşık olasılıklar sunarak satranç teorisyenlerine ve matematikçilere onlarca, hatta yüzyıllarca çözülemeyecek zorluklar sunuyor.

Temmuz 2021’de böyle bir zorluk nihayet çözüldü – en azından bir noktaya kadar. Massachusetts’teki Harvard Üniversitesi’nden matematikçi Michael Simkin, n-kraliçeler sorunu Bu, 1840’larda ilk kez hayal edildiğinden beri uzmanların kafasını karıştırıyor.

Satrancınızı biliyorsanız, vezirin tahtadaki en güçlü taş olduğunu ve herhangi bir sayıda kareyi herhangi bir yönde hareket ettirebileceğini bilirsiniz. n-vezir problemi şunu sorar: Belirli sayıda vezir(n) ile, vezirlerin birbirinden yeterince uzakta olduğu ve hiçbirinin diğerini alamayacağı şekilde kaç düzenleme mümkündür?

Standart bir 8 x 8 tahtadaki sekiz vezir için cevap 92’dir, ancak bunların çoğu sadece 12 temel çözümün döndürülmüş veya yansıtılmış varyantlarıdır.

Peki ya 1.000 x 1.000 karelik bir tahtadaki 1.000 vezir? Peki ya bir milyon kraliçe? Simkin’in probleme yaklaşık çözümü (0.143n)ⁿ – 0,143 ile çarpılan kraliçe sayısı, n’nin gücüne yükseltilmiştir.

Elinizde kalan kesin cevap değil, ancak şu anda elde etmek mümkün olduğu kadar yakın. Bir milyon vezirle, rakamdan sonra beş milyon basamaklı bir sayı olarak çıkıyor – bu yüzden burada sizin için yeniden üretmeyeceğiz.

Simkin’in, kullanılan çeşitli yaklaşımlar ve teknikler ve bir çözüme giden yolda birkaç engel ile denklemi bulması neredeyse beş yıl sürdü. Nihayetinde matematikçi, farklı yöntemler kullanarak olası çözümlerin alt sınırlarını ve üst sınırlarını hesaplayabildi ve neredeyse eşleştiklerini buldu.

“Eğer bana vezirlerinizi tahtaya falanca şekilde koymanızı istediğimi söylerseniz, o zaman algoritmayı analiz edebilir ve size bu kısıtlamaya uyan kaç tane çözüm olduğunu söyleyebilirdim.” diyor Simkin.

“Resmi anlamda, sorunu bir optimizasyon sorununa indirger.”

Önceleri, Simkin ve meslektaşı Zur Luria, İsviçre Federal Teknoloji Enstitüsü Zürih’te düzenlenmiş torodial veya modüler problem olarak bilinen n-queens probleminin bir varyasyonu üzerine. Bunda, köşegenler tahtanın etrafına sarılır, böylece bir vezir, örneğin bir tahtanın sağ kenarından çapraz olarak hareket edebilir ve örneğin solda yeniden görünebilir.

Bu, her vezire bir hücum simetrisi verir, ancak normal bir satranç tahtasının işleyişi böyle değildir: Tahtanın köşesindeki bir vezirin ortadaki kadar hücum açısı yoktur.

Sonuçta, çiftin toroidal problem üzerinde çalışmak durdu (her ne kadar bazı sonuçlar yayınlasalar da), ancak Simkin bu emeğin meyvelerinden bazılarını nihai çözümüne uyarladı.

Tahtalar büyüdükçe ve vezir sayısı arttıkça, araştırmalar, izin verilen konfigürasyonların çoğunda vezirlerin tahtanın kenarlarında toplanma eğiliminde olduğunu ve ortalarda daha az vezirin saldırıya maruz kaldıkları yerde toplanma eğiliminde olduğunu gösteriyor. Bu bilgi daha ağırlıklı bir yaklaşım sağlar.

Teoride, n-kraliçe bulmacasına daha kesin bir cevap mümkün olmalıdır – ancak Simkin bizi her zamankinden daha yakınlaştırdı ve daha fazla çalışması için bu zorluğu başka birine devretmekten mutlu.

“Sanırım kişisel olarak bir süreliğine n-kraliçeler sorunuyla işim bitebilir, bununla yapacak başka bir şey olmadığı için değil, sadece satranç hakkında rüya gördüğüm ve devam etmeye hazır olduğum için. benim hayatım,” diyor Simkin.

Simkin’in çözümle ilgili makalesi ön baskı sunucusunda mevcuttur arXiv.