An der TU München habe ich in einer Informatik-Vorlesung Anfang der 70iger Jahre bei Professor Paul folgendes schönes Beispiel für Algorithmen gehört:
Es gilt zu entscheiden, ob bei bestem Spiel der Anziehende (der Führer der weißen Steine) aufgrund des Anzugvorteils bei bestem Spiel beider Parteien zwingend gewinnt oder ob es nur zum Remis reicht (dass Schwarz gewinnt ist aus schachlichen Gründen sehr unwahrscheinlich).
Diese Frage ist meines Wissens bis heute nicht gelöst. Dass sie aber eindeutig lösbar ist, wurde von Professor Paul aufgezeigt.
Er hat folgendes Vorgehen zur Beantwortung dieser Frage vorgeschlagen: Man konstruiere einen Baum, der alle möglichen Züge enthält. Man fügt einfach in jeder Ebene alle Zugmöglicheiten abwechselnd von Schwarz und Weiß hinzu. Im ersten Zug sind das wohl 20 Züge für Weiß (16 Bauernzüge und 4 Springerzüge), dann genauso viel für Schwarz. Dann ist Weiß dran, da gibt es wieder eine gewisse (stellungsabhängige) Anzahl von Zügen usw.
Wenn man diesen Baum komplett erstellt hat (was freilich nicht möglich ist), dann muss man nur noch von den Endstellungen (Ende der Partie, durch Matt, Patt oder nicht mehr zu gewinnende Position) alle Knoten des Baum markieren und kann dann leicht sehen, ob es einen zwingenden Gewinn für Weiß gibt, oder ob es doch nur zum Remis reicht. Algorithmisch ist das ganz einfach.
Das Beispiel hat mich seit langem fasziniert. Der entwickelte Algorithmus beweist sehr effektiv, dass die Frage eindeutig zu beantworten ist. Durch die Ineffizienz wird aber mit mit diesem Algorithmus diese Frage nie zu beantworten sein (bestimmt aber irgendwann mal auf andere Art und Weise).
Professor Paul wollte mit seinem Beispiel den Unterschied zwischen Effizienz und Effektivität aufzeigen.
Für Fragen, die ganz einfach erscheinen, findet man oft keine Antwort, selbst wenn man beweisen kann, dass es eine Antwort gibt. So ist das auch in unserem Leben: Manchmal glauben wir sogar an das Funktionieren von „Algorithmen“, obwohl diese uneffizient und uneffektiv sind.
RMD
Wird geladen ...
4 Antworten
It is very doubtful whether the result of a perfect chess game can be established („eindeutig lösbar“). I certainly do not share Roland’s belief that this will ever be proved. With current views about the size and age of the universe, there is neither enough material to store the game trees he describes, nor enough time to carry out the calculation before all useful energy in the universe is used up. Incidentally, the algorithm he describes is very inefficient. A given position can be reached by very many paths, so this algorithm evaluates every position many times over.
The best algorithm considers every possible position of the pieces. Some of these are drawn (stalemate or not enough material left for checkmate), some are checkmate. Next, one considers all position just one move away from these (decided) positions. One continues like this till all possible positions have been dealt with. This is the algorithm which is used to make computers much better endgame players than any human. The available storage on a good computer is sufficient to deal with endings up to about 7 pieces. Using all computers in the world for years, perhaps one could solve all 9 piece endings. In a few thousand years, perhaps 11 piece endings can be solved like this. I do not believe the 32 piece „ending“ that is the normal chess starting position will ever be solved.
If chess is ever „solved“, one can move on to the harder case of Go.
Nur zur Erläuterung: Mit meiner Geschichte wollte ich zeigen, dass man beweisen kann, dass Dinge entscheidbar sind, auch wenn man noch nicht weiß, wie das Ergebnis aussehen wird.
In diesem Fall durch Definition eines Algorithmus, der zeigt, dass es zwingend eine Aussage gibt wie z.B. „Weiß gewinnt bei bestem Spiel (A)“ oder „Bei bestem Spiel ergibt sich zwangsläufig Remis (B) oder (Erstaunlicherweise verliert Weiß bei bestem Spiel (C).
Derselbe Algorithmus ist leider ineffizient (warum ist auch jedem klar) und man kann mit diesem nicht herausfinden, ob A, B oder C richtig ist.
Ich glaube aber, dass die Entwicklung der Schachtheorie und -computer auf einem guten Wege sind, zumindest bald eine belegbare Vermutung für diese Problemlösung zu finden.
Ob die Frage, ob der Anziehende zwingend gewinnt, bei Go wirklich systemisch/mathematischer schwieriger ist als beim Schach, kann ich nicht entscheiden. Soweit ich Go kenne, bin ich mir da nicht sicher.
Aber die Frage und vor allem die Lösungsstrategie zu dieser Frage finde ich sehr interessant. Würde mich freuen, wenn ein Experte sich dazu äußern würde, auch an (guten) Links ins Internet zu diesen Themen bin ich sehr interessiert.
I understand an „inefficient algorithm“ differently. It is not inefficient to try to drown a fish. It just does not work. First a bit more detail about the good exact algorithm for evaluating endgames.
For every possible position , one needs two bits to record whether the position is win, draw, loss or not yet calculated (e.g. from the white side). Each piece is on one of 64 squares, (or has been captured). A pawn can stand on only 48 squares, but may get promoted, so afterwards it can be on any of the 64 squares. If a piece is captured, its position can be represented as the same as one of the kings, so that one can work with the convenient number 64, rather than 65. So to evaluate a position with 6 pieces (including the two kings), one needs storage for 2x64x64x64x64 x64x64 bits; already 16Gbytes (But rather more storage than that is needed, since it makes a difference which side is to move, and it makes a difference whether one side or both can still castle, and whether en-passant capture is possible. Furthermore it may be good for each calculated position to store the number of moves needed till the game finishes. This helps find the shortest win, and helps deal with the 50 move rule).
The amount of storage to „solve“ the initial position this way is a number with about 60 digits.
Advances in chess theory and computers are not beginning to get near to this.
Personally, I „believe“ a perfect game would be drawn. (This statement is philosophically problematic, as I do not believe it can ever be proved). Huge collections of chess games show that in a Sicilian defence White statistically has only slightly the better chances. Only to a small extent, is this because this is a defence that is chosen by strong players. (It gives them good chances of beating a weaker opponent).
GO is harder, because the board is bigger. It has 361 points, each of which is empty, or occupied by White, or Black. This gives about 3 to the power 361 possible positions, a number with about 170 digits.
A draw at Go is extremely rare, and it is clear that the first move is a significant advantage. It is not known by exactly how many points the first player should win. But a mathematically correct proof that the perfect game is not a draw will not be produced.
This is the only significant board game where the best humans beat the best computers.