Logical-Löse-Programm

[Naphthalin]

sudoku hat ja auch nichts mit spannenden rätseln zu tun. und ich bezweifle nicht, dass ein computergeneriertes rätsel eine schöne lösung haben kann, aber versuch mal einem computer beizubringen, was für den löser "schwer" ist. und genau an dieser stelle liegt das problem. für einen computer ist schwer, was zB 5-stufige fallunterscheidungen braucht. versuch mal mit einem computer ein schönes schweres tapa zu erzeugen. du wirst daran aller wahrscheinlichkeit scheitern^^ je "intuitiver" das lösen ist, desto härter wird das.

Naphthalin

[~ÔttÔ~]

Naphtalin: "Sudoku hat ja auch nichts mit spannenden rätseln zu tun" -- vor 4 Jahren hätte man diesen Satz vielleicht nicht gelesen. Abgesehen davon reden wir hier ja nicht von Einzelanfertigungen, wie sie im Rätselportal stehen, sonden von Standard-AUfgaben mit Standard-Regeln. Wahrscheinlich wird heute jede Rätselart, von der es mehr als 100 Aufgaben gibt, als "nicht spannend" bezeichnet.

Naphtalin: "versuch mal einem computer beizubringen, was für den löser "schwer" ist" -- kein prinzipielles Problem. Dazu bedarf es nur einer Korrelation zwischen den Lösungsschritten und der Lösungszeit. Bei Sudoku ist dieses Ranking ziemlich ausgefeilt. Die "gefühlte" Schwierigkeit einer Aufgabe stimmt im übrigen sehr oft nicht; die Löser lassen sich da bei der Bewertung oft von anderen Faktoren beeinflussen.

Naühtalin: "für einen computer ist schwer, was zB 5-stufige fallunterscheidungen braucht" -- Aber ganz und gar nicht, das schafft er mit links in Sekundenbruchteilen. Und nicht einmal die Programmierung ist schwierig. Schwierig sind i.d.R. nur die Generatoren, nicht die Löser. Vor allem, wenn es nur darum geht, eine Lösung zu finden. Im übrigen ist zwischen einer Fallunterscheidung und Trial+Error technisch kein Unterschied. Der Unterschied ist menschlicher Natur: Trial+Error wird zur Fallunterscheidung, wenn man sie noch im Kopf durchführen kann. Der Unterschied ist also nur die Suchtiefe.

Naphtalin: "versuch mal mit einem computer ein schönes schweres tapa zu erzeugen. du wirst daran aller wahrscheinlichkeit scheitern" -- Ganz sicher nicht. Das ist nur eine Frage des Aufwands. Wahrecheinlich würdest Du das gleiche von einem Masyu-Generator behaupten - und da kann ich ich den Gegenbeweis antreten. Oder schau Dir mal Bernies Slitherlink-Generator an (der besser als meiner ist). Und ich kann mir vorstellen, dass Bernie schon an einem Tapa-Generator arbeitet :-)

~ÔttÔ~

[berni]

(da kannst Du genau die Felder vorgeben, die die Vorgabezahlen enthalten sollen).

Das würde ich dann aber nicht mehr als computergeneriert durchgehen lassen. Da hat nämlich ein Mensch an dem so entstandenen Sudoku mitgearbeitet. Für mich wäre das ein Hybrid-Rätsel was ich besser als reine computergenerierten Rätsel einsortieren würde. Und da stimme ich dir dann auch zu: Bei Hybrid-Rätseln kommt man sehr nahe an handgefertigte Rätsel ran. (Ich habe übrigens auch keine Probleme damit, wenn ein rein handgefertigtes Rätsel anschließend durch einen Sudokusolver gejagt wird um zu testen ob es wirklich eindeutig ist. Das finde ich sogar sinnvoll!)

Naphtalin: "Sudoku hat ja auch nichts mit spannenden rätseln zu tun" -- vor 4 Jahren hätte man diesen Satz vielleicht nicht gelesen.

Also ich hab sowas auch schon vor 8 Jahren gesagt, nur dass ich das Wort Sudoku damals noch nicht kannte.

Wahrscheinlich wird heute jede Rätselart, von der es mehr als 100 Aufgaben gibt, als "nicht spannend" bezeichnet.

Japanische Summen löse ich immernoch sehr gerne, Tapa ebenfalls und auch bei Rundwegen gibt es immernoch neues zu entdecken. Bei allen dreien möchte ich mal behaupten, dass ich schon über 100 Rätsel gelöst habe. (Naja, bei den Tapa vielleicht noch nicht ganz.)

Die "gefühlte" Schwierigkeit einer Aufgabe stimmt im übrigen sehr oft nicht; die Löser lassen sich da bei der Bewertung oft von anderen Faktoren beeinflussen.

Das ist genau das Problem. Wie schwer ist ein Rätsel? Wenn ich dann sage, das ist so schwer wie mein Computer behauptet, dass es schwer ist, dann stimmt das nicht. Ein Beispiel: Ich erzeuge zwei Sudoku, einmal Standardsudoku, einmal Gebietssudoku. Beide erstelle ich mit dem gleichen Programm und es geht so vor, wie du vorschlägst. Das Programm behauptet, die beiden Sudoku seine gleichschwer. Erfahrungsgemäß wird aber das Gebietssudoku als deutlich schwerer wahrgenommen als das Standardsudoku. Also ist es schwerer! (Auch wenn der Computer da anderer Meinung ist, aber der hat da nichts zu sagen!)

Im übrigen ist zwischen einer Fallunterscheidung und Trial+Error technisch kein Unterschied.

Meiner Meinung nach sind das zwei Wörter (in unterschiedlichen Sprachen) für ein und die selbe Sache.

[Calavera]

Im übrigen ist zwischen einer Fallunterscheidung und Trial+Error technisch kein Unterschied.

Meiner Meinung nach sind das zwei Wörter (in unterschiedlichen Sprachen) für ein und die selbe Sache.

Zumindest im Rätselportal wird immer von Fallunterscheidung geredet. Dass damit dann wieder nur das schriftlich Durchgeführte und nicht das Durchgehen im Kopf gemeint ist, ist eine andere Geschichte...


Schönen Gruß,
Calavera

[Naphthalin]

außerdem führt man als löser fallunterscheidungen anders durch: man schaut, welche felder vermutlich wenige möglichkeiten haben. dabei finden wir aber nicht automatisch das beste feld. ein rechner hingegen nutzt entweder bruteforce und ignoriert dieses "beste feld" oder aber er findet es mit sicherheit...

Naphthalin

[~ÔttÔ~]

Naphtalin: »Ein rechner hingegen nutzt entweder bruteforce und ignoriert dieses "beste feld"« -- Das kommt darauf an. Wenn es darum geht, alle Lösungen zu finden bzw. zu beweisen, dass eine Aufgabe nur eine Lösung hat, dann muss man bei Brute Force sowieso alles durchprobieren und die Reihenfolge ist egal. Anders ist es bei echten Spielprogrammen mit Minimax-Algorithmus, da werden sehr wohl die Zuglisten vorsortiert (also der erfolgsversprechendste Zug zuerst begutachtet), damit man möglichst viele Alpha/Beta-Schnitte bekommt. Wenn es bei einem Puzzle-Löseprogramm nur darum geht, *eine* Lösung zu finden, dann kann man das natürlich auch machen. Vorausgesetzt, es gibt eine vernünftige Bewertungsfunktion, die ein Sortierkriterium liefert.

~ÔttÔ~

[~ÔttÔ~]

Bernie: "Ich erzeuge zwei Sudoku, einmal Standardsudoku, einmal Gebietssudoku. Beide erstelle ich mit dem gleichen Programm und es geht so vor, wie du vorschlägst. Das Programm behauptet, die beiden Sudoku seine gleich schwer. Erfahrungsgemäß wird aber das Gebietssudoku als deutlich schwerer wahrgenommen als das Standardsudoku. Also ist es schwerer!" -- Dann gehst Du eben nicht so vor wie ich es vorschlage. Mein Vorschlag: Generiere Sudokus und Gebietssudokus. Messe die Schwierigkeit der Aufgaben. Und dann bringe dem Programm bei, dass es derartige Aufgaben so zu bewerten hat, wie es die Messergebnisse nahelegen. Da kommt dann zwangsläufig heraus, dass Gebietssudokus schwerer sind, selbst wenn das Programm die gleichen Methoden zum Lösen verwendet.

Abgesehen davon braucht man eine größere Zahl von Testlösern, um die Schwierigkeit einer Aufgabe zu messen. Und ich meine *messen*, nicht aus dem Bauch bewerten lassen. Ich verwende dazu simpel die zum Lösen benötigte Zeit.

Dann gibt es ein weiteres Phänomen, habe ich ausprobiert: Ein eher leichtes Sudoku und mehrfach präsentiert, gespiegelt, gedreht, umgestülpt, umnummeriert. Für ein Programm sind die Sudokus identisch, für den menschlichen Löser aber nicht. Der Unterschied ist statistisch signifikant, wenn auch nicht allzu groß. Meine These ist, dass sich unser Gehirn mit bestimmten Mustern leichter tut als mit anderen. Und dass die Löser Vorlieben haben, beispielsweise zuerst nach 1ern suchen, dann nach 2ern, usw. und eben nicht immer mit der "erfolgsversprechendsten" Zahl beginnen.

~ÔttÔ~

[SilBer]

Mann, das wäre genau das Forschungsthema gewesen, was mich "damals" an der Uni interessiert hätte!! Mein Bereich war Spieltheorie, so weit weg wäre das gar nicht gewesen... Mein Prof wollte aber lieber gesundheitsbezogene Lebensqualität, naja, ist auch einigermaßen spannend.
Wo forschst du denn, oder ist das nur so privat??
LG Silke

[berni]

Bernie: "Ich erzeuge zwei Sudoku, einmal Standardsudoku, einmal Gebietssudoku. Beide erstelle ich mit dem gleichen Programm und es geht so vor, wie du vorschlägst. Das Programm behauptet, die beiden Sudoku seine gleich schwer. Erfahrungsgemäß wird aber das Gebietssudoku als deutlich schwerer wahrgenommen als das Standardsudoku. Also ist es schwerer!" -- Dann gehst Du eben nicht so vor wie ich es vorschlage. Mein Vorschlag: Generiere Sudokus und Gebietssudokus. Messe die Schwierigkeit der Aufgaben. Und dann bringe dem Programm bei, dass es derartige Aufgaben so zu bewerten hat, wie es die Messergebnisse nahelegen. Da kommt dann zwangsläufig heraus, dass Gebietssudokus schwerer sind, selbst wenn das Programm die gleichen Methoden zum Lösen verwendet.

Tja, und wenn dann eines dieser Gebietssudoku zufällig aussieht wie ein Standardsudoku, dann wird dieses plötzlich falsch einsortiert, oder?!? Wo ist da die Grenze? Oder muss ich jetzt dem Programm auch noch beibringen wie nahe am Standardsudoku ein Gebietssudoku ist? So langsam wird es kompliziert und meiner Meinung lohnt sich dann irgendwann der Aufwand einfach nicht mehr. Außer halt, wenn man wirklich riesige Massenproduktion betreiben will. Aber dafür sind die Gebietssudoku bereits zu unpopulär.

Abgesehen davon braucht man eine größere Zahl von Testlösern, um die Schwierigkeit einer Aufgabe zu messen. Und ich meine *messen*, nicht aus dem Bauch bewerten lassen. Ich verwende dazu simpel die zum Lösen benötigte Zeit.

Du solltest diese wenigstens noch durch die Größe des Rätsels teilen. Sonst sind 16x16-Sudoku immer extrem schwer, verglichen mit den 9x9. Aber auch so denke ich, dass es möglich ist, leichte Rätsel zu erstellen, für die man viel Zeit benötigt (bei Sudoku wohl nicht; die dürften dann aber eher langweilig sein, weil nervige Routinearbeit). Ob man schwere Rätsel erstellen kann, die man schnell lösen kann, weiß ich nicht. Wahrscheinlich nicht.

Dann gibt es ein weiteres Phänomen, habe ich ausprobiert: Ein eher leichtes Sudoku und mehrfach präsentiert, gespiegelt, gedreht, umgestülpt, umnummeriert. Für ein Programm sind die Sudokus identisch, für den menschlichen Löser aber nicht. Der Unterschied ist statistisch signifikant, wenn auch nicht allzu groß. Meine These ist, dass sich unser Gehirn mit bestimmten Mustern leichter tut als mit anderen. Und dass die Löser Vorlieben haben, beispielsweise zuerst nach 1ern suchen, dann nach 2ern, usw. und eben nicht immer mit der "erfolgsversprechendsten" Zahl beginnen.

Ich hab's zwar nie getestet, aber vermutet und auch schon bei Wettbewerben genutzt.

[Calavera]

Ob man schwere Rätsel erstellen kann, die man schnell lösen kann, weiß ich nicht. Wahrscheinlich nicht.

Naja, je nach Bewertung... Ich denke da an ein Rätsel, für dessen Lösung man auf einen besonders schweren Ansatz kommen muss, das danach aber leicht zu lösen ist. Das kann man dann schnell lösen, obwohl es schwer ist.

Dann gibt es ein weiteres Phänomen, habe ich ausprobiert: Ein eher leichtes Sudoku und mehrfach präsentiert, gespiegelt, gedreht, umgestülpt, umnummeriert. Für ein Programm sind die Sudokus identisch, für den menschlichen Löser aber nicht. Der Unterschied ist statistisch signifikant, wenn auch nicht allzu groß. Meine These ist, dass sich unser Gehirn mit bestimmten Mustern leichter tut als mit anderen. Und dass die Löser Vorlieben haben, beispielsweise zuerst nach 1ern suchen, dann nach 2ern, usw. und eben nicht immer mit der "erfolgsversprechendsten" Zahl beginnen.

Ich hab's zwar nie getestet, aber vermutet und auch schon bei Wettbewerben genutzt.

Ich vermute, dass es auch einen sehr starken Unterschied macht, ob Zahlen senkrecht oder waagerecht zueinander angeordnet sind. Mir zumindest fällt es bei Kropkis und Sudokus immer schwerer, Spalten zu kontrollieren als Zeilen. Bei Kulturen, die senkrecht schreiben, dürfte das Phänomen umgekehrt sein...


Schönen Gruß,

Calavera