Informatik II

Informatik II - Übung 09
Christian Beckel
[email protected]
29.04.2015
|
|
Vorschau
Übungsblatt 9
Christian Beckel |
29/04/15
|
2
Hinweise zu U9.A1
Spieltheorie/Spielbaumauswertung
a)  Bisschen Theorie
b)  Minimax-Algorithmus
c)  Optimale Strategie für MAX-Spieler
d)  Alpha/Beta-Algorithmus
3 |
|
U9.A1 – Spieltheorie
§  Bestanteile eines Spielbaums
§ 
§ 
§ 
§ 
Wurzel
Knoten
Kante
Blatt
à
à
à
à
Aktuellen Spielstellung
Spielzustand
Spielzug
Endzustand, (Spiel zu Ende)
4 |
|
U9.A1b – Minimax-Algorithmus
§  Algorithmus zur Ermittlung der optimalen Spielstrategie für
Nullsummenspiele
§  Sichert höchstmöglichen Gewinn bei optimaler Spielweise des
Gegners
5 |
|
U9.A1b – Minimax-Algorithmus
?
0
0
0
+1
+1
0
0
-1
+1
-1
-1
+1
0
0
6 |
|
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!!
7 |
|
U9.A1d – Der α-β-Algorithmus
Online Beispiel durchgerechnet:
http://www.vs.inf.ethz.ch/edu/FS2015/I2/slides/Info2-ITET-AlphaBeta.pdf
Online JAVA Applet:
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
8 |
|
%
|
|
|
|
|
|
Alpha-Beta-Algorithmus
§  Übungsbeispiel online, wir schauen mal rein...
12 |
12.05.2011
|
Informatik
II
Alpha-Beta-Algorithmus
|
|
Alpha-Beta-Algorithmus
beta
Beta-Schnitt: MAX wird sicher einen Wert grössergleich 20 erreichen. Eine
10 ist bereits bekannt. Der Wert des Teilbaums spielt keine Rolle!
|
|
Alpha-Beta-Algorithmus
alpha
beta
Alpha-Schnitt: MIN wird sicher einen Wert kleinergleich 8 erreichen. Eine 10
ist bereits bekannt. Der Wert des Teilbaums spielt keine Rolle!
|
|
Hinweise zu U9.A2 – Reversi (Teil 3)
HumanPlayer
nextMove()
RandomPlayer
nextMove()
GreedyPlayer
MinMaxPlayer
nextMove()
nextMove()
wählt nächsten
Zug
anhand Min-MaxAnalyse mit
neuer
Bewertungsfunktion
Übung 9
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
16 |
| II - Übung 9
Informatik
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
17 |
| II - Übung 9
Informatik
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
18 |
| II - Übung 9
Informatik
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
§  Zum Herunterladen von der Reversi-Webseite
§  username: i2bib
§  password: reversi
§  Artificial Intelligence: A Modern Approach
§  Stuart Russell and Peter Norvig (2nd Edition, 2003)
19 |
| II - Übung 9
Informatik
U9.A2c – Bewertungsfunktion (II)
§  Mögliche „Bewertungsfunktionen“
§  Wie viele Steine werden umgedreht?
§  Wo liegen die umgedrehte Steine (innen/Rand)?
§  In welcher Phase des Spiels sind wir? Anzahl Steine vs. Mobility
20 |
| II - Übung 9
Informatik
Besprechung
Übungsblatt 8
Christian Beckel |
29/04/15
| 21
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
22
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 kleinen Zahlen suche ist diese Methode schneller, im
Durchschnitt aber schlechter (tiefer Baum)
Informatik II - Übung 9
23
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
24
Lösung U8.A2a – 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]
09.05.2012
Informatik II - Übung 10
25
Lösung U8.A2b – 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;
}
09.05.2012
Informatik II - Übung 10
26
Lösung U8.A2c – Backtracking.java
private class FindResult {
public int value;
public Selection selection;
FindResult(int val, Selection sel){
value = val;
selection = sel;
}
}
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
FindResult result = find(new Selection(0), 0, values, weights, maxWeight);
return result.selection;
}
09.05.2012
Informatik II - Übung 10
27
Lösung U8.A2c – Backtracking.java
// find(new Selection(0), 0, values, weights, maxWeight);
private FindResult find(Selection selection, int weight,
ArrayList<Integer> values, ArrayList<Integer> weights, int maxWeight)
{
final int depth = selection.size();
if(depth == values.size())
return new FindResult( selection.sum(values), selection );
Selection without = new Selection(depth + 1, selection.bits());
without.set(depth, false);
FindResult resultWithout = // recursion without current item
find(without, weight, values, weights, maxWeight);
if( weight + weights.get(depth) <= maxWeight) {
Selection with = new Selection(depth + 1, selection.bits());
with.set(depth, true);
FindResult resultWith = // recursion with current item
find(with, weight + weights.get(depth), values, weights, maxWeight);
if(resultWith.value > resultWithout.value)
return resultWith;
}
return resultWithout;
}
09.05.2012
the actual Backtracking
Informatik II - Übung 10
28
Lösung U8.A2d – 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
09.05.2012
Informatik II - Übung 10
29
Lösung U8.A3a – checkMove: how to
Informatik II - Übung 9
30
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
31
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)
§  …
Informatik II - Übung 9
32
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
33
…viel Spass!
Christian Beckel |
29/04/15
| 34