Informatik II (D-ITET)

Informatik II (D-ITET)
Übungsstunde 9, 05.05.2016
Hossein Shafagh, [email protected]
Distributed Systems Group, ETH Zürich
Ablauf
§  Besprechung von Übung 8
§  Hinweise für Übung 9 (Spielbäume, Reversi)
Lösung U8.A1a,b – Binäre Suche
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 7 17 25 33 47 56 62 65 66 68 70 78 89 92
li
mi
re
mi = (re-li)/2 + li;
Informatik II - Übung 9
3
Lösung U8.A1c – Binäre Suche (mit Faktor 3)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 7 17 25 33 47 56 62 65 66 68 70 78 89 92
li
re
mi
mi = (re-li)/3 + li;
Fazit: wenn ich nach kleiner Zahlen suche, die im Array vorhanden sind, ist
diese Methode schneller, im allgemeinen Fall aber schlechter (tiefer Baum)
Informatik II - Übung 9
4
Lösung U8.A1d – BinarySearch
§  Sub-arrays immer zu kopieren ist keine gute Idee
à lieber eine eigene Methode erstellen, die zusätzlich zwei int-Werte, begin und
end als Parameter nimmt:
public Value find(ArrayList<Unit<Key, Value>> haystack, Key needle)
{
return findRecursive(haystack, needle, 0, haystack.size());
}
private Value findRecursive( ArrayList<Unit<Key, Value>> haystack,
Key needle, int begin, int end)
{
...
}
Eclipse DEMO
Informatik II - Übung 9
5
Lösung U8.A2 – Tic-Tac-Toe
Strategie von
MAX
MAX
MIN
MAX
MIN
Informatik II - Übung 9
6
Lösung U8.A3a – checkMove: how to
ungültig!!
gültig?
Informatik II - Übung 9
7
Lösung U8.A3a – checkMove
§  boolean checkMove(GameBoard …,Coordinates c)
§  Feld muss frei sein!
§  Überprüfen alle Richtungen
§  Solange nicht mindestens eine Richtung „gültig“ ist…
for( int i = -1; i <= 1; ++i )
for( int j = -1; j <= 1; ++j )
if( i != 0 || j != 0 )
if( checkDirection(gb, player, c, new Coordinates(i, j) )
return true; //wäre ein möglicher Zug
return false; //kein möglicher Zug
§  trace( gb, player, pos, dir )
§  sum := #Steine von Gegner(player) in Richtung dir
§  Rückgabe := sum > 0 && letzter Stein gehört player
§  letzter Stein befindet sich an Koordinaten
(pos.x+sum*dir.x, pos.y+sum*dir.y)
Informatik II - Übung 9
Ähnliche Lösung:
Eclipse DEMO
8
Lösung U8.A3a – Reversi Tipps & Tricks
§  checkMove ist in reversi.GameBoard deklariert
§  boolean reversi.GameBoard.checkMove(int, Coordinates)
§  Weitere nützliche Methoden
§  boolean reversi.GameBoard.isMoveAvailable(int)
§  boolean reversi.GameBoard.validCoordinates(Coordinates)
§  int reversi.GameBoard.countStones(int)
§  int reversi.Utils.other(int)
§  …
§  Fazit: JavaDoc ist cool…
§  wenn andere sie geschrieben haben
Informatik II - Übung 9
9
Lösung U8.A3b – GreedyPlayer
§  Player-AI
§  für alle möglichen Züge
§  Simuliere Zug auf Kopie des aktuellen Boards
§  Bewerte die resultierende Situation
§  Speichere Zug und Bewertung in einer Liste
§  Sortiere die Liste / Such das/die Maximum/Maxima
§  Wähle den/zufällig einen maximalen Zug
§  Bewertungsfunktion (bisher)
§  Verhältnis eigene Steine vs. Gegnersteine
§  Datenstrukturen
§  MoveInfo: speichert ausgewertete Zuginformationen
§  Coordinates und Bewertung
§  List<MoveInfo> (z.B. eine ArrayList)
§  effizienter als ein Vector
§  praktischer als ein Array
Informatik II - Übung 9
Ähnliche Lösung
ohne Liste:
Eclipse DEMO
10
L8.A4a – Einfache Diebstrategie
§  Liefert die einfache Diebstrategie immer das optimale Ergebnis?
§  Ja, weil man alle Konfigurationen durchgeht
§  Gibt es immer genau eine optimale Lösung?
§  Nein, weil es mehrere optimale Lösungen geben kann
§  Beweis durch Gegenbeispiel:
§  Gegenstände <Gewicht, Wert>
[ <1,1>, <2,1>, <3,2> ]
§  Gmax = 3
§  Lösung 1 = [true, true, false]
§  Lösung 2 = [false, false, true]
Informatik II - Übung 9
11
L8.A4b – BruteForce.java
public Selection findBest( ArrayList<Integer> values,
ArrayList<Integer> weights, int maxWeight)
{
int last = (int) Math.pow(2, values.size());
int bestsum = 0;
Selection bestsel = new Selection(values.size());
Selection sel = new Selection(values.size());
for(int i = 0; i < last; i++)
{
sel.setBits(i);
if( sel.sum(weights) <= maxWeight ){
if( sel.sum(values) > bestsum ){
bestsum = sel.sum(values);
bestsel.setBits(i);
}
}
}
return bestsel;
}
Informatik II - Übung 9
12
L8.A4c – Backtracking.java
public Selection findBest(ArrayList<Integer> values, ArrayList<Integer> weights, int maxWeight)
{
if (values.size() != weights.size()) throw new
IllegalArgumentException("sizes of values and weights vectors are not equal");
// give initial selection and weight 0
Selection result = find(new Selection(0), 0, values, weights, maxWeight);
return result;
}
Informatik II - Übung 9
13
L8.A4c – Backtracking.java
// find(new Selection(0), 0, values, weights, maxWeight);
private Selection find(Selection selection, int weight, ArrayList<Integer> values,
ArrayList<Integer> weights, int maxWeight) {
final int depth = selection.size();
if (depth == values.size()) {
return selection;
}
Selection without = new Selection(depth + 1, selection.bits());
without.set(depth, false);
Selection resultWithout = find(without, weight, values, weights, maxWeight);
if (weight + weights.get(depth) <= maxWeight) {
Selection with = new Selection(depth + 1, selection.bits());
with.set(depth, true);
Selection resultWith = find(with, weight + weights.get(depth),values,weights, maxWeight);
if (resultWith.sum(values) > resultWithout.sum(values)) {
return resultWith;
}
}
return resultWithout;
}
Backtracking
Informatik II - Übung 9
14
L8.A4d – Zeitaufwand
§  Messung (2GHz Intel)
§  Brute Force: ~4.0s
§  Backtracking: ~0.08s
§  Backtracking benötigt ca. 2% der Zeit von Brute Force
§  G beträgt ca. 5x das Durchschnittsgewicht aus weights
§  Im Schnitt werden nur 5 Gegenstände aus 20 ausgewählt (25%)
§  Viele vorzeitige Abbrüche
Informatik II - Übung 9
15
Ablauf
§  Besprechung von Übung 8
§  Hinweise für Übung 9 (Spielbäume, Reversi)
Hinweise zu U9.A1
Spieltheorie/Spielbaumauswertung
a)  Bisschen Theorie
b)  Minimax-Algorithmus
c)  Optimale Strategie für MAX-Spieler
d)  Alpha/Beta-Algorithmus
Informatik II - Übung 9
17
U9.A1 – Spieltheorie
§  Bestanteile eines Spielbaums
§ 
§ 
§ 
§ 
Wurzel
Knoten
Kante
Blatt
à
à
à
à
Aktuellen Spielstellung
Spielzustand
Spielzug
Endzustand, (Spiel zu Ende)
Informatik II - Übung 9
18
U9.A1b – Minimax-Algorithmus
§  Algorithmus zur Ermittlung der optimalen Spielstrategie für
Nullsummenspiele
§  Sichert höchstmöglichen Gewinn bei optimaler Spielweise des
Gegners
§  Bei Nicht-Nullsummenspielen können andere Algorithmen besser sein
Informatik II - Übung 9
19
U9.A1b – Minimax-Algorithmus
?
0
0
0
+1
+1
0
0
-1
+1
-1
-1
Informatik II - Übung 9
+1
0
0
20
U9.A1c – Strategie für Max
§  Strategie
§  Eine Strategie (für Max) sei ein Graph, der aus dem Spielbaum
entsteht, indem man alle Kanten streicht und nur für jeden MaxKnoten eine einzige ausgehende Kante übrig lässt
Also i.A. eine Menge von Knoten/
Kanten, nicht nur ein Pfad!!
Informatik II - Übung 9
21
U9.A1d – Der α-β-Algorithmus
§  Der α-β-Algorithmus
§  Reduziert den Spielbaum durch Schnitte, aber liefert den gleichen MinmaxWert der Wurzel wie der eigentliche MinMax-Algorithmus
§  Der MinMax-Algorithmus bewertet den vollständigen Suchbaum. Dabei
werden aber auch Knoten betrachtet, die in das Ergebnis (die Wahl des
Zweiges an der Wurzel) nicht einfliessen. Die Alpha-Beta-Suche ignoriert
eben genau diese Knoten
§  α
grösster bisher bekannter Wert aller MAX-Vorfahren des MIN-Knotens
§  Ist relevant für Auswertung von Min-Knoten (Evaluierung der weiteren Nachfolgern
kann abgebrochen werden, sobald der berechnete Rückgabewert kleinergleich α ist)
§  β
kleinster bisher bekannter Wert aller MIN-Vorfahren des MAX-Knotens
§  Ist relevant für Auswertung von Max-Knoten (Evaluierung der weiteren Nachfolgern
kann abgebrochen werden, sobald der berechnete Rückgabewert grössergleich β ist)
Informatik II - Übung 9
22
U9.A1d – Der Baum
§  Berechnen Sie den Wert der Wurzel des folgenden Spielbaums mit
Hilfe der α-β-Methode
β-cut: MIN hat schon einen Knoten mit β < 7 → Vorzeitiger Abbruch!
Informatik II - Übung 9
23
U9.A2d – Der α-β-Algorithmus
Online Beispiel durchgerechnet:
§ 
§ 
http://www.vs.inf.ethz.ch/edu/I2/slides/Info2-ITET-AlphaBeta.pdf
http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm
Online JAVA Applet:
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
Informatik II - Übung 9
24
Hinweise zu U9.A2 – Reversi (Teil 3)
HumanPlayer
RandomPlayer
GreedyPlayer
nextMove()
nextMove()
nextMove()
wartet auf Eingabe
von der
Kommandozeile
wählt ein zufälligen
(aber gültigen!)
nächsten Zug
wählt nächsten Zug
anhand einer
einfachen,
nicht-rekursiven
Bewertungsfunktion
Download
Übung 7
Übung 8
Informatik II - Übung 9
MinMaxPlayer
nextMove()
wählt nächsten Zug
anhand Min-MaxAnalyse mit neuer
Bewertungsfunktion
Übung 9
25
U9.A2a – Reversi (Teil 3)
§  Auswertung von Spielbäumen
§  Implementieren Sie eine Methode, die den Spielbaum mit MinMax (oder
NegaMax) maximal bis zur Tiefe d auswertet (abwechselnd Max und Min)
§  Suchtiefe konfigurierbar
§  Rekursiver Ansatz
§  Spielbaum rekursiv aufbauen
§  Situation auf Tiefe d bewerten
§  Minmax auf erhaltene Wertung ergibt die Strategie
§  Alle Spezialfälle berücksichtigen (z.B. passen)!
§  Noch keine Zeitbegrenzung
Informatik II - Übung 9
26
U9.A2b – timeLimit
§  Zeitbegrenzung pro Zug:
§  Vor Ablauf von timeLimit Millisekunden soll ihre Methode nextMove() einen
gültigen Zug zurückgeben
§  Seht einen kleinen Zeitbuffer vor (Grössenordnung einige 10ms), das
Abbrechen und Resultat-zurückliefern passiert nicht sofort!
§  Möglicher Ansatz: eine out-of-time-exception werfen
Informatik II - Übung 9
27
U9.A2c – Bewertungsfunktion (I)
§  Als „Inspirationsquelle“ könnt Ihr u.A. folgenden Artikel benutzen:
§  „The Development of a World Class Othello Program“, Kai-Fu Lee and
Sanjoy Mahajan, 1990
§  Artificial Intelligence: A Modern Approach
§  Stuart Russell and Peter Norvig (2nd Edition, 2003)
Informatik II - Übung 9
28
U9.A2c – Bewertungsfunktion (II)
§  Mögliche „Bewertungsfunktionen“
§  Wie viele Steine werden umgedreht?
§  Wo liegen die umgedrehte Steine (innen/Rand)?
§  ....
§  Hinsichtlich dem Tournier empfiehlt sich
§  die Idee für die Bewertungsfunktion erst einmal mittels Pseudocode
festzuhalten
§  den Pseudocode weiter zu entwickeln
§  der Pseudocode gibt erste Hinweise darauf, was für Informationen für jeden
Zug berechnet werden müssen
§  aus den verschiedenen Versionen des Pseudocodes nach und nach den
Tournierspieler implementieren
Informatik II - Übung 9
29