Bild: FlankerFF/Wikimedia
Eine beliebte Schach-problem bekannt als die Königin Puzzle gefesselt hat Mathematiker und computer-Wissenschaftler seit Jahren, doch niemand war in der Lage zu schreiben, ein Computerprogramm, das kann lösen das Problem schnell und effizient. Forscher aus Großbritannien behaupten nun, dass Computer nie bis zu der Aufgabe—und Sie bieten eine $1 Millionen, wer kann beweisen, dass Sie falsch ist.
Die Queen ‘ s Puzzle gibt es schon seit den 1850er-Jahren, und es fordert ein Spieler, acht Damen auf einem ansonsten leeren herkömmlichen Schachbrett, so dass keine Königin droht jedem anderen. Dies ist sehr schwierig, angesichts der immensen macht der Königin; der Spieler muss dafür sorgen, dass jede Dame platziert auf seine eigene Spalte, aber so, dass keine Königin bedroht eine andere, entlang der anderen diagonalen und Zeilen.
Dieses Rätsel gelöst wurde, indem Menschen (es gibt 92 Lösungen aus 4,426,165,368 mögliche Anordnungen von acht Damen auf einem 8×8-Brett), aber es ist weiterhin eine faszinierende und komplexe Herausforderung für die Mathematiker und computer-Wissenschaftler, besonders, wenn das board skaliert werden über die standard-acht-durch-acht Dimensionen. Wenn das board immer größer wird und mehr Königinnen Hinzugefügt werden, erstellt es ein problem, dass, wie ein neues Papier veröffentlicht in Der Zeitschrift der Künstlichen-Intelligenz-Forschung weist darauf hin, ist es unmöglich für ein computer zu lösen, in einer angemessenen Höhe der Zeit.
Computer-Programme neigen zu einem “brute force” – Ansatz, um das problem systematisch zu gehen, durch jede mögliche permutation. Dies ist der Grund, warum die Königin das Rätsel als “sehr teuer”, wo die Gesamtzahl der Kombination erreichen entsetzlich großen zahlen (27×27 Brett, zum Beispiel, bietet 2.34 Billiarden mögliche Lösungen, oder 234,000,000,000,000,000). Wie die neue Studie weist darauf hin, sobald die board ‘ s dimension erreicht 1,000×1,000, und mit bis zu 1.000 Königinnen, Platz, Computern geschlafen, versinken in einen scheinbar endlosen Abgrund der Berechnungen.
Als lead-Forscher Ian Gent von der University of St. Andrews weist darauf hin, effiziente Lösungen, um der Königin Puzzle bleibt schwer für computer-Programmierer, erfordern Computer, um die Abwanderung Weg in die Möglichkeiten für buchstäblich Tausende von Jahren (die fiktive supercomputer Deep Thought aus per Anhalter durch die Galaxis in den Sinn kommt, eine Maschine, die eine halbe million Jahre berechnen, die Bedeutung von allem). Gent wurde bewusst das Acht-Queen problem, nachdem ein Freund ihn ansprach, um es zu lösen, die auf Facebook—eine Herausforderung Gent und seine Kollegen haben sich jetzt zu einer formalen Studie und einen Preis im Wert von $1 Millionen, wie das US-amerikanische Clay Mathematics Institute.
Dieses problem ist nicht nur einigen arkanen oder zügellos übung für computer-geeks. Gent meint, dass ein computer-Programm, das effizient lösen können die Queen ‘ s Puzzle wäre auch in der Lage sein, die Aufgaben lösen, die derzeit als unmöglich, wie die Entschlüsselung einige der härtesten Sicherheits-Protokolle im internet.
“Wenn Sie schreiben, könnte ein computer-Programm, das das problem lösen könnte wirklich schnell, man könnte es anpassen, um lösen viele der wichtigsten Probleme, die uns alle täglich”, sagte Gent in einer Pressemitteilung. “Das schließt triviale Aufgaben wie arbeiten, die größte Gruppe Ihrer Facebook-Freunde, die nicht wissen, einander, oder sehr wichtig sind, wie das knacken der codes, die halten alle unsere online-Transaktionen sicher sind.”
Wie bereits in dem Papier werden die Vorteile eines solchen Programms wäre immens, sowohl in Bezug auf, was es bedeuten würde, auf den Feldern der Mathematik, der informatik und der künstlichen Intelligenz, aber auch in Bezug auf finanzielle Belohnungen. Das erste team, das knacken dieses Codes, zusätzlich zu gewinnen eine million Dollar, würde der erste sein zu nehmen, die Technologie auf den Markt.
Aber Gent und co-Autor Peter Nachtigall haben Ihre Zweifel, dass hier jemand lösen dieses problem in absehbarer Zeit. Das problem hat zu tun mit so vielen Optionen verfügbar, um den computer und das Problem des backtracking, wo ein Algorithmus betrachtet jede einzelne mögliche option zu einem problem, und dann ablehnt, oder “Rücken Weg”, von der eine offensichtlich ungültige Lösung, bis die richtige Lösung gefunden werden kann. Dieser Prozess, auch für den schnellsten Computer, kann Jahre dauern.
“Allerdings ist das alles theoretisch. In der Praxis hat niemand jemals nahe zu kommen, um ein Programm schreiben, das das problem lösen kann schnell”, sagte Nachtigall. “Also, was unsere Forschung hat gezeigt, dass für alle praktischen Zwecke – es kann nicht getan werden.”
Für diejenigen, die für eine technische Erklärung für dieses problem— früher bekannt als das P vs NP-Problem—ich schlage vor, Sie Auschecken Mike James’ excellent post at I Programmregler. Der Wikipedia-Eintrag über das Acht Königinnen-Rätsel ist auch sehr gut.
Korrektur: Eine frühere version dieses Artikels genannten 2.34 septendecillion, wenn es tatsächlich 2.34 Billiarden. Sorry für den Fehler.
[Die Zeitschrift Journal of Artificial Intelligence Research]