Post on 23-Oct-2015
description
transcript
Kurz-Info:
Informatischer Inhalt: Spieltheorie
Jahrgangsstufe: Q1 bis Q2
Vorwissen: Java-Kenntnisse, Matrizen
Schlau gewinnt…und
wir zeigen wie!
Einführung in die
Spieltheorie
Ein Modul für das Schülerlabor Informatik -
InfoSphere- an der RWTH Aachen
Verfasser:
Christian Tetz Julian Schürkes Frank Weidler
Computer-Supported Learning Research Group Prof. Dr. U. Schroeder RWTH Aachen
Seite 1
Kurzinformation für die Lehrkraft
Titel: Schlau gewinnt…und wir zeigen wie! Einführung in die Spieltheorie
Schulstufe: Oberstufe
optimale Jahrgangsstufe: Q1-Q2
Themenbereich: Lösungskonzepte der Spieltheorie wie bspw. Nash-Gleichgewicht,
Min-Max-Algorithmus; ein Teilbereich der theoretischen Informatik.
EINORDNUNG IN GESETZLICHE RAHMENBEDINGUNGEN
Lehrplan NRW:
Konzepte des objektorientierten Modellierens als zielgerichtetes Vereinfachen und
strukturiertes Darstellen der Wirklichkeit am Beispiel von einfachen Spielen. Die
Darstellungen erfordern zum Teil Baumstrukturen, die den Bereich Datenstrukturen
tangieren. Ebenso werden Methoden in vordefinierten Klassen implementiert.
Bildungsstandards der GI:
Die Schülerinnen und Schüler (SuS) können mit Hilfe von verschiedenen
Darstellungsformen die spieltheoretischen Problemstellungen modellieren und
analysieren, wie es im Prozessbereich „Darstellen und Interpretieren“ gefordert wird.
Darüber hinaus werden Algorithmen zur Lösung von Problemen erarbeitet und getestet.
Einbindung in den Unterricht: Als Ausblick nach dem Erwerb von Java-Grundlagen in
die Welt der theoretischen Informatik.
Vorkenntnisse: Java Programmierkenntnisse (Variablen, Schleifen und Abfragen,
Arrays), das mathematische Konstrukt der Matrizen kennen (keine weiteren Kenntnisse
wie bspw. Gaußverfahren erforderlich)
Dauer: 4 Stunden
Inhaltsbeschreibung: In diesem Modul lernen die SuS anhand von vielen kleinen
Problemen die grundlegenden Konzepte der Spieltheorie kennen und wenden diese
direkt an. Dabei werden unter anderem die Themen wie das Nash-Gleichgewicht und
die Dominanz an einfachen Alltagsproblemen oder Spielen erschlossen. Zum Ende
werden die erlernten Strategien und Konzepte auf ein komplexeres Problem, wie Tic
Tac Toe angewandt. So entwickeln die SuS nach und nach ein Gefühl, wie man an
solche Probleme herangehen und einzelne erlernte Strategien miteinander verknüpfen
kann, um somit auch ein Problem, das mit einer Strategie alleine nicht lösbar wäre, zu
bewältigen.
Seite 2
LERNZIELE
Die SuS sollen einen allgemeinen Einblick in die Spieltheorie erhalten und zwischen den verschiedenen
Arten unterscheiden können.
Die SuS sollen verschiedene Lösungskonzepte verstehen und eine Auswahl dieser, wie beispielsweise das
Nash-Gleichgewicht, Dominanz etc. anwenden können.
Die SuS sollen die Darstellungsformen extensiv und Normalform von Spielen differenzieren können.
Die SuS sollen einen Einblick in die verschiedenen Informationsarten, auf denen die Lösungskonzepte
aufbauen, bekommen.
Die SuS können verschiedene Lösungskonzepte verknüpfen, um komplexere Probleme zu lösen.
FACHLICHE ANALYSE
In diesem Modul werden die unterschiedlichen Lösungskonzepte der Spieltheorie (Nash-Gleichgewicht, Dominanz, Minimax-Algorithmus) behandelt und die unterschiedlichen Arten der Spieltheorie (2-Personen- Nullsummenspiel, nicht-kooperative Spieltheorie) behandelt. Mit Hilfe des Verständnisses für Strategien werden kleine Java-Programme geschrieben, die zum einen Vertiefungscharakter haben und zum anderen aufzeigen wie Probleme automatisiert abgehandelt werden können.
2-Personen-Nullsummenspiel:
Nullsummenspiele beschreiben in der Spieltheorie Situationen, also Spiele im verallgemeinerten Sinne, bei
denen die Summe der Gewinne und Verluste aller Spieler zusammengenommen gleich null ist. Alle
Strategiespiele für zwei Spieler, bei denen es im Ergebnis nur auf Sieg, Unentschieden und Verlust ankommt,
kann man als Nullsummenspiele auffassen, wenn man einen Sieg mit +1 Punkt, ein Unentschieden mit 0
Punkten und einen Verlust mit -1 Punkt wertet. Am Ende eines solchen Spiels ist die Summe immer null (A
gewinnt und B verliert: 1+(-1) = 0; oder unentschieden: 0+0 = 0; oder A verliert und B gewinnt: -1+1 = 0).
Nash-Gleichgewicht:
Das Nash-Gleichgewicht ist ein zentraler Begriff der mathematischen Spieltheorie. Es beschreibt in nicht-
kooperativen Spielen eine Kombination von Strategien, eine für jeden Spieler, von der ausgehend kein
einzelner Spieler für sich einen Vorteil erzielen kann, indem er einseitig von seiner Strategie abweicht. In einem
Nash-Gleichgewicht bereut daher kein Spieler seine Strategiewahl. Die Strategien der Spieler sind wechselseitig
beste Antworten.
Dominanz:
Eine Strategie dominiert eine Andere strikt, wenn ihre Auszahlung (z.B. 1 für gewinnen und -1 für verlieren)
IMMER besser ist als die der Anderen. Dominiert eine Strategie die andere schwach, dann ist die Auszahlung
IMMER besser oder gleich groß.
Minimax-Algorithmus:
Der Minimax-Algorithmus ist ein Algorithmus zur Ermittlung der optimalen Spielstrategie für endliche Zwei-
Personen-Nullsummenspiele. Eine mit dem Minimax-Algorithmus berechnete Strategie wird Minimax-
Strategie genannt. Sie sichert dem betreffenden Spieler den höchstmöglichen Gewinn, der unabhängig von der
Spielweise des Gegners zu erzielen ist. Das aus den Minimax-Strategien beider Spieler gebildete Strategie-Paar
bildet ein Nash-Gleichgewicht. Bei Nicht-Nullsummenspielen, bei denen die Niederlage des Gegners nicht
Seite 3
zwangsläufig mit dem eigenen Gewinn zusammenfällt, liefert der Minimax-Algorithmus nicht unbedingt eine
optimale Strategie.
Nicht-kooperative Spieltheorie: Die Spieler können keine bindenden Verträge abschließen oder sich absprechen.
EINORDNUNG IN GESETZLICHE RAHMENBEDINGUNGEN
LEHRPLAN INFORMATIK
Sind im Unterricht einmal Algorithmen und Datenstrukturen behandelt und ist Java als Programmiersprache
erlernt worden, bietet sich dieses Modul gut an, dieses Wissen hier in einem Bereich der Spieltheorie
anzuwenden und zu vertiefen. Spiele werden von ihrer Problematik her logisch zerlegt, analysiert und in
verschiedenen Darstellungsformen beschrieben. Nach dem Erarbeiten eines Lösungsalgorithmus, wird dieser
von den SuS in der Programmiersprache Java implementiert.
VORGABEN ZUM ZENTRALABITUR
In diesem Modul werden grundlegende Strategien wie beispielsweise Dominanz und das Nash-Gleichgewicht
verwendet, um Spielsituationen zum bestmöglichen eigenen Nutzen zu verändern. Diese Strategien werden
theoretisch erläutert und sollen an kleinen Beispielen programmiert werden. Damit das gelingt sind Kenntnisse
aus dem Bereich I.1 "Konzepte des objektorientierten Modellierens" zwingend erforderlich. Gleichzeitig
vertiefen die Programmierübungen auch die Fertigkeiten dort.
Abstrakte Theorien werden immer leichter verständlich, wenn sie veranschaulicht werden. So werden auch
hier die Lösungsstrategien auf Basis von Grundinformationen, die aus der Spielsituation heraus entnommen
werden, in Form von Bäumen, Graphen oder Diagrammen dargestellt. Dabei steht das "Lesen" und die
Interpretation der Bäume etc. im Vordergrund. Die SuS sind damit zusätzlich auch selbst in der Lage diese
aufzustellen. Durch dieses erworbene Verständnis können dann Lösungswege erkannt und analysiert werden,
um im Anschluss daran die wie oben bereits erwähnte beste Möglichkeit auszuwählen. Durch die Verwendung
von Graphen und Bäumen kann hier eine weitere Einordnung in den Bereich I.2 "Datenstrukturen"
vorgenommen werden. Die Möglichkeit, mit verschiedenen Strategien manchmal zum selben Ziel zu gelangen,
kann unter anderem dem besseren Verständnis der verschiedenen Möglichkeiten von Suchalgorithmen
dienlich sein.
Zuletzt finden sich in diesem Model auch Inhalte aus dem Bereich III "Endliche Automaten und formale
Sprachen" wieder. Die SuS arbeiten in manchen Fällen auch mit Entscheidungsbäumen, deren grundlegendes
Prinzip dem eines nichtdeterministischen Automaten gleich kommt, in denen für jeden Zustand eine „richtige“
Entscheidung gefällt werden muss.
BENÖTIGTE UNTERRICHTLICHE VORAUSSETZUNGEN
Java Programmierkenntnisse (Variablen, Schleifen und Abfragen, Arrays)
das mathematische Konstrukt der Matrizen (keine weiteren Kenntnisse wie bspw. Gaußverfahren
erforderlich)
EINBETTUNG IN DEN SCHULUNTERRICHT
Dieses Modul eignet sich vertiefend auf die bereits gelernte Programmiersprache Java aufzusetzen. Es werden dabei nur grundlegende programmiertechnische Elemente verwendet wie Variablen Deklarationen, Schleifen,
Seite 4
Kontrollstrukturen und Datenstrukturen wie Arrays. Kenntnisse zur Objektorientierung werden nicht benötigt. Im Folgenden sind hier nun Anregungen zur Wiederholung der verwendeten Fertigkeiten sowie Aufgaben angegeben.
DIDAKTISCH/METHODISCHE SCHWERPUNKTSETZUNG
Beschreibung:
Das Modul ist in drei Phasen (Einstieg, Mini-Spiele und Abschluss) aufgeteilt. Zu Beginn wird das Einstiegsspiel
3D-Tic-Tac-Toe in Zweiergruppen gespielt, damit die SuS spielerisch an das Thema herangeführt werden und
einen kurzen Einblick bekommen.
Anschließend folgt eine Phase, in der die SuS grundlegende Strategien in Mini-Spielen erlernen und anwenden.
In kurzen Präsentationen wird Theoriewissen erläutert und mit Hilfe dessen anschließend Aufgaben zu dieser
Strategie bearbeitet werden. Da die Präsentationen den SuS in einem Moodle-Kurs zur Verfügung stehen, ist es
möglich, dass die SuS in einem unterschiedlichen Lerntempo arbeiten können. Durch die Unabhängigkeit der
einzelnen Mini-Spiele können die Unterschiede des Lerntempos aufgefangen werden.
Das Modul wird von der Programmierung einer KI des Spiels Tic-Tac-Toe abgeschlossen. Dort werden die
Strategien der Mini-Spiele aufgegriffen. Somit können die SuS ihr erlerntes Wissen anwenden und
kombinieren, um ein komplexeres Problem zu lösen.
Einstieg:
Die SuS spielen in Zweiergruppen das Online-Spiel 3D-Tic-Tac-Toe gegeneinander. Einer spielt mit einer
Anleitung, in der die perfekte Strategie beschrieben wird, der Andere spielt hingegen ohne Anleitung. Dabei
sollen die SuS an das Thema herangeführt werden und schon einmal den Sinn und Nutzen von Spielstrategien
erkennen, da der Spieler mit Anleitung besser abschneidet.
Mini-Spiele:
Die SuS lernen in vier Minispielen einige Lösungsstrategien der Spieltheorie (Nash-Gleichgewicht, Dominanz,
Minimax-Algorithmus).
1. Schnick-Schnack-Schnuck mit Brunnen:
In diesem Spiel sollen die SuS das Prinzip der Dominanz erlernen. Zuerst sollen sie eine Spielmatrix
aufstellen und anhand dieser erkennen, ob ein Element ein anderes Element dominiert. Dadurch
sollen die SuS sich eigene Gedanken zum Thema Dominanz machen und werden gleichzeitig auf die
Programmieraufgabe vorbereitet, da sie die einzelnen Elemente vergleichen, so wie es im Code später
auch umgesetzt wird. Anschließend erstellen die SuS unter Anleitung ein Programm, mit dem man
jede Spielmatrix auf Dominanz untersuchen kann. Die Anleitung ist in mehrere Teilaufgaben aufgeteilt,
damit die SuS immer genau wissen, was sie wo machen müssen.
Nun sollen die SuS überprüfen was passiert, wenn das dominante Element entfernt wird. Daran sollen
sie sehen, dass aus einem Spiel mit Dominanz auch ein Spiel ohne dominantes Element entstehen
kann.
Anschließend folgt eine Star-Wars-Edition, die die SuS mit Hilfe des Programms auf Dominanz
untersuchen. So können die SuS ihr geschriebenes Programm nochmals anwenden und sehen, dass
dies universell einsetzbar ist.
2. Gefangenendilemma:
Dieses Spiel beschäftigt sich mit dem Nash-Gleichgewicht. Anfangs spielen die SuS zu dritt das Spiel
selbst durch, um die Regeln und die Problematik zu verinnerlichen. Nachdem ihnen erklärt wurde, was
ein Nash-Gleichgewicht ist und wie man es bestimmt, bestimmen die SuS es für dieses Beispiel. So
Seite 5
wird das gerade erlernte Theoriewissen gefestigt. Anschließend erstellen die SuS wieder unter
Anleitung ein Programm, das für alle 2x2 Matrizen das Nash-Gleichgewicht bestimmt. Die Anleitung ist
wie im ersten Spiel in mehrere Unterpunkte unterteilt. Abschließend wenden die SuS ihr Programm
auf andere Strafen an. Dies hat wieder den Nutzen, dass die SuS erkennen, dass das Programm jede
Strafenkombination lösen kann.
3. Marktkampf:
Dieses Spiel ist thematisch eine Fortführung des Gefangenendilemmas. Die SuS beschäftigen sich also
weiter mit dem Nash-Gleichgewicht. Bevor sie dieses allerdings berechnen können, müssen sie die
gegebenen Daten aus der Baumdarstellung (Extensivform) in die Matrixdarstellung (Normalform)
umwandeln. So erkennen die SuS, dass es nicht nur eine Darstellungsform gibt und dass man die
Daten von einer Darstellungsform in eine andere überführen kann. Dann müssen die SuS erkennen,
dass man dieses Problem auch mit dem Nash-Gleichgewicht lösen kann. So wird überprüft, ob die SuS
gelernt haben, dass man solche Probleme mit dieser Strategie löst. Anschließend wird das im zweiten
Spiel geschrieben Programm auf 3x3 Matrizen erweitert, damit das gegebene Problem mit dem
Programm gelöst werden kann. So sehen die SuS, dass man vorhandene Programme leicht erweitern
kann.
Abschließend wird das Problem mit anderen Firmen und Gewinnen gestellt und von den SuS gelöst.
4. Nim-Spiel:
In diesem Spiel werden die SuS an den Minimax-Algorithmus herangeführt. Zuerst stellen die SuS den
Spielbaum für das Nim-Spiel mit gegebenem Anfangswert auf. Anschließend beantworten die SuS zum
besseren Verständnis des Baumes ein Paar Fragen in einem Moodle-Quiz. Nun folgt eine Erklärung des
Minimax-Algorithmus, der danach auf den Spielbaum angewendet wird. Es folgt zur Ergebnissicherung
wieder ein Quiz.
Abschluss:
Die SuS programmieren am Ende des Moduls einen Teil einer KI zum Spiel Tic-Tac-Toe. Dabei werden auch die
in den Mini-Spielen erlernten Strategien (wie der Minimax-Algorithmus) verwendet. Dies erfolgt wieder in einer
kleinschrittigen Anleitung. Außerdem werden große Teile des Programms vorgegeben, damit SuS sich nur auf
die KI konzentrieren können und sich nicht mit der Darstellung beschäftigen müssen.
Seite 6
VERLAUFSPLAN DES MODULS
Zeit Phase Inhalt Medium Sozialform
5 Min. Begrüßung
20 Min.
„Erster Einblick in die
Spieltheorie“ durch ein Spiel mit Anleitung
Ziel der Spieltheorie und Nutzen direkt am Spiel erkennen
3D-TicTacToe Lehrervortrag, Partnerarbeit
40 Min. (wird für
jedes der 4 Minispiele
wiederholt, also insges. 160 Min.)
Erarbeitung und Festigung
des Theoriewissens
anhand von Minispielen
Lösungsstrategien der Spieltheorie
Arbeitsblätter: ABSSS,ABGD,ABMK,
PowerPoint Präsentation und Nimspiel im Moodle
Partnerarbeit
60 Min.
Anwendung der gelernten
Lösungskonzepte auf
TicTacToe
Vernetzen der gelernten Konzepte
Arbeitsblatt: TicTacToe Partnerarbeit
QUELLENVERZEICHNIS
Min Max Algorithmus TicTacToe: http://cvpr.uni-muenster.de/teaching/ss12/KI/script/KI03-Spiele.pdf
Java Kenntnisse: http://openbook.galileocomputing.de/javainsel/
Bild Marktkampf: http://www.fuechse.info/faq/images/Schumann_kampf.jpg
Bild Gefangenendilemma: http://www.alteapotheke-online.de/images/gefangener.gif
Abschlussspiel: http://vincentloy.files.wordpress.com/2011/04/thinking_7_tnb.png
Bild Schnick Schnack Schnuck: http://view.stern.de/de/picture/1405190/Schere-Stein-Papier-Grau-Digiart-510.jpg
Seite 7
ANHANG
Modulvorbereitende Aufgaben:
GESCHACHTELTE SCHLEIFEN
Schleifen, und das gilt insbesondere für for-Schleifen, können verschachtelt werden.
Syntaktisch ist das auch logisch, da sich innerhalb des Schleifenrumpfs beliebige
Anweisungen aufhalten dürfen. Um fünf Zeilen von Sternchen auszugeben, wobei in jeder Zeile immer ein Stern mehr erscheinen soll, schreiben wir:
for ( int i = 1; i <= 5; i++ )
{
for ( int j = 1; j <= i; j++ )
System.out.print( "*" );
System.out.println();
}
Als besonderes Element ist die Abhängigkeit des Schleifenzählers j von i zu werten. Es
folgt die Ausgabe:
*
**
***
****
*****
Die übergeordnete Schleife nennt sich äußere Schleife, die untergeordnete innere
Schleife. In unserem Beispiel wird die äußere Schleife die Zeilen zählen und die innere die Sternchen in eine Zeile ausgeben, also für die Spalte verantwortlich sein.
Da Schleifen beliebig tief geschachtelt werden können, muss besonderes Augenmerk auf
die Laufzeit gelegt werden. Die inneren Schleifen werden immer so oft ausgeführt, wie die äußere Schleife durchlaufen wird.
Aufgabe 1: Gestalte die obige Ausgabe so um, dass folgendes Bild entsteht:
*****
****
***
** *
ARRAYS
Ein Array (auch Feld oder Reihung genannt) ist ein spezieller Datentyp, der mehrere
Werte zu einer Einheit zusammenfasst. Er ist mit einem Setzkasten vergleichbar, in dem
die Plätze durchnummeriert sind. Angesprochen werden die Elemente über einen
ganzzahligen Index. Jeder Platz (etwa für Schlümpfe) nimmt immer Werte des gleichen
Typs auf (nur Schlümpfe und keine Pokémons). Normalerweise liegen die Plätze eines
Arrays (seine Elemente) im Speicher hintereinander, doch ist dies ein für Programmierer nicht sichtbares Implementierungsdetail der virtuellen Maschine.
Seite 8
Jedes Array beinhaltet Werte nur eines bestimmten Datentyps bzw. Grundtyps. Dies
können sein:
elementare Datentypen wie int, byte, long und so weiter
Referenztypen
Referenztypen anderer Arrays, um mehrdimensionale Arrays zu realisieren
GRUNDBESTANDTEILE
Für das Arbeiten mit Arrays müssen wir drei neue Dinge kennenlernen:
1. das Deklarieren von Array-Variablen
2. das Initialisieren von Array-Variablen, Platzbeschaffung
3. den Zugriff auf Arrays. Das umfasst den Lesenden Zugriff ebenso wie den
schreibenden.
Beispiel
1. Deklariere eine Variable randoms, die ein Array referenziert:
double[] randoms;
2. Initialisiere die Variable mit einem Array-Objekt der Größe 10:
randoms = new double[ 10 ];
3. Belege das erste Element mit einer Zufallszahl und das zweite Element mit dem
Doppelten des ersten Elements:
randoms[ 0 ] = Math.random();
randoms[ 1 ] = randoms[ 0 ] * 2;
Schauen wir uns den ersten und dritten Punkt nun noch einmal genauer an.
DEKLARATION VON ARRAYS
Eine Array-Variablendeklaration ähnelt einer gewöhnlichen Deklaration, nur dass nach
dem Datentyp die Zeichen »[« und »]« gesetzt werden.
Beispiel
Deklariere zwei Feld-Variablen:
int[] primes;
Point[] points;
Eine Variable wie primes hat jetzt den Typ »ist Feld« und »speichert int-Elemente«, also
eigentlich zwei Typen.
Seite 9
Hinweis
Die eckigen Klammern lassen sich bei der Deklaration einer Array-Variablen auch hinter
den Namen setzen, doch ganz ohne Unterschied ist die Deklaration nicht. Das zeigt sich spätestens dann, wenn mehr als eine Variable deklariert wird:
int []primes,
matrix[], threeDimMatrix[][];
Das entspricht dieser Deklaration :
int primes[], matrix[][], threeDimMatrix[][][];
Damit Irrtümer dieser Art ausgeschlossen werden, sollten Sie in jeder Zeile nur eine
Deklaration eines Typs schreiben. Nach reiner Java-Lehre gehören die Klammern
jedenfalls hinter den Typbezeichner, so hat es der Java-Schöpfer James Gosling gewollt.
ARRAYS MIT INHALT FÜLLEN
Die bisherigen Deklarationen von Array-Variablen erzeugen noch lange kein Array-
Objekt, das die einzelnen Array-Elemente aufnehmen kann. Wenn allerdings die Einträge
direkt mit Werten belegt werden sollen, gibt es in Java eine Abkürzung, die ein Array-
Objekt anlegt und zugleich mit Werten belegt.
Beispiel
Wertebelegung eines Felds:
int[] primes = { 2, 3, 5, 7, 7 + 4 };
String[] strings = {
"Haus", "Maus",
"dog".toUpperCase(), // DOG
new java.awt.Point().toString(),
};
In diesem Fall wird ein Feld mit passender Größe angelegt, und die Elemente, die in der
Aufzählung genannt sind, werden in das Feld kopiert. Innerhalb der Aufzählung kann
abschließend ein Komma stehen, wie die Aufzählung bei strings demonstriert.
MEHRDIMENSIONALE ARRAYS
Java realisiert mehrdimensionale Arrays durch Arrays von Arrays. Sie können etwa für
die Darstellung von mathematischen Matrizen oder Rasterbildern Verwendung finden.
Dieser Abschnitt lehrt, wie Objekte für mehrdimensionale Felder initialisiert, aufgebaut
und abgegrast werden.
FELD-OBJEKTE MIT NEW AUFBAUEN
Seite 10
Die folgende Zeile deklariert ein zweidimensionales Feld mit Platz für 32 Zellen, die in
vier Zeilen und acht Spalten angeordnet sind:
int[][] A = new int[ 4 ][ 8 ];
Obwohl mehrdimensionale Arrays im Prinzip Arrays mit Arrays als Elementen sind, lassen
sie sich leicht deklarieren. Zwei alternative Deklarationen (die Position der eckigen Klammern ist verschoben) sind:
int A[][] = new int[ 4 ][ 8 ];
int[] A[] = new int[ 4 ][ 8 ];
ANLEGEN UND INITIALISIEREN IN EINEM SCHRITT
Ebenso wie bei eindimensionalen Feldern lassen sich mehrdimensionale Felder gleich
beim Anlegen initialisieren:
int[][] A3x2 = { {1, 2}, {2, 3}, {3, 4} };
int[][] B = { {1, 2}, {2, 3, 4}, {5} };
Der zweite Fall lässt erkennen, dass das Feld nicht unbedingt rechteckig sein muss. Dazu
gleich mehr.
ZUGRIFF AUF ELEMENTE
Einzelne Elemente spricht der Ausdruck A[i][j] an.(Die in Pascal übliche Notation
A[i,j] wird in Java nicht unterstützt. Die Notation wäre im Prinzip möglich, da Java im Gegensatz zu C(++) den Komma-Operator nur in for-Schleifen
zulässt.) Der Zugriff erfolgt mit so vielen Klammerpaaren, wie die Dimension des
Arrays angibt.
Beispiel
Der Aufbau von zweidimensionalen Feldern (und der Zugriff auf sie) ist mit einer Matrix
beziehungsweise Tabelle vergleichbar. Dann lässt sich der Eintrag im Feld a[x][y] in
folgender Tabelle ablesen:
a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] ...
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5]
a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5]
...
Aufgabe 2: Du hast nun gelernt wie ein- und zweidimensionale Arrays funktionieren.
Lege jetzt eine 3x3 Matrix mit den Zahlen 1-9 an. Verwende das oben aufgefrischte
Wissen zu Schleifen, um alle Elemente der Matrix aufzuaddieren. Gebe das Ergebnis aus. Es sollte dir bekannt sein ;-)
Zusatzaufgabe(Partner): Ihr braucht für diese Aufgabe vier Namen, vier Verben und
vier Adverbien und schreibt sie auf. Nun deklariert ihr drei 2-dimensionale Arrays vom
Typ String mit dem Namen n, v, a und initialisiert sie mit den jeweiligen Worten. Damit
habt ihr nun drei 2x2 Matrizen. Durchlauft sie genau wie in der Aufgabe davor und addiert die Elemente der Matrix in dieser Art:
Seite 11
n[0][0] + v[0][0] + a[0][0]
n[0][1] + v[0][1] + a[0][1] n[1][0] + …
Somit entstehen lustige Sätze wie „Leopold popelt oft.“ Viel Spaß! :-)
Seite 12
Arbeitsblätter
3D TicTacToe
Beschreibung: Jeder von euch kennt wahrscheinlich das Spiel Tic-Tac-Toe. Wer drei Kreuze in einer
Reihe hat, gewinnt. 3D-Tic-Tac-Toe ist eine Erweiterung ins Dreidimensionale. So hat man drei
normale Tic-Tac-Toe Spielfelder übereinander, sodass drei Ebenen entstehen. Man gewinnt bei dieser
Version ebenfalls, wenn man drei Kugeln in einer Reihe hat, dabei kann man allerdings die
verschiedenen Ebenen benutzen.
Seite 13
Aufgabe: Spielt das Spiel zu zweit gegeneinander. Ruft dazu den Link im Moodle auf. Einer von euch
bekommt eine Spielanleitung mit einer Spielstrategie. Wiederholt das Spiel mehrmals und achtet
darauf, ob derjenige mit der Spielstrategie öfters gewinnt.
Siege Spieler 1
Siege Spieler 2
Seite 14
Schnick-Schnack-Schnuck mit Brunnen:
Quelle: http://view.stern.de/de/picture/1405190/Schere-Stein-Papier-Grau-Digiart-510.jpg
Regeln:
Zwei Spieler wählen gleichzeitig eine der vier möglichen (Schere, Stein,
Papier, Brunnen) Symbole.
Dabei gelten folgende Regeln:
Schere schlägt Papier und verliert gegen Brunnen und Stein.
Stein schlägt Schere und verliert gegen Brunnen und Papier.
Papier schlägt Stein und Brunnen und verliert gegen Schere.
Brunnen schlägt Schere und Stein und verliert gegen Papier.
Aufgabe 1: Veranschaulicht das Spiel grafisch in einer 4x4 Matrix und entwickelt mit Hilfe
dieser Veranschaulichung eine Strategie, welches Element man am besten wählt und welches
lieber nicht. Stellt euch dabei folgende Fragen:
- Gibt es ein Element, das nie besser ist als ein Anderes?
- Gibt es ein Element, das besser ist als alle Anderen?
- Gibt es ein Element, das man nie wählen sollte?
Ruft nun die Powerpoint-Präsentation zur Dominanz auf, in der euch erklärt wird, wie man
herausfinden kann, ob ein Element besser ist als ein Anderes und wenn ja, welches.
Aufgabe 2: Programmiert mit Hilfe der grafischen Darstellung aus Aufgabe 1 ein
Programm, das überprüft, ob eine Strategie eine andere schwach dominiert und das
Ergebnis ausgibt. Benutzt dazu die Programmvorlage im Moodle.
2.1 Übertragt die Matrix in das zweidimensionale Array Spielmatrix
2.2 Deklariert zwei Variablen DominatorA und DominatorB, die als Zähler dienen, wie
oft z.B. die Strategie Schere besser ist als die Strategie Stein.
Seite 15
2.3 Erstellt ein String-Array der Länge vier in dem die vier Auswahlmöglichkeiten
stehen.
2.4 Überprüft die Matrix mit Hilfe von verschachtelten Schleifen auf Dominanz.
Überlegt euch vorher per Hand, wie ihr am besten alle Elemente der Matrix
miteinander vergleichen könnt und übertragt dieses Prinzip in 3 For-Schleifen
(siehe Code).
2.5 Gebt aus, ob eine Strategie die Andere dominiert. Falls ja, gebt aus welche
Strategien dies sind.
Aufgabe 3: Da kein Spieler ein dominiertes Element wählt, kann man es auch aus
dem Spiel streichen, da es niemand mehr wählen wird, wenn er intelligent spielt.
Stellt eine Matrix ohne das Element, das dominiert wird auf. Gibt es noch ein
dominantes Element? Vergleicht abschließend diese neue Version mit Schnick-
Schnack-Schnuck ohne Brunnen. Was fällt euch auf?
Aufgabe 4: Schnick-Schnack-Schnuck Starwars-Edition. Wir betrachten nun eine
Version des Spiels, in der man anstatt die vier üblichen Elemente vier Charaktere von
Starwars wählt. Dabei gelten folgende Regeln:
Luke siegt gegen Darth Vader und verliert gegen Yoda und den Imperator...
Luke Darth Vader Yoda Imperator
Luke 0 +1 -1 -1
Darth Vader -1 0 +1 +1
Yoda +1 -1 0 -1
Imperator +1 -1 +1 0
Seite 16
Ändert euer Programm so, dass es nun überprüft, ob bei dieser Variante auch ein
Element dominiert. Gebt die Antwort wieder in der Konsole aus. Speichert die
Änderungen in einem anderen neuen Dokument, damit euer Programm für die erste
Version nicht verloren geht.
Seite 17
Marktkampf
Quelle: http://www.fuechse.info/faq/images/Schumann_kampf.jpg
Beschreibung: Zwei Unternehmen (z.B. Adidas und Puma) überlegen, wie stark sie sich in Zukunft
auf dem Markt engagieren (z.B. Werbung schalten) wollen. Dabei hängt ihr Gewinn auch vom
Engagement des anderen Unternehmens ab. Der folgende Baum beschreibt, welche Gewinne sich
aus den unterschiedlichen Entscheidungen ergeben.
Seite 18
Aufgabe 1: Übertragt den Baum in eine 3x3 Matrix.
Aufgabe 2: Mit welcher euch bereits bekannten Spielstrategie lässt sich dieses Problem (welche
Werbeausrichtung beide Unternehmen am besten wählen, um für sich selbst den maximalen Gewinn
zu erhalten) lösen? Löst das Problem, indem ihr die bereits bekannte Spielstrategie zu diesem
Lösungskonzept anwendet.
Aufgabe 3: Erweitert das Programm zum Gefangenendilemma so, dass auch dieses Problem damit
zu lösen ist. Wenn ihr den veränderten Code speichert, dann wählt einen neuen Dateinamen aus,
damit eure alte Lösung nicht verloren geht.
Aufgabe 4: Wir betrachten nun die beiden Unternehmen Apple und Samsung. Welche
Werbeausrichtung sollten die Unternehmen wählen, wenn folgende Matrix die Gewinne beschreibt?
Gebt hierfür die neuen Werte und Namen in euer Programm ein.
(x,y) mit x = Gewinn von Apple in Mio. € und y = Gewinn von Samsung in Mio. €
Engagement auf
dem Markt: Samsung
Apple
gering mittel stark Gering (120,140) (100,160) (80,170) Mittel (130,120) (130,155) (120,140) Stark (160,100) (140,150) (110,120)
Seite 19
Quelle: http://www.alteapotheke-online.de/images/gefangener.gif
Gefangenendilemma:
Spielregeln:
Zwei Gefangene werden verdächtigt, gemeinsam eine Straftat begangen zu haben. Beide Gefangene
werden in getrennten Räumen verhört und haben keine Möglichkeit, sich zu beraten bzw. ihr
Verhalten abzustimmen. Die Höchststrafe für das Verbrechen beträgt sechs Jahre. Wenn die
Gefangenen sich entscheiden zu schweigen, werden beide wegen kleinerer Delikte zu je zwei Jahren
Haft verurteilt. Gestehen jedoch beide die Tat, erwartet beide eine Gefängnisstrafe, wegen der
Zusammenarbeit mit den Ermittlungsbehörden jedoch nicht die Höchststrafe, sondern lediglich von
vier Jahren. Gesteht nur einer und der andere schweigt, bekommt der erste als Kronzeuge eine
symbolische einjährige Bewährungsstrafe und der andere bekommt die Höchststrafe von sechs
Jahren.
Aufgabe 1: Fertigt zuerst eine Matrix an, in der die Strafen für beide Gefangenen für alle
Spielausgänge stehen. Spielt nun zu viert das Spiel nach. Setzt euch zu zweit zusammen, wobei einer
jeweils den Verdächtigen spielt und der andere den Kommissar. Anschließend treffen sich beide
Kommissare und stellen aufgrund der gewählten Strategien die Strafe ihres Verdächtigen fest und
teilen ihm diese mit.
Aufgabe 2: Wir wollen nun wissen, wie sich beide Gefangenen entscheiden, wenn sie das beste
Ergebnis für sich selbst erreichen wollen. Dies finden wir heraus, indem wir das Nash-Gleichgewicht
bestimmen. Das Vorgehen dazu wird euch in der Powerpoint-Präsentation "Nash-Gleichgewicht"
erklärt. Ruft diese nun im Moodle auf. Ermittelt anschließend mit Hilfe der Matrix die optimale
Seite 20
Spielstrategie, indem ihr den Algorithmus zur Bestimmung eines Nash-Gleichgewichts, der euch in der
Powerpoint-Präsentation erklärt wurde, ausführt.
Sammlung der Ergebnisse an der Tafel/Smartboard
Aufgabe 3: Programmiert einen Algorithmus, mit dem zu einer gegebenen Matrix das Nash-
Gleichgewicht ermittelt werden kann. Öffnet dafür den Programmcode im Moodle und erarbeitet
folgende Unterpunkte:
3.1 Legt zwei Arrays an, in denen die Strafen vom Gefangenen A und Gefangenen B stehen.
3.2 Für den Algorithmus müsst ihr die jeweiligen Maxima bestimmen. Beim Durchlaufen der Matrizen
müsst ihr euch die Maxima merken und auch an welcher Stelle sie gefunden wurden. Legt euch
hierfür 4 Variablen an, die diese Informationen für euch speichern.
3.3 Überlegt euch zunächst wie ihr in Aufgabe 2 vorgegangen seid, um die optimale Strategie zu
ermitteln. Übertragt dieses Vorgehen dann in die Schleifen und beachtet dabei die Hinweise aus
Aufgabe 3.2.
3.4 Überprüft ob euer Programm funktioniert, indem ihr das Ergebnis aus der Konsole mit dem aus
Aufgabe 2 vergleicht.
Aufgabe 4: Die Staatsanwaltschaft entscheidet sich dazu, die Strafen zu verändern. Wie sollten sich
die Gefangenen verhalten, wenn nun folgende Strafen gelten?
Benutzt hierfür euer Programm aus Aufgabe 3 und passt die Werte an.
(-x,-y) mit x = Jahre im Gefängnis für Gefangenen 1 und y = Jahre im Gefängnis für Gefangenen 2
Seite 21
Nim-Spiel
Beschreibung: Zwei Spieler sollen einen Stapel mit Münzen solange in unterschiedlich große Teile
aufteilen, bis es nicht mehr möglich ist. Ein Spielzug besteht somit aus dem Aufteilen des Stapels. Man
gewinnt das Spiel, wenn der Gegner am Zug ist, aber der Stapel nicht mehr aufteilbar ist.
Hier seht ihr die Darstellung für den Startwert 5. Spieler A hat den Stapel in Stapel der Höhe 4 und 1
aufgeteilt und Spieler B anschließend den Stapel der Höhe 4 in zwei Stapel mit der Höhe 3 und 1. Es gibt
also nun 3 Stapel. Einen Stapel mit der Höhe 3 und zwei Stapel mit der Höhe 1. Dies ist nur ein Teil des
Baumes für den Startwert 5.
Seite 22
Da Spieler B den Stapel nur noch in 2 gleiche Teile aufteilen kann, endet der Baum hier, weil es keine
weitere Möglichkeit gibt.
Aufgabe 1: Erstellt einen Spielbaum, in dem alle Spielmöglichkeiten dargestellt werden. Das Spiel wird
mit sieben Münzen gespielt. Öffnet nun das Quiz zum Nim-Spiel, in dem euch ein paar Fragen zu dem
Baum gestellt werden und spielt es durch.
- Wie viele verschiedene Spielverläufe gibt es?
- Wie viele Spielzüge kann es maximal/minimal geben? - Was bedeuten die einzelnen Ebenen des Baumes? - Wann gewinnt A und wann gewinnt B? Gibt es eine Beziehung zu den Ebenen?
Seite 23
Aufgabe 2: Man kann mit Hilfe eines Algorithmus bestimmen, welcher Spielzug für Spieler A der Beste ist.
Je nach Spiel kann man sogar direkt den Spielausgang erkennen. Dies geschieht mit Hilfe des Minimax-
Algorithmus. Ruft nun die Powerpoint-Präsentation zum Minimax-Algorithmus auf. Wendet anschließend
den Minimax-Algorithmus, der euch in der Powerpoint-Präsentation erklärt wurde, auf den Spielbaum an.
Beschriftet die Blätter, bei denen A gewinnt, mit +1 und die Blätter, bei denen A verliert, mit -1.
Untersucht das Ergebnis im Hinblick auf folgende Fragen:
- Wie geht das Spiel aus, wenn beide optimal spielen? - Wie geht das Spiel aus, wenn der Stapel in (6,1) und dann in (5,1,1) aufgeteilt wurde und ab dann
beide optimal spielen? - Kann man mit Hilfe des Baumes direkt für jede Spielsituation sagen, wie das Spiel ausgeht?
Seite 24
…als künstliche Intelligenz
Tic Tac Toe ist ein Spiel, das jeder von euch kennt und auch sehr einfach zu verstehen ist. Bestimmt
hat der eine oder andere auch seine persönliche Strategie oder Vorgehensweise, wie man am
schnellsten gewinnt oder seinem Mitspieler eine Falle stellt, dass wenn er einen „dummen“ Zug
macht und danach keine Chance mehr hat zu gewinnen. Wäre es nicht toll, wenn der Computer
einem diese Arbeit abnimmt? ;-) 1996 gelang es Deep Blue als erstem Computer der Welt den damals
amtierenden Weltmeister im Schach in einem Match zu besiegen. Doch heute wollen wir keine
Weltmeister zu Fall bringen, sondern eine K.I. (künstliche Intelligenz) schreiben, die ein cleveres
TicTacToe Match spielt.
Dazu benötigen wir den in diesem Modul bereits erwähnten Min-Max-Algorithmus. Ihr werdet auf
diesem Blatt Stück für Stück lernen wie der Algorithmus am Beispiel TicTacToe funktioniert und seid
dann in der Lage dies im Java Editor Eclipse in einem eigenen Programm zu verwirklichen. In den
vorgefertigten Code-Dateien findet ihr noch weitere Hinweise wie ihr vorgehen könnt um eure K.I. zu
programmieren. Also keine Angst das wird schon ;-)
1. Schritt:
Stellt euch vor ihr seid jetzt der Computer und bekommt vom Spieler eine Spielsituation als Eingabe.
Diese könnte dann in etwa so aussehen:
Du als Computer hast dein X in die Mitte gesetzt und der Spieler, hier als Kreis,
hat mit einem Zug auf das Feld oben in der Mitte geantwortet.
Tic
Tac Toe
Seite 25
Wir schauen uns nun alle möglichen Felder an auf die wir noch ein X setzen können. Das wären in
diesem Fall sieben Möglichkeiten
Unter all diesen Möglichkeiten müssen wir uns nun entscheiden, welche die
Beste ist und um das bewerten zu können machen wir nun weiter mit dem…
2. Schritt:
Wir errechnen für jede mögliche Position eine sogenannte Gewichtung aus, die angibt wie gut oder
schlecht der Zug für den Spieler ist. Dafür betrachten wir aber nicht allein unseren eigenen Zug,
sondern zusätzlich noch den des Gegners, damit wir mehr Informationen für unsere Analyse haben.
Ein Beispiel:
Angenommen wir setzen unser X nach oben links. Dann kann der Spieler zwischen
6 Positionen entscheiden, was ihr nun hier unten sehen könnt.
Hier beginnt es nun spannend zu werden. Für jeden der sechs möglichen Züge, die der Spieler
unternehmen kann, wird eine Gewichtung berechnet. Nehmen wir den Fall ganz links. Der Computer
hat bei dieser Spielsituation 4 Möglichkeiten zu gewinnen nämlich
zwei Mal diagonal, sowie einmal waagerecht (unten) und senkrecht (rechts).
Der Gegner hat nur die beiden Möglichkeiten waagerecht (unten) und senkrecht
(rechts).
Daher bekommt dieser den Wert 2. Das Gewicht ist somit die Differenz zwischen
der möglichen Anzahl der Spalten, Zeilen und Diagonalen, die der Computer noch
einnehmen kann(4) und der Anzahl der Spalten, Zeilen und Diagonalen, die der
Spieler noch vollständig einnehmen kann(2). Deswegen bekommt dieser Zug des
Computers das Gewicht 2. Wie ihr oben seht werden die Gewichte für alle Antworten des Spielers
Seite 26
ausgerechnet. Eine kleine Zahl bedeutet nach unserer Rechnung also, dass der Spieler die meisten
Siegchancen hat, wohingegen eine große Zahl für eine bessere Chance des Computers steht. Da der
Spieler natürlich nicht dumm ist, wird er sich für die Antwort entscheiden, die ein möglichst kleines
Gewicht hat (Minimum). Somit bekommt die Möglichkeit des Computers oben links sein X zu setzen
den Wert 1 zugewiesen, da dies der kleinste Wert unter den Gewichten darstellt.
3. Schritt:
Nach dem die Berechnungen aus Schritt 2 alle gemacht wurden sieht das Ergebnis schematisch
veranschaulicht so aus:
Seite 27
Nun wählt der Computer aus seiner Sicht die Möglichkeit mit dem größtmöglichen Gewicht aus
(Maximum). Diese wurde oben rot markiert und stellt den Zug des Computers dar.Dann antwortet
der Spieler seinerseits wiederum auf diesen Zug, welche die neue Spielsituation als Eingabe des
Computers für den Min-Max-Algorithmus ist.
Aufgabe 1)
Ihr werdet nun die elementaren Teile, die für diesen Algorithmus nötig sind selber programmieren
und am Ende ein lauffähiges Spiel starten können.
Also öffnet zunächst Eclipse. Unter dem Projektnamen Spieltheorie findet ihr bei den Sources das
Paket endspielSchuelerVersion und die drei Klassen: Gameloop, Spielbrett, TicTacToeKI. Für diese
Aufgabe öffnet ihr die Klasse Spielbrett und klickt euch durch bis zur Funktion gueltigerZug(int zug).
Es ist im Code aber auch noch mal deutlich gemacht wo sich Aufgabe 1 befindet, genau wie die
anderen Aufgaben.
Diese Funktion ist wichtig für den Schritt 1 der oben erläutert wurde. Sie prüft, ob ich überhaupt in
das Kästchen mit der Nummer zug setzen darf. Anders ausgedrückt: prüft ob das Kästchen frei ist.
Erst dann ist dies nämlich ein gültiger Zug. Implementiert also diese Funktion und gebt ein true oder
false zurück, je nachdem, ob der Zug gemacht werden darf oder nicht. Das Feld mit der
gleichnamigen Klassenvariablen ist so durchnummeriert:
0 1 2
3 4 5
6 7 8
Aufgabe 2)
Ebenfalls in der Klasse Spielbrett findet ihr die Funktion berechneGewicht(). Diese errechnet die oben
im Schritt 2 erwähnten Gewichte für eine Spielsituation wie beispielsweise hier. Falls ihr nicht mehr
wisst wie die Zahlen zustande kommen, lest es oben noch mal nach. Die X und O sind
in der Klassenvariablen feld gespeichert. Programmiert das Prinzip aus Schritt 2 hier
nach und gebt als Ergebnis eine Integer Zahl als das Gewicht (in diesem Fall 1) zurück.
Aufgabe 3)
Hier soll noch der letzte Schritt programmiert werden, in dem der Computer den für sich besten Zug
wählt. In der Klasse TicTacToeKI seht ihr die Funktion besterZug(Spielbrett aktuellesBrett) bei der ihr
euch nur auf die else-Bedingung der for-Schleife konzentrieren müsst. Die Schleife geht alle
Seite 28
möglichen Züge des Computers durch, prüft erst das schon zum Sieg reicht, falls nicht bekommt
dieser Zug mit der Funktion gegnerGewichte() eine Zahl. Wie im Schritt 3 könnt ihr in der Abbildung
die eingekreisten Zahlen für jeden Zu sehen (1,0,1,0 von links gelesen), die die Minima darstellen.
Das sind die Gegnergewichte. Ziel in dieser Aufgabe ist es unter den Zügen zuege, den Zug mit dem
maximalsten Wert zu finden und in besterCompiZug zu speichern.
Wenn die Aufgaben von euch korrekt gelöst wurden, könnt ihr die Gameloop.java öffnen, auf den
grünen Play-Button drücken und das Spiel startet ;-)
Quelle: http://vincentloy.files.wordpress.com/2011/04/thinking_7_tnb.png
Weiterführende Links:
Min-Max Algorithmus http://de.wikipedia.org/wiki/Minimax-Algorithmus
Alpha-Beta-Suche als Optimierung des Min-Max-Algorithmus http://de.wikipedia.org/wiki/Alpha-Beta-Suche
Dazu noch eine gute Präsentation von der Uni Münster http://cvpr.uni-
muenster.de/teaching/ss12/KI/script/KI03-Spiele.pdf
Expliziter Java Code für Min-Max mit Alpha-Beta Suche
http://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html