Schachcomputer.info Community

Zurück   Schachcomputer.info Community > Schachcomputer / Chess Computer: > Die ganze Welt der Schachcomputer / World of chess computers


Antwort
 
Themen-Optionen Ansicht

  #1  
Alt 03.09.2017, 01:10
Benutzerbild von udo
udo udo ist offline
Lebende Foren Legende
 
Registriert seit: 19.08.2006
Ort: Itzehoe
Alter: 69
Land:
Beiträge: 2.200
Abgegebene Danke: 330
Erhielt 1.137 Danke für 677 Beiträge
Aktivitäten Langlebigkeit
8/20 18/20
Heute Beiträge
0/3 sssss2200
Das Millionen Dollar Schachproblem

Hallo, ich bin zufällig auf eine Seite der University of St. Andrews in Schottland über Umwegen gestoßen, wo es wohl darum geht, ein Algorithmus zu finden, um bei einem Schachbrett mit 1000x1000 Feldern Damen so zu verteilen, das sie sich nicht gegenseitig bedrohen, wenn ich das ganze richtig verstanden habe. Für Computer wohl nicht lösbar, bzw. sollte ein Deep Thought dafür angeblich 500.000.000 Jahre brauchen.
Das ganze soll mit 1 Millionen Dollar belohnt werden.

Durch eine ev. Lösung sollen widerrum andere Probleme besser lösbar sein.

https://www.st-andrews.ac.uk/news/ar...1539813,en.php

Tja, wer gerade mal nichts zu tun hat
Mit Zitat antworten
  #2  
Alt 03.09.2017, 11:48
MHz MHz ist offline
Excalibur Grandmaster
 
Registriert seit: 05.03.2017
Land:
Beiträge: 98
Abgegebene Danke: 73
Erhielt 36 Danke für 23 Beiträge
Aktivitäten Langlebigkeit
0/20 7/20
Heute Beiträge
0/3 sssssss98
AW: Das Millionen Dollar Schachproblem

Hallo,
auf einem normalen Schachbrett ist das kein Problem,
aber bei 1000 x 1000 Feldern !? Das ist mir zu viel ..

Grüße
Gerd
Mit Zitat antworten
  #3  
Alt 04.09.2017, 12:49
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.509
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
0/3 sssss1509
AW: Das Millionen Dollar Schachproblem

 Zitat von MHz Beitrag anzeigen
Hallo,
auf einem normalen Schachbrett ist das kein Problem,
aber bei 1000 x 1000 Feldern !? Das ist mir zu viel ..

Grüße
Gerd
Es ist nicht so schwierig ein rekursives Algorithmus dafür zu programmieren, habe ich schon mal gemacht. Aber das wird wohl sehr viel rechenzeit kosten für ein 1000 x 1000 brett...
Und dazu hat man auch noch gesagt eine lösung sei nicht genügend: es sollte ein neues, sehr effizientes algorithmus sein... So etwas wie ein alternatives Simplex algorithmus?!

Ein million ist aber das pondern wert...

Gruss, Paul
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
  #4  
Alt 04.09.2017, 16:06
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
AW: Das Millionen Dollar Schachproblem

 Zitat von paulwise3 Beitrag anzeigen
Es ist nicht so schwierig ein rekursives Algorithmus dafür zu programmieren, habe ich schon mal gemacht. Aber das wird wohl sehr viel rechenzeit kosten für ein 1000 x 1000 brett...
Sehr viel ist eine gnadenlose Untertreibung.
Der Algorithmus muss schon ausgefallener sein...
Mit Zitat antworten
  #5  
Alt 04.09.2017, 19:13
Drahti Drahti ist offline
Revelation
 
Registriert seit: 27.02.2016
Ort: An der Schleuse
Land:
Beiträge: 730
Abgegebene Danke: 602
Erhielt 390 Danke für 254 Beiträge
Aktivitäten Langlebigkeit
3/20 8/20
Heute Beiträge
0/3 ssssss730
AW: Das Millionen Dollar Schachproblem

Was soll der Algorithmus denn finden bzw. beweisen? Eine (von möglicherweise vielen) Lösung(en) zu konstruieren ist doch vergleichsweise trivial. Es können nicht mehr als 1000 Damen sein. Jede Reihe und jede Spalte darf max. eine Dame enthalten... Zusätzlich sind die Diagonalen zu beachten. Wenn mich nicht alles täuscht, kann man die Damen einfach auf dem Brett aufstellen nach einem Schema "nächste Zeile 2 Felder rechts" und nach Überlauf in der letzten Spalte rechts dann wieder links entsprechend die nächste freie Spalte besetzen...

Also: was genau ist die Aufgabe und wo löst man dann den 1 Mio Scheck ein?
Mit Zitat antworten
  #6  
Alt 04.09.2017, 19:35
Benutzerbild von DarkStar
DarkStar DarkStar ist offline
Saitek RISC 2500
 
Registriert seit: 30.05.2010
Land:
Beiträge: 197
Bilder: 17
Abgegebene Danke: 30
Erhielt 264 Danke für 68 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss197
AW: Das Millionen Dollar Schachproblem

 Zitat von Drahti Beitrag anzeigen
Also: was genau ist die Aufgabe und wo löst man dann den 1 Mio Scheck ein?
Dein Algo ist völlig korrekt und Du brauchst nur eine gültige Lösung für den Scheck ...

Das "Problem" steckt einfach in der Fakultät von 1000. Sonst alles easy ...

Stay tuned ...
Carsten
__________________
ChessLab BCS - http://google.com/+CarstenMeyer
Mit Zitat antworten
Folgender Benutzer sagt Danke zu DarkStar für den nützlichen Beitrag:
Solwac (04.09.2017)
  #7  
Alt 04.09.2017, 20:29
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.509
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
0/3 sssss1509
AW: Das Millionen Dollar Schachproblem

 Zitat von Solwac Beitrag anzeigen
Sehr viel ist eine gnadenlose Untertreibung.
Der Algorithmus muss schon ausgefallener sein...
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
  #8  
Alt 04.09.2017, 21:56
Drahti Drahti ist offline
Revelation
 
Registriert seit: 27.02.2016
Ort: An der Schleuse
Land:
Beiträge: 730
Abgegebene Danke: 602
Erhielt 390 Danke für 254 Beiträge
Aktivitäten Langlebigkeit
3/20 8/20
Heute Beiträge
0/3 ssssss730
AW: Das Millionen Dollar Schachproblem

Carsten, was ist das tatsächliche Problem? Muss man ALLE Lösungen finden? Oder die Anzahl der möglichen Lösungen? Möglicherweise reduziert um Spiegelungen und Drehungen? Wenn es so einfach wäre, hätte doch schon jemand das Geld abgeholt...
Mit Zitat antworten
  #9  
Alt 04.09.2017, 22:21
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.509
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
0/3 sssss1509
AW: Das Millionen Dollar Schachproblem

 Zitat von Drahti Beitrag anzeigen
Was soll der Algorithmus denn finden bzw. beweisen? Eine (von möglicherweise vielen) Lösung(en) zu konstruieren ist doch vergleichsweise trivial. Es können nicht mehr als 1000 Damen sein. Jede Reihe und jede Spalte darf max. eine Dame enthalten... Zusätzlich sind die Diagonalen zu beachten. Wenn mich nicht alles täuscht, kann man die Damen einfach auf dem Brett aufstellen nach einem Schema "nächste Zeile 2 Felder rechts" und nach Überlauf in der letzten Spalte rechts dann wieder links entsprechend die nächste freie Spalte besetzen...

Also: was genau ist die Aufgabe und wo löst man dann den 1 Mio Scheck ein?
Wenn das nur so einfach wäre... Versuche es doch mal auf ein schachbrett 8 x 8, du wirst sehen das es einige zeit kostet bevor du eine lösung hast .

Wenn man weiter liest auf die website, wird es klar das man nicht nur eine (der möglich viele) lösung haben will, doch das man auch ein (wenn möglich neues) effizientes algoritmus sucht das man vielleicht auch für viele andere komplexe probleme nutzen kann.

Gruss, Paul
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
  #10  
Alt 05.09.2017, 07:55
Benutzerbild von DarkStar
DarkStar DarkStar ist offline
Saitek RISC 2500
 
Registriert seit: 30.05.2010
Land:
Beiträge: 197
Bilder: 17
Abgegebene Danke: 30
Erhielt 264 Danke für 68 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss197
AW: Das Millionen Dollar Schachproblem

Hi,

 Zitat von Drahti Beitrag anzeigen
Carsten, was ist das tatsächliche Problem? Muss man ALLE Lösungen finden? Oder die Anzahl der möglichen Lösungen?
Möglicherweise reduziert um Spiegelungen und Drehungen? Wenn es so einfach wäre, hätte doch schon jemand das Geld abgeholt...
Eigentlich wird bei der Fragestellung n-Damen auf einem n x n Feld immer gefordert, dass alle Lösungen gefunden werden (gesamt und um Symmetrien bereinigt, bei einem 8 x 8 Feld sind das 96 Lösungen und 12 bereinigt).

Bei n = 1000 hast du ca. 1000! (1000 Fakultät) Möglichkeiten. Da liegt das Problem. Ich glaube , Du hast dir über die Größe der Zahl noch keine Gedanken gemacht.

Das ein effizienter Algo gesucht wird (wie Paul schreibt), ist nicht die Aufgabe, sondern quasi der Nebeneffekt. Hast du nämlich einen Algo, der alle Lösungen in Polynominalzeit lösen könnte, wäre der automatisch sehr sehr effizient.

Ich würde dir allerdings schon einige Tüten Gummibärchen spendieren, wenn du bis Jahresende eine einzige Lösung für n = 1000 präsentierst Egal wie elegant der Algo ist ...

Stay tuned ...
Carsten
__________________
ChessLab BCS - http://google.com/+CarstenMeyer
Mit Zitat antworten
Antwort

Themen-Optionen
Ansicht

Forumregeln
Du bist nicht berechtigt, neue Themen zu erstellen.
Du bist nicht berechtigt, auf Beiträge zu antworten.
Du bist nicht berechtigt, Anhänge hochzuladen.
Du bist nicht berechtigt, deine Beiträge zu bearbeiten.

BB code ist An
Smileys sind An.
[IMG] Code ist An.
HTML-Code ist An.

Gehe zu

Ähnliche Themen
Thema Erstellt von Forum Antworten Letzter Beitrag
Hilfe: Mondial II - Problem Eckehard Kopp Technische Fragen und Probleme / Tuning 5 09.05.2016 22:48
Frage: MM I-Problem Eckehard Kopp Technische Fragen und Probleme / Tuning 1 26.03.2016 03:09
Frage: Problem mit einem Problem udo Teststellungen und Elo Listen / Test positions and Elo lists 10 29.05.2011 01:25


Alle Zeitangaben in WEZ +1. Es ist jetzt 05:51 Uhr.



Powered by vBulletin (Deutsch)
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
©Schachcomputer.info