SELF AVOIDING WALK
Ein Programm zur verteilten Berechnung des self avoiding walks im 9x9-Quadrat
Von Felix Schremmer alias ZEVS (Felix.Schremmer@gmx.de)

1. bersicht der Dateien

	.saw_worker.bmx       : Quellcode fr das Hintergrund-Berechnungsprogramm.
	.saw_worker.exe       : Hintergrung-Berechnungsprogramm. Wird vom GUI-Programm ausgefhrt.
	changelog.txt         : bersicht der nderungen.
	perfect_snake_api.c   : C-Bibliothek zur eigentlichen Berechnung, da BlitzMax zu langsam ist.
	perfect_snake_api.o   : Kompillierte Version von perfect_snake_api.c (s. 4.).
	README.txt            : Vorliegend.
	self_avoiding_walk.bmx: Quellcode des GUI-Programms.
	self_avoiding_walk.exe: Das GUI-Programm. Ist zur Berechnung auszufhren.
	showPath.bmx          : Programm zur Veranschaulichung der Pfade.

	[saw.ini              : Konfigurationsdatei. Wird erstellt, wenn sie nicht existiert.]
	[log/                 : Verzeichnis der Logdateien. In saw.ini einstellbar.
	                        Wird erstellt, falls nicht existent]
	[log/toc.txt          : bersicht der Dateien in log (table of contents).
	                        Enthlt auserdem Absturzmeldungen]


2. Allgemeines zum Problem

Das Problem wurde unter http://www.blitzforum.de/forum/viewtopic.php?t=39751 intensiv errtert. Es wurde der Entschluss gefasst, das unbekannte 9x9-Quadrat verteiltet zu berechnen.
Jeder Pfad (= wie die Schlange liegt) beginnt links oben. Dann geht er nach rechts weiter.
(Anmerkung: Smtliche Pfade, die mit "nach unten" beginnen, lassen sich durch Spiegelung an der Hauptdiagonalen zu Pfaden transformieren, die mit "nach rechts" beginnen. Das Endergebnis muss dann nur noch verdoppelt werden, der Berechnungsaufwand ist aber nur halb so gro).
Dann kann es nach unten oder nach rechts weitergehen. Um diese Entscheidung und alle folgenden mglichst kompakt darzustellen, gilt folgende Konvention: Der Pfad wird als Folge der Buchstaben N, E, S, W dargestellt. N bedeutet hierbei, dass der Pfad nach oben weitergeht, E nach rechts, S nach unten und W nach links (Vgl. englische Himmelsrichtungen). Die ersten beiden Felder sind hierbei nicht erwhnt, es geht mit der ersten echten Entscheidung (zwischen E und S) weiter. Beispiel: EESSWN

 # # # #
     h # (h: Schlangenkopf)
     # #

(wer einen BlitzMax-Compiler hat, kann das Programm showPath.bmx ausfhren, um sich dieses Prinzip klarer zu machen)

Man kann Pfade vergleichen. Es gelte N < E < S < W. Um zwei Pfade zu vergleichen, vergleicht man die Buchstaben, wobei weiter links stehende hherwertig sind. Z.B. ist N < S, SN > EW, SEW > SEN. Ist der eine Pfad der Anfang des anderen, so ist der krzere der beiden als kleiner definiert (N < NW).
Das Programm zur verteilten Berechnung ist so konzipiert, dass es bei einem gegebenen Pfad I (initial path) anfngt zu suchen und bei einem anderen Pfad F (final path) aufhrt. Wenn dies geschehen ist, sind alle Pfade P mit I <= P <= F untersucht.Stoppt das Programm frher an einem Pfad F', so sind alle Pfade P mit I <= P <= F' untersucht.
Man kann die Berechnung daher recht einfach aufspalten: Mchte man das Quadrat auf zwei Rechnern parallel ausrechnen, so lsst man den einen von E bis S suchen und den anderen von S bis W (die Tatsache, dass W kein gltiger Pfad ist, ist hier irrelevant. Es werden alle Pfade P mit S <= P < W untersucht, das reicht).
Mit mehr Rechnern ist es ebenso mglich. Es gibt am Anfang einen Bereich (E-W), der untersucht werden muss. Solange alle parallel rechnenden untereinender verknpft sind und sich absprechen, knnen sie diesen Bereich an mehreren Stellen gleichzeitig erforschen. Am Ende gilt es dann, die Lcken zu fllen.
Beispiel:
A: Hallo Leute, ich untersuche mal von Anfang an (starte bei E, ende bei W).
B: Das dauert zu lange, ich helfe mal mit. Untersuche von S bis W.
C: Ich mache auch mit. Da A wahrscheinlich noch bei irgendwelchen EE...-Pfaden hngt, fange ich bei ES an.
A: So, ich hre jetzt wieder auf. Habe alles von E-EEES berechnet.
D: Ich beteilige mich mal. Da B vermutlich noch einen SE...-Pfad hat, rechne ich mit SS weiter.
B: NAZI!
C: lol
...
C: So, ich bin bei S angekommen, fr alles danach ist B zustndig. Ich mache Schluss fr heute.
B: Ich habe jetzt auch meinen Teil bis SS fertig.
D: Dann bleibe ich ja alleine brig. Ich hre bei SSW auf.
Nchster Tag:
A: Fehlt also nur noch EEES-ES und SSW-W. Ich rechne jetzt von EEES bis ES.
B: Dann mache ich SSW-W.
A: Fertig!
B: Bin auch gerade fertig geworden.

Die vier addieren ihre Zwischenergebnisse und multiplizieren das Ergebnis mit zwei. Jeder kann natrlich betrgen und falsche Werte weitersenden. Deshalb ist es wichtig, viele Zwischenergebnisse (z.B. EEEEESS-EEEEESW) zu speichern, dann knnen stichprobenartig Teile berprft werden und ein Zweifelnder kann so vom Ergebnis berzeugt werden.

3. Die Anwendung

Es gibt zwei Eingabefelder um den Anfangspfad (initial path) und den Endpfad (final path) einzugeben. Durch einen grnen Balken wird ungefhr angezeigt, welchen Bereich man bearbeitet (links steht der kleinste Pfad, rechts der grte). Drckt man auf Start!, wird der Hintergrundprozess gestartet (Achtung: Wenn die GUI-Anwendung jetzt abstrzt, kann es sein, dass der Hintergrundprozess weiterhin Resourcen braucht. Benutze dann den Task-Manager o..). Der Hintergrundprozess braucht ungefhr 90% CPU-Leistung (in .saw_worker.bmx einstellbar). Alle zehn Sekunden fllt sich das Textfeld unten mit einer weiteren Zeile der Form
<Anfangspfad>;<Endpfad>;<Perfekte Spiele>;<Zeit>      .
Dies bedeutet, dass es zwischen dem <Anfangspfad> und dem <Endpfad> genau die gegebene Anzahl an perfekten Spielen gibt. Hierfr wurde die gegebene Zahl von Millisekunden bentigt.
Die Berechnung beendet sich selbst exakt am gegebenen Endpfad, sobald dieser erreicht wird. Wenn man sie manuell mit dem Stop!-Knopf beendet, bleiben die Zeilen natrlich stehen.
Die genaue Art und Weise, die einzelnen Berechnungen zu koordinieren und die Ergebnisse zusammenzutragen steht bislang noch nicht fest. Da mit einer berschaubaren Anzahl an Freiwilligen gerechnet wird, ist keine komplizierte Koordinationssoftware vonnten. Es wre sehr schn, wenn jemand aber eine Online-Formular zum Eintragen der Zusammenfassungen gestalten wrde, das den Stand der Berechnungen dann ansprechend darstellt und eine Orientierung, wo es sinnvoll wre, weiterzurechnen, bietet.

4. Der Sourcecode

Der rechnende Kern befindet sich (wegen des Wunsches, mglichst schnell rechnen zu knnen) in der C-Datei (perfect_snake_api.c). Die direkte Verwaltung dieses Rechnerkerns als Konsolenanwendung, die auerdem die CPU-Drosselung auf 90% vornimmt, findet man in .saw_worker.bmx (ein ndern der CPU-Auslastung ist sehr einfach mglich und in einem Kommentar an Ort und Stelle erklrt). Die GUI nebst Rckgriff auf .saw_worker.exe im Hintergrund findet man in self_avoiding_walk.bmx.
Es gibt zwei Mglichkeiten, das Programm zu kompillieren. Die einfachere besteht darin, in .saw_worker.bmx die Datei perfect_snake_api.c direkt zu importieren. Anschlieend kompilliert man .saw_worker.bmx nach .saw_worker.exe (wichtig: ein eingeschobenes .mt oder .debug sorgt dafr, dass das Programm die Datei nicht findet. Der exakte Dateiname ist wichtig. Wenn (z.B. unter Linux) dennoch ein anderer Name als ".saw_worker.exe" verwendet werden soll, muss man in self_avoiding_walk.bmx eine Zeile ndern).
In der aufwndigeren kompilliert man perfect_snake_api.c manuell (und schaltet alle Optimierungen ein!), also

 > gcc -o perfect_snake_api.o -O3 -c perfect_snake_api.c

und importiert dann perfect_snake_api.o in .saw_worker.bmx . Dies hat den Vorteil, dass die Berechnung wesentlich schneller ist (wegen der starken Optimierung durch -O3).

Die GUI-Datei kann man unabhngig hiervon kompillieren.

5. Fazit

Mit dem 9x9-Quadrat betreten wir sozusagen Neuland, niemand hat vorher den Wert errechnet. Ich lade euch unerschrockene Eroberer ein, es vollstndig zu erforschen und anschlieend mit dem Recht des Entdeckers es als erste Kolonie des Blitzforums in Besitz zu nehmen.
Mge das Rechnen beginnen!
