(Michael Schröpl)
Das Spiel Golf besteht aus zwei Teilen:
Wie bestimmt das Programm nun aber diese Zahl?
Die grundlegende Idee dabei ist, daß das Programm gar nicht berechnet, mit wievielen Schlägen ein Spieler die konkret vorliegenden Bahnen spielen kann. Das Programm berechnet vielmehr, mit wievielen Schlägen der Spieler aufgrund seines Schlägersatzes jede mögliche Bahn spielen kann.
Obwohl das so klingt, als wäre es sehr viel aufwendiger, ist gerade das Gegenteil der Fall. Das verwendete Verfahren berechnet für jede mögliche Bahnlänge nur ein einziges Mal die minimale Anzahl von Schlägen. Die Laufzeit des Verfahrens hängt also direkt von der Anzahl der möglichen Bahnlängen ab, insbesondere also nicht von der Qualität des Schlägersatzes. (Diese Aussage wird in einem späteren Teil dieser Beschreibung teilweise außer Kraft gesetzt werden.)
Als Arbeitsbereich wird eine Tabelle verwendet, die für jedes mögliche Zwischenergebnis auf dem Weg zum Einlochen ein Feld enthält. Die Tabelle enthält also Felder mit den Nummern 1 bis 707. Die größte Feldnummer wird dabei bestimmt als
In jedem Feld wird die Anzahl der Schläge gespeichert, die minimal notwendig waren, um dieses Feld zu erreichen.
An dieser Stelle sei bereits angemerkt, daß das Verfahren nicht feststellt, wie das entsprechende Feld erreicht worden ist. Würde man den kompletten Weg zum Einlochen speichern wollen, dann müßte man zusätzliche Informationen speichern, die für die gestellte Teilaufgabe nicht benötigt werden.
Zu Beginn der Berechnung wird in jedes Feld ein "beliebig" hoher Wert eingetragen, der als "das Feld wurde noch nicht getroffen" interpretiert wird.
Zunächst werden nun diejenigen Felder mit einer Anzahl von Schlägen markiert, bei der dies besonders einfach ist. Das sind natürlich die (bis zu) vier Felder, die mit einem Schlag direkt getroffen werden können. Dies wird ebenfalls bei der Initialisierung des Verfahrens erledigt. Außerdem werden die entsprechenden Nummern in einer Liste gespeichert.
Anschließend beginnt die eigentliche Berechnung. Diese wird in einer Schleife durchgeführt, die solange wiederholt wird, bis die Berechnung keine Veränderung der Schlagzahlen mehr bewirkt. Zu Beginn eines jeden Durchgangs wird zunächst der Zähler, der angibt, wieviele Schläge bereits durchgeführt wurden, um 1 erhöht. (Nach der Initialisierung hatte dieser Zähler den Wert 1.)
Anschließend wird für jedes Feld, das im vorhergehenden Durchgang neu markiert wurde (das nämlich ist der Sinn der oben erwähnten Liste), versucht, mit jedem der vier Schläger einen Schlag weit vorwärts bzw. rückwärts zu spielen. Jedes "aktive" Element kann also bis zu 8 weitere Markierungen bewirken.
Ein Feld wird allerdings nur dann neu markiert (und seine Nummer in die Liste für den nächsten Durchgang neu aufgenommen), falls der Wert der Feldes größer war als die Nummer des aktuellen Durchgangs. Ein Feld, das bereits früher markiert worden war, hat ja bereits selbst wieder als aktives Element andere Markierungen nach sich gezogen, so daß ein erneutes Erreichen desselben Felder keine Vorteile mehr bringt und daher ignoriert werden kann.
Außerdem werden nur Felder innerhalb der Tabelle berücksichtigt; liegt das Ergebnis der Summe bzw. Differenz außerhalb der Tabelle, dann wird es ignoriert.
Jeder Durchgang der Berechnung arbeitet also eine Liste von "aktiven" Elementen ab und erzeugt eine weitere Liste von Elementen für den nächsten Durchgang. Die Berechnung endet, wenn die neue aktive Liste leer ist. In diesem Falle wurde im vorhergehenden Durchgang kein neues Feld mehr markiert, und der Inhalt aller Felder hat seinen endgültigen Wert.
Das Ganze läßt sich naheliegenderweise mit zwei wechselnden aktiven Listen realisieren. Programmtechnisch ist es allerdings günstiger, nur eine Liste zu führen und diese jeweils am Ende zu verlängern: Ein bestimmter Teil (dessen Länge zu diesem Zeitpunkt bereits bekannt ist) enthält die aktive Liste des aktuellen Durchgangs, dahinter werden die neu erzeugten Einträge angefügt. Da jeder Wert der zu füllenden Tabelle maximal einmal in die aktive Liste eingetragen werden kann, ist deren maximale Länge ebenfalls bekannt.
Aus der Tübinger Golf-Spieler-Gruppe (um Martin Kretschmar), die bei der Entwicklung erster Einlochprogramme Pionierarbeit geleistet hat, kam ein Vorschlag zu Verbesserung des Verfahrens.
Die obige Beschreibung geht davon aus, daß während der Berechnung jeder mögliche Weg zu einer noch nicht markierten Bahn parallel durchgeführt wird, und zwar in der Reihenfolge der Schläge auf diesem Weg.
Diese Berechnung kann man aber auch rückwärts durchführen. Dies bedeutet, daß nicht die Felder
<element> +/- <schläger>,
sondern die Felder
<schläger> +/- <element>
neu markiert werden. Dies bedeutet - anschaulich ausgedrückt -, daß nicht von einem Zwischenergebnis aus der nächste Schlag durchgeführt wird, sondern von einem Schläger aus ein weiterer kompletter Weg zu einem Zwischenergebnis.
Man kann zeigen, daß es immer möglich ist, die Schläge auf dem entsprechenden Weg so umzusortieren, daß der Weg eine Länge zwischen 1 und 358 hat. Anders gesagt: Es ist niemals erforderlich, daß der letzte Schlag auf dem Weg zu einer Bahn "rückwärts" führt. Man könnte ihn nämlich mit dem Schlag, der auf das Feld jenseits des Ziels geführt hat, tauschen. War dieser Schlag weiter als der Rückwärtsschlag, dann liegt das Zwischenergebnis unterhalb 358; ist dies nicht der Fall, dann führt man den Tausch dennoch durch und betrachtet als nächstes den vorletzten Schlag vorwärts, für den dasselbe gilt wie für den letzten. Irgendwie muß man ja über die maximale Bahnlänge hinausgeschlagen haben, daher wird diese Tauschmethode - mit eventuell mehreren Wiederholungen - zum gewünschten Ziel führen.
Für das oben beschriebene Verfahren bedeutet dies, daß man die Tabelle auf 358 Felder verkleinern kann. Diejenigen Wege zu einer Bahn, die nun nicht mehr durchlaufen werden, sind solche, die durch Umstellung der Reihenfolge von Schlägen ein Zwischenergebnis außerhalb der Tabelle bewirken. Dadurch wird die Berechnung signifikant beschleunigt: es ist nun nicht mehr erforderlich, zu warten, bis auch sämtliche Felder zwischen 358 und 708 getroffen wurden; das Verfahren berechnet auch hier nun weniger überflüssige Zwischenergebnisse.
Als Ergebnis der Berechnung entsteht eine Tabelle, in der jedes Feld
Letzteres ist genau dann der Fall, wenn der größte gemeinsame Teiler aller vier Schlägerwerte ungleich 1 ist. Sind alle Schlägerlängen ein Vielfaches von <n>, dann gilt dies auch für Summen bzw. Differenzen dieser Schlägerlängen, und nur solche Bahnlängen können mit diesem Schlägersatz getroffen werden. (Da die meisten Spieler den Schläger mit der Länge 1 verwenden, tritt dieser Fall nur sehr selten ein; für die Vollständigkeit des Verfahrens, insbesondere für die Berechnung eines bestmöglichen Schlägersatzes, muß das Verfahren aber auch mit einem solchen Fall fertig werden.)
Die Anzahl der Schläge eines Spielers für ein Turnier, dessen konkrete Bahnlängen bekannt sind, ist also einfach die Summe der entsprechenden sechs Felder der Tabelle.
Der Erwartungswert eines Schlägersatzes für ein zu spielendes Turnier ist der gewichtete arithmetische Mittelwert aus den Ergebnissen des Spielers für alle Mengen konkreter Bahnlängen, die aufgrund der Turnierausschreibung möglich sind.
Statt diese Bahnlängen einzeln zu berechnen, genügt es, die Summe der Schlagzahlen für alle Werte zu berechnen, die in dem vorliegenden Turnier als Bahnlängen auftreten können, und jede diese Zahlen mit der Wahrscheinlichkeit dafür, daß tatsächlich dieser Wert als Bahnlänge verwendet wird, zu multiplizieren.
Für die vom Programm Golf verwendeten Turnierausschreibungen sieht das folgendermaßen aus:
| Bahn 1 (b1+1W3): | p(b1+1) = p(b1+2) = p(b1+3) = 1/3 |
| Bahn 2 (b2+1W4): | p(b2+1) = p(b2+2) = p(b2+3) = p(b2+4) = 1/4 |
| Bahn 3 (b3+1W6): | p(b3+1) = p(b3+2) = p(b3+3) = p(b3+4) = p(b3+5) = p(b3+6) = 1/6 |
| Bahn 4 (b4+2W2): | p(b4+2) = p(b4+4) = 1/4, p(b4+3) = 1/2 |
| Bahn 5 (b5+2W3): | p(b5+2) = p(b5+6) = 1/9, p(b5+3) = p(b5+5) = 2/9, p(b5+4) = 3/9 |
| Bahn 6 (b6+2W4): | p(b6+2) = p(b6+8) = 1/16, p(b6+3) = p(b6+7) = 2/16, p(b6+4) = p(b6+6) = 3/16, p(b6+5) = 4/16 |
Aus der beim Einlochen berechneten Tabelle kann also der Erwartungswert für einen Schlägersatz bei einem bestimmten Turnier ebenfalls direkt abgelesen werden.
Für das Füllen der Tabelle ist an dieser Stelle eine mögliche Optimierung zu erkennen: Man kann die gesuchten Felder anders als "nicht getroffen" markieren als die übrigen Felder und beim Füllen mitzählen, wieviele dieser Felder man bereits gefunden hat (und abbrechen, sobald keines mehr fehlt). Bei "guten" Schlägersätzen, die tendenziell die gesuchten Felder eher füllen als die übrigen, kann das etwas bringen; bei "schlechten" Schlägersätzen kosten die erforderlichen Abfragen allerdings nur zusätzlichen Rechenzeit.
Für Standard-Golf, wo das Kontingent von Schlägerwechseln beschränkt ist, ist die Überprüfung aller Möglichkeiten eines einfachen Schlägerwechsels eine naheliegende Aufgabe. Dabei sind 1397 Schlägersätze zu bewerten, nämlich der bereits vorliegende Schlägersatz sowie 349 neue Werte pro Schläger.
Natürlich ist es einfacher zu programmieren, für jeden Schläger einfach alle Werte von 1 bis 350 durchlaufen zu lassen, als die drei überflüssigen Schlägersätze explizit herauszufiltern. Und die jeweils 350 Vergleiche kosten auch ähnlich viel Zeit wie die eine zusätzliche Berechnung.
Als "bester" Schlägersatz soll dabei derjenige Schlägersatz betrachtet werden, dessen Erwartungswert minimal ist. Der Erwartungswert eines Schlägersatzes, mit dem nicht alle Felder der zu spielenden Bahnen getroffen werden können, kann nicht exakt bestimmt werden, ist in der Praxis allerdings auch nicht relevant und soll daher an dieser Stelle nicht berücksichtigt werden.
Im Gegensatz zur oben definierten Aufgabe beim Einlochen bzw. der exakten Berechnung des Erwartungswertes ist es nun nicht mehr interessant, jeden Erwartungswert vollständig zu bestimmen. Wenn es möglich ist, während der Berechnung erkennen zu können, daß kein neuer Bestwert mehr möglich ist, dann kann die Untersuchung des vorliegenden Schlägersatzes abgebrochen werden.
Der Erwartungswert würde normalerweise am Ende der Berechnung bestimmt werden. Dazu würden die 3+4+6+3+5+7 = 28 Schlagzahlen der relevanten Felder jeweils mit der Wahrscheinlichkeit ihrer Verwendung multipliziert und die Ergebnisse aufsummiert werden. Statt dessen kann man auch einen Zähler mit dem Wert 6 (dem minimal denkbaren Wert für 6 Bahnen bei beliebig vielen Schlägern) initialisieren und nach jedem Durchgang für jedes noch nicht getroffene Feld die entsprechende Wahrscheinlichkeit addieren. So erhält man nach jedem Durchgang eine untere Abschätzung für den Erwartungswert. Würden im nächsten Durchgang alle relevanten Felder getroffen werden, dann läge schon der tatsächliche Erwartungswert vor.
Obwohl dies die Verwaltung zusätzlicher Informationen und die mehrfache Überprüfung auch bereits verarbeiteter Werte von Feldern bedeutet, wird dadurch das Verfahren erneut signifikant beschleunigt. Je besser der bereits gefundene beste Schlägersatz ist, um so früher kann ein nachfolgend betrachteter Schlägersatz als uninteressant verworfen werden. Hat man bereits einen guten Wert unter 20 gefunden, kann man gerade bei schlechten Schlägersätzen mit einem Erwartungswert von 30 oder 40 schon nach etwa 4 Durchgängen (in denen noch kaum etwas getroffen wurde) abbrechen und sich oft mehr als die Hälfte der Berechnung sparen.
Auf die kleineren Optimierungen, um etwa die Anzahl der Indexzugriffe zu reduzieren oder die lästige Addition von Gleitpunktzahlen zu vermeiden, soll hier nicht näher eingegangen werden.
Es bringt aber in der Tat etwas, über die innerste Schleife lange nachzudenken und ggf. sogar Code zu duplizieren (bzw. mit Makros generieren zu lassen).
Das Auswerteprogramm verwendet dieses Verfahren für alle Berechnungen, auch für die exakte Berechnung des Erwartungswertes eines Schlägersatzes und sogar zum Einlochen. Dafür braucht lediglich ein beliebig schlechter Erwartungswert als "zu unterbieten" angegeben werden, damit für einen konkreten Schlägersatz das Feld vollständig gefüllt wird. Wieso auch unterschiedliche Prozeduren schreiben, wenn die beste alles kann?