Rekursion bricht nicht ab

[Christian H. Kuhn]

Hallo Gemeinde,

Die letzten paarundzwanzig Mal hat sich die Lösung beim Schreiben der
Hilfebitte gefunden, diesmal wohl nicht ...

Ich bringe mir gerade Continous Integration bei, weil ich nicht
ausschließen will, dass ich das mal beruflich brauche. Eclipse, Git,
Maven, Jenkins, verteilt auf LapTop, Tower und remote server. Ein paar
Tests mit Checkstyle, JUnit4, JaCoCo. Was genau davon sinnvoll ist,
ist diskutierbar, hier geht es eher um die Bedienung. Und um die
Technik zu testen, habe ich mir als Fingerübung einen Lösungsfinder
für das Android-Spiel Lyfoes geschrieben.

Die Vorbereitung war natürlich das aufwendigste. TDD, ein paar
Klassen, aus denen die Hauptklasse nachher zusammengesetzt wird, die
ganzen Tests, Checkstyle besteht auf javadoc, Variablennamen im
richtigen Format, dann doch einen Testfall vergessen und zu geringe
Testabdeckung (und dabei auch gelernt, warum 100% Testabdeckung nicht
immer nur Fetisch ist), und ganz zum Schluss die eigentliche Lösungssuche.

Natürlich per Rekursion. Die Lyfoes werden durch Buchstaben
repräsentiert, die Reagenzgläser durch Vector<Character>, das gesamte
Setup durch Vector<Vector<Character>>. Im Prinzip wird bei getResult()
überprüft:

- - Stellung gelöst? Dann Zugfolge bis hierher als Lösung zurückgeben.
- - Stellung schon mal gesehen? Dann null zurückgeben, ansonsten hash
der Stellung in Set für diesen Rekursionszweig zufügen.
- - Mögliche Zugliste generieren. Liste leer? Null zurückgeben.
- - Züge ausführen, auf neue Stellung getResult() aufrufen (die
Rekursion). Wenn erhaltenes result != null, kommt es in eine Liste
allResults.
- - Nach ausführen aller Züge: Wenn allResults leer, null zurückgeben.
Sonst eine kürzeste Zugfolge aus allResults zurückgeben.

Klappt in einigen einfachen Testfällen. Klappt insbesondere dann, wenn
in der Startposition nur ein leeres Reagenzglas als Puffer fürs
Umsortieren ist. Sobald da zwei sind, bricht die Rekursion nicht mehr ab.

Ich sehe zwei Möglichkeiten: Entweder habe ich eine Abbruchbedingung
übersehen. Ich finde aber keine weitere. Oder die hashCode-Funktion
für die Stellungen taugt nix. Den Verdacht hatte ich eh, aber eher in
die andere Richtung: dass ich für eine neue Stellung den gleichen hash
habe wie für eine bisherige und deshalb Lösungen nicht finde. Ideal
wäre eine bijektive hash-Funktion, die aber den Zahlenraum int nicht
sprengt ...

Aufgrund dieser allgemeinen Beschreibung wird mir niemand helfen
können. Der Quellcode ist hier: https://www.qno.de/lyfoesolver.zip
steht unter keiner Lizenz (jedenfalls wüsste ich nichts), lachen ist
erlaubt ;-) (ebenfalls zu Lernzwecken habe ich alles Mögliche und
vermutlich manches mehr mit Exceptions geregelt). Für Hinweise, wo
genau ich mich wie dämlich angestellt habe, bin ich dankbar.

TIA
QNo

[Patrick Roemer]

Post by Christian H. Kuhn
Klappt in einigen einfachen Testfällen. Klappt insbesondere dann, wenn
in der Startposition nur ein leeres Reagenzglas als Puffer fürs
Umsortieren ist. Sobald da zwei sind, bricht die Rekursion nicht mehr ab.

Geh das kleinstmögliche Szenario, bei dem das Verhalten auftritt, mal
mit Papier und Stift von Hand durch. Dann lass in Deinem Programm in
jedem Rekursionsschritt den Spielzustand ausgeben (oder steppe im
Debugger durch) und vergleiche mit Deinen Erwartungen. Oft findet man so
schon raus, wo es hakt.

Post by Christian H. Kuhn
Aufgrund dieser allgemeinen Beschreibung wird mir niemand helfen
können. Der Quellcode ist hier: https://www.qno.de/lyfoesolver.zip

Es wird wohl schwierig, anhand dieses Codes hier Hilfe zu finden - schon
alleine, weil man ja erst mal verstehen müsste, worum es bei dem Spiel
überhaupt geht. :)

Zumindest wäre es sinnvoll, ein paar funktionierende Testfälle
beizulegen, und einen, der das Problem demonstriert.

Viele Grüße,
Patrick

[Christian H. Kuhn]

Responding to Christian H. Kuhn: Geh das kleinstmögliche Szenario,
bei dem das Verhalten auftritt, mal mit Papier und Stift von Hand
durch. Dann lass in Deinem Programm in jedem Rekursionsschritt den
Spielzustand ausgeben (oder steppe im Debugger durch) und
vergleiche mit Deinen Erwartungen. Oft findet man so schon raus,
wo es hakt.

Also erstmal versucht, das kleinstmögliche Szenario zu finden. Und
dabei festgestellt, dass der Rekursionsbaum bei sonst gleichbleibenden
Bedingungen exponentiell mit der Anzahl der leeren Reagenzgläser
wächst. Ich hatte keine nicht abbrechende Rekursion, ich habe
lediglich die Rechenzeit massiv unterschätzt. Tage statt Minuten. Ich
werde also einen anderen Ansatz verwenden müssen, der den Suchbaum
Stufe für Stufe aufbaut und auf Lösungen überprüft, bevor die nächste
Stufe berechnet wird.

Es wird wohl schwierig, anhand dieses Codes hier Hilfe zu finden -
schon alleine, weil man ja erst mal verstehen müsste, worum es bei
dem Spiel überhaupt geht.

Ich nahm an, ein Spiel, das sogar ich kenne, müsse allgemein bekannt
sein, offensichtlich irrte ich Lyfoes ist ein Android-Spiel. Man
hat einen Satz von gefärbten pelzigen Lebewesen, genannt Lyfoes. Die
kommen in verschiedenen Farben. Ausgangslage: Viele Lyfoes bunt
verteilt auf Reagenzgläser (Anzahl pro Farbe gleich Fassungsvermögen
eines Glases, bisher gesichtet 3 oder 4. Anzahl der Gläser gleich
Anzahl der Farben plus eins oder zwei für leere Gläser). Ziel: Alle
Gläser nur mit gleichfarbigen gefüllt oder leer. Zug: Lyfoe aus einem
Glas in ein leeres oder in ein nichtvolles mit gleichfarbigem oberem
Lyfoe.

Zumindest wäre es sinnvoll, ein paar funktionierende Testfälle
beizulegen, und einen, der das Problem demonstriert.

Sind in LSBoard.main().

Vielen Dank
QNo

[Peter Büttner]

Post by Christian H. Kuhn

schon alleine, weil man ja erst mal verstehen müsste, worum es bei
dem Spiel überhaupt geht.

Ich nahm an, ein Spiel, das sogar ich kenne, müsse allgemein bekannt
sein, offensichtlich irrte ich Lyfoes ist ein Android-Spiel. Man
hat einen Satz von gefärbten pelzigen Lebewesen, genannt Lyfoes. Die
kommen in verschiedenen Farben. Ausgangslage: Viele Lyfoes bunt
verteilt auf Reagenzgläser (Anzahl pro Farbe gleich Fassungsvermögen
eines Glases, bisher gesichtet 3 oder 4. Anzahl der Gläser gleich
Anzahl der Farben plus eins oder zwei für leere Gläser). Ziel: Alle
Gläser nur mit gleichfarbigen gefüllt oder leer. Zug: Lyfoe aus einem
Glas in ein leeres oder in ein nichtvolles mit gleichfarbigem oberem
Lyfoe.

Letztlich wie ein Kartenspiel Patience (da gibt es hunderte, eins passt
schon). Vielleicht findest du da ein Konzept zur Lösung, oder eine
Inspiration. "Sortieren mit beschränkten Ressourcen".

Das es bei dir mit Brute force zu lange dauert kann natürlich auch
an 'schlecht Programmiert' liegen:-) (deinen Code schaute ich mir
nicht an).


Peter

[Christian H. Kuhn]

Post by Peter Büttner
Das es bei dir mit Brute force zu lange dauert kann natürlich auch
an 'schlecht Programmiert' liegen:-) (deinen Code schaute ich mir
nicht an).

Bei brute force steigt der Rechenaufwand halt von Level zu Level um
einen Faktor. Der ändert sich nicht, egal wie grausam man codiert. Und
wenn ich meine Minimalbeispiele im Test anschaue, dann erreiche ich bei
einer Geschwindigkeitssteigerund um Faktor 1000 immer noch keine Lösung
realistischer Stellungen in realistischer Zeit.

Ansonsten kann ich mir gut vorstellen, dass ich unter
Effizienzgesichtspunkten „schlecht programmiert“ habe. Ich könnte mir
gut vorstellen, dass Fehlerbehandlung im C-Stil über einen
int-Rückgabewert schneller funktioniert als der etwas ... ausufernde
Gebrauch von Exceptions. Deren Verwendung sauber durchzuziehen war aber
Lernziel. Sollte ich je eine auf Effizienz getrimmte Fassung schreiben,
werde ich das überdenken.

lg
QNo

[Wanja Gayk]

Post by Christian H. Kuhn
Ansonsten kann ich mir gut vorstellen, dass ich unter
Effizienzgesichtspunkten ?schlecht programmiert? habe. Ich könnte mir
gut vorstellen, dass Fehlerbehandlung im C-Stil über einen
int-Rückgabewert schneller funktioniert als der etwas ... ausufernde
Gebrauch von Exceptions. Deren Verwendung sauber durchzuziehen war aber
Lernziel. Sollte ich je eine auf Effizienz getrimmte Fassung schreiben,
werde ich das überdenken.

Ich glaube nicht, dass das das Problem ist, sondern bei derart harten
Geschwindigkeitsproblemen solltest du den Flaschenhals
a) im Algorithmus suchen (insb. bei Rekursion: Werden z.B. bereits
gewonnene Erkentnisse verworfen und/oder neu berechnet, obwohl man sie
sich merken kann?)
oder
b) in der Datenstruktur (z.B. du löscht immer Werte am Anfang einer
ArrayList, das ist O(n) -> bei einer LinkedList ist removeFirst() nur O
(1), z.B. du iterierst ohnehin immer durch eine Liste und ab und zu
löscht du was an der aktuellen Position, dann ist LinkedList und
Iterator#remove() besser statt ArrayList#remove(n) oder
LinkedList#remove(n), oder z.B. die Suche in einem Ergebnis ist linear,
dabei ist die Liste selten geschriebenm aber oft gelesen und eine binäre
Suche ist schneller, oder vielleicht willst du auch eine HashMap, zb.
ein HashSet, um zu checken, ob etwas schon vorhanden ist?)
oder
c) in der Speicherverwaltung - und zwar weniger im Erzeugen von vielen,
kurzlebigen Objekten, sondern darin dem Garbage-Collector nicht genügend
Speicher gegeben zu haben( -verbose:gc ), sodass es unnötig viele full
garbage collections gibt.

Der Overhead vom Exceptionhandling ist jedenfalls in 99.9999999999999%
aller Fälle kein Problem.

Aber wie immer: Wer nicht misst, liegt in der Regel falsch.
Schau dur dazu am besten das Tool "JVisualVM" an und versuch dort einmal
einmal mit dem Sampler und einmal mit dem Profiler deine Applikation zu
vermessen und schau, wo die meiste Zeit drauf geht (Sampler und Profiler
haben beide Vor- und Nachteile, der Sampler erwischt oft häufige sehr
kurze Aufrufe nicht, der Profiler bläst ggf. kurze Aufrufe mit seinem
eigenen Overhead auf).

Download hier: https://visualvm.java.net/

Gruß,
-Wanja-

[Christian H. Kuhn]

Hallo Wanja,

Danke für die Hinweise.

Post by Wanja Gayk
a) im Algorithmus suchen (insb. bei Rekursion: Werden z.B. bereits
gewonnene Erkentnisse verworfen und/oder neu berechnet, obwohl man sie
sich merken kann?)

Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe,
suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
nächsten Version probieren.

Post by Wanja Gayk
b) in der Datenstruktur (z.B. du löscht immer Werte am Anfang einer
ArrayList, das ist O(n) -> bei einer LinkedList ist removeFirst() nur O
(1), z.B. du iterierst ohnehin immer durch eine Liste und ab und zu
löscht du was an der aktuellen Position, dann ist LinkedList und
Iterator#remove() besser statt ArrayList#remove(n) oder
LinkedList#remove(n), oder z.B. die Suche in einem Ergebnis ist linear,
dabei ist die Liste selten geschriebenm aber oft gelesen und eine binäre
Suche ist schneller, oder vielleicht willst du auch eine HashMap, zb.
ein HashSet, um zu checken, ob etwas schon vorhanden ist?)

Hm. Werde ich ausprobieren und messen müssen. Wo ich nur peek, pop und
push brauche, verwende ich einen Stack<>, und da der von Vector<> erbt,
kann ich beim Hashen auch mal eben durchiterieren. Zum Speichern schon
gesehener Stellungen benutze ich je nachdem HashMap oder HashSet. Die
ArrayList<>s habe ich aufgrund deines Posts mal mit LinkedList<>s
ersetzt, weil ich tatsächlich hauptsächlich durchiteriere und nur
gelegentlichst mal auf eine Index-Position zugreife. Allerdings ohne
signifikanten Zeitvorteil. Werde ich mir nochmal genauer anschauen.

Post by Wanja Gayk
c) in der Speicherverwaltung - und zwar weniger im Erzeugen von vielen,
kurzlebigen Objekten, sondern darin dem Garbage-Collector nicht genügend
Speicher gegeben zu haben( -verbose:gc ), sodass es unnötig viele full
garbage collections gibt.

Auch damit habe ich mal rumgespielt. Speicher bleibt bislang insgesamt
unter 300 MB, -Xmx1g hat keine Zeitveränderung gezeigt.

Post by Wanja Gayk
Download hier: https://visualvm.java.net/

Das ist doch mal ein interessantes Werkzeug :-) Warum lernt man sowas
nicht im Studium? Vielen Dank!

lg
QNo

[Wanja Gayk]

Post by Christian H. Kuhn
Die
ArrayList<>s habe ich aufgrund deines Posts mal mit LinkedList<>s
ersetzt, weil ich tatsächlich hauptsächlich durchiteriere und nur
gelegentlichst mal auf eine Index-Position zugreife.

Dazu muss ich vielleicht etwas erklären:
Ein stumpfes list.remove(x) ist bei ArrayList und LinkedList etwa gleich
schnell - die eine verschwendet die Zeit beim Zugriff auf den Index, die
andere beim Kopieren der restlichen Elemente "nach links" um die Lücke
am gelöschten Index zu entfernen.
Bei einer LinkedList wird beim Löschen lediglich das nächste Objekt an
das vorherige geknüpft und das aktuelle Objekt ist damit nicht mehr
referenziert), während das Löschen aus einer ArrqaList bedeutet, dass
alle folgenden Positionen eine Position "nach links" kopiert werden
müssen. Dafpr muss die LinkesList der Kette ablaufen, bis es am
jeweiligen index ist.

Der Vorteil der LinkedList stellt sich also nur in einer recht
speziellen Situation ein, nämlich wenn du während des Iterierens löscht.

Iterator<X> it = arrayList.iterator();
while(it.hasNext()){ O(n)
if(canBeUsed(x)){
use(x);
}
if(mustBeDeleted(x)){
it.remove(); //ist O(n) für ArrayList
}
}

Iterator<X> it = linkedList.iterator();
while(it.hasNext()){ /O(n)
if(canBeUsed(x)){
use(x);
}
if(mustBeDeleted(x)){
it.remove(); //ist O(1) für LinkedList
}
}

Hier hat die ArrayList O(n*n) und die LinkedList O(n).

Gruß,
-Wanja-

[Wanja Gayk]

Post by Christian H. Kuhn
Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe,
suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
nächsten Version probieren.

An der Stelle ist ein BloomFilter eine interessante Datenstruktur.
Ein Bloomfilter kanndir mit Sicherheit sagen, dass er eine bytefolge
noch nie gesehen hat, kann aber fälschlicherweise behaupten, er würde
eine bytefolge schon kennen, auch wenn er sie noch nie gesehen hat.

Kurz, er antwortet so:
Filter, habe ich das schon geprüft? Sicher nicht!
Filter, habe ich das schon geprüft? Wahrscheinlich ja.

Weil ein Bloomfilter aber nur ein (oder mehrere) Bitfelder sind, deren
Bits über mehrere hashes einer Bytefolge gesetzt werden, braucht er,
verglichen mit einem HashSet wenig Speicher, hat aber eben die
Unsicherheit, dass er behaupten kann "kenne ich schon", obwohl man es
nie rein getan hat.
Bzgl. dienes Problems kannst du also die Teilbäume, die keine Lösung
enthoelten in einen BloomFilter schicken und den immer fragen: "Hey,
kennst du den Teilbaum?" (war der Teilbaum ein Miserfolg?) und wenn der
sagt: "Den kenne ich nicht!", weißt du, dass den Baum neu aufbauen und
prüfen musst.

In der Guava Bibliothek (https://github.com/google/guava ) gibt es eine
Implementation für einen BloomFilter:
Siehe javadoc:
https://google.github.io/guava/releases/snapshot/api/docs/com/google/com
mon/hash/BloomFilter.html
Siehe Sourcecode:
https://github.com/google/guava/blob/master/guava/src/com/google/common/
hash/BloomFilter.java
Download:
https://github.com/google/guava/releases/tag/v19.0

Gruß,
-Wanja-

[Patrick Roemer]

Post by Wanja Gayk

Post by Christian H. Kuhn
Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe,
suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
nächsten Version probieren.

An der Stelle ist ein BloomFilter eine interessante Datenstruktur.
Ein Bloomfilter kanndir mit Sicherheit sagen, dass er eine bytefolge
noch nie gesehen hat, kann aber fälschlicherweise behaupten, er würde
eine bytefolge schon kennen, auch wenn er sie noch nie gesehen hat.
Filter, habe ich das schon geprüft? Sicher nicht!
Filter, habe ich das schon geprüft? Wahrscheinlich ja.

Den Hinweis verstehe ich in diesem Kontext nicht.

Es gibt zum einen eine "Menge der aktuell weiter zu untersuchenden
Stellungen" - eben Christians obenstehendes "alle Stellungen in Tiefe
n", also die Queue in der Breitensuche. Da braucht man offenkundig die
konkreten Stellungen selber, nicht nur die Information, ob Stellung x
schon gesehen wurde.

Zum anderen will man vermeiden, bereits untersuchte Stellungen noch
einmal zu durchlaufen. Da bringt ein Bloomfilter aber auch nix. Wenn ich
eine Stellung sicher nicht gesehen habe, muss ich sie untersuchen. Wenn
ich eine Stellung wahrscheinlich schon gesehen habe, muss ich sie auch
untersuchen, denn es könnte ja sein, dass sie doch nicht gesehen wurde,
und dass es sich um die Stellung handelt, die zur (kürzesten oder gar
einzigen) Lösung führt. Das war ja genau das Problem mit Christians
initialem #hashCode()-Ansatz. (Ist ja auch nah verwandt.)

Für die gesehenen Stellungen würde ich zunächst mal ein ordinäres
HashSet verwenden. Wenn sich rausstellt, dass das tatsächlich in
Speicherprobleme läuft, würde ich erst mal schauen, ob man die
Repräsentation der Stellungen nicht kompakter hinbekommt. Nur, wenn da
das Ende der Fahnenstange erreicht ist, würde ich für die gesehenen
Stellungen eine kompaktere Alternativrepräsentation verwenden - das
könnte z.B., wenn ich das richtig verstanden habe, Christians
"bigHashCode" sein. Auf jeden Fall will man sicher sein, dass nicht
gesehene Stellungen *immer* überprüft werden.

Habe ich da was falsch verstanden oder übersehen?

Viele Grüße,
Patrick

[Wanja Gayk]

Post by Patrick Roemer

Post by Wanja Gayk

Post by Christian H. Kuhn
Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe,
suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
nächsten Version probieren.

An der Stelle ist ein BloomFilter eine interessante Datenstruktur.
Ein Bloomfilter kanndir mit Sicherheit sagen, dass er eine bytefolge
noch nie gesehen hat, kann aber fälschlicherweise behaupten, er würde
eine bytefolge schon kennen, auch wenn er sie noch nie gesehen hat.
Filter, habe ich das schon geprüft? Sicher nicht!
Filter, habe ich das schon geprüft? Wahrscheinlich ja.

Den Hinweis verstehe ich in diesem Kontext nicht.

Jetzt, wo ich den Post nochmal lese, muss ich dir recht geben, dass es
wohl nicht ganz passt, weil er ja erst tiefer herab steigt, wenn die
kürzere Tiefe nichts brachte und die Lösung möglicherweise weiter unten
im Baum liegt.

Post by Patrick Roemer
Zum anderen will man vermeiden, bereits untersuchte Stellungen noch
einmal zu durchlaufen. Da bringt ein Bloomfilter aber auch nix. Wenn ich
eine Stellung sicher nicht gesehen habe, muss ich sie untersuchen. Wenn
ich eine Stellung wahrscheinlich schon gesehen habe, muss ich sie auch
untersuchen, denn es könnte ja sein, dass sie doch nicht gesehen wurde,
und dass es sich um die Stellung handelt, die zur (kürzesten oder gar
einzigen) Lösung führt. Das war ja genau das Problem mit Christians
initialem #hashCode()-Ansatz. (Ist ja auch nah verwandt.)

Die Idee beim Filter war eher, dass Bäume, die schon als "tot" erkannt
wurden, nicht neu durchlaufen werden müssen.
Alles was nicht garantiert tot ist, enthält eine mögliche Lösung.
Bei einem Baum (0 links, 1 rechts)
0000 (keine Lösung)
0001 (keine Lösung)
0010 (keine Lösung)
0011 (keine Lösung)
Würde man sich folgende (Teil-)Bäume im Filter merken können:
0000
0001
0010
0011
000
001
00

Nehmen wir an, mit dem Wissen baue ich nun alle möglichen Bäume von
Grund auf neu auf, so wird der Filter bei "00" sagen: "Kenne ich schon,
ist tot, such weiter.", also kann man bei 01 starten und spart sich alle
zuvor genannten Teilbäume.

Aber dummerweise hatte ich übersehen, dass es eine Breitensuche ist, da
wird halt nicht zuerst 0000 durchlaufen, dann 0001, dann 0010...
(jetzt mal vereinfacht für eine maximale Tiefe von 4), insofern bringt
das nix.

Post by Patrick Roemer
Habe ich da was falsch verstanden oder übersehen?

Nein, ich glaube eher, ich habe etwas falsch verstanden.

Gruß,
-Wanja-

[Wanja Gayk]

Post by Wanja Gayk
Nehmen wir an, mit dem Wissen baue ich nun alle möglichen Bäume von
Grund auf neu auf...

(...)
Und jetzt erkenne ich noch, dass es wohl ein wenig spät ist, weil das
natürlich Unsinn ist.

Gruß,
-Wanja-

[Patrick Roemer]

Post by Wanja Gayk

Post by Christian H. Kuhn
Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe,
suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste
alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann
bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der
nächsten Version probieren.

[...]

Post by Wanja Gayk
Bzgl. dienes Problems kannst du also die Teilbäume, die keine Lösung
enthoelten in einen BloomFilter schicken und den immer fragen: "Hey,
kennst du den Teilbaum?" (war der Teilbaum ein Miserfolg?) und wenn der
sagt: "Den kenne ich nicht!", weißt du, dass den Baum neu aufbauen und
prüfen musst.

Den Absatz hatte ich natürlich gekonnt überlesen. :) Ich verstehe es
aber immer noch nicht. Abgesehen davon, dass der Ansatz mit der
stufenweisen Tiefensuche an sich schon sehr fragwürdig ist: Was sind
denn da die "Teilbäume, die keine Lösung enthalten"? Eine definitive
Lösung hat bis hierher ja wohl keiner, sonst wären wir ja schon fertig.
Also solche, die definitiv keine Lösung enthalten? Das wären dann
solche, bei denen alle Pfade Tiefe <= n haben, weil an den
Endpunkten/Blättern kein weiterer Zug mehr möglich ist? Die dürften bei
diesem Spiel aber nur einen äußerst überschaubaren Bruchteil der
Teilbäume ausmachen...

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Wanja Gayk
Der Overhead vom Exceptionhandling ist jedenfalls in 99.9999999999999%
aller Fälle kein Problem.

Ich habe visualvm dann mal eingesetzt. Mann, habe ich gelacht. Je
nachdem, ob ich dem Profiler oder dem Sampler glaube, verbringe ich
65–95% der Rechenzeit im Konstruktor von drei verschiedenen Exceptions,
wobei zwei etwa gleich viel Zeit brauchen und die dritte ein Viertel
davon. Und es sieht so aus, dass es tatsächlich die Aufrufe sind und
weder super(String) noch die Erstellung des String.

Die Exceptions werden bei der Überprüfung eines Zugs auf Legalität
geworfen. Das betrifft hauptsächlich Züge in ein volles Glas und Züge
auf einen Platz mit falschfarbigem Untermann, z.T. auch Züge mit
gleichem Start und Ziel. Hm. Mal schauen, was sich da in der
Zuggenerierung abfangen lässt.

lg
QNo

[Christian H. Kuhn]

Post by Christian H. Kuhn

Post by Wanja Gayk
Der Overhead vom Exceptionhandling ist jedenfalls in 99.9999999999999%
aller Fälle kein Problem.

Ich habe visualvm dann mal eingesetzt. Mann, habe ich gelacht. Je
nachdem, ob ich dem Profiler oder dem Sampler glaube, verbringe ich
65–95% der Rechenzeit im Konstruktor von drei verschiedenen Exceptions,
wobei zwei etwa gleich viel Zeit brauchen und die dritte ein Viertel
davon. Und es sieht so aus, dass es tatsächlich die Aufrufe sind und
weder super(String) noch die Erstellung des String.
Die Exceptions werden bei der Überprüfung eines Zugs auf Legalität
geworfen. Das betrifft hauptsächlich Züge in ein volles Glas und Züge
auf einen Platz mit falschfarbigem Untermann, z.T. auch Züge mit
gleichem Start und Ziel. Hm. Mal schauen, was sich da in der
Zuggenerierung abfangen lässt.

Gigantisch. Alte Version: getMoveList() erzeugt die Liste der erlaubten
Züge, indem alle denkbaren Züge erzeugt und mit isLegalMove() überprüft
werden; in isLegalMove() werden dann die ganzen Exceptions geworfen. Die
erste Stellung aus Level 4 braucht dann 2270765 ms. Stattdessen:
Einhaltung der Größengrenzen ist durch die verschachtelten Schleifen
garantiert; die übrigen Fehlermöglichkeiten stehen als if (x || y || z)
{ continue; } drin. Reduktion auf 98558 ms. Ich bin begeistert.

Jetzt kommt noch der letzte Optimierungsschritt: Ich mache eigentlich
keine Breitensuche, sondern eine definiert abbrechende Tiefensuche. Mal
schauen, was ich da noch rauskitzle.

lg
QNo

[Christoph Schneegans]

Post by Christian H. Kuhn
Ich habe visualvm dann mal eingesetzt. Mann, habe ich gelacht. Je
nachdem, ob ich dem Profiler oder dem Sampler glaube, verbringe ich
65–95% der Rechenzeit im Konstruktor von drei verschiedenen Exceptions,
wobei zwei etwa gleich viel Zeit brauchen und die dritte ein Viertel
davon. Und es sieht so aus, dass es tatsächlich die Aufrufe sind und
weder super(String) noch die Erstellung des String.

java.lang.Throwable.fillInStackTrace() macht typischerweise den
Löwenanteil aus. Wenn man den Stacktrace ohnehin nicht braucht,
erscheint mir sowas völlig legitim:

public class TracelessException
extends Exception
{
private static final long serialVersionUID = -9043029795604539423L;

public TracelessException()
{
super();
}

public TracelessException(final String message)
{
super(message);
}

@Override
@SuppressWarnings("sync-override")
public Throwable fillInStackTrace()
{
return this;
}
}

[Wanja Gayk]

Post by Christian H. Kuhn

Post by Wanja Gayk
Der Overhead vom Exceptionhandling ist jedenfalls in 99.9999999999999%
aller Fälle kein Problem.

Ich habe visualvm dann mal eingesetzt. Mann, habe ich gelacht. Je
nachdem, ob ich dem Profiler oder dem Sampler glaube, verbringe ich
65?95% der Rechenzeit im Konstruktor von drei verschiedenen Exceptions,
wobei zwei etwa gleich viel Zeit brauchen und die dritte ein Viertel
davon. Und es sieht so aus, dass es tatsächlich die Aufrufe sind und
weder super(String) noch die Erstellung des String.

Das klingt ganz danach, als ob du die Exceptions nicht als "Ausnahme"
benutzt, sondern Mittel für den regulären Kontrollfluss. Wenn Exceptions
zur Regel werden, dann passt der Name "Exception" eigentlich nicht mehr.

Was du dort siehst, ist also in etwa so, als ob du ein extra
Rückgabeobjekt mit Stacktrace erzeugst, immer wenn du z.B. kein
Suchergebnis findest. Das ist eigentlich nicht das, wofür man eine
Exception nutzen sollte.

Eine Exception ist eigentlich immer eine Sonderbedingung, Beispiel:
Du hast ein Handelsprogramm, bei dem du checkst, ob die Ware auf Lager
ist und wenn ja, wird es dem Kunden abgeboten, der erteilt dann den
Auftrag die Ware vom Lager zu nehmen und ihm zu schicken. Eine Ausnahme
baust du für den Fall ein, dass zwischen dem Bestandscheck und dem
tatsächlichen Auftrag ein anderer Auftrag dazwischen kam, der die Ware
vom Lager nahm. Damit würde es beim Auftrag eine Art OutOfStockException
geben und du müsstest dem Kunden mitteilen: Sorry, zwischen unserem
Angebot und deinem Auftrag hat ein anderer Kunde das Zeug gekauft und
ihm anbieten das Zeug mit etwas Wartezeit trotzdem zu bestellen oder die
Transaktion abzubrechen.

Aber für so Sachen, wie eine Suche, wo sehr oft zu erwarten ist, dass du
nicht findest, was du suchst, ist eine Exception (Ausnahme!) nicht das
richtige Mittel.
Dort gibt man zum Beispiel sowas, wie ein "Optional" zurück, also:
public <X extends NamedItem> Optional<X> searchByName(Iterable<X> xs,
String name){
for(X x : xs){
if(x != null && Utils.equals(x.getName(), name)){
return Optional.of(x);
}
}
return Optional.empty();
}

Oder eben, wenn man den Konstruktor des Optionals umgehen muss, das
Objekt selbst oder null.

Gruß,
-Wanja-

[Christian H. Kuhn]

Post by Wanja Gayk
Das klingt ganz danach, als ob du die Exceptions nicht als "Ausnahme"
benutzt, sondern Mittel für den regulären Kontrollfluss.

Jain. Der Grundgedanke ist schon der, dass Methoden mit korrekten
Parametern aufgerufen werden; es sollte der Ausnahmefall sein, wenn das
nicht passiert, und dann gibt es halt eine Exception zurück, die auch
genau beschreibt, was los ist.

In getMoveList() habe ich es dann übertrieben: Ich habe alle
kombinatorisch möglichen Züge erzeugt und dann Exceptions werfen lassen.
DAS war ein Mißbrauch des Mechanismus.

Aktuell erzeuge ich nur erlaubte Züge in getMoveList(). Weil die
Schnittstelle erlaubt, dass auch irgendwo Züge als Parameter übergeben
werden, die nicht aus einer mit getMoveList() erzeugten Liste stammen,
muss ich weiterhin eine Überprüfung von auszuführenden Zügen machen, und
die arbeitet weiter mit Exceptions. Was mir gar nicht gefällt: Ich habe
die Legalität an zwei Stellen codiert, die ich bei Änderungen beide
anpassen muss.

Alternativen zum Exception-Mechanismus gefallen mir alle nicht. Rückgabe
boolean ist zu vage, da kann man nicht spezifizieren, was los ist.
Rückgabe int (mit darin codierten Flags) ist C-Style, sowas von
Achtziger und semantisch in komplexen Situationen nicht immer zu
durchschauen, weil das Prinzip der Kapselung verletzt ist.

Post by Wanja Gayk
Dort gibt man zum Beispiel sowas, wie ein "Optional" zurück,

Das kannte ich noch nicht, das schaue ich mir an.

Post by Wanja Gayk
Oder eben, wenn man den Konstruktor des Optionals umgehen muss, das
Objekt selbst oder null.

Das bringt auch nicht mehr Information als boolean.

lg
Christian

[Stefan Ram]

Post by Christian H. Kuhn
Alternativen zum Exception-Mechanismus gefallen mir alle nicht. Rückgabe
boolean ist zu vage, da kann man nicht spezifizieren, was los ist.
Rückgabe int (mit darin codierten Flags) ist C-Style, sowas von
Achtziger und semantisch in komplexen Situationen nicht immer zu
durchschauen, weil das Prinzip der Kapselung verletzt ist.

»Structure and Interpretation of Computer Programs« stammt
von 1985 und nimmt vieles voraus, was jetzt langsam beim
Programmieren zum Mainstream wird. Ich sehe gerade ein Video
von 1986, wo Jay Sussman Streams (à la »java.util.streams)
und das Wiring von Objekte erklärt. Etwas als »Achtziger« zu
kritisieren ist also unsachlich.

Du mußt Ausnahme nicht werfen, sondern kannst sie auch zurückgeben:

java.lang.Exception toReciprocal()
{ if( this.getDouble() != 0 ){ this.set( 1 / this.getDouble() ); return null; }
else return new DivisionByZeroException( this.getDouble() ); }
¯¯¯¯¯¯
oder auch andere beliebig komplexe Objekte, welche den
aufgetretenen Fehler beschreiben.

Aber bei so einem relativ kleinen Programm braucht man nicht
die Architektur einer Millionen-Zeilen-Anwendung mit voll
entkoppelten Bibliotheken. Daher wären hier für mich auch
enum-Werte als Fehlerrückgabe in Ordnung. Wichtig ist es
immer, alles stets gut mit JavaDoc-Kommentaren zu dokumentieren,
insbesondere auch die Vorbedingungen bei Werten von Argumenten.

[Patrick Roemer]

Post by Stefan Ram
java.lang.Exception toReciprocal()
{ if( this.getDouble() != 0 ){ this.set( 1 / this.getDouble() ); return null; }
else return new DivisionByZeroException( this.getDouble() ); }
¯¯¯¯¯¯

Gibt es eigentlich einen Fachausdruck für sachlich korrekten Unfug? :)

Viele Grüße,
Patrick

[Wanja Gayk]

Post by Patrick Roemer

Post by Stefan Ram
java.lang.Exception toReciprocal()
{ if( this.getDouble() != 0 ){ this.set( 1 / this.getDouble() ); return null; }
else return new DivisionByZeroException( this.getDouble() ); }
¯¯¯¯¯¯

Gibt es eigentlich einen Fachausdruck für sachlich korrekten Unfug? :)

Wenn er funktioniert: Hack.
Wenn er sinnfrei ist: WTF ( Kandidat für: http://thedailywtf.com/ )

Gruß,
-Wanja-

[Patrick Roemer]

Post by Christian H. Kuhn
Aktuell erzeuge ich nur erlaubte Züge in getMoveList(). Weil die
Schnittstelle erlaubt, dass auch irgendwo Züge als Parameter übergeben
werden, die nicht aus einer mit getMoveList() erzeugten Liste stammen,
muss ich weiterhin eine Überprüfung von auszuführenden Zügen machen, und
die arbeitet weiter mit Exceptions.

Das ist ja auch völlig legitim.

Post by Christian H. Kuhn
Was mir gar nicht gefällt: Ich habe
die Legalität an zwei Stellen codiert, die ich bei Änderungen beide
anpassen muss.

Wenn das in beiden Fällen ähnlicher Code sein sollte, ist das in der Tat
ein Designfehler, der sich leicht beheben lassen sollte.

Falls Du damit meinst, dass Du einmal "synthetischen" Code hast (in
#getMoveList(), wo die Regeln implizit im Code sind, der die gültigen
Züge erzeugt) und einmal "analytischen" (zum Prüfen der externen
Eingaben, wo die Regeln explizit in Form von if/throw-Validierungen
vorliegen) - das wird sich wohl kaum mit vertretbarem Aufwand vermeiden
lassen und ist eigentlich gut verargumentierbar: Das eine ist die
Implementierung eines Spielers, das andere die Implementierung des Spiels.

Aber die Regeln an sich dürften sich ja eher selten ändern. Und dass man
beide Stellen anpacken muss, wenn man z.B. eine andere
Datenrepräsentation wählt - tough luck. Aber auch das sollte ja nicht
ständig passieren.

Viele Grüße,
Patrick

[Patrick Roemer]

[...]

Post by Christian H. Kuhn
Also erstmal versucht, das kleinstmögliche Szenario zu finden. Und
dabei festgestellt, dass der Rekursionsbaum bei sonst gleichbleibenden
Bedingungen exponentiell mit der Anzahl der leeren Reagenzgläser
wächst.

Das klingt so, als könntest Du den Suchraum verkleinern, indem Du Dein
Modell so umstellst, dass es Gläser gleichen Inhalts zu einem möglichen
Bearbeitungsschritt zusammenfasst.

Also statt

[[a,b], [a,b], [b,a], [], []]
=> move b to empty
[[b], [a,b], [b,a], [a], []]

sowas wie

{[a,b] -> 2, [b,a] -> 1, [] -> 2}
=> move b to empty
{[a] -> 1, [b] -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Post by Christian H. Kuhn
Ich hatte keine nicht abbrechende Rekursion, ich habe
lediglich die Rechenzeit massiv unterschätzt. Tage statt Minuten. Ich
werde also einen anderen Ansatz verwenden müssen, der den Suchbaum
Stufe für Stufe aufbaut und auf Lösungen überprüft, bevor die nächste
Stufe berechnet wird.

Das wäre äußerst sinnvoll. :) Breitensuche statt Tiefensuche, und die
erste gefundene Lösung zurückgeben, die ist dann schon kürzestmöglich.

Ggfs. könnte man dann noch Heuristiken anwenden, um auf jeder Stufe die
"erfolgversprechendsten" Spielstände und -züge jeweils zuerst
auszuprobieren.

Post by Christian H. Kuhn

Post by Patrick Roemer
Zumindest wäre es sinnvoll, ein paar funktionierende Testfälle
beizulegen, und einen, der das Problem demonstriert.

Sind in LSBoard.main().

Hmnaja... Anhand Deiner initialen Beschreibung hätte ich erwartet, dass
die schon in einzelne Unit-Tests gegossen sind.

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer
Also statt
[[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
[b,a], [a], []]
sowas wie
{[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
-> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Ich hab inzwischen sowas ähnliches gemacht, aber ganz anders ;-) Ich
habe die Hashcode-Berechnung geändert. (a,b), (b,a), (), () hat jetzt
den gleichen Hashcode wie (), (b,a), (), (a,b). Das hat für die
Testfälle mit zwei Farben und zwei Bewohnern pro Glas die Rechenzeiten
in erträgliche Dimensionen gebracht. Für reelle Berechnungen reicht es
leider noch nicht.

lg
QNo

[Patrick Roemer]

Post by Christian H. Kuhn

Post by Patrick Roemer
Also statt
[[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
[b,a], [a], []]
sowas wie
{[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
-> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Das sollte natürlich jeweils "move a to empty" heissen. m(

Post by Christian H. Kuhn
Ich hab inzwischen sowas ähnliches gemacht, aber ganz anders ;-) Ich
habe die Hashcode-Berechnung geändert. (a,b), (b,a), (), () hat jetzt
den gleichen Hashcode wie (), (b,a), (), (a,b). Das hat für die
Testfälle mit zwei Farben und zwei Bewohnern pro Glas die Rechenzeiten
in erträgliche Dimensionen gebracht. Für reelle Berechnungen reicht es
leider noch nicht.

Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
ausprobieren. :)

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer

Post by Patrick Roemer
Also statt
[[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
[b,a], [a], []]
sowas wie
{[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
-> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
ausprobieren. :)

Hab ich dann auch mal ausprobiert, aber anders.

public final Vector<LSMove> getMoveList() {
Vector<LSMove> moveList = new Vector<LSMove>();
HashSet<Integer> startTubes = new HashSet<Integer>();
for (int i = 0; i < boardSize; i++) {
if (startTubes.contains(tubes.get(i).hashCode())) {
continue;
}
startTubes.add(tubes.get(i).hashCode());
HashSet<Integer> targetTubes = new HashSet<Integer>();
for (int j = 0; j < boardSize; j++) {
if (targetTubes.contains(tubes.get(j).hashCode())) {
continue;
}
targetTubes.add(tubes.get(j).hashCode());
LSMove move = new LSMove(i, j);
try {
isLegalMove(move);
moveList.add(move);
} catch (LSBoardBadSizeParameterException |
LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
| LSBoardFullTargetTubeException |
LSBoardDifferentColoursException e) {
// illegale Züge werden einfach nicht geaddet, keine
weitere Aktion nötig.
}
}
}
return moveList;
}

Mit erstaunlichen Ergebnissen:

public static void main(final String[] _args) throws Throwable {

// Ohne Zugreduzierung: 499 ms, mit 864 ms.
// LSBoard board = new LSBoard(4, 3, 2);
// Vector<Vector<Character>> positionOneLevelOne = new
Vector<Vector<Character>>(
// Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'c', 'b')),
// new Vector<Character>(Arrays.asList('a', 'a', 'c', 'c')),
// new Vector<Character>(Arrays.asList('c', 'a', 'b', 'b'))));

// Ohne Zugreduzierung: 39 ms, mit 33 ms.
// LSBoard board = new LSBoard(3, 2, 2);
// Vector<Vector<Character>> positionOne = new
Vector<Vector<Character>>(
// Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a')),
// new Vector<Character>(Arrays.asList('a', 'b', 'b'))));

// Ohne Zugreduzierung: 231 ms, mit 340 ms.
// LSBoard board = new LSBoard(4, 4, 1);
// Vector<Vector<Character>> positionTwentyLevelTwo = new
Vector<Vector<Character>>(
// Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a', 'c')),
// new Vector<Character>(Arrays.asList('c', 'd', 'c', 'd')),
// new Vector<Character>(Arrays.asList('a', 'b', 'b', 'd')),
// new Vector<Character>(Arrays.asList('a', 'b', 'c', 'd'))));

// Ohne Zugreduzierung: 2496251 ms, mit 2270765 ms.
LSBoard board = new LSBoard(4, 10, 2);
Vector<Vector<Character>> positionOneLevelFour = new
Vector<Vector<Character>>(
Arrays.asList(new Vector<Character>(Arrays.asList('a',
'b', 'c', 'd')),
new Vector<Character>(Arrays.asList('b', 'c',
'e', 'f')),
new Vector<Character>(Arrays.asList('f', 'g',
'e', 'h')),
new Vector<Character>(Arrays.asList('h', 'c',
'g', 'e')),
new Vector<Character>(Arrays.asList('b', 'h',
'i', 'g')),
new Vector<Character>(Arrays.asList('a', 'd',
'd', 'i')),
new Vector<Character>(Arrays.asList('f', 'a',
'i', 'j')),
new Vector<Character>(Arrays.asList('i', 'j',
'b', 'g')),
new Vector<Character>(Arrays.asList('j', 'e',
'a', 'j')),
new Vector<Character>(Arrays.asList('h', 'f',
'c', 'd'))));

board.initializeBoard(positionOneLevelFour);
long startTime = System.nanoTime();
LSResult result = board.result();
long endTime = System.nanoTime();
long elapsedTime = (endTime - startTime) / 1000000;

System.out.println("Lösung:");
for (LSMove move : result.getOneShortestSolution()) {
System.out.println(move.toString());
}
System.out.printf("Zeit: %1$d ms", elapsedTime);
}

Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
als der größere Baum.

lg
QNo

[Patrick Roemer]

Post by Christian H. Kuhn

Post by Patrick Roemer

Post by Patrick Roemer
Also statt
[[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
[b,a], [a], []]
sowas wie
{[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
-> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
ausprobieren. :)

Hab ich dann auch mal ausprobiert, aber anders.

Das "anders" ist wahrscheinlich das Problem. ;) s.u.

Post by Christian H. Kuhn
public final Vector<LSMove> getMoveList() {
Vector<LSMove> moveList = new Vector<LSMove>();
HashSet<Integer> startTubes = new HashSet<Integer>();
for (int i = 0; i < boardSize; i++) {
if (startTubes.contains(tubes.get(i).hashCode())) {
continue;
}
startTubes.add(tubes.get(i).hashCode());
HashSet<Integer> targetTubes = new HashSet<Integer>();
for (int j = 0; j < boardSize; j++) {
if (targetTubes.contains(tubes.get(j).hashCode())) {
continue;
}
targetTubes.add(tubes.get(j).hashCode());
LSMove move = new LSMove(i, j);
try {
isLegalMove(move);
moveList.add(move);
} catch (LSBoardBadSizeParameterException |
LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
| LSBoardFullTargetTubeException |
LSBoardDifferentColoursException e) {
// illegale Züge werden einfach nicht geaddet, keine
weitere Aktion nötig.
}
}
}
return moveList;
}

Dass die Exceptions hier sowohl semantisch als auch von der Performance
her eher fehl am Platz sind, hast Du ja anderweitig schon festgestellt. :)

if(isLegalMove(move)) {
moveList.add(move);
}

(Bzw. erst gar keine illegalen Züge generieren.)

Das hashCode-Gewerkel finde ich weiterhin äußerst fishy...

Post by Christian H. Kuhn
Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
als der größere Baum.

Gemeint war auch nicht, in jedem Einzelschritt umzukopieren, sondern
durchgehend auf einem Modell a la Map<List<Character>, Integer> zu arbeiten.

Anyway, solange der Algorithmus an sich suboptimal ist, sind Experimente
auf dieser Ebene eher unangebracht. Bau halt mal auf echte Breitensuche
um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.
Danach kann man immer noch weiter optimieren.

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer
Bau halt mal auf echte Breitensuche
um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.

Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
in die Queue getan. While bricht ab, wenn die Queue leer ist.

In der While-Schleife wird die Stellung und die bisherige Zugliste aus
der Queue entnommen. Wenn die Stellung eine Lösung ist, wird ein
Lösungsobjekt aus der Zugliste gebildet und zurückgegeben.

Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
weitergezählt.

Ansonsten wird bigHashCode() zur Liste der gesehenen Stellungen
zugefügt. Es wird die Liste der möglichen Züge ermittelt. Aus der
aktuellen Position werden die Positionen der nächsten Tiefe und die dazu
führenden Zuglisten erzeugt und in die Queue getan.

Massiver Rückgang der Rechenzeit. Beispiele:

(Jeweils: 1. Levelweise Tiefensuche, Zugerzeugung incl. illegaler Züge,
Prüfung auf legal bei Ausführung. 2. dto, Zugerzeugung erzeugt nur
legale Züge. 3. Breitensuche mit FIFO)

(a, b, a) (a, b, b), zwei leere Gläser. 1. 39 ms, 2. 28 ms, 3. 12 ms.

Erste Stellung Level 1:
(a, b, c, b) (a, a, c, c) (c, a, b, b), zwei leere Gläser. 1. 499 ms, 3.
67 ms.

Stellung 20 Level 2:
(a, b, a, c), (c, d, c, d) (a, b, b, d) (a, b, c, d), ein leeres Glas.
1. 231 ms, 2. 340 ms, 3. 35 ms.

Stellung 1 Level 4:
(a, b, c, d) (b, c, e, f) (f, g, e, h) (h, c, g, e) (b, h, i, g) (a, d,
d, i) (f, a, i, j) (i, j, b, g) (j, e, a, j) (h, f, c, d), zwei leere
Gläser. 1. 2270765 ms, 2. 105984 ms, 3. 4261 ms.

Ich danke an der Stelle nochmals allen, die sich beteiligt haben. Ich
habe durch eure Beiträge viel gelernt. Im nächsten Semester werde ich im
Master wohl „Effiziente Graphenalgorithmen“ hören und die Problematik in
dem Zusammenhang nochmal aufgreifen. Vielleicht wird ein kleiner Artikel
daraus.

lg
QNo

[Patrick Roemer]

Post by Christian H. Kuhn

Post by Patrick Roemer
Bau halt mal auf echte Breitensuche
um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.

Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
in die Queue getan. While bricht ab, wenn die Queue leer ist.

Genau. :)
[...]

Post by Christian H. Kuhn
(a, b, c, d) (b, c, e, f) (f, g, e, h) (h, c, g, e) (b, h, i, g) (a, d,
d, i) (f, a, i, j) (i, j, b, g) (j, e, a, j) (h, f, c, d), zwei leere
Gläser. 1. 2270765 ms, 2. 105984 ms, 3. 4261 ms.

Das sieht doch gut aus. Da dürfte immer noch Luft drin sein, aber nicht
mehr in der Größenordnung, die man durch die Algorithmenwahl erreicht.
*Jetzt* wäre der Punkt, wo man mal hprof/visualvm anwerfen könnte und
anhand der so gefundenen Hotspots low-level-Optimierungen ausprobieren
könnte.

Spontan würde mir einfallen:
- Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
Gläser zusammengefasst werden.
- Vector<Character> durch String ersetzen.
- Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.
- Vector durch ArrayList ersetzen.

Keine Ahnung, ob und wieviel das jeweils bringt, da muss man dann
wirklich im Vergleich messen. Zumindest bei den ersten beiden wäre ich
aber zuversichtlich.

Ausserdem würde ich das explizite Gewerkel mit dem Hashcode und das
Cloning auf den Prüfstand stellen. IMHO leidet die Codeverständlichkeit
darunter, es bietet Raum für zusätzliche Fehlerquellen, und vom
Bauchgefühl her würde ich da keinen Gewinn von erwarten - zumindest
keinen signifikanten. Ich würde anstelle des "bigHashCode" die
eigentlichen Objekte mit "normalem" #equals() und #hashCode() verwenden,
und den copy constructor statt des #clone().

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer
- Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
Gläser zusammengefasst werden.

Geht halt nicht unbeschränkt. (a,a,a) () ist zwar ideell dasselbe wie ()
(a,a,a), sieht aber anders aus. Das sind auf dem Screen zwei
verschiedene Stellungen. Wenn ich die einheitlich repräsentiere, brauche
ich nicht nur einen Algorithmus, der die tatsächliche Stellung in die
vereinfachte überführt, sondern auch einen, der sie dann incl. Lösung
zurücküberführt. Selbst Chessbase, bei denen Jahrzehnte an Entwicklung
und viel Geld dahinter stehen, hatten neulich noch einen Bug drin: Eine
Stellung ist durch eigenartiges Spiel mit vertauschten Farben
entstanden, Schwarz am Zug, bei „regulärem“ Verlauf wäre Weiß am Zug.
Chessbase hat die Identität der Stellung erkannt, aber die Lösung nicht
transformiert. Züge wurden angegeben, als sei Weiß am Zug. Irritierend.

Post by Patrick Roemer
- Vector<Character> durch String ersetzen.

Ich dachte, veränderliche Dinge sind durch konstante Strings schlecht
repräsentiert?

Post by Patrick Roemer
- Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.

In der Breitensuche sicher sinnvoll. Da wird man aber aufpassen müssen,
dass man nicht soviel Optimierungslogik erzeugt, dass die Optimierung
aufwändiger als die Lösung ist :-)

Post by Patrick Roemer
- Vector durch ArrayList ersetzen.

Das hatte ich mir schon mal vorgenommen, mich in die Details einzulesen,
wann welche Liste/Vector besser ist.

Post by Patrick Roemer
Ausserdem würde ich das explizite Gewerkel mit dem Hashcode und das
Cloning auf den Prüfstand stellen. IMHO leidet die Codeverständlichkeit
darunter, es bietet Raum für zusätzliche Fehlerquellen, und vom
Bauchgefühl her würde ich da keinen Gewinn von erwarten - zumindest
keinen signifikanten. Ich würde anstelle des "bigHashCode" die
eigentlichen Objekte mit "normalem" #equals() und #hashCode() verwenden,
und den copy constructor statt des #clone().

Ich habe das mal ausprobiert, dass ich keine HashSet<BigInteger>,
sondern wirklich eine HashSet<LSBoard> verwende. Erster Durchlauf:
Katastrophe. War im Nachhinein auch klar, denn in bigHashCode() bekommen
unterschiedliche, aber äquivalente Stellungen den gleichen Hashcode,
während bislang equals() wirklich nur identische Stellungen als gleich
erkennt, aber keine Permutationen.

Also equals() angepasst. Um das eindeutig zu bekommen, müssen die LSTube
irgendwie eindeutig sortiert werden. Also muss LSTube jetzt Comparable
implementieren. Für LSTube#compareTo(LSTube) ist mir im Moment noch
nichts besseres eingefallen als das Vergleichen von int hashCode(). Mit
dem Ergebnis, dass ich mich jetzt insgesamt 95% der Rechenzeit in
LSBoard#equals() und LSTube#hashCode() aufhalte. Rechenzeitzunahmen
bislang zwischen 50 und 1500%. Ineffektiv bei der aktuellen
Datenrepräsentation. Ohne grundlegende Änderungen ist der status quo
wohl das beste erreichbare Ergebnis. Und es ist praxistauglich.

Die nächste Idee ist, die Gläser statt eines Vector<Character> durch ein
Bitfeld zu repräsentieren. Mit 31 Farben sollte ich gut hinkommen, das
wären 5 bit, max. 4 Plätze macht 20 bit, das ist gut in ein int
reinzupacken. hashCode() ist dann nur ein Getter für den int. Ich suche
noch effiziente Algorithmen für Stackoperationen auf einem Bitfeld.

Dann denke ich doch nochmal über deine Art nach, Züge zu repräsentieren.
Die beschreibt Reagenzgläser nicht durch ihren Platz, sondern durch
ihren Inhalt. Und du hast völlig recht, dass das bei der Zuggeneration
Zeit spart. Es ist halt „ausgabeunfreundlich“. Im Prinzip sind die
Gläser dann nicht in einer Liste o.ä., sondern in einer Menge. Wenn ich
da mal ne GUI drüberlege, brauche ich noch eine Liste, in der
festgehalten ist, welches Glas auf welchem Platz steht. Das wird
vermutlich in dem Moment lustig, in dem von zwei Gläser gleichen Inhalts
sich mindestens eins verändert ((a,a) (a,a) -> (a) (a,a,a)). Und ich
brauche eine Zuordnung des Zuges (a,a)->(a,a) zu den graphischen
Objekten. Lösbar; die Frage ist halt die nach der Effizienz.

Mit soviel Lerneffekt hatte ich gar nicht gerechnet, als ich angefangen
habe. Und mit Stefan Rams Ansatz, der offensichtlich in nochmal deutlich
kürzerer Zeit eine, aber nicht unbedingt die kürzeste Lösung findet,
habe ich mich noch gar nicht beschäftigt.

Ach ja, die eigentlichen Lerninhalte haben funktioniert: Ich lernte,
dass beim Refactoring eine umfangreiche Suite von Unit-Tests unendlich
hilfreich ist; dass 100% Code-Abdeckung durch Tests kein Fetisch ist;
dass checkstyle mit der gleichen Regeldatei in unterschiedlichen
Umgebungen seltsamerweise unterschiedliche Ergebnisse bringt; und dass
Maven und Jenkins jetzt laufen :-)

Und daher wende ich mich jetzt aktuelleren Aufgaben zu. Der Thread ist
gebookmarked, irgendwann im Wintersemester greife ich das wieder auf.

lg
QNo

[Patrick Roemer]

Responding to Christian H. Kuhn:

Da Du mit Deinem Projekt soweit erst mal zufrieden scheinst, nur in Kürze...

Post by Christian H. Kuhn

Post by Patrick Roemer
- Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
Gläser zusammengefasst werden.

Geht halt nicht unbeschränkt. (a,a,a) () ist zwar ideell dasselbe wie ()
(a,a,a), sieht aber anders aus. Das sind auf dem Screen zwei
verschiedene Stellungen. Wenn ich die einheitlich repräsentiere, brauche
ich nicht nur einen Algorithmus, der die tatsächliche Stellung in die
vereinfachte überführt, sondern auch einen, der sie dann incl. Lösung
zurücküberführt.

Unterschiedliche Repräsentationen: List für Game/UI, Map für Solver.

Hin: Trivial.
Zurück: Replay der Resultatzugliste auf der List, bei gleichbelegten
Gläsern irgendeins davon wählen.

Post by Christian H. Kuhn

Post by Patrick Roemer
- Vector<Character> durch String ersetzen.

Ich dachte, veränderliche Dinge sind durch konstante Strings schlecht
repräsentiert?

Konzeptuell ist da nix veränderlich - eine Stellung und ein Zug
spezifizieren eine andere Stellung.

Auf Implementierungsebene hast Du Vectors mit geboxten Chars, klonst
mühsam alle und modifizierst dann zwei davon. Alternativ könntest Du
alle Stringreferenzen einfach kopieren und dann zwei neue Strings
erzeugen. Was klingt effizienter?

Post by Christian H. Kuhn
Ich habe das mal ausprobiert, dass ich keine HashSet<BigInteger>,
Katastrophe. War im Nachhinein auch klar, denn in bigHashCode() bekommen
unterschiedliche, aber äquivalente Stellungen den gleichen Hashcode,
während bislang equals() wirklich nur identische Stellungen als gleich
erkennt, aber keine Permutationen.

Eventuell ein Zeichen dafür, dass Du für den Solver eine andere
Repräsentation willst - eine, deren #equals()/#hashCode() Du in
#bigHashCode() quasi schon implementiert hast.

Post by Christian H. Kuhn
Ach ja, die eigentlichen Lerninhalte haben funktioniert: Ich lernte,
dass beim Refactoring eine umfangreiche Suite von Unit-Tests unendlich
hilfreich ist; dass 100% Code-Abdeckung durch Tests kein Fetisch ist;
dass checkstyle mit der gleichen Regeldatei in unterschiedlichen
Umgebungen seltsamerweise unterschiedliche Ergebnisse bringt; und dass
Maven und Jenkins jetzt laufen :-)

Das klingt doch nach einer Erfolgsgeschichte. :)

Viele Grüße,
Patrick

[Patrick Roemer]

Responding to Christian H. Kuhn:

Jetzt habe ich auch noch mal sinnentnehmend gelesen. ;)

Post by Christian H. Kuhn
Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
in die Queue getan. While bricht ab, wenn die Queue leer ist.
In der While-Schleife wird die Stellung und die bisherige Zugliste aus
der Queue entnommen. Wenn die Stellung eine Lösung ist, wird ein
Lösungsobjekt aus der Zugliste gebildet und zurückgegeben.

Ob eine Stellung eine Lösung ist, kann man doch schon prüfen, bevor man
sie in die Queue einreiht (und sie im Erfolgsfall direkt zurückgeben).

Post by Christian H. Kuhn
Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
weitergezählt.

Dito: Gesehene Stellungen würde ich vor dem Anhängen an die Queue
rausfiltern. ("Gesehen" bedeutet dann: Ist (oder war schon mal) in der
Queue. Man würde also die neu an die Queue angehängten Kandidaten direkt
in das Set der "gesehenen" Stellungen aufnehmen.)

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer

Post by Christian H. Kuhn
Wenn die Stellung bereits gesehen wurde, wird die While-Schleife
weitergezählt.

Done. 1% schneller.

Post by Patrick Roemer
Dito: Gesehene Stellungen würde ich vor dem Anhängen an die Queue
rausfiltern. ("Gesehen" bedeutet dann: Ist (oder war schon mal) in der
Queue. Man würde also die neu an die Queue angehängten Kandidaten direkt
in das Set der "gesehenen" Stellungen aufnehmen.)

Hatte ich schon drin. Hatte mich unklar ausgedrückt.

lg
QNo

[Stefan Ram]

...

Post by Christian H. Kuhn
steht unter keiner Lizenz (jedenfalls wüsste ich nichts)

Es dürfte sich hierbei um eine stillschweigende Lizenzierung
handeln, welche es dem Leser zumindest erlauben sollte, den
Code während der Diskussion abzurufen, zu speichern, zu
bearbeiten und zu starten.

Allerdings beschäftige ich mich bevorzugt mit kleinen
kompilierbaren Programmen, die im Quelltext in diese
Newsgroup gepostet werden. Ich gehe persönlich also
nicht so gerne auf Web-Seiten.

Aber vielleicht hilft Dir ein Vergleich mit meinem Quellcode
weiter. Auf der folgenden Web-Seite habe ich ein Programm
veröffentlicht, das »Drei gewinnt« (»Tic-Tac-Toe«) rekursiv
spielt:

http://www.purl.org/stefan_ram/pub/tictactoe_java

(bei 403 mit Google auf die Seite gehen).

Ich muß sagen, daß es mir jetzt doch deutlich schwerer
fällt, meinen Code zu lesen als zu der Zeit, zu der ich ihn
geschrieben habe. Vielleicht ist dies ein Argument /für/
Dokumentation!

Die Rekursion findet in meiner KI bei »playonce« statt, das
versuchsweise einen Zug macht, und dann »playonce« aufruft,
um zu evaluieren, wie gut dieser ist. Die Rekursion endet
bei mir, wenn ein Gewinner feststeht (»winner != null«) oder
kein Platz auf dem Spielbrett mehr frei ist (»b.full()«).

Dabei wird bei jeder neuen Rekursionstiefe von »playonce«
die Perspektive gewechselt, um auch die Züge des Gegners zu
spielen. Daher ist es in dem untenstehenden Pseudocode
nötig das /Negative/ der Bewertung des nächsten Zuges
zu verwenden, weil diese aus der Sicht des /Gegners/ erfolgt.

Dies könnte man als einen »brute-force« Algorithmus
klassifizieren, der alle Spielmöglichkeiten des Spielers
und des Gegners durchspielt, um dann alle Stellungen
bewerten zu können.

Mein Rekursionsschema sieht also so aus:

Bewerte einen Zug:
wenn kein Zug mehr moeglich, dann
Ergebnis = Bewertung der jetzigen Stellung
sonst
für alle Möglichkeiten für den nächsten Zug:
mache diesen nächsten Zug versuchsweise
Ermittle seine Bewertung (durch Rekursion)
Ergebnis = das Negative der Zusammenfassung der Bewertungen

Dabei ist es für die Beendigung der Rekursion wichtig,
daß es einen Spielzustand gibt, bei dem kein weiterer
Zug mehr möglich ist, dieser nach endlich vielen Zügen
erreicht wird, und jede neue Rekursionstiefe einen
Schritt in die Richtung zu jenem Endzustand geht.

Man muß sich auch überlegen, welche Variablen für mehrere
Rekursionstiefen geteilt werden können und welche bei
jeder Rekursion neu anzulegen sind. Im Zweifelsfalle
sollte man alle veränderbaren Zustände bei jeder Rekursion,
bei der sie verändert werden könnten, erst einmal
als Kopie der vorigen Zustände neu anlegen und dann am
Ende des Rekursionsschritts sicherstellen, daß der
vorige Zustand wiederhergestellt ist.

Nun, dieser Code von mir ist bei weitem nicht perfekt,
ich habe ihn ja damals in kurzer Zeit geschrieben und
ich habe noch eine große Aufgabenliste, was ich daran
noch alles verbessern will, wozu ich aber noch nicht
gekommen bin. Aber die Rekursion hat bis jetzt jedenfalls
immer terminiert.

[Volker Borchert]

Post by Stefan Ram
Dabei wird bei jeder neuen Rekursionstiefe von »playonce«
die Perspektive gewechselt, um auch die Züge des Gegners zu
spielen. Daher ist es in dem untenstehenden Pseudocode
nötig das /Negative/ der Bewertung des nächsten Zuges
zu verwenden, weil diese aus der Sicht des /Gegners/ erfolgt.

Klassisches MINIMAX-Verfahren also.

Post by Stefan Ram
Man muß sich auch überlegen, welche Variablen für mehrere
Rekursionstiefen geteilt werden können und welche bei
jeder Rekursion neu anzulegen sind. Im Zweifelsfalle
sollte man alle veränderbaren Zustände bei jeder Rekursion,
bei der sie verändert werden könnten, erst einmal
als Kopie der vorigen Zustände neu anlegen und dann am
Ende des Rekursionsschritts sicherstellen, daß der
vorige Zustand wiederhergestellt ist.

In C++ z.B. trivial durch pass by value mit geeignetem copy ctor

[Christian H. Kuhn]

Post by Stefan Ram
http://www.purl.org/stefan_ram/pub/tictactoe_java

Danke, schaue ich mir die Tage mal in Ruhe an.

mfg
QNo

[Patrick Roemer]

Post by Christian H. Kuhn
Oder die hashCode-Funktion
für die Stellungen taugt nix. Den Verdacht hatte ich eh, aber eher in
die andere Richtung: dass ich für eine neue Stellung den gleichen hash
habe wie für eine bisherige und deshalb Lösungen nicht finde. Ideal
wäre eine bijektive hash-Funktion, die aber den Zahlenraum int nicht
sprengt ...

Ich habe mir gerade spasseshalber mal das Demovideo für das Spielchen
angeschaut. Wenn ich mich nicht verzählt habe, bringen die da ein
Beispiel mit 15 Gläsern zu je 4 "Bewohnern" und 10 Farben. Ich bin nicht
fit genug in Stochastik, um da ad hoc eine sinnvolle Obergrenze für
auszurechnen, aber vom Bauchgefühl her: Kannst Du knicken.

Ich vermute mal, dass Du eh eine Art Breitensuche machen müssen wirst.
Da hast Du zwangsweise schon größere Mengen an Kandidatenzuständen im
Speicher. Ich würde die "bereits gesehenen" Zustände in einem echten
HashSet halten (natürlich mit sinnvoller #hashCode-Implementierung, aber
eben mit #equals-Vergleich bei Übereinstimmung), und Optimierungsenergie
lieber erst mal darauf verwenden, den Suchraum zu minimieren.

Code sollte zunächst mal korrekt sein, und dann erst performant. Wenn Du
Gefahr läufst, eine Lösung nicht zu finden, weil es in einer Sackgasse
vorher mal den selben Hashcode gab, läuft was schief.

Viele Grüße,
Patrick

[Christian H. Kuhn]

[...] eine sinnvolle Obergrenze [...] Kannst Du knicken.

Inzwischen: ACK. Das ist aber kein Grund, es nicht doch zu optimieren :-)

Ich vermute mal, dass Du eh eine Art Breitensuche machen müssen
wirst. Da hast Du zwangsweise schon größere Mengen an
Kandidatenzuständen im Speicher. Ich würde die "bereits gesehenen"
Zustände in einem echten HashSet halten (natürlich mit sinnvoller
#hashCode-Implementierung, aber eben mit #equals-Vergleich bei
Übereinstimmung), und Optimierungsenergie lieber erst mal darauf
verwenden, den Suchraum zu minimieren.

Siehe <***@mid.individual.net>.

Wobei du mich noch auf eine andere Idee bringst: Eine Rekursion darf
tatsächlich auch dann abbrechen, wenn die Stellung bei geringerer
Rechentiefe in einem anderen Zweig des Baumes aufgetaucht ist, nicht
aber, wenn sie im anderen Zweig bei tieferer Suche gefunden wird. Man
könnte statt einem Set eine Map nehmen, bei der zum Hash die
Rechentiefe mit vermerkt wird.

Code sollte zunächst mal korrekt sein, und dann erst performant.
Wenn Du Gefahr läufst, eine Lösung nicht zu finden, weil es in
einer Sackgasse vorher mal den selben Hashcode gab, läuft was
schief.

Das wir die ursprüngliche Befürchtung, für die ich aber in der Praxis
bisher keine Anzeichen habe. Ich habe einen BigInteger bigHashCode()
gewählt, der die Gläser nach fallender Größe ihres Hashcodes
verarbeitet und so allen Permutationen von Gläsern den gleichen Code
verpasst, und solange maximal 16 Farben und Gläser auftauchen und
nicht mehr als 4 Bewohner in ein Glas passen, müsste diese Funktion
bijektiv sein (jedenfalls wenn man Stellungen als identisch definiert,
wenn sie durch Glaspermutation auseinander entstehen). Und damit
sollte diese Fehlerquelle für eine übersehene Lösung wegfallen.

lg
QNo

[Patrick Roemer]

Post by Christian H. Kuhn

[...] eine sinnvolle Obergrenze [...] Kannst Du knicken.

Inzwischen: ACK. Das ist aber kein Grund, es nicht doch zu optimieren :-)

Ich meinte damit: Eine bijektive Abbildung auf int kannst Du knicken. Da
gibt's auch nicht wirklich was dran zu optimieren. :)

Post by Christian H. Kuhn
Wobei du mich noch auf eine andere Idee bringst: Eine Rekursion darf
tatsächlich auch dann abbrechen, wenn die Stellung bei geringerer
Rechentiefe in einem anderen Zweig des Baumes aufgetaucht ist, nicht
aber, wenn sie im anderen Zweig bei tieferer Suche gefunden wird. Man
könnte statt einem Set eine Map nehmen, bei der zum Hash die
Rechentiefe mit vermerkt wird.

Ich halte es einfach für den grundfalschen Ansatz, mit Tiefensuche den
kompletten Zugbaum ablaufen zu wollen. Nimm eine Breitensuche, halte die
Objektrepräsentationen bereits gesehener Stellungen in einem HashSet und
liefere die erste gefundene Lösung zurück. Wenn man bei größeren
Szenarien feststellen sollte, dass durch das HashSet der Speicher
platzt, kann man immer noch schauen, ob und wie man das optimieren kann.

Mit dem Ansatz solltest Du für die einfachen Beispiele aus dem
Trailervideo in den Zehntelsekundenbereich kommen, ganz ohne
Optimierungskapriolen.

Post by Christian H. Kuhn

Code sollte zunächst mal korrekt sein, und dann erst performant.
Wenn Du Gefahr läufst, eine Lösung nicht zu finden, weil es in
einer Sackgasse vorher mal den selben Hashcode gab, läuft was
schief.

Das wir die ursprüngliche Befürchtung, für die ich aber in der Praxis
bisher keine Anzeichen habe.

Wie auch - Du hast ja bisher nur sehr überschaubare Szenarien. Und
Hashkollisionen zeichnen sich üblicherweise dadurch aus, dass sie eher
selten auftreten.

Post by Christian H. Kuhn
Ich habe einen BigInteger bigHashCode()
gewählt, der die Gläser nach fallender Größe ihres Hashcodes
verarbeitet und so allen Permutationen von Gläsern den gleichen Code
verpasst, und solange maximal 16 Farben und Gläser auftauchen und
nicht mehr als 4 Bewohner in ein Glas passen, müsste diese Funktion
bijektiv sein (jedenfalls wenn man Stellungen als identisch definiert,
wenn sie durch Glaspermutation auseinander entstehen). Und damit
sollte diese Fehlerquelle für eine übersehene Lösung wegfallen.

Zum einen verstehe ich nicht recht, wo bei einem BigInteger dann noch
das Limit für die Bijektivität herkommen soll, zum anderen wäre die
Frage, wieviel Speicher man damit im Vergleich zu einer kompakten
Repräsentation eines Glases überhaupt noch spart.

Viele Grüße,
Patrick

[Christian H. Kuhn]

Post by Patrick Roemer
Nimm eine Breitensuche, halte die
Objektrepräsentationen bereits gesehener Stellungen in einem HashSet und
liefere die erste gefundene Lösung zurück. Wenn man bei größeren
Szenarien feststellen sollte, dass durch das HashSet der Speicher
platzt, kann man immer noch schauen, ob und wie man das optimieren kann.
Mit dem Ansatz solltest Du für die einfachen Beispiele aus dem
Trailervideo in den Zehntelsekundenbereich kommen, ganz ohne
Optimierungskapriolen.

Ausprobiert. Stellung: (a,b,c,b), (a,a,c,c), (c,a,b,b), (), (). Das ist
die erste Stellung im einfachsten Level. Die kürzeste Lösung hat 10 Züge.

Erster Ansatz: Wie beim kompletten Baum nur Hashes des aktuellen Zweigs
vorgehalten und verglichen. Lösungszeit 35s.

Zweiter Ansatz: In der Breitensuche muss ich eine Stellung auch dann
nicht mehr prüfen, wenn sie vorher in einem anderen Zweig vorgekommen
ist. Es wird also jede neue Stellung in das HashSet eingetragen.
Lediglich beim Ändern des Suchtiefezählers, nach dem ja von vorne
begonnen wird, wird das HashSet mit den gesehenen Stellungen gelöscht.
Lösungszeit 367ms. Du hast richtig abgeschätzt :-) Jetzt erzeuge ich
immer noch unnötig Stellungen, siehe dein Post mit dem Vorschlag für
andere Zugstruktur. Da muss ich noch drüber nachdenken.

Post by Patrick Roemer
Zum einen verstehe ich nicht recht, wo bei einem BigInteger dann noch
das Limit für die Bijektivität herkommen soll,

Eben. BigInteger garantiert die Bijektivität. Ich will Hashkollisionen
völlig ausschließen.

Post by Patrick Roemer
zum anderen wäre die
Frage, wieviel Speicher man damit im Vergleich zu einer kompakten
Repräsentation eines Glases überhaupt noch spart.

Vermutlich keinen. Der Hash eines Glases besteht aus 4 Bit pro Platz,
jedes Nibble repräsentiert die Belegung eines Platzes von leer bis Farbe
15, aufgefüllt auf 16 Bit. Der Hash einer Stellung multipliziert den
Hash ohne das aktuelle Glas mit 2^16 und addiert den Hash des aktuellen
Glases. Das IST eine kompakte Repräsentation eines Glases. Die
Repräsentation als ArrayList<LSTube> ist redundant und ermöglicht nur
die bessere Zugreifbarkeit. Eine mögliche spätere Version könnte auf die
ArrayList komplett verzichten und LSTube als Sammlung statischer
Methoden auf einer 16Bit-Zahl implementieren.

Beim Auffüllen der Tests auf 100% Abdeckung ist mir noch ein Fall
aufgestoßen, an den ich bisher nicht gedacht hatte. Es gibt Stellungen,
die keine Lösung haben. Beim Durchsuchen des kompletten Baumes ist das
kein Problem. Bei der Breitensuche brauche ich das zusätzliche
Abbruchkriterium, dass die erreichte Suchtiefe kleiner als die maximal
erlaubte ist.

lg
QNo

[Stefan Ram]

Post by Christian H. Kuhn
Ausprobiert. Stellung: (a,b,c,b), (a,a,c,c), (c,a,b,b), (), (). Das ist
die erste Stellung im einfachsten Level. Die kürzeste Lösung hat 10 Züge.
Erster Ansatz: Wie beim kompletten Baum nur Hashes des aktuellen Zweigs
vorgehalten und verglichen. Lösungszeit 35s.

Mein Algorithmus versucht wiederholt zufällige Züge, bis er
zufällig eine Lösung gefunden hat, und schafft dabei hier
zirka 7 Millionen Züge pro Sekunde.

Das Programm findet aber nicht immer eine Lösung in wenigen
Sekunden. Es könnte sein, daß dies manchmal daran liegt, daß
es in diesem Fall keine Lösung gibt.

abcb
aacc
cabb
====
====

bbbb
====
====
cccc
aaaa

Game is solved.
240 iterations

--------------------------------
Process exited after 0.009412 seconds with return value 0
Press any key to continue . . .

bbigchd
fdciaei
biccgdh
agbefgh
cddfeda
cfgdbeg
baefiia
gchabeh
hfeifah
=======
=======
=======

=======
eeeeeee
=======
ggggggg
hhhhhhh
aaaaaaa
bbbbbbb
iiiiiii
=======
fffffff
ddddddd
ccccccc

Game is solved.
4649166 iterations

--------------------------------
Process exited after 0.6779 seconds with return value 0
Press any key to continue . . .


#include <stdint.h> /* uint_least64_t */
#include <stdio.h> /* putchar */
#include <stdlib.h> /* rand, RAND_MAX */
#include <time.h>

// enums

/* a game board has sites, each of which can carry a stack of
tokens. At the beginning of a game, there some empty sites
(like one or two), and the depth of a site is the number of
same tokens of a color. */
enum
{ /* the number of sites */
numberofsites = 10,

/* the maximum number of tokens per site */
/* must be > 0 */
maxdepthpersite = 7,

/* the number of sites that are initially empty */
numberofemptysites = 3, };

enum
{ /* the number of sites initially filled */
numberoffilledsites = numberofsites - numberofemptysites,

numberofcolors = numberoffilledsites,

/* the maximum number of for tokens in a board */
size = numberofsites * maxdepthpersite,

/* the number of tokens for each color */
numberoftokenspercolor = maxdepthpersite,

/* the number of tokens in the game */
numberoftokens = numberofcolors * numberoftokenspercolor };

// tokens

typedef char token;
typedef int site;
typedef uint_least64_t unicode;
typedef int boolean;
typedef int color;
typedef int position;

static inline unicode tokentounicode( token const i )
{ char value =
i == 0? '-':
i == 1? 'a':
i == 2? 'b':
i == 3? 'c':
i == 4? 'd':
i == 5? 'e':
i == 6? 'f':
i == 7? 'g':
i == 8? 'h':
i == 9? 'i':
i ==10? 'j':
i ==11? 'k':
i ==12? 'l':
i ==13? 'm':
i ==14? 'n':
i ==15? 'o':
i ==16? 'p':
i ==17? 'q':
i ==18? 'r':
i ==19? 's':
i ==20? 't':
'?';
return( unicode )value; }

// board

/* array of all the places where a token can be placed */
token buffer[ size ];

/* current number of tokens at the site given by the index */
int max[ numberofsites ];

static inline void resetboard( )
{ register int i;
for( i = 0; i < size; ++i )i[ buffer ]= 0;
for( i = 0; i < numberofsites; ++i )i[ max ]= 0; }

/* base address of this site */
static inline token * base( site const s )
{ return buffer + s * maxdepthpersite; }

/* critical */
static inline token peek( site const i )
{ token * const b = base( i );
return *( b +( max[ i ] - 1 ) ); }

static inline void put( site const i, token const t )
{ token * const b = base( i );
*( b + max[ i ]++ )= t; }

static inline token get( site const i )
{ token * const b = base( i );
return *( b + --max[ i ] ); }

/* critical */
static inline void move( site const to, site const from )
{ *( base( to ) + max[ to ]++ )= *( base( from ) + --max[ from ] ); }

static inline boolean isfull( site const i )
{ return max[ i ]>= maxdepthpersite; }

/* critical */
static inline boolean isnotfull( site const i )
{ return max[ i ]< maxdepthpersite; }

/* critical */
static inline boolean isnotempty( site const i )
{ return max[ i ]> 0; }

/* critical */
static inline boolean isempty( site const i )
{ return max[ i ]== 0; }

static inline void showboard()
{ for( site s = 0; s < numberofsites; ++s )
{ for( int j = 0; j < maxdepthpersite; ++j )
putchar( j >= max[ s ]? '=':
( char )tokentounicode( buffer[ s * maxdepthpersite + j ]));
putchar( '\n' ); }
puts( "" ); }


// initialization

void shuffle( token * array, size_t const n )
{ if( n > 1 )
{ size_t i;
for( i = 0; i < n - 1; ++i )
{ size_t j =( size_t )( i + rand() /( RAND_MAX /( n - i )+ 1 ) );
int const v = array[ j ];
array[ j ] = array[ i ];
array[ i ] = v; }}}

static inline void init()
{ resetboard();
token a[ numberoftokens ]; int i = 0;
for( color c = 0; c < numberofcolors; ++c )
for( int t = 0; t < maxdepthpersite; ++t )
a[ i++ ]= c + 1;
shuffle( a, numberoftokens );
i = 0;
for( site s = 0; s < numberoffilledsites; ++s )
for( position p = 0; p < maxdepthpersite; ++p )
put( s, a[ i++ ] ); }

static inline void init_abcb_aacc_cabb()
{ resetboard();
int const a = 1;
int const b = 2;
int const c = 3;
token array[ numberoftokens ]=
{ a, b, c, b, a, a, c, c, c, a, b, b };
int i = 0;
for( site s = 0; s < numberoffilledsites; ++s )
for( position p = 0; p < maxdepthpersite; ++p )
put( s, array[ i++ ] ); }

static inline boolean issolved()
{ for( site s = 0; s < numberofsites; ++s )
{ if( !( isempty( s )|| isfull( s )))return 0;
color basecolor = *base( s );
for( position p = 1; p < maxdepthpersite; )
if( *( base( s )+ p++ )!= basecolor )return 0; }
return 1; }

static inline void showsolved()
{ puts
( issolved()?
"Game is solved." : "Game is not solved." ); }

static inline int randomsite()
{ return rand() % numberofsites; }

static inline int randomsiteexcept( int const i )
{ int result = rand() %( numberofsites - 1 );
if( result >= i )++result;
return result; }

static int findexcept( int const site )
{ color const cs = peek( site );
int a[ numberofsites ]; int top = 0;
for( int i = 0; i < numberofsites; ++i )
if( i != site &&( isempty( i )||( isnotfull( i ) && peek( i )== cs )))
a[ top++ ]= i;
if( !top )return -1;
return a[ rand() % top ]; }

int main( void )
{ srand( time( 0 )* time( 0 )); rand(); rand(); rand();
init();
/* init_abcb_aacc_cabb(); */
uint_least64_t gencount = 0;
showboard();
int to; int from;
next:;
if( issolved() )goto out;
retry: from = randomsite(); if( isempty( from ))goto retry;
to = findexcept( from );
if( to == -1 )goto retry;
{ move( to, from );
/* uncomment the next line to see the moves. */
/* showboard(); */ }
++gencount; goto next;
out:
showboard();
showsolved();
printf
( "%d iterations\n", gencount ); }

[Stefan Ram]

Post by Stefan Ram
bbigchd

Jetzt habe ich versucht, »issolved« noch einmal
zu optimieren. Das brachte aber nicht so viel.

Hier eine Ausgabe von einem Spiel mit 17 Reagenzgläsern mit
jeweils 7 Plätzen, von den Reagenzgläsern sind anfangs 5 leer:

gikcjjc
icilcdk
bjhhedi
agilgjb
bdkhkbg
fegahlh
cabidgj
hgffjdh
cedkbel
ldjfefk
lklaeic
eabaffa
=======
=======
=======
=======
=======

eeeeeee
=======
iiiiiii
bbbbbbb
hhhhhhh
=======
lllllll
kkkkkkk
ggggggg
=======
ddddddd
=======
=======
fffffff
aaaaaaa
jjjjjjj
ccccccc

Game is solved.
22682238 iterations

--------------------------------
Process exited after 3.28 seconds with return value 0
Press any key to continue . . .

Bei einer weiteren Erhöhung der Anzahl der Reagenzgläser
erhalte ich oft (nach einer Wartezeit von vielleich 10
Sekunden) keine Lösung mehr. Dies könnte daran liegen, daß
es dann länger als 10 Sekunden dauern würde oder aber auch
daran, daß es keine Lösung gibt. Ich versuche dann die Zahl
der leeren Reagenzgläser zu variieren, was aber nicht immer
hilft.

/* critical */
static inline boolean issolved()
{ for( site s = 0; s < numberofsites; ++s )
if( isnotempty( s )&& isnotfull( s ))return 0;
for( site s = 0; s < numberofsites; ++s )
{ if( !( isempty( s )))
{ color basecolor = *base( s );
for( position p = 1; p < maxdepthpersite; )
if( *( base( s )+ p++ )!= basecolor )return 0; }}
return 1; }

Hier die Ausgabe der ersten Schritte:

daijhaf
iefealc
beagcff
cblggbl
gcblgkk
hhjdcfg
jkdjhbb
elliabc
fhiieda
djceagj
leddkkf
hhkkjii
=======
=======
=======
=======
=======

daijhaf
iefealc
beagcff
cblggb=
gcblgkk
hhjdcfg
jkdjhbb
elliabc
fhiieda
djceagj
leddkkf
hhkkjii
=======
=======
l======
=======
=======

daijhaf
iefealc
beagcff
cblggb=
gcblgkk
hhjdcfg
jkdjhbb
elliabc
fhiieda
djceagj
leddkkf
hhkkji=
=======
=======
l======
i======
=======

daijhaf
iefealc
beagcff
cblggb=
gcblgkk
hhjdcfg
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
=======
f======
l======
i======
=======

daijhaf
iefealc
beagcff
cblggb=
gcblgk=
hhjdcfg
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
=======
f======
l======
i======
k======

daijhaf
iefealc
beagcff
cblggb=
gcblgk=
hhjdcf=
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
g======
f======
l======
i======
k======

daijhaf
iefealc
beagcff
cblggb=
gcblgk=
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
g======
ff=====
l======
i======
k======

daijhaf
iefealc
beagcff
cblggb=
gcblgkk
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddk==
hhkkji=
g======
ff=====
l======
i======
k======

daijhaf
iefealc
beagcff
cblggb=
gcblgkk
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
g======
ff=====
l======
i======
=======

daijhaf
iefealc
beagcf=
cblggb=
gcblgkk
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
g======
ff=====
l======
i======
f======

daijha=
iefealc
beagcf=
cblggb=
gcblgkk
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkk=
hhkkji=
g======
ff=====
l======
i======
ff=====

daijha=
iefealc
beagcf=
cblggb=
gcblgk=
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkkk
hhkkji=
g======
ff=====
l======
i======
ff=====

daijha=
iefealc
beagcf=
cblggb=
gcblgk=
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkkk
hhkkjii
g======
ff=====
l======
=======
ff=====

daijha=
iefealc
beagcf=
cblggb=
gcblgk=
hhjdc==
jkdjhbb
elliabc
fhiieda
djceagj
leddkkk
hhkkji=
g======
ff=====
l======
i======
ff=====

[Stefan Ram]

Post by Stefan Ram
abcb
aacc
cabb
====
====
bbbb
====
====
cccc
aaaa
Game is solved.
240 iterations

Es kommt mir so vor, als ob ich mit dem neuen »issolved« nun
immer deutlich weniger Iterationen brauche. Vielleicht hat
das vorige nicht alle Lösungen erkannt? Hier eine vollständige
Darstellung eines Lösungsweges zur obigen Ausgangsstellung.

Es sieht vielleicht nach einem zielgerichteten Vorgehen aus,
aber jeder Zug ist rein zufällig und könnte beispielsweise
auch in der Rücknahme des direkt vorigen Zuges bestehen:

abcb
aacc
cabb
====
====

abcb
aacc
cab=
b===
====

abc=
aacc
cabb
b===
====

abc=
aacc
cab=
b===
b===

abcc
aac=
cab=
b===
b===

abcc
aac=
ca==
b===
bb==

abcc
aac=
ca==
====
bbb=

abcc
aac=
c===
a===
bbb=

abc=
aac=
cc==
a===
bbb=

abcc
aa==
cc==
a===
bbb=

abcc
a===
cc==
aa==
bbb=

abcc
====
cc==
aaa=
bbb=

abcc
a===
cc==
aa==
bbb=

abcc
====
cc==
aaa=
bbb=

abcc
b===
cc==
aaa=
bb==

abc=
b===
ccc=
aaa=
bb==

abcc
b===
cc==
aaa=
bb==

abcc
====
cc==
aaa=
bbb=

abcc
a===
cc==
aa==
bbb=

abc=
a===
ccc=
aa==
bbb=

ab==
a===
cccc
aa==
bbb=

ab==
aa==
cccc
a===
bbb=

abb=
aa==
cccc
a===
bb==

abb=
aaa=
cccc
====
bb==

abb=
aaa=
cccc
b===
b===

ab==
aaa=
cccc
bb==
b===

abb=
aaa=
cccc
bb==
====

ab==
aaa=
cccc
bb==
b===

a===
aaa=
cccc
bb==
bb==

====
aaaa
cccc
bb==
bb==

====
aaaa
cccc
b===
bbb=

b===
aaaa
cccc
====
bbb=

====
aaaa
cccc
b===
bbb=

====
aaaa
cccc
====
bbbb

Game is solved.
33 iterations

--------------------------------
Process exited after 0.1228 seconds with return value 0
Press any key to continue . . .

Ohne Ausgabeanweisungen:

--------------------------------
Process exited after 0.007772 seconds with return value 0
Press any key to continue . . .

[Stefan Ram]

Post by Stefan Ram
Es kommt mir so vor, als ob ich mit dem neuen »issolved« nun
immer deutlich weniger Iterationen brauche. Vielleicht hat
das vorige nicht alle Lösungen erkannt? Hier eine vollständige
Darstellung eines Lösungsweges zur obigen Ausgangsstellung.

Ich habe nun die Stellung mit 15 Reagenzgläsern aus dem Video
nachgebaut:

hffl
ldlm
fgeg
jcbj
heib
eidb
adje
jcig
amfm
dhhk
kagl
kcka
icbm
====
====

Hier findet mein Programm aber innerhalb mehrerer Minuten
Rechenzeit keine Lösung, obwohl eine existiert.

[Stefan Ram]

Post by Stefan Ram
Hier findet mein Programm aber innerhalb mehrerer Minuten
Rechenzeit keine Lösung, obwohl eine existiert.

Ich hatte damals ursprünglich angenommen, daß jeder Zug
durch einen weiteren Zug rückgängig gemacht werden kann.
Dies war jedoch ein Irrtum.

Dadurch konnte mein Spielbrett in einen Zustand kommen,
von dem aus kein weiterer Zug mehr möglich war, und das
Programm war in einer Endlosschleife gefangen.

Nun erkenne ich eine solche Endlosschleife daran, daß
nach einer gewissen Anzahl von Versuchen kein möglicher
Zug gefunden wurde (auch das ist stochastisch, könnte
also eine möglichen Zug übersehen). In diesem Fall,
beginne ich wieder von vorn (bei der Ausgangsstellung).

Nach dem Einbau dieser Änderung findet das Programm nun
auch bei 15 Reagenzgläsern in 0,05 Sekunden eine Lösung.
(Bei der angezeigten Zahl der Iterationen sind die
Fehlversuche mit Endlosschleifen nicht mitgezählt.
Wenn man das Programm laufen läßt, könnten sich bei jedem
Lauf andere Werte und Laufdauern zeigen.)

hffl
ldlm
fgeg
jcbj
heib
eidb
adje
jcig
amfm
dhhk
kagl
kcka
icbm
====
====

====
cccc
kkkk
aaaa
ffff
bbbb
eeee
jjjj
hhhh
dddd
gggg
iiii
====
mmmm
llll

Game is solved.
306 iterations

--------------------------------
Process exited after 0.05402 seconds with return value 0
Press any key to continue . . .

#include <stdint.h> /* uint_least64_t */
#include <stdio.h> /* putchar */
#include <stdlib.h> /* rand, RAND_MAX */
#include <time.h>

// enums

/* a game board has sites, each of which can carry a stack of
tokens. At the beginning of a game, there some empty sites
(like one or two), and the depth of a site is the number of
same tokens of a color. */
enum
{ /* the number of sites */
numberofsites = 15,

/* the maximum number of tokens per site */
/* must be > 0 */
maxdepthpersite = 4,

/* the number of sites that are initially empty */
numberofemptysites = 2, };

enum
{ /* the number of sites initially filled */
numberoffilledsites = numberofsites - numberofemptysites,

numberofcolors = numberoffilledsites,

/* the maximum number of for tokens in a board */
size = numberofsites * maxdepthpersite,

/* the number of tokens for each color */
numberoftokenspercolor = maxdepthpersite,

/* the number of tokens in the game */
numberoftokens = numberofcolors * numberoftokenspercolor };

// tokens

typedef char token;
typedef int site;
typedef uint_least64_t unicode;
typedef int boolean;
typedef int color;
typedef int position;

static inline unicode tokentounicode( token const i )
{ char value =
i == 0? '-':
i == 1? 'a':
i == 2? 'b':
i == 3? 'c':
i == 4? 'd':
i == 5? 'e':
i == 6? 'f':
i == 7? 'g':
i == 8? 'h':
i == 9? 'i':
i ==10? 'j':
i ==11? 'k':
i ==12? 'l':
i ==13? 'm':
i ==14? 'n':
i ==15? 'o':
i ==16? 'p':
i ==17? 'q':
i ==18? 'r':
i ==19? 's':
i ==20? 't':
'?';
return( unicode )value; }

// board

/* array of all the places where a token can be placed */
token buffer[ size ];

/* current number of tokens at the site given by the index */
int max[ numberofsites ];

static inline void resetboard( )
{ register int i;
for( i = 0; i < size; ++i )i[ buffer ]= 0;
for( i = 0; i < numberofsites; ++i )i[ max ]= 0; }

/* base address of this site */
static inline token * base( site const s )
{ return buffer + s * maxdepthpersite; }

/* critical */
static inline token peek( site const i )
{ token * const b = base( i );
return *( b +( max[ i ] - 1 ) ); }

static inline void put( site const i, token const t )
{ token * const b = base( i );
*( b + max[ i ]++ )= t; }

static inline token get( site const i )
{ token * const b = base( i );
return *( b + --max[ i ] ); }

/* critical */
static inline void move( site const to, site const from )
{ *( base( to ) + max[ to ]++ )= *( base( from ) + --max[ from ] ); }

static inline boolean isfull( site const i )
{ return max[ i ]>= maxdepthpersite; }

/* critical */
static inline boolean isnotfull( site const i )
{ return max[ i ]< maxdepthpersite; }

/* critical */
static inline boolean isnotempty( site const i )
{ return max[ i ]> 0; }

/* critical */
static inline boolean isempty( site const i )
{ return max[ i ]== 0; }

static inline void showboard()
{ for( site s = 0; s < numberofsites; ++s )
{ for( int j = 0; j < maxdepthpersite; ++j )
putchar( j >= max[ s ]? '=':
( char )tokentounicode( buffer[ s * maxdepthpersite + j ]));
putchar( '\n' ); }
puts( "" ); }


// initialization

// static inline int random(){ return( rand() ^( rand() >> 8 ))%RAND_MAX; }
static inline int random(){ return rand(); }

static inline void shuffle( token * array, size_t const n )
{ if( n > 1 )
{ size_t i;
for( i = 0; i < n - 1; ++i )
{ size_t j =( size_t )( i + random() /( RAND_MAX /( n - i )+ 1 ) );
int const v = array[ j ];
array[ j ] = array[ i ];
array[ i ] = v; }}}

static inline void init()
{ resetboard();
token a[ numberoftokens ]; int i = 0;
for( color c = 0; c < numberofcolors; ++c )
for( int t = 0; t < maxdepthpersite; ++t )
a[ i++ ]= c + 1;
shuffle( a, numberoftokens );
i = 0;
for( site s = 0; s < numberoffilledsites; ++s )
for( position p = 0; p < maxdepthpersite; ++p )
put( s, a[ i++ ] ); }

static inline void init_abcb_aacc_cabb()
{ resetboard();
int const a = 1;
int const b = 2;
int const c = 3;
token array[ numberoftokens ]=
{ a, b, c, b, a, a, c, c, c, a, b, b };
int i = 0;
for( site s = 0; s < numberoffilledsites; ++s )
for( position p = 0; p < maxdepthpersite; ++p )
put( s, array[ i++ ] ); }

static inline void init_demo()
{ resetboard(); int c = 1;
color const blue = c++;
color const turquoisish = c++;
color const shag = c++;
color const gray = c++;
color const green = c++;
color const greenish = c++;
color const magenta = c++;
color const orangeish = c++;
color const purple = c++;
color const purpleish = c++;
color const red = c++;
color const white = c++;
color const yellow = c++;
token array[ numberoftokens ]=
{ orangeish, greenish, greenish, white,
white, gray, white, yellow,
greenish, magenta, green, magenta,
purpleish, shag, turquoisish, purpleish,
orangeish, green, purple, turquoisish,
green, purple, gray, turquoisish,
blue, gray, purpleish, green,
purpleish, shag, purple, magenta,
blue, yellow, greenish, yellow,
gray, orangeish, orangeish, red,
red, blue, magenta, white,
red, shag, red, blue,
purple, shag, turquoisish, yellow };
int i = 0;
for( site s = 0; s < numberoffilledsites; ++s )
for( position p = 0; p < maxdepthpersite; ++p )
put( s, array[ i++ ] ); }

/* critical */
static inline boolean issolved()
{ for( site s = 0; s < numberofsites; ++s )
if( isnotempty( s )&& isnotfull( s ))return 0;
for( site s = 0; s < numberofsites; ++s )
{ if( isnotempty( s ))
{ color basecolor = *base( s );
for( position p = 1; p < maxdepthpersite; )
if( *( base( s )+ p++ )!= basecolor )return 0; }}
return 1; }

static inline void showsolved()
{ puts
( issolved()?
"Game is solved." : "Game is not solved." ); }

static inline int randomsite()
{ return random() % numberofsites; }

static inline int randomsiteexcept( int const i )
{ int result = random() %( numberofsites - 1 );
if( result >= i )++result;
return result; }

static inline int findexcept( int const site )
{ color const cs = peek( site );
int a[ numberofsites ]; int top = 0;
for( int i = 0; i < numberofsites; ++i )
if( i != site &&( isempty( i )||( isnotfull( i ) && peek( i )== cs )))
a[ top++ ]= i;
if( !top )return -1;
return a[ random() % top ]; }

static inline void initialize()
{ init_demo();
/* init_abcb_aacc_cabb(); */
/* int(); */ }

int main( void )
{ srand( time( 0 )* time( 0 )); rand(); rand(); rand();
initialize();
uint_least64_t gencount = 0;
uint_least64_t tries; // max 32 with 15 sites
showboard();
int to; int from;
next:;
tries = 0;
if( issolved() )goto out;
retry:
++tries; if( tries > size + 9 ){ initialize(); goto next; }
from = randomsite(); if( isempty( from ))goto retry;
to = findexcept( from );
if( to == -1 )goto retry;
{ move( to, from );
/* uncomment the next line to see the moves. */
/* showboard(); */ }
/* if( gencount % 100000ul ){ showboard(); } */
if( !( gencount % ( 100ul * 1000ul * 1000ul )))
{ srand( time( 0 )* time( 0 )); rand(); rand(); rand(); }
++gencount; goto next;
out:;
showboard();
showsolved();
printf( "%d iterations\n", gencount ); }

[Stefan Ram]

Post by Stefan Ram
Nach dem Einbau dieser Änderung findet das Programm nun
auch bei 15 Reagenzgläsern in 0,05 Sekunden eine Lösung.

Hier ein Beispiel, wo das Programm bei 20 Reagenzgläsern,
von denen 5 leer sind, und jedes Reagenzglas 7 Plätzen hat,
nach 5 Sekunden eine Lösung findet (in einem Durchgang, also
ohne Neustart):

ojemgik
jddifji
biofehn
nhkjonl
hloenge
ccfhkac
eleoafa
jadhccb
ngacicd
kobmikf
ejfgmbl
mlgohkd
lkmhgag
nbfmbdm
nbdljia
=======
=======
=======
=======
=======

hhhhhhh
kkkkkkk
eeeeeee
ooooooo
=======
fffffff
=======
aaaaaaa
ccccccc
=======
iiiiiii
mmmmmmm
ddddddd
jjjjjjj
=======
ggggggg
=======
nnnnnnn
lllllll
bbbbbbb

Game is solved.
23045748 iterations

--------------------------------
Process exited after 5.463 seconds with return value 0
Press any key to continue . . .

Um so etwas mit dem Programm aus dem vorigen Posting
nachzuvollziehen sind folgende Änderungen nötig:

1.)

enum
{ /* the number of sites */
numberofsites = 20,

/* the maximum number of tokens per site */
/* must be > 0 */
maxdepthpersite = 7,

/* the number of sites that are initially empty */
numberofemptysites = 5, };

2.)

static inline void initialize()
{ /* init_demo(); */
/* init_abcb_aacc_cabb(); */
init(); }

PS: Natürlich ist es gut, wenn man bei seinem Compiler eine
höhere Optimierungsstufe einstellt, wenn man das compiliert.

Hier verwende ich bei GCC etwa

-msse3 -march=native -Ofast -O3 -funsafe-loop-optimizations
-fweb -fwhole-program

[Stefan Ram]

Post by Stefan Ram
Nach dem Einbau dieser Änderung findet das Programm nun
auch bei 15 Reagenzgläsern in 0,05 Sekunden eine Lösung.
hffl
ldlm
fgeg
jcbj
heib
eidb
adje
jcig
amfm
dhhk
kagl
kcka
icbm
====
====
Game is solved.
306 iterations

Da diese Besetzung aus dem Film bekannt ist, verwende ich
sie hier als »Standard-Beispiel«.

Inzwischen habe ich noch zwei Änderungen an meinem Programm
vorgenommen: Erstens wird ein Zug jetzt nicht mehr gemacht,
wenn er einfach nur die direkte Umkehrung des vorigen Zuges
ist, und zweitens versucht das Programm jetzt nach dem Finden
einer Lösung eine Lösung mit weniger Zügen zu finden. Dadurch
konnte ich die obige Zahl von Zügen jetzt auf 74 reduzieren,
die mein Programm jetzt auch in einer Kurzform anzeigt:

7>14 12>13 8>13 4>12 4>7 1>13 6>4 0>1 8>0 3>6 2>14 5>3 2>4
14>2 8>13 14>2 9>14 11>8 14>11 3>14 3>14 12>14 12>14 3>12 6>3
6>3 5>6 7>5 7>5 12>7 12>7 5>12 5>12 5>12 4>5 4>5 4>5 4>9 7>4
7>4 7>4 7>3 2>7 2>7 2>7 0>2 0>2 0>2 9>0 9>0 9>0 9>6 1>9 1>9
10>9 6>1 10>7 6>1 10>8 1>6 1>6 11>10 11>10 11>4 11>10 1>11
6>11 6>11 1>9 6>1 6>8 3>6 1>11 6>3

Game is solved.
74 iterations, 74 moves

Diese 74 Züge sollten also die oben zitierte
Ausgabenpositition lösen. Wobei die erste Position
»hffl« die Kennzahl »0« hat.

Das Programm kam bei zwei Läufen immer relative schnell bis
74 und blieb dann dort stehen. Das könnte bedeuten, daß es
vielleicht schon eine optimale Lösung gefunden hat. Da das
Programm aber stochastisch arbeitet, kann man das nicht
sicher sagen.

Ein weitere Optimierung, die ich noch nicht eingebaut habe,
ist es, einen Zug zu einer leeren Position immer durch einen
Zug zu der leeren Position mit der kleinsten Kennzahl zu
ersetzen, da dies nur eine Umbenennung darstellt und der
Suchraum auf diese Weise etwas verkleinert wird. Ferner
könnte man die Positionen nach jedem Zug alphabetisch
aufsteigend umnumerieren, um den Suchraum weiter zu
verkleinern und äquivalente Positionen nicht mehrfach
darzustellen.

[Stefan Ram]

Post by Stefan Ram
Ein weitere Optimierung, die ich noch nicht eingebaut habe,
ist es, einen Zug zu einer leeren Position immer durch einen
Zug zu der leeren Position mit der kleinsten Kennzahl zu
ersetzen, da dies nur eine Umbenennung darstellt und der
Suchraum auf diese Weise etwas verkleinert wird. Ferner
könnte man die Positionen nach jedem Zug alphabetisch
aufsteigend umnumerieren, um den Suchraum weiter zu
verkleinern und äquivalente Positionen nicht mehrfach
darzustellen.

Dann kann man auch noch die Spielsteine selber umbenennen.

Die Stellung

hffl
ldlm
fgeg
jcbj
heib
eidb
adje
jcig
amfm
dhhk
kagl
kcka
icbm
====
====

ist erst einmal äquivalent zu der sortierten
(hffl ist jetzt weiter unten zu finden)

adje
amfm
dhhk
eidb
fgeg
heib
hffl
icbm
jcbj
jcig
kagl
kcka
ldlm
====
====

und diese ist wiederum äquivalent zu der umbenannten
(a->a, d-->b, j-->c, usw.)

abcd
aefe
bggh
dibj
fkdk
gdij
gffl
imje
cmjc
cmik
hakl
hmha
lble
====
====

.

[Patrick Roemer]

Post by Stefan Ram

hffl
ldlm
fgeg
jcbj
heib
eidb
adje
jcig
amfm
dhhk
kagl
kcka
icbm
====
====

[...]

Post by Stefan Ram
Das Programm kam bei zwei Läufen immer relative schnell bis
74 und blieb dann dort stehen. Das könnte bedeuten, daß es
vielleicht schon eine optimale Lösung gefunden hat. Da das
Programm aber stochastisch arbeitet, kann man das nicht
sicher sagen.

Es sollte in 53 Zügen lösbar sein. Wenn ich nix falsch gemacht habe. ;)

Move(kagl,), Move(hffl,l), Move(amfm,), Move(ldlm,m), Move(ldl,ll),
Move(icbm,mm), Move(eidb,icb), Move(ld,eid), Move(l,lll), Move(kag,),
Move(fgeg,g), Move(jcig,gg), Move(amf,hff), Move(am,mmm), Move(a,ka),
Move(icbb,), Move(heib,b), Move(icb,bb), Move(kcka,kaa), Move(jci,hei),
Move(ic,jc), Move(heii,i), Move(hei,ii), Move(he,fge), Move(dhhk,kck),
Move(dhh,h), Move(dh,hh), Move(eidd,d), Move(eid,dd), Move(ei,iii),
Move(fgee,e), Move(adje,ee), Move(fge,eee), Move(fg,ggg), Move(hfff,f),
Move(hff,ff), Move(hf,fff), Move(h,hhh), Move(jcc,), Move(jc,c),
Move(jcbj,j), Move(jcb,bbb), Move(jc,cc), Move(j,jj), Move(adj,jjj),
Move(ad,ddd), Move(kaaa,a), Move(kaa,aa), Move(ka,aaa), Move(kckk,k),
Move(kck,kk), Move(kc,ccc), Move(k,kkk)

Viele Grüße,
Patrick