[heise.de] 26-Damen-Problem gelöst

ChessBrain, Chess960@home und andere Schachprojekte
Antworten
Nachricht
Autor
-horn-
Stromkosten-Ignorierer
Stromkosten-Ignorierer
Beiträge: 1053
Registriert: 21.06.2009 19:04

[heise.de] 26-Damen-Problem gelöst

#1 Ungelesener Beitrag von -horn- » 19.07.2009 13:15

26-Damen-Problem gelöst

Die Aufgabe, acht Damen so auf einem Schachbrett zu platzieren, dass sich keine davon gegenseitig schlagen können, läuft früher oder später jedem Informatik-Erstsemester über den Weg. 92 Möglichkeiten gibt es, und ein aktueller PC benötigt ungefähr null Sekunden, um sie alle auszurechnen. Doch wie bei vielen kombinatorischen Problemen werden die Zahlen und damit die Zeiten, sie zu ermitteln, schnell gigantisch, wenn man die Aufgabe größer macht: Wie viele Möglichkeiten gibt es, n Damen bedrohungsfrei auf einem n×n-Schachbrett zu platzieren?
...
Den Rest der Nwws gibt es hier http://www.heise.de/newsticker/26-Damen ... ung/142206
http://www.hdtvtotal.com | Your European Total Source To HDTV!
Bild

Benutzeravatar
Thommy3
Projekt-Fetischist
Projekt-Fetischist
Beiträge: 639
Registriert: 25.08.2003 10:29

Re: [heise.de] 26-Damen-Problem gelöst

#2 Ungelesener Beitrag von Thommy3 » 19.07.2009 13:45

Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.

gardenone

Re: [heise.de] 26-Damen-Problem gelöst

#3 Ungelesener Beitrag von gardenone » 19.07.2009 14:16

Es soll ja jeder rechnen was er möchte, aber dafür würde ich noch nicht ein einziges Watt zur Verfügung stellen!

Worin besteht der Nutzen eines solchen Projektes?
Was kann damit erreicht werden?

Dennis Kautz
Vereinsmitglied
Vereinsmitglied
Beiträge: 4742
Registriert: 22.02.2003 02:12
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#4 Ungelesener Beitrag von Dennis Kautz » 19.07.2009 15:49

Thommy3 hat geschrieben:Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.
Dann sollten sie damit aufhören.

-horn-
Stromkosten-Ignorierer
Stromkosten-Ignorierer
Beiträge: 1053
Registriert: 21.06.2009 19:04

Re: [heise.de] 26-Damen-Problem gelöst

#5 Ungelesener Beitrag von -horn- » 20.07.2009 16:13

moien,
gardenone hat geschrieben:Es soll ja jeder rechnen was er möchte, aber dafür würde ich noch nicht ein einziges Watt zur Verfügung stellen!

Worin besteht der Nutzen eines solchen Projektes?
Was kann damit erreicht werden?
ich berechne auch keine schachprobleme. es liegt aber nicht daran, dass ich das für sinnlos halte, interessieren tut mich das schon. nur wäge ich immer ab, wo ich mit mache, denn überall mitmachen kann ich ja auch schliesslich nicht. deswegen kommt zum interessieren noch der punkt hinzu, ob ich es für nützlich halte und da bin ich dann doch der meinung, dass ich zb. bei der krankheitsbekämpfung sinnvoller mitarbeiten kann.

frost hat geschrieben:
Thommy3 hat geschrieben:Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.
Dann sollten sie damit aufhören.
auf der halben strecke aufgeben? ;). ias dennoch zu ende rechnen lassen, denn man kann ja damit dann das andere ergbnis bestätigen.

grüße, Andreas
http://www.hdtvtotal.com | Your European Total Source To HDTV!
Bild

Benutzeravatar
LinuxFan
Vereinsmitglied
Vereinsmitglied
Beiträge: 1200
Registriert: 17.07.2001 01:00
Wohnort: Berlin
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#6 Ungelesener Beitrag von LinuxFan » 20.07.2009 19:38

Zum Bestätigen guckst du einfach auf die Lösung und musst sie nicht extra ein zweites Mal finden ;)

Benutzeravatar
EdmundBlackadder
Task-Killer
Task-Killer
Beiträge: 784
Registriert: 20.02.2008 17:56
Wohnort: Prekariat
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#7 Ungelesener Beitrag von EdmundBlackadder » 20.07.2009 20:13

Als Laie verstehe ich das so: Wenn ich das vom Schach abstrahiere, kann NQueens vielleicht bei der Logistik wie z.B. TSP oder anderen Fragen der Logik helfen. Natürlich sollte NQueens sofort den Durchlauf mit n=26 beenden. NQueens wäre somit komplett überflüssig, denn Queens@TUD bereitet bereits n=27 vor. Oft ist zweimal nachdenken (Queens@TUD) doch besser als brute force (NQueens). Mit anderen Worten: Das Problem ist nicht effizient mit BOINC zu lösen, sondern nur mit Spezial-HW.
Das Projekt Queens@TUD wurde von Studenten an der TU Dresden durchgeführt, und diente Linie Forschungs- und Schulungszwecken.
Zuletzt geändert von EdmundBlackadder am 20.07.2009 21:39, insgesamt 1-mal geändert.
Verschenke XP x64 und Vista Business 32/64 bit Lizenzen.
Ritschie hat geschrieben:Ich will ja nicht nur für Credits rechnen, sondern 'nen sinnvollen Beitrag leisten.

Benutzeravatar
LinuxFan
Vereinsmitglied
Vereinsmitglied
Beiträge: 1200
Registriert: 17.07.2001 01:00
Wohnort: Berlin
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#8 Ungelesener Beitrag von LinuxFan » 20.07.2009 20:53

Spezial-Hardware ist nicht der Punkt, denn damit gewinnst du nur einen konstanten Faktor. (z.B. 1000 FPGAs = Faktor 1000)

Erfolgversprechender sind Techniken aus der KI, so lässt sich das n-Damenproblem zum Beispiel gut als CSP (Constraint Satisfaction Problem, siehe http://de.wikipedia.org/wiki/Constraint ... on-Problem) formulieren. Allerdings muss man dann ziemlich viel Grips in die Parallelisierung stecken, vermute ich.

Benutzeravatar
nico
Vereinsmitglied
Vereinsmitglied
Beiträge: 2211
Registriert: 22.12.2002 13:22
Wohnort: C-Town
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#9 Ungelesener Beitrag von nico » 20.07.2009 21:03

EdmundBlackadder hat geschrieben: Mit anderen Worten: Das Problem ist nicht effizient mit BOINC zu lösen, sondern nur mit Spezial-HW.
Das hast aber mit so gut wie allen Problemen...FPGAs sind für spezielle Probleme immer schneller als General Purpose CPUs allerdings kosten die auch eine ganze Stange Geld und Entwicklungszeit. Mal eben ein C Programm schreiben ist da nicht - da ist VHDL angesagt. Die "Compilierung" für den FPGA kann dann auch paar Stunden dauern (u.a. weil z.B. Xilinx es nicht fertig bringt das ganze auf einem SMP zu parallelisieren und es keine OpenSource Software gibt, die Interessierte optimieren könnten... afaik).
Bild

Benutzeravatar
nico
Vereinsmitglied
Vereinsmitglied
Beiträge: 2211
Registriert: 22.12.2002 13:22
Wohnort: C-Town
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#10 Ungelesener Beitrag von nico » 20.07.2009 21:11

LinuxFan hat geschrieben:CSP (Constraint Satisfaction Problem, siehe http://de.wikipedia.org/wiki/Constraint ... on-Problem) formulieren. Allerdings muss man dann ziemlich viel Grips in die Parallelisierung stecken, vermute ich.
Ist CSP nicht ==3SAT und damit NP-Vollständig und damit eigenltich egal wie implementiert immer schlecht zu lösen? (nicht schlagen, hatte nur TI1 und hab des nicht so gemocht... ;) )
Bild

Benutzeravatar
LinuxFan
Vereinsmitglied
Vereinsmitglied
Beiträge: 1200
Registriert: 17.07.2001 01:00
Wohnort: Berlin
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#11 Ungelesener Beitrag von LinuxFan » 20.07.2009 21:55

nico hat geschrieben:Ist CSP nicht ==3SAT und damit NP-Vollständig und damit eigenltich egal wie implementiert immer schlecht zu lösen? (nicht schlagen, hatte nur TI1 und hab des nicht so gemocht... ;) )
CSP hat halt den Vorteil, dass du mit heuristischen Suchverfahren relativ leicht eine Lösung finden kannst. Aber mir fällt gerade ein, dass die ja ALLE Lösungen finden wollen.

Benutzeravatar
EdmundBlackadder
Task-Killer
Task-Killer
Beiträge: 784
Registriert: 20.02.2008 17:56
Wohnort: Prekariat
Kontaktdaten:

Re: [heise.de] 26-Damen-Problem gelöst

#12 Ungelesener Beitrag von EdmundBlackadder » 20.07.2009 22:27

EdmundBlackadder hat geschrieben:Natürlich sollte NQueens sofort den Durchlauf mit n=26 beenden.
Lieber Edmund, das ist völliger Quatsch. Nach Lektüre des Heise Forums komme ich zu der Meinung, NQueens soll n=26 noch fertig berechnen, damit man die Ergebnisse vergleichen kann. Wenn diese gleich sind, kann die BOINC-Methode guten Gewissens zu den Akten gelegt werden.
Verschenke XP x64 und Vista Business 32/64 bit Lizenzen.
Ritschie hat geschrieben:Ich will ja nicht nur für Credits rechnen, sondern 'nen sinnvollen Beitrag leisten.

Antworten

Zurück zu „Schach“