Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 08 / spiel.doc < prev next >

Wrap

Text File | 1989-04-24 | 23.0 KB | 678 lines

Spieltheorie Dem Glück auf der Spur oder warum ein guter Schachspieler den Computer schlägt Die Spieltheorie ist ein relativ junger Zweig der Mathematik. Ihre grundlegenden Ideen stammen von dem Franzosen Emile Bo- rel, während die ersten fundierten mathematischen Aussagen 1926 von John v. Neumann ausgearbeitet wurden. In der Hauptsache beschäftigt sich die Spieltheorie mit Zwei- personen-Nullsummenspielen, das heißt zwei Personen treten in einem Wettbewerb gegeneinander an. Nullsummenspiel bedeutet nichts weiter, als daß der Gewinn des einen Spielers gleich dem Verlust des anderen ist. Ein solches Spiel wird vollstän- dig beschrieben durch eine Auszahlungstabelle, auch Spielma- trix genannt, in der alle Strategien der beiden Spieler A und B und der jeweils resultierende Gewinn/Verlust des ersten Spielers eingetragen werden: Hat Spieler A genau m Strategien (A1,...,Am), Spieler B sei- nerseits n (B1,...,Bn) und ist aij der Gewinn für Spieler A, wenn er Ai und sein Gegner Bj gebrauchen, so ist ││aij││ die zu dem Spiel gehörende Matrix. Beispiel: Der Spieler A wählt aus der Zahlengruppe -1, 0, 1 eine Zahl s, der Spieler B eine Zahl t aus. Nach Bekanntgabe der gewählten Zahlen erhält A den Betrag s(t-s)+ t(t+s) von B. Ist der Ausdruck negativ, so zahlt A den Betrag an B. Die Spielmatrix sieht wie folgt aus: Repro 1 B wählt │ -1 0 1 ────┼──────────── -1 │ 2 -1 -2 A wählt 0 │ 1 0 1 1 │ -2 -1 2 │ Skin-Spiel: A besitzt die Karten Karo As, Pik As und Karo Zwei, während B die Karten Karo As, Pik As und Pik Zwei in der Hand hält. Unabhängig voneinander spie~ len sie jeweils eine Karte aus. A gewinnt, wenn die Karten von gleicher Farbe sind, andernfalls gewinnt B. Der Gewinn entspricht dem Wert der Karte, die der Gewinner gespielt hat (As zählt 1). Aus diesen Regeln ergibt sich dann folgende Spielmatrix: Repro 2 │ Karo As Pik As Pik 2 ──┼────────────────────────────── Karo As │ 1 -1 -2 │ Pik As │ -1 1 1 │ Karo 2 │ 2 -1 -2 Auf den ersten Blick scheint diese Spiel B zu übervorteilen, da es mehr negative als positive Matrixelemente enthält. Die spätere genaue Analyse wird jedoch ergeben, daß der durchschnittliche Gewinn gerade 0 beträgt. Das Minimax-Prinzip Natürlich wünscht sich Spieler A einen möglichst großen Gewinn, während Spieler B den kleinstmöglichen Wert anstrebt; man nennt A daher auch Maximum-Spieler und B wird entsprechend Minimum-Spieler genannt. Wählt jetzt A eine Strategie Ai, so muß er damit rechnen, daß B mit derjenigen Strategie Bj antwortet, für die der Gewinn aij minimal wird. Der Wert der Strategie Ai ist also: αi = min aij j Natürlich wird A versuchen, den größten Zeilengewinn zu erhalten: α = max αi = max min aij i j Der Wert α heißt kleinster Wert des Spiels oder Maximin- Gewinn. Die Strategie Ai, für die α=αi ist, wird optimal genannt. Ähnlich gilt für B: ß = min ßj = min max aij. j j i Entsprechend wird ß größter Wert des Spiels bzw. Minimax- Gewinn genannt. In dem obengenannten Zahlenspiel ergibt sich: Repro3 │ B1 │ B2 │ B2 │ α ───┼────┼─────┼─────┼───── A1 │ 2 │ -1 │ -2 │ -2 ───┼────┼─────┼─────┼───── A2 │ 1 │ 0 │ 1 │ 0 ───┼────┼─────┼─────┼───── A3 │-2 │ -1 │ 2 │ -2 ───┼────┼─────┼─────┼───── ß │ 2 │ 0 │ 2 │ Gilt α=ß, so ist der Wert des Spiels ▓=α=ß. Der Matrixeintrag aij, der den beiden optimalen Strategien Ai und Bj entspricht, heißt Sattelpunkt. Er ist zugleich Zeilenminimum als auch Spaltenmaximum. Spiele, bei denen ein Sattelpunkt existiert, bei denen also der Maximin- Gewinn gleich dem Minimax-Gewinn ist, haben folgende Eigenschaft: Wählen beide Spieler ihre optimalen Strategien, so ist der Gewinn gleich dem Wert des Sattelpunktes. Weicht einer der beiden Spieler von seiner optimalen Strategie ab, so kann er dabei nur verlieren und niemals seinen Gewinn vergrößern. Unser Zahlenspiel gehört in diese Kategorie: a22 = 0 ist der Sattelpunkt, A2 und B2 sind die optimalen Strategien und der Wert des Spiels ist ▓=α=ß=0. Wählt A die Zahl 0, so muß B ebenfalls 0 wählen, um den Wert ▓ zu er- reichen. Weicht er ab, so wird er garantiert ein schlechteres Ergebnis erzielen. Das aber bedeutet ebenso, daß A auch nach Bekanntgabe der von B gewählten Zahl seine Wahl nicht bereuen wird; verlieren kann er mit 0 nie. Ebenso wird natürlich auch B argumentieren und stets seiner optimalen Strategie folgen. Damit ist klar, daß ein Zweipersonen-Nullsummenspiel mit Sattelpunkt seinen Reiz verliert, sobald es einmal vollständig analysiert worden ist. Interessanterweise besitzt auch das Schachspiel einen solchen Sattelpunkt; vom theoretischen Standpunkt aus wäre es daher als trivial zu bezeichnen. Mithin dürfte es jedoch kaum gelingen, eine vollständige Matrix zu erstellen und daraus die (vollständige) Lösung des Schachspiels abzulesen. Gemischte Strategien Weitaus interessanter sind Matrix-Spiele ohne Sattelpunkt, wie zum Beispiel das bekannte Knobelspiel: Unabhängig voneinander wählen beide Spieler ein Symbol aus der Menge "Stein", "Schere" und "Papier". Die folgende Matrix entspricht den gängigen Regeln (1 entspricht Gewinn A, -1 entspricht Verlust A, 0 entspricht Unentschieden): Repro 4 │ Stein │ Schere │ Papier ─────────┼───────┼────────┼──────── Stein │ 0 │ 1 │ -1 Schere │ -1 │ 0 │ 1 Papier │ 1 │ -1 │ 0 Es ergibt sich: α=-1╪ß=1. Offensichtlich läßt sich bei diesem Spiel keine optimale Strategie angeben. Um dennoch sowohl den Wert des Spiels als auch doch ein Verhaltensempfehlung ermitteln zu können, wird der Begriff der gemischten Strategie eingeführt: Eine gemischte Strategie ist ein m-Tupel (p1,...,pm), wobei der Wert pi die Häufigkeit angibt, mit der die Strategie Ai angewendet wird: Repro 5 m A* = (p1,...,pm), wobei Σ pi =1. i=1 Wählt nun B beispielsweise stets die Strategie Bj, so ist der mittlere Erwartungswert für A: Repro 6 m = Σ pi aij i=1 Arbeitet B ebenfalls mit einer gemischten Strategie, B*=(q1,...,qn), so gilt: repro 7 n m m n = Σ qj Σ pi aij = Σ Σ pi qj aij. j=1 i=1 i=1 j=1 Offensichtlich gilt für das Knobelspiel: A* =(1/3,1/3,1/3) und B* =(1/3,1/3,1/3) und damit ist ░=0, das heißt für beide Spie- ler ist es am günstigsten, jedes der drei Symbole mit der gleichen Wahrscheinlichkeit zu wählen. Der mittlere Erwartungswert beträgt dann 0. Wie können nun solche optimalen gemischten Strategien allgemein ermittelt werden? Graphische Lösung Es sei zunächst die Matrix dahingehend beschränkt, daß einer der beiden Spieler, zum Beispiel A, nur zwei Strategien zur Auswahl hat. Wählt man in einem Koordinatensystem als Abszisse die (gemischte) Strategie von A und als Ordinate die jeweilige Auszahlung, so kann jede Spalte der Spielmatrix durch eine Strecke repräsentiert werden, die den Gewinn abhängig von dem Mischungsverhältnis (p1 /p2) wiedergibt. Spieler B wird, da er der Minimum-Spieler ist, einen möglichst niedrigen Punkt in dem Diagramm anstreben. Da A maximiert, ist diejenige gemischte Strategie die Lösung, für die der niedrigste Strategiepunkt von B am höchsten liegt. Beispiel: Für ein nicht näher differenziertes Spiel mit der Matrix 2 -1 -1 0 2 1 stellt das Pascal-Programm Spieltheorie-Grafik (Listing 1) das Diagramm in Abbildung 1 auf. Das "maximierte Minimum" liegt hier bei p1 =0.25. Damit ist die optimale Strategie für A: A* =(0.25,0.75). Der Wert des Spiels ist auf der Ordinate abzulesen: ▒= 0.5. Leider lassen sich mit diesem Verfahren nur Spiele lösen, die eine 2xn-Matrix besitzen. Für eine 3xn-Matrix kann noch ein dreidimensionales Diagramm erstellt werden, wobei jedoch das Eintragen und Ablesen schon sehr unübersichtlich wird. Daher wird jetzt eine Methode vorgestellt, mit der beliebige nxn- Matrizen mit Hilfe der linearen Optimierung gelöst werden können. Damit läßt sich zum Beispiel zeigen, daß das oben genannte Skin-Spiel tatsächlich fair ist. Lineare Optimierung Die lineare Optimierung befaßt sich allgemein mit der Maximierung (bzw. Minimierung) einer von mehreren Variablen abhängigen Gleichung, wobei die Variablen durch ein System von Ungleichungen eingeschränkt werden. Diese Aufgaben spielen besonders im kaufmännischen Bereich eine entscheidende Rolle. Bereits das folgende, aus nur zwei Variablen bestehende Problem macht deutlich, wie aufwendig der Lösungsweg gestaltet ist. Daher ist die lineare Optimierung in der Praxis erst im Computerzeitalter anwendbar geworden. Ein Beispiel: Ein landwirtschaftlicher Betrieb möchte Kühe- und Schafhaltung einführen. Für diesen Betrieb gelten folgende Bedingungen: Der Platz für die Tiere ist beschränkt; es stehen Ställe für maximal 50 Kühe sowie für 200 Schafe zur Verfügung. Von den vorhandenen 72 Morgen Weideland fallen auf eine Kuh genau 1 Morgen, während pro Schaf 0.2 Morgen benötigt werden. Es können in einem Jahr höchstens 10000 Arbeitsstunden geleistet werden; auf eine Kuh fallen jährlich 150, auf ein Schaf 25 Stunden. Der jährliche Gewinn beträgt für eine Kuh 250 DM, für ein Schaf dagegen 45 DM. Die Aufgabe lautet, den jährlichen Gewinn zu maximieren. Die zu lösende Gleichung ist: Q(x1,x2) = 250x1 + 45x2. Das System der zu berücksichtigenden Ungleichungen stellt sich wie folgt dar: Repro 8 x1 ≤ 50 x2 ≤ 200 x1 + 0.2 x2 ≤ 72 150 x1 + 25 x2 ≤ 10000 x1 ≥ 0, x2 ≥ 0. Die Simplex-Methode Alle Aufgaben dieser Art werden mit Hilfe der sog. Simplex- Methode gelöst: Gegeben sei eine Zielfunktion Q mit n Variablen x1,...,xn und ein Ungleichungssystem mit m Ungleichungen. Die Simplex-Methode ermittelt das Minimum der jeweiligen Zielfunktion. Um auch eine Maximierungsforderung lösen zu können, muß die Gleichung mit (-1) multipliziert werden: Q(x1,x2) = -250x1 -45x2 = Min! . Gearbeitet wird im Simplex-Verfahren mit folgendem Schema: repro 9 │... i ... │ ────┼──────────────┼─────┬─────── ... │... ... ... │ ... │ ... │ │ │ k │... aki ... │ bk │ bk/aki │ │ │ ... │... ... ... │ ... │ ... ────┼──────────────┼─────┼─────── │... zi ... │ Q │ Zu Beginn wird das Ungleichungssystem in Form der Matrix ║a║ und dem Vektor │b│ in das Schema eingetragen. Die letzte Zeile erhält die -zi, das heißt die negativen(!) Komponenten der xi (i=1,...,n). Die Zielfunktion Q hat zunächst den Wert 0. Die Spalten und Zeilen werden der Reihe nach durchnumeriert (1,...,i,...,n, n+1,...,k,...,n+m). Für unser Problem ergibt sich damit die folgende Anfangsbelegung: repro 10 │ 1 2 │ ─────┼──────────────┼───────┬── 3 │ 1 0 │ 50 │ 4 │ 0 1 │ 200 │ 5 │ 1 0.2 │ 72 │ 6 │ 150 25 │ 10000 │ ─────┼──────────────┼───────┼── │ 250 45 │ 0 │ Für jeden weiteren Schritt ist nun ein neues Schema anzulegen. Jeder Schritt besteht aus der Auswahl eines Pivotelements aus der Matrix ║a║ und dem darauffolgenden Spalten- und Zeilentausch der durch das Pivotelement festgelegten Spalte/Zeile: I. Auswahl des Pivotelements: 1.) Zunächst wird ein zi >0 gesucht. Ist keins mehr vorhanden, so ist der Algorithmus be- endet und die Lösung aus dem Schema ablesbar. Andern falls ist durch den Index i die Pivotspal- te bestimmt. 2.) In die zu Beginn freigehaltene Spalte wird für alle bk der Quotient bk/aki (i entspricht der Pivotspalte) eingetragen, wenn das Element aki >0 ist. Wird kein solches Element gefunden, so ist der Algorithmus an die- ser Stelle zu unterbrechen. 3.) Unter diesen Quotienten bestimmt der kleinste die Pivotzeile k. II. Tausch. 1.) An die Stelle des Pivotelements aki tritt 1/aki. 2.) Alle Zahlen der Pivotzeile (auch das bk) werden ersetzt durch ihr 1/aki -faches, alle Zahlen der Pivotspalte (auch das zi) durch ihr -1/aki -faches. 3.) Alle übrigen Zahlen (auch das Q) werden nach folgender Regel (dersog. Rechteckregel) ersetzt: repro 11 P.-spalte P.-zeile aki ... x ... ... y ... z z wird ersetzt durch: z-(xy)/aki (so gilt z.B. für Q: Q -> Q - (bk zi )/aki) 4.)Die Indizes i und k sind zu vertauschen. Bei allen Ersetzungen ist übrigens zu beachten, daß nie die neuen, bereits ermittelten Zahlen verwendet werden; es sind stets die Zahlen aus dem alten Schema zu verwenden! Mit dem Pascal-Programm "Simplex" (Listing 2) kann jeder Lösungsschritt genau verfolgt werden. Das Verfahren endet, wenn in I.1) kein zi >0 oder in I.2) kein aki >0 mehr gefunden werden kann. In unserem Beispiel ergibt sich als letztes Schema: repro 12 │ 5 6 │ ────┼───────────────┼────────┬── 1 │ -5 0.04 │ 40 │ 4 │ -30 0.2 │ 40 │ 3 │ 5 -0.04 │ 10 │ 2 │ 30 -0.2 │ 160 │ ────┼───────────────┼────────┼── │-100 -1 │ -17200 │ Die Lösungen stehen am Ende der Zeilen, die die anfänglichen Indizes der Spalten beinhalten, das heißt: x1 = 40, x2 =160 Die Zielfunktion Q hat den Wert: Q(x1,x2)=-17200. Der Betrieb sollte sich also 40 Kühe und 160 Schafe anschaffen, um in einem Jahr den Maximalgewinn von 17200 DM zu erzielen. Besteht in der Aufgabenstellung das Ungleichungssystem aus den Zeichen "≥", so ist das Schema zu Beginn zu stürzen: Die Ungleichungen werden in die Spalten der Matrix eingetragen, der Vektor b und die Komponenten der Zielfunktion tauschen ebenso ihre Plätze wie die Indizes (erst werden die Zeilen, dann die Spalten numeriert). Die Lösungen sind in diesem Fall natürlich am Ende der jeweiligen Spalte ablesbar. Die Forderung für die Zielfunktion besteht hierbei in der Maximierung; gegebenenfalls ist diese wieder mit (-1) zu multiplizieren. Umformung von Matrix-Spielen in Aufgaben der linearen Optimierung Ziel dieser Einführung in die lineare Optimierung war ja, eine Möglichkeit zu finden, für beliebige nxn-Matrizen eine gemischte Strategie als Lösung anzugeben. Diese Matrix-Spiele lassen sich nämlich ohne Schwierigkeiten in Probleme der line- aren Optimierung umsetzen. Dazu ist es zunächst notwendig, den sogenannten Hauptsatz der Spieltheorie, der 1926 von J. v. Neumann bewiesen wurde, anzugeben: Es seien eine Auszahlungsmatrix (aij) und die gemisch ten Strategien A* =(p1 ,...,pm) und B* =(q1,...,qn) gegeben. Der für A zu erwartende Durchschnittsgewinn beträgt dann minde- stens: m min Σ pi aij. j i=1 Da A der Maximum-Spieler ist, wird er seine Strategie A* so wählen, daß dieser Wert möglichst groß wird: m 1 = max min Σ pi aij . A* j i=1 Entsprechend gilt für B: repro 15 n 2 = max min Σ qj aij . B* i j=1 Der Hauptsatz der Spieltheorie sagt nun aus, daß der Wert des Spiels ▒=▒1 =▒2 ist. Der Beweis des Hauptsatzes ist äußerst komplex und daher an dieser Stelle nicht wiederzugeben; interessierte Leser können ihn in (1) nachlesen. Betrachten wir nun noch einmal das Skin-Spiel mit der Auszahlungsmatrix: repro 16 │ B1 B2 B3 ────┼────────────────── A1 │ 1 -1 -2 │ A2 │ -1 1 1 │ A3 │ 2 -1 -2 Oben wurde bereits gesagt, daß A mit einer Strategie A* =(p1,p2,p3) den Gewinn repro 17 3 min Σ pi aij j i=1 erwarten darf. Daraus folgt, daß für alle j gilt: a1j p1 + a2j p2 + a3j p3 ≥ ▒. Wird jetzt x1 = pi /▒ gesetzt, so ergibt sich: a1j x1 + a2j x2 + a3j x3 ≥ 1. Außerordentlich wichtig ist natürlich, daß der Wert ▒ nicht 0 wird! Daher müssen zunächst alle Wert der Spielmatrix durch Addition einer Konstanten positiv werden. Nach Lösung der Optimierungs-Aufgabe muß diese Konstante selbstverständlich von dem ermit- telten Wert ▒ wieder subtrahiert werden. Damit steht bereits das Ungleichungssystem fest. Der Wert, den A maximieren will, ist natürlich ▒, das heißt: x1 + x2 + x3 = 1/▒ (p1 + p2 + p3) = 1/▒ = Min!. Für das Skin-Spiel gilt also (die Konstante ist 3): repro 18 4x1 +2x2 +5x3 ≥ 1 2x1 +4x2 +2x3 ≥ 1 x1 +4x2 + x3 ≥ 1 x1 +x2 + x3 =Min! Entsprechendes gilt für die gemischte Strategie von B. Beide Aufgaben können in ein und demselben Sche- ma mit dem Simplex-Verfahren gelöst werden: repro 19 │ y1 y2 y3 │ ────┼────────────────┼───┬── x1 │ 4 2 1 │ 1 │ │ │ │ x2 │ 2 4 4 │ 1 │ │ │ │ x3 │ 5 2 1 │ 1 │ ─────┼────────────────┼───┼── │ 1 1 1 │ 0 │ Als Lösung ermittelt unser Programm folgendes Schema: Repro 20 │ x3 x2 y2 │ ───┼───────────────────────┼───────┬─── x1 │ -0.78 -0.06 0.22 │ 0.17 │ │ │ │ y3 │ -0.11 0.28 0.89 │ 0.17 │ │ │ │ y1 │ 0.22 -0.06 0.22 │ 0.17 │ ───┼───────────────────────┼───────┼─── │ -0.11 -0.22 -0.11 │ -0.33 │ Der Wert der Zielfunktion ist -1/3 und damit ist ▒=3. Tritt im Lösungsschema eine Variable xi bzw. yj nicht wie erwartet in einer Zeile/Spalte auf, so bedeutet dies, daß die jeweilige Strategie nutzlos ist, das heißt das pi bzw. qj ist 0. Die gemischten Strategien lauten also: A* = ▒(x1,x2,x3) = (0,2/3,1/3) sowie B* = ▒(y1,y2,y3) =(0.5,0,0.5). Als Wert des Skin-Spiels ergibt sich ▒-3 = 0, das heißt, das Spiel ist tatsächlich fair! Das Fallenlassen des Strategiepaares (A1,B2) bedeutet, daß die verkleinerte 2x2-Matrix gebildet aus den restlichen Strategien dieselbe Lösung liefert, wie auch das Programm aus der 1. Folge bestätigt, das die graphische Lösung liefert. Weitreichende Anwendungen Möglicherweise haben Sie den Eindruck, daß es sich bei der Spieltheorie um eine bloße mathematische Spielerei handelt. Genau das Gegenteil ist jedoch der Fall: Insbesondere auf dem militärischen Gebiet spielt sie eine erhebliche Rolle, wenn verschiedene Angriffs- und Verteidigungsstrategien gegeneinander abgewägt werden müssen. Dementsprechend fallen auch die bekanntesten und weitreichendsten neuen Entwicklungen auf diesem Gebiet in die Zeit des zweiten Weltkriegs, nachdem die Spieltheorie nach ihrer ersten Erwähnung 1926 kaum beachtet wurde. Ein kleines, aber durchaus nicht triviales Beispiel soll (trotz seiner Einfachheit) einmal andeuten, wie die Spieltheorie in der Praxis angewendet werden kann: Neben dem Spiel zweier menschlicher Gegner spielt der Wettstreit Mensch gegen Natur die zweite große Rolle in der Anwendung der Spieltheorie. Ist das "Verhalten" der Natur unbekannt, so muß mit der für den menschlichen Spieler unangenehmsten "Strategiewahl" der Natur gerechnet werden: "Ein Arzt hat eine Krankheit zu behandeln, die durch zwei verschiedene, von ihm nicht unterscheidbare Erreger verursacht wird. Er hat ebenso keinen Anhaltspunkt darüber, wie häufig der eine bzw. der andere Erreger die Ursache ist. Zur Behandlung stehen ihm zwei verschieden Medikamente zur Verfügung, wobei die Herstellerfirma ermittelt hat, daß das erste Medikament einen durchschnittlichen Heilungserfolg von 60% verspricht, falls der erste Erreger die Krankheit verursacht hat, ansonsten beträgt die Erfolgsquote 40%. Für das zweite Medikament lauten diese Werte 30% bzw. 90%. Mit welchen Häufigkeiten sollte der Arzt nun das erste bzw. das zweite Medikament anwenden, um einen maximalen Heilungserfolg zu gewährleisten?" Zur Lösung dieses Problems wird die folgende x 2 2-Spielmatrix aufgestellt und analysiert: repro 21 │ E1 E2 ───┼──────────── M1 │ 60% 40% │ M2 │ 30% 90% Die mit den bereits vorgestellten Methoden ermittelte Lösung lautet: Wenn der Arzt in 75% aller Fälle das erste Medikament anwendet, so beträgt sein durchschnittlicher Heilungserfolg mindestens 52,5%. Die "optimale Strategie" der Natur, die für den Arzt unangenehmste Verteilung der Erreger, lautet: (0.625,0.375). Diese Einführung behandelte vorwiegend die mathematische Seite der Spieltheorie als notwendige Grundlage. Es gibt jedoch erstaunlich viele praktische Anwendungen; wer sich für ein bestimmtes Gebiet interessiert, der sei auf die folgende Li- teraturauswahl verwiesen. In einem Teil davon werden Probleme aus einem begrenzten Fachbereich mit Hilfe der Spieltheorie formalisiert. Literatur: 1 Stefan Vajda: "Einführung in die Linearplanung und die Theorie der Spiele", R.Oldenbourg 1967 2 Callatz, Wetterling: "Optimierungsaufgaben", Springer Verlag 1966 3 Dr. Ernst Herrmann: "Spieltheorie und lineares Programmieren", Au- lis Verlag Deubner & Co KG Köln 1964 4 Douglas R. Hofstadter: "Metamagicum", Klett-Cotta 1988 5 Spektrum der Wissenschaft, A.K.Dewdney: "Compu- ter-Kurzweil", 1/1988, S. 8ff. 6 Max Woitschach: "Strategie des Spiels", Deutsche Verlags-Anstalt Stuttgart 1968 7 Rainer Künsken: "Eine Untersuchung über Macht- beziehungen mit Hilfe der Spieltheorie", Disser- tation an der TU Berlin 1976