Gesetze und Heuristiken bei der Suche nach zielführenden Zugfolgen
Vier gewinnt.
Möglichkeiten, die weitere Ausfüllung des Brettes zu bestimmen:
Letzteres ist natürlich immer der Fall, aber beim Schach, beispielsweise, unterscheiden sich diese Bedingungen für jede Figur und sind auch nur im Falle der Bauern ähnlich einfach und zwingend (immer vorwärts, nie zurück).
Entsprechend stark unterscheiden sich die Charaktere der beiden Spiele, Vier gewinnt lebt davon, daß es Menschen trotz der besseren Übersicht über die Aussichten einer Stellung nicht so ohne weiteres möglich ist, die Aussichtslosigkeit einer Stellung korrekt festzustellen, wodurch es oftmals dazu kommt, daß ein Spieler trotz seiner eigenen Fehlkalkulation ein Spiel gewinnt, weil sie dem anderen auch nicht klar ist und er sich schon alleine dadurch in weitere Fehlkalkulationen verstrickt. Dies gilt so freilich wieder für alle Strategiespiele, aber bei Vier gewinnt entsteht daraus ganz regelmäßig ein fortgesetztes Fallen Stellen und Sich Herauswinden, welches der Spieler gewinnt, welcher die meiste Erfahrung darin hat, wohingegen es beim Schach nur während des gegenseitigen Figurenschlagens dazu kommt, welches aber keine exakte Wissenschaft ist, sondern im Grunde genommen nur dazu dient, die Lage übersichtlicher zu gestalten, um das End- und damit das eigentliche Schachspiel einzuleiten. Und in diesem eigentlichen Schachspiel gibt es keinen linearen Fahrplan mehr, wo man abzählen könnte, an welcher Station zum Ziel man nun angekommen ist. Vielmehr hält man die Augen auf nach allem, was irgendwie nicht nach Remis aussieht, irrt sich dabei oftmals und gibt sich dann doch mit Remis zufrieden.
Jedenfalls ist es das letzte Mal zwischen Carlsen und Anand so gelaufen.
Nun gut, worauf ich hier eigentlich hinauswill ist, daß ich es für einen falschen Ansatz der künstlichen Intelligenz halte, menschliche Heuristiken, wie etwa beim Schachspiel, statisch zu imitieren. Vier gewinnt liefert ein schönes Beispiel dafür, warum man das nicht tun sollte: Diese Heuristiken pflegen falsch zu sein, ich habe beispielsweise fast immer als B gegen andere menschliche Spieler gewonnen und auch gegen die künstliche Intelligenz der Linuxversion, obwohl B sich von Anfang an in einer aussichtslosen Lage befindet.
Die folgende Eröffnung, beispielsweise, ist ziemlich furchteinflößend,
....... ....... .......
....... ....... .......
....... .o..... .o....o
.x.o... .x.o..x .x.ox.x
aber eben nicht zielführend. Die Linuxversion auf hard eingestellt (Stufe 6 von 7, aber 7 macht's genauso) ist übrigens so blöd, gleich zweimal nach einander in die Mitte zu setzen.
.......
...x...
...o...
.x.o...
Das Spiel ist verloren nach der ersten Garantie, nunja, beinahe, A kann noch in die sechste Spalte setzen, worauf B in die fünfte, A in die vierte, B in die sechste, A in die zweite, B in die erste, aber dann ist der Ofen aus. Stufe 6 bedrängt einen indes nicht derartig unnachgiebig, und so man kann sogar etwas Kunst schaffen und folgendes Bild bis zum Sieg auffüllen:
xxxxxxx
oooxooo
xxxoxxx
oooxooo
xxxoxxx
oooxooo
ooxoxoo
xxoooxx
Nennen wir es: Maximaler Unnutz. A hat zwei 4er und elf 3er, aber nützen tun sie alle nichts.
Nein, der statische Teil einer künstlichen Intelligenz sollte nur aus Aussagen bestehen, welche beweisbar stimmen. Dann kann sie immer noch Heuristiken wie die Unterteilung der Spielphasen beim Schach entwickeln, um ihre Chancen, im Suchraum etwas Brauchbares in der nunmal nur vorhandenen Zeit zu finden, aus dem jeweiligen Blickwinkel heraus zu erhöhen.
Vorzugsweise sollte sie aber auch dort nach Gesetzen suchen, welche den Ausgang von möglichen Zugfolgen vorhersagen.
Betrachten wir dazu ein anderes Beispiel.
Schiebepuzzle.
Wie schiebt man die Teile herum, um das Bild zusammenzukriegen?
Nun, das ist nicht schwer. Man schiebt bei Numerierung von links nach rechts und dann wieder von links nach rechts eine Zeile tiefer und unter der Annahme, daß das letzte Feld frei bleibt, das erste Teil auf das erste Feld und so weiter, bis man beim n-1. Teil angekommen ist, wobei n die Anzahl der Zeilen und Spalten im quadratisch angenommenen Schiebepuzzle bezeichne, eine Annahme übrigens, welche völlig unwesentlich ist. Dieses n-1. Teil also schiebt man auf Feld n, um es anschließend mit einer kleinen 4er Rotation in einem 2x2-Feld zusammen mit dem n. Teil an die richtige Stelle zu bekommen.
Anschließend kümmert man sich analog um den Rest der ersten Spalte, um dann in einem Schiebepuzzle der Größe n-1 wie gehabt fortzufahren, bis man schließlich bei einem Schiebepuzzle der Größe 2x2 anlangt, in welchem man nur noch rotieren kann.
Betrachten wir das einmal genauer:
12 1. .1 31 31 3. .3 23 23
3. 32 32 .2 2. 21 21 .1 1.
Die Permutationsgruppe von 3 Elementen, hat 6 Elemente, von welchen uns hier aber nur 3 zur Verfügung stehen, nämlich die Rotationen (1)(2)(3), (123) und (132) , oder anders gesagt Stillstand, Schritt nach rechts und Schritt nach links.
Was heißt das für die Permutationsgruppe der Teile des Schiebepuzzles?
Nun ja, es heißt, daß wir mit unserem Algorithmus in einer Untermenge bleiben, welche nicht (n*n-1)! Elemente besitzt, sondern nur (n*n-1)!/2.
Und was heißt das?
Das heißt, das wir beweisen müssen, daß in einem Schiebepuzzle nur Permutationen möglich sind, deren Signum positiv ist.
Das ist indes einfach. Jede Permutation des Schiebepuzzles ist aus einer Abfolge von Vertauschungen des freien Felds mit einem Teil des Schiebepuzzles zusammengesetzt so, daß das freie Feld am Anfang und am Ende am selben Platz, dem letzten Feld, steht.
Eine solche Permutation hat die Form (ab) und ein negatives Signum. Wir müssen also zeigen, daß die Anzahl dieser Vertauschungen gerade ist.
Und nichts leichter als das. Denken wir uns schlicht ein Schachfeld. Das letzte Feld sei schwarz. Dann führt jede gerade Anzahl von Vertauschungen das freie Feld auf ein schwarzes Feld und jede ungerade das freie Feld auf ein weißes, und da wir von schwarz auf schwarz wollen, benötigen wir also eine gerade Anzahl von Vertauschungen.
Mit anderen Worten brauchen wir uns nicht darum zu sorgen, daß wir durch Rotation im verbleibenden 2x2-Puzzle nicht die richtige Anordnung zu Stande bringen, denn eine entsprechende Umordnung ist durch das Kaputtschieben des Ausgangsbildes nicht erreichbar.
Anders ausgedrückt können wir jedes Schiebepuzzle mit unserem Algorithmus Schritt für Schritt zurückschieben.
Hier ist es also so, daß wir ein Gesetz gefunden haben, welches uns die nötigen Züge zur Erreichung unseres Zieles vollständig an die Hand gibt, indem wir eine Weise erkannt haben, so zu ziehen, daß die späteren Züge den partiellen Erfolg der vorherigen nicht zu Nichte machen.
Übrigens gibt es auch ein, wenn auch nicht hinreichendes, so doch notwendiges Gesetz des Philosophierens. Es lautet:
Die Hinreichendheit eines Gesetzes bedeutet, daß es zur Lösung führt, die Notwendigkeit, daß es Unsinn ausschließt, meistens aber sind den Ausgang absehende Gesetze weder notwendig, noch hinreichend, um zum Ziel zu gelangen, nichtsdestotrotz aber von wesentlichem Nutzen zu diesem Zweck, wie man am Beispiel der Gesetze zu Vier gewinnt ersehen kann.
Möglichkeiten, die weitere Ausfüllung des Brettes zu bestimmen:
- B kann vor jedem Zug von A sämtliche auf geraden Höhen (Zählung beginnt mit 1) momentan unerreichbaren Stellen für sich sicherstellen oder anders ausgedrückt, A kann eine Stelle auf einer gerade Höhe nur dann belegen, wenn B sie A freiwillig überläßt, denn wenn B am Zug ist, gibt es stets in wenigstens einer Spalte eine Stelle auf einer gerade Höhe, welche B belegen kann.
- Wenn A es schafft, B dazu zu bringen, nicht weiter in gewisse Spalten zu setzen, in welchen eine ungerade Anzahl von Steinen liegt, so vertauschen sich die Rollen von A und B in den übrigen Spalten.
- Ist nur noch eine Spalte übrig geblieben, so belegt A die übrigen Stellen auf ungerader Höhe und B die übrigen Stellen auf gerader Höhe.
Letzteres ist natürlich immer der Fall, aber beim Schach, beispielsweise, unterscheiden sich diese Bedingungen für jede Figur und sind auch nur im Falle der Bauern ähnlich einfach und zwingend (immer vorwärts, nie zurück).
Entsprechend stark unterscheiden sich die Charaktere der beiden Spiele, Vier gewinnt lebt davon, daß es Menschen trotz der besseren Übersicht über die Aussichten einer Stellung nicht so ohne weiteres möglich ist, die Aussichtslosigkeit einer Stellung korrekt festzustellen, wodurch es oftmals dazu kommt, daß ein Spieler trotz seiner eigenen Fehlkalkulation ein Spiel gewinnt, weil sie dem anderen auch nicht klar ist und er sich schon alleine dadurch in weitere Fehlkalkulationen verstrickt. Dies gilt so freilich wieder für alle Strategiespiele, aber bei Vier gewinnt entsteht daraus ganz regelmäßig ein fortgesetztes Fallen Stellen und Sich Herauswinden, welches der Spieler gewinnt, welcher die meiste Erfahrung darin hat, wohingegen es beim Schach nur während des gegenseitigen Figurenschlagens dazu kommt, welches aber keine exakte Wissenschaft ist, sondern im Grunde genommen nur dazu dient, die Lage übersichtlicher zu gestalten, um das End- und damit das eigentliche Schachspiel einzuleiten. Und in diesem eigentlichen Schachspiel gibt es keinen linearen Fahrplan mehr, wo man abzählen könnte, an welcher Station zum Ziel man nun angekommen ist. Vielmehr hält man die Augen auf nach allem, was irgendwie nicht nach Remis aussieht, irrt sich dabei oftmals und gibt sich dann doch mit Remis zufrieden.
Jedenfalls ist es das letzte Mal zwischen Carlsen und Anand so gelaufen.
Nun gut, worauf ich hier eigentlich hinauswill ist, daß ich es für einen falschen Ansatz der künstlichen Intelligenz halte, menschliche Heuristiken, wie etwa beim Schachspiel, statisch zu imitieren. Vier gewinnt liefert ein schönes Beispiel dafür, warum man das nicht tun sollte: Diese Heuristiken pflegen falsch zu sein, ich habe beispielsweise fast immer als B gegen andere menschliche Spieler gewonnen und auch gegen die künstliche Intelligenz der Linuxversion, obwohl B sich von Anfang an in einer aussichtslosen Lage befindet.
Die folgende Eröffnung, beispielsweise, ist ziemlich furchteinflößend,
....... ....... .......
....... ....... .......
....... .o..... .o....o
.x.o... .x.o..x .x.ox.x
aber eben nicht zielführend. Die Linuxversion auf hard eingestellt (Stufe 6 von 7, aber 7 macht's genauso) ist übrigens so blöd, gleich zweimal nach einander in die Mitte zu setzen.
.......
...x...
...o...
.x.o...
Das Spiel ist verloren nach der ersten Garantie, nunja, beinahe, A kann noch in die sechste Spalte setzen, worauf B in die fünfte, A in die vierte, B in die sechste, A in die zweite, B in die erste, aber dann ist der Ofen aus. Stufe 6 bedrängt einen indes nicht derartig unnachgiebig, und so man kann sogar etwas Kunst schaffen und folgendes Bild bis zum Sieg auffüllen:
xxxxxxx
oooxooo
xxxoxxx
oooxooo
xxxoxxx
oooxooo
ooxoxoo
xxoooxx
Nennen wir es: Maximaler Unnutz. A hat zwei 4er und elf 3er, aber nützen tun sie alle nichts.
Nein, der statische Teil einer künstlichen Intelligenz sollte nur aus Aussagen bestehen, welche beweisbar stimmen. Dann kann sie immer noch Heuristiken wie die Unterteilung der Spielphasen beim Schach entwickeln, um ihre Chancen, im Suchraum etwas Brauchbares in der nunmal nur vorhandenen Zeit zu finden, aus dem jeweiligen Blickwinkel heraus zu erhöhen.
Vorzugsweise sollte sie aber auch dort nach Gesetzen suchen, welche den Ausgang von möglichen Zugfolgen vorhersagen.
Betrachten wir dazu ein anderes Beispiel.
Schiebepuzzle.
Wie schiebt man die Teile herum, um das Bild zusammenzukriegen?
Nun, das ist nicht schwer. Man schiebt bei Numerierung von links nach rechts und dann wieder von links nach rechts eine Zeile tiefer und unter der Annahme, daß das letzte Feld frei bleibt, das erste Teil auf das erste Feld und so weiter, bis man beim n-1. Teil angekommen ist, wobei n die Anzahl der Zeilen und Spalten im quadratisch angenommenen Schiebepuzzle bezeichne, eine Annahme übrigens, welche völlig unwesentlich ist. Dieses n-1. Teil also schiebt man auf Feld n, um es anschließend mit einer kleinen 4er Rotation in einem 2x2-Feld zusammen mit dem n. Teil an die richtige Stelle zu bekommen.
Anschließend kümmert man sich analog um den Rest der ersten Spalte, um dann in einem Schiebepuzzle der Größe n-1 wie gehabt fortzufahren, bis man schließlich bei einem Schiebepuzzle der Größe 2x2 anlangt, in welchem man nur noch rotieren kann.
Betrachten wir das einmal genauer:
12 1. .1 31 31 3. .3 23 23
3. 32 32 .2 2. 21 21 .1 1.
Die Permutationsgruppe von 3 Elementen, hat 6 Elemente, von welchen uns hier aber nur 3 zur Verfügung stehen, nämlich die Rotationen (1)(2)(3), (123) und (132) , oder anders gesagt Stillstand, Schritt nach rechts und Schritt nach links.
Was heißt das für die Permutationsgruppe der Teile des Schiebepuzzles?
Nun ja, es heißt, daß wir mit unserem Algorithmus in einer Untermenge bleiben, welche nicht (n*n-1)! Elemente besitzt, sondern nur (n*n-1)!/2.
Und was heißt das?
Das heißt, das wir beweisen müssen, daß in einem Schiebepuzzle nur Permutationen möglich sind, deren Signum positiv ist.
Das ist indes einfach. Jede Permutation des Schiebepuzzles ist aus einer Abfolge von Vertauschungen des freien Felds mit einem Teil des Schiebepuzzles zusammengesetzt so, daß das freie Feld am Anfang und am Ende am selben Platz, dem letzten Feld, steht.
Eine solche Permutation hat die Form (ab) und ein negatives Signum. Wir müssen also zeigen, daß die Anzahl dieser Vertauschungen gerade ist.
Und nichts leichter als das. Denken wir uns schlicht ein Schachfeld. Das letzte Feld sei schwarz. Dann führt jede gerade Anzahl von Vertauschungen das freie Feld auf ein schwarzes Feld und jede ungerade das freie Feld auf ein weißes, und da wir von schwarz auf schwarz wollen, benötigen wir also eine gerade Anzahl von Vertauschungen.
Mit anderen Worten brauchen wir uns nicht darum zu sorgen, daß wir durch Rotation im verbleibenden 2x2-Puzzle nicht die richtige Anordnung zu Stande bringen, denn eine entsprechende Umordnung ist durch das Kaputtschieben des Ausgangsbildes nicht erreichbar.
Anders ausgedrückt können wir jedes Schiebepuzzle mit unserem Algorithmus Schritt für Schritt zurückschieben.
Hier ist es also so, daß wir ein Gesetz gefunden haben, welches uns die nötigen Züge zur Erreichung unseres Zieles vollständig an die Hand gibt, indem wir eine Weise erkannt haben, so zu ziehen, daß die späteren Züge den partiellen Erfolg der vorherigen nicht zu Nichte machen.
Übrigens gibt es auch ein, wenn auch nicht hinreichendes, so doch notwendiges Gesetz des Philosophierens. Es lautet:
- Sammle Erfahrungen, ordne sie und beginne von vorn.
Die Hinreichendheit eines Gesetzes bedeutet, daß es zur Lösung führt, die Notwendigkeit, daß es Unsinn ausschließt, meistens aber sind den Ausgang absehende Gesetze weder notwendig, noch hinreichend, um zum Ziel zu gelangen, nichtsdestotrotz aber von wesentlichem Nutzen zu diesem Zweck, wie man am Beispiel der Gesetze zu Vier gewinnt ersehen kann.
Labels: 12, computer design, formalisierung, intelligenz, mathematik, φιλοσοφία
Eingetragen Am/um
22:40
