Tanrılar algoritması - Gods algorithm - Wikipedia

Tanrı'nın algoritması çözüm yolları tartışmalarından kaynaklanan bir fikirdir. Rubik küp bulmaca,[1] ancak diğerlerine de uygulanabilir kombinatoryal bulmacalar ve matematik oyunları.[2] Mümkün olan en az sayıda harekete sahip bir çözüm üreten herhangi bir algoritmayı ifade eder; her şeyi bilen herhangi bir konfigürasyondan optimal bir adımı bilebilir.

Dürbün

Tanım

Fikir için geçerlidir bulmacalar bu varsayılabilir sonlu Yapılandırmalara uygulanabilen ve daha sonra yeni bir yapılandırmaya yol açan, nispeten küçük, iyi tanımlanmış bir "hareket" cephaneliğine sahip "yapılandırma" sayısı. Bulmacayı çözmek, belirlenmiş bir "nihai konfigürasyona", tekil bir konfigürasyona veya bir konfigürasyon koleksiyonundan birine ulaşmak demektir. Bulmacayı çözmek için bazı gelişigüzel başlangıç ​​konfigürasyonlarından başlayarak bir dizi hareket uygulanır.

Çözüm

Girdi olarak gelişigüzel bir başlangıç ​​konfigürasyonu alırsa ve çıktı olarak bir son konfigürasyona yol açan bir dizi hareket üretirse, böyle bir bulmacayı çözmek için bir algoritma düşünülebilir (Eğer bulmaca bu ilk konfigürasyondan çözülebilir, aksi takdirde bir çözümün imkansızlığına işaret eder). Hareket dizisi mümkün olduğu kadar kısaysa çözüm optimaldir. Bu sayı olarak bilinir Tanrı'nın numarası,[3] veya daha resmi olarak minimax değer.[4] O halde, Tanrı'nın algoritması, belirli bir bulmaca için, bulmacayı çözen ve yalnızca en uygun çözümleri üreten bir algoritmadır.

David Joyner gibi bazı yazarlar, bir algoritmanın doğru bir şekilde "Tanrı'nın algoritması" olarak adlandırılması için, pratikBu, algoritmanın olağanüstü miktarda bellek veya zaman gerektirmediği anlamına gelir. Örneğin, bir dev kullanmak arama tablosu İlk yapılandırmalar tarafından indekslenenler, çözümlerin çok hızlı bulunmasına izin verir, ancak olağanüstü miktarda bellek gerektirir.[5]

Tam bir çözüm istemek yerine, aynı şekilde, hareketin bazı optimal çözümlerin ilki olduğu, başlangıçtaki ancak nihai olmayan bir yapılandırmadan tek bir hareket istenebilir. Sorunun tek hareket versiyonu için bir algoritma, sonuncusuna ulaşılana kadar mevcut konfigürasyona bildirilen her hareket uygulanırken tekrar tekrar çalıştırılarak orijinal problem için bir algoritmaya dönüştürülebilir. Tersine, orijinal problem için herhangi bir algoritma, çıktısını ilk hareketine kısaltarak tek hareket versiyonu için bir algoritmaya dönüştürülebilir.

Örnekler

Bu tanıma uyan iyi bilinen bulmacalar mekanik bulmacalar sevmek Rubik küp, Hanoi Kuleleri, ve 15 yapboz. Tek kişilik oyun peg solitaire aynı zamanda birçok mantık bulmacaları, benzeri misyonerler ve yamyam sorunu. Bunların ortak olabilecekleri matematiksel olarak modellendi olarak Yönlendirilmiş grafik konfigürasyonların köşeler olduğu ve yayların hareket ettiği.

Mekanik bulmacalar

n-Bulmacalar

On beş bulmaca 80 tek kiremit hamlede çözülebilir[6] veya 43 çok parçalı hareket[7] en kötü durumda. Genellemesi için n-puzzle, en uygun çözümü bulma problemi NP-zor.[8] Bu nedenle, bu sorun için pratik bir Tanrı algoritmasının var olup olmadığı bilinmemektedir, ancak olası görünmemektedir.

Hanoi Kuleleri

İçin Hanoi Kuleleri bulmaca, bir Tanrı'nın algoritması herhangi bir disk sayısı için bilinir. Disk sayısında hareket sayısı üsseldir ().[9]

Rubik küp

Ana makale: Rubik Küpü için en uygun çözümler

Rubik Küpünü çözmek için minimum hamle sayısını belirleyen bir algoritma 1997 yılında Richard Korf tarafından yayınlandı.[10] 1995'ten beri 20'nin, en kötü durumda çözüm için hamle sayısında daha düşük bir sınır olduğu bilinmesine rağmen, 2010 yılında kapsamlı bilgisayar hesaplamaları aracılığıyla hiçbir konfigürasyonun 20'den fazla hareket gerektirmediği kanıtlandı.[11] Böylece 20 bir keskin üst sınır optimal çözümlerin uzunluğu üzerine. Matematikçi David Singmaster 1980'de bu sayının 20 olduğunu "aceleyle tahmin etmişti".[4]

Çözülmemiş oyunlar

Çok sınırlı sayıda basit ve iyi tanımlanmış kurallara ve hareketlere sahip bazı iyi bilinen oyunlar, yine de Tanrı'nın bir kazanma stratejisi için algoritmasını belirlememiştir. Örnekler masa oyunlarıdır satranç ve Git.[12] Her iki oyun da her harekette hızla artan sayıda pozisyona sahiptir. Olası tüm pozisyonların toplam sayısı, yaklaşık 10154 satranç için[13] ve 10180 (19 × 19 tahtada) Go için,[14] mevcut hesaplama teknolojisi ile kaba kuvvet çözümüne izin vermeyecek kadar büyüktür (şu anda çözülmüş olanı büyük zorluklarla karşılaştırın, Rubik Küpü sadece yaklaşık 4,3 × 1019 pozisyonlar[15]). Sonuç olarak, bu oyunlar için Tanrı'nın algoritmasının kaba kuvvet tespiti mümkün değildir. En iyi insan oyuncuları bile yenebilecek satranç bilgisayarları yapılırken, oyunu sonuna kadar hesaplamazlar. Koyu mavi örneğin, yalnızca 11 hamle ileride arandı (her oyuncunun bir hamlesini iki hamle olarak sayarak), arama alanını yalnızca 10'a düşürdü17.[16] Bundan sonra, insan oyunundan ve deneyiminden elde edilen kurallara göre her pozisyonu avantaj için değerlendirdi.

Go ile bu strateji bile mümkün değil. Değerlendirilecek çok daha fazla pozisyona sahip olmanın yanı sıra, şimdiye kadar hiç kimse bir Go pozisyonunun gücünü satrançta olduğu gibi değerlendirmek için bir dizi basit kuralı başarıyla oluşturmadı.[17] Değerlendirme algoritmaları temel hatalar yapmaya eğilimlidir[18] Dolayısıyla, hedefi en güçlü ara konumu bulmakla sınırlı ileriye dönük sınırlı bir bakış için bile, Go için bir Tanrı'nın algoritması mümkün olmamıştır.

Diğer taraftan, taslaklar (dama), satranca yüzeysel benzerlikler taşıyan, uzman uygulayıcıları tarafından uzun süredir "oynandığından" şüpheleniliyor.[19] 2007'de Schaeffer et al. on veya daha az parça içeren tüm pozisyonların bir veri tabanını hesaplayarak bunun böyle olduğunu kanıtladı. Bu nedenle Schaeffer, taslakların tüm son oyunları için bir Tanrı algoritmasına sahiptir ve bunu, mükemmel oynanan tüm taslak oyunlarının bir berabere biteceğini kanıtlamak için kullandı.[20] Ancak, yalnızca 5 × 10 içeren taslaklar20 pozisyonlar[21] ve daha da azı, 3,9 × 1013Schaeffer'ın veritabanında,[22] kırılması çok daha kolay bir sorundur ve Rubik küpü ile aynı sıradadır.

Bir bulmacanın konumlarının büyüklüğü, bir Tanrı'nın algoritmasının mümkün olup olmadığını tam olarak belirlemez. Halihazırda çözülmüş olan Hanoi Kulesi bulmacası, rastgele sayıda parçaya sahip olabilir ve konumların sayısı, . Bununla birlikte, çözüm algoritması herhangi bir boyuttaki probleme uygulanabilir ve algoritma çalışma süresi sorun NP-zordur.[23]

Ayrıca bakınız

Notlar

  1. ^ Paul Anthony Jones, Jedburgh Justice ve Kentish Fire: On İfade ve İfadede İngilizcenin Kökenleri, Hachette İngiltere, 2014 ISBN  1472116224.
  2. ^ Bkz. Ör. Rubik'in Kübik Özeti Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx ve Tamás Vekerdy ​​(1987, Oxford University Press, ISBN  0-19-853202-4), s. 207: "... Pyraminx, Sihirli Küp'ten çok daha basit ... Nicholas Hammond, Tanrı'nın Algoritmasının en fazla 21 hareket olduğunu gösterdi (dört önemsiz köşe hareketi dahil). [Daha yakın zamanda, üç kişi Tanrı'nın Algoritmasını buldu. Maksimum hareket sayısı 15'tir (dört köşe hareketi dahil).] "
  3. ^ Jonathan Fildes (11 Ağustos 2010). "Hızlı çözüm için Rubik Küp arayışı sona eriyor". BBC haberleri.
  4. ^ a b Singmaster, s. 311, 1980
  5. ^ Joyner, sayfa 149
  6. ^ A. Brüngger, A. Marzetta, K. Fukuda ve J. Nievergelt, Paralel arama tezgahı ZRAM ve uygulamaları, Yöneylem Araştırması Yıllıkları 90 (1999), s. 45–63.
  7. ^ "Onbeş Bulmaca 43'te çözülebilir hareketler". Küp Forum Alanı
  8. ^ Daniel Ratner, Manfred K. Warmuth (1986). "15-bulmacanın N × N uzantısı için en kısa çözümü bulmak zor.". içinde Bildiriler AAAI-86. Ulusal Yapay Zeka Konferansı, 1986. s. 168–172.
  9. ^ Carlos Rueda, "Towers of Hanoi Puzzle için en uygun çözüm".
  10. ^ Richard E. Korf, "Model veritabanlarını kullanarak Rubik Küpüne en uygun çözümleri bulmak ", Proc. Natl. Conf. Yapay Zeka Üzerine (AAAI-97), Providence, Rhode Island, Temmuz 1997, s. 700–705.
  11. ^ "Tanrı'nın Numarası 20". Cube20.org
  12. ^ Rothenberg, s. 11
  13. ^ Baum, s. 187
  14. ^ Baum, s. 199
  15. ^ Singmaster, 1981
  16. ^ Baum, s. 188
  17. ^ Baum, s. 197
    • Mohammadian, s. 11
  18. ^ Baum, s. 1997
  19. ^ Fraser ve Hannah, s. 197
  20. ^ Moore ve Mertens, bölüm 1.3, "Tanrı ile satranç oynamak"
  21. ^ Schaeffer et al., s. 1518
  22. ^ Moore ve Mertens, Bölüm 1'e "Notlar"
  23. ^ Rueda

Referanslar

  • Baum, Eric B., Düşünce nedir?, MIT Press, 2004 ISBN  0262025485.
  • Davis, Darryl N .; Chalabi, T .; Berbank-Green, B., "Yapay yaşam, ajanlar ve Go", Mohammadian, Masoud, Hesaplamalı Zeka ve Uygulamalarında Yeni Sınırlar, s. 125–139, IOS Press, 2000 ISBN  9051994761.
  • Fraser, Rober (ed); Hannah, W. (ed), Draft Players 'Weekly Magazine, cilt. 2, Glasgow: J H Berry, 1885.
  • David Joyner (2002). Grup Teorisindeki Maceralar. Johns Hopkins Üniversitesi Yayınları. ISBN  0-8018-6947-1.
  • Moore, Cristopher; Mertens, Stephan, Hesaplamanın Doğası, Oxford University Press, 2011 ISBN  0191620807.
  • Rothenberg, Gadi, Kataliz, Tanrı'nın Algoritması ve Yeşil Şeytan, Amsterdam University Press, 2009 ISBN  9056295896.
  • Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Dama çözüldü", Bilim, cilt. 317, hayır. 58444, s. 1518–1522, 14 Eylül 2007.
  • Şarkıcı David, Rubik'in Sihirli Küpü ile ilgili notlar, Penguen, 1981 ISBN  0-907395-00-7.
  • Singmaster, David, "Macar 'Sihirli Küpünün eğitim değeri", Dördüncü Uluslararası Matematik Eğitimi Kongresi Bildirileri, Berkeley, California'da düzenlendi, 10-16 Ağustos 1980, s. 307–312, Birkhauser Boston Inc, 1983 ISBN  978-0-8176-3082-9.