Backtracking (Zurücksetzen)
10
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
10.1
Grundlagen
Ablauf:
• Implizit wird ein Baum mogliher Losungsansatze aufgebaut.
Prinzip:
• Systematishes
Explorieren
aller
eventuellen
Losungsmoglihkeiten (exhaustive Suhe)
• mit Zur
uksetzen, falls ein Weg als niht zum Ziel fuhrend erkannt wird (z.B. im Irrgarten).
• F
uhrt ein Kind eines Knotens niht zur Losung, wird zum Va-
ter zurukgesetzt und es werden, falls vorhanden, weitere Kinder
untersuht.
• Dies entspriht der Tiefensuhe DFS in Graphen; dort wird ebenfalls implizit ein Spannbaum erzeugt.
Dagegen sind beim dynamishen Programmieren alle unterwegs
berehneten Werte essentiell fur das Gesamtergebnis.
c B. Möller
{1{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
{2{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Ein typishes Beispiel ist die
Beispiel 10.1.1 (Acht-Damen-Aufgabe) Stelle aht Damen so
auf ein Shahbrett, dass sie sih paarweise niht bedrohen.
Lösung:
• Setze eine Dame auf ein beliebiges Feld.
• Versuhe nun, die restlihen so zu plazieren, dass die Aufgabe
gelost wird.
• Geht dies niht, setze zur
uk und versuhe ein anderes Feld fur
die vorige Dame.
⊓
⊔
c B. Möller
c B. Möller
{3{
Informatik III WS 2011/12
Entsheidend ist, dass oft sofort, ohne in die Tiefe abzusteigen,
• erkannt werden kann, dass ein Weg niht zum Ziel f
uhrt bzw.
• sih keine Losung mit besserer Gewihtung als die bisher gefun-
denen bietet (branh-and-bound).
Dies ergibt in der Regel, wenn auh niht im shlehtesten Fall,
eine erheblihe Beshleunigung.
Beispiel 10.1.2 (Forts. Acht-Damen-Aufgabe) F
ur die zweite
Dame sheiden alle Felder aus, die die erste bedroht.
c B. Möller
{4{
⊓
⊔
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
Schemaalgorithmus f
ur Baktraking-Verfahren (erfolgreich
ist eine globale Variable, die mit false zu initialisieren ist):
public static void solve() ;
{ initialisiere Kandidatenwahl für nächsten Schritt ;
do { wähle nächsten Kandidaten ;
if (annehmbar)
{ liste den Kandidaten auf ;
if (Lösung unvollstaendig)
{ solve() ;
// untersuche nächste Suchbaumetage
if (!erfolgreich)
lösche Kandidaten aus der Liste ;
}
else erfolgreich = true ;
}
}
while (!erfolgreich && weitere Kandidaten) ;
}
c B. Möller
{5{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Grundlage ist, dass sih in zulassigen Stellungen die Damen auh
auf Ausshnitten des Shahbretts niht gegenseitig bedrohen.
• Damit ist folgende Verallgemeinerung moglih:
• Betrahte zu beliebigem n ein n × n-Shahbrett mit n Damen.
• Versuhe nun durh Rekursion, eine Losung f
ur ein kleines Brett
zu einer Losung fur ein groeres zu erweitern.
c B. Möller
{6{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Beobachtung: In einer zulassigen Stellung stehen nie 2 Damen in
der selben Spalte oder Zeile.
Also kann man die Damen z.B. anhand ihrer Spaltennummern
identizieren und brauht nur noh die Zeilenposition jeder Dame
zu speihern.
c B. Möller
Wir geben nun ein Programm fur das Aht-Damen-Problem an.
{7{
Informatik III WS 2011/12
In der folgenden Java-Losung handeln die Damen
\eigenverantwortlih":
• Jede fordert ihre rehte Nahbarin auf, sih zulassig zu platzieren;
• misslingt dies, shreitet sie ein Feld in ihrer Spalte fort und wie-
derholt das Verfahren.
c B. Möller
{8{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
class Queen
{ int row ;
int column ;
Queen neighbor ;
int testOrAdvance()
{ if (neighbor != null && neighbor.canAttack(row, column))
return next();
return 1 ;
}
public Queen(int c, Queen ngh)
{ column = c ; neighbor = ngh ;
}
public int first()
boolean canAttack (int r, int c)
{ int cd ;
if (row == r)
return true;
cd = c - column;
if (row + cd == r || row - cd == r)
return true;
if (neighbor != null)
return neighbor.canAttack(r, c) ;
return false ;
}
// berechne erste zulässige Stellung
// für Dame und Nachbarin
{ row = 1 ;
if (neighbor!= null && neighbor.first() != 0)
return testOrAdvance() ;
return 1 ;
}
c B. Möller
{9{
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
public int next()
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
// berechne weitere zulässige Stellung
// für Dame und Nachbarin
{ if (row == 8)
{ if (neighbor == null || neighbor.next() == 0)
return 0 ;
row = 0 ;
}
row = row + 1;
return testOrAdvance() ;
}
public void print() // print solution
{ if (neighbor != null)
neighbor.print() ;
System.out.println("column " + column + " row " + row) ;
}
c B. Möller
{ 10 {
c B. Möller
{ 11 {
Informatik III WS 2011/12
public static void main(String[] args)
//Hauptprogramm
{ Queen lastQueen;
int i;
lastQueen = null ;
for (i = 1; i <= 8; i++)
lastQueen = new Queen(i, lastQueen) ;
if (lastQueen.first() != 0)
lastQueen.print() ;
}
}
c B. Möller
{ 12 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
10.2
Backtracking (Zurücksetzen)
Spiele
Ziel dieses Abshnitts ist die Entwiklung einer Strategie fur das
Spiel Rehner gegen Mensh.
Beispiel 10.2.1 (Tic-Tac-Toe, 3-Gewinnt) •
Idee: Zeihne die moglihen Spielablaufe als Baum bzw. Graphen.
• Zur Analyse konnte man Tabellen verwenden, in denen alle
• Die Knoten entsprehen Stellungen, Kanten stehen f
ur moglihe
Uberg
ange gema den Spielregeln.
• Versuhe, mit dem Spannbaum des Graphen allein auszukommen, um mehrfahe Analyse gleiher Stellungen zu vermeiden.
Bei optimalem Spiel beiderseits entsteht stets Remis.
moglihen Spielverlaufe festgehalten sind.
• Damit wird aber nur das spezielle Spiel Ti-Ta-Toe erfasst.
• Auerdem werden die Tabellen f
ur komplexere Spiele viel zu gro.
Besser ist ein allgemeiner Ansatz zur Berehnung, ob eine Stellung
sihere Gewinn-, Remis- oder Verluststellung ist.
Fragestellung: Gibt es eine Strategie, die stets zu Remis bzw.
zum Verlust des Gegners fuhrt?
{ 13 {
c B. Möller
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
10.2.1
c B. Möller
{ 14 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Minmax-Strategie
Wir betrahten Spiele mit zwei Teilnehmern.
• Die Spieler seien S1 (etwa der Rehner) und S2 (etwa der
Mensh).
• Weiter verwenden wir eine ganzzahlige Bewertungsfunktion f
ur
Stellungen, etwa Wert 0 fur Remis, positive Bewertung fur sihere
Gewinnstellungen von S1 und negative fur sihere Verluststellungen von S1.
• Eine Stellung, f
ur die die Bewertung sofort bestimmt werden
kann, heit terminal.
• F
ur eine niht-terminale Stellung berehnet man die Bewertung
durh rekursive Analyse aller Nahfolgestellungen unter Annahme von optimalem Spiel beider Gegner.
c B. Möller
{ 15 {
Informatik III WS 2011/12
• Ist in einer Stellung P der Spieler S1 am Zug, so bewertet er
rekursiv alle Nahfolgestellungen. Er zieht in eine Nahfolgestellung P ′ mit maximaler Bewertung.
• In P ′ ist nun S2 am Zug. Er bewertet rekursiv alle Nahfolgestellungen von P ′ und zieht in eine mit minimaler Bewertung.
c B. Möller
{ 16 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
class Pair
{ public int value ;
public int best_move ;
Pair (int v, int m)
{ value = v ;
best_move = m ;
}
Konkretisierung in unserem Spiel:
• 0 f
ur unentshieden (remis)
• 1 Computer gewinnt (comp win)
}
• -1 Mensh gewinnt (comp loss)
Damit ergibt sih unser erstes Programm fur Ti-Ta-Toe:
class MyTicTac
{ public static int comp = 1 ;
public static int human = -1 ;
static int free = 0 ;
static Pair undecided = new Pair(0,-1) ;
c B. Möller
{ 17 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
static int remis
static int comp_win
static int comp_loss
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
= 0 ;
= 1 ;
= -1 ;
int best_move = start ;
for (int i=start ; i < 9 ; i++)
// 9 ist die Felderzahl
if (is_empty(i))
{ place(i, player) ;
int response = find_move(opponent(player)).value ;
if (better(player, response, value))
{ value = response ;
// bisher besten Zug
best_move = i ;
// verbessern
}
unplace(i);
// Brett wiederherstellen
}
return new Pair(value,best_move) ;
int board [] = {free,free,free,free,free,free,free,free,free} ;
int filled = 0;
public Pair find_move (int player)
{ if (board_full())
return undecided ;
else
{ Pair p = test_immediate_win(player) ;
if (p.value == win(player))
return p ;
else
{ int value = loss(player) ;
int start = first_free() ;
c B. Möller
{ 18 {
c B. Möller
{ 19 {
}
}
}
// Initialisierung
// fuer Extremumssuche
Informatik III WS 2011/12
c B. Möller
{ 20 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
boolean better (int player, int response, int value)
{ return (player == comp)?(response > value):(response < value) ;
}
boolean board_full ()
{ return filled == 9 ;
}
static int opponent (int player)
{ return -player ;
}
int first_free ()
{ for (int i = 0 ; i < 9 ; i++)
if (is_empty(i))
return i ;
return -1 ;
}
static int win (int player)
{ return (player==comp)?comp_win:comp_loss ;
}
int loss (int player)
{ return (player==comp)?comp_loss:comp_win ;
}
c B. Möller
{ 21 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
boolean is_empty (int i)
{ return board[i] == free ;
}
c B. Möller
{ 22 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
void place (int pos, int player)
{ board[pos] = player ;
filled++ ;
}
else if (board[pos1] == free && board[pos2] == player &&
board[pos3] == player)
return new Pair(win(player),pos1) ;
else return undecided ;
}
void unplace (int pos)
{ board[pos] = free ;
filled-- ;
}
Pair can_complete (int player, int pos1, int pos2, int pos3)
{ if (board[pos1] == player && board[pos2] == player &&
board[pos3] == free)
return new Pair(win(player),pos3) ;
else if (board[pos1] == player && board[pos2] == free &&
board[pos3] == player)
return new Pair(win(player),pos2) ;
c B. Möller
{ 23 {
Informatik III WS 2011/12
Pair test_immediate_win (int player)
{ Pair p = can_complete(player,0,1,2) ;
if (p.value == win(player)) return p ;
p = can_complete(player,3,4,5) ;
if (p.value == win(player)) return p ;
p = can_complete(player,6,7,8) ;
if (p.value == win(player)) return p ;
p = can_complete(player,0,3,6) ;
if (p.value == win(player)) return p ;
p = can_complete(player,1,4,7) ;
if (p.value == win(player)) return p ;
c B. Möller
{ 24 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
p = can_complete(player,2,5,8) ;
if (p.value == win(player)) return p ;
p = can_complete(player,0,4,8) ;
if (p.value == win(player)) return p ;
return can_complete(player,2,4,6) ;
for (int i = 0 ; i < 9 ; i++)
{ p = tt.find_move(player) ;
}
System.out.print("player: "+player+"
best move: "+
p.best_move+"\n") ;
public void print_board()
{ System.out.print(board[0]+" "+board[1]+" "+board[2]+" "+"\n") ;
System.out.print(board[3]+" "+board[4]+" "+board[5]+" "+"\n") ;
System.out.print(board[6]+" "+board[7]+" "+board[8]+" "+"\n") ;
}
tt.place(p.best_move, player) ;
player = opponent(player) ;
}
tt.print_board() ;
}
public static void main (String argv [])
{ MyTicTac tt = new MyTicTac() ;
int player = comp ; Pair p = undecided ;
c B. Möller
{ 25 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
c B. Möller
{ 26 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
• F
ur Ti-Ta-Toe ist bei optimalem Spiel beiderseits stets Remis
garantiert.
• Daher wird als Startfeld des Rehners Feld 01 berehnet.
• Dazu werden 97162 Stellungen untersuht.
• Wenn der Mensh als erster am Zug ist, so werden 5185 Stellun-
gen gepruft, 9761 Stellungen, wenn er das Mittelfeld wahlt, und
fur ein Ekfeld 13233.
c B. Möller
}
{ 27 {
Informatik III WS 2011/12
• F
ur komplexere Spiele ist also der naive Minmax-Ansatz oenbar
niht mehr durhfuhrbar.
• Dort muss die Rekursion nah einer bestimmten Tiefe gestoppt werden, um dann auf eine genauere Bewertungsfunktion
zurukzugreifen.
• Die G
ute eines Spielprogramms wird von der Rekursionstiefe
(Zugzahl der Vorausberehnung) und der Genauigkeit der Bewertungsfunktion bestimmt.
c B. Möller
{ 28 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
Wie lasst sih (zunahst unabhangig von der Bewertungsfunktion)
die Vorausshautiefe verbessern?
• Fasse Stellungen zu Klassen zusammen.
• Tabelliere bereits untersuhte Stellungen mit ihren Werten und
vermeide Neuberehnungen.
• Eine solhe Tabelle heit Transpositionstabelle; sie wird meist
durh Hashing implementiert.
Beispiel: Endspiele im Shah: Man hat nur noh wenige Figuren,
daher werden haug gleihe Stellungen erreiht.
c B. Möller
{ 29 {
⊓
⊔
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
10.2.2
α-β-Beschneidung (Pruning)
Idee: Sheide Nahfolgestellungen aus der Untersuhung aus, wenn
aufgrund der Vorgeshihte klar ist, dass sie keine Verbesserung
bringen.
Insbesondere konnte man in obigem Programm in der for-Shleife
von find move die Abbruhbedingung verbessern zu i < 9 &&
better(player,win(player),value).
Wir ordnen dies aber einem allgemeineren Ansatz unter.
{ 30 {
c B. Möller
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
• Nun stehe Knoten x mit seinem Teilgraphen zur Untersuhung
Wir betrahten Spielgraphen, deren Knoten mit allgemeinen
ganzen Zahlen markiert sind.
an:
• Wir bewerten zunahst eine Stellung, d.h. einen Knoten, in dem
der Rehner am Zug ist.
• Dieser Knoten soll als Wert das Maximum der Werte seiner unmittelbaren Teilgraphen erhalten.
• Jeder Wurzelknoten eines solhen hat als Wert das Minimum der
Werte seiner unmittelbaren Teilgraphen.
• Die bisher ermittelten Approximationen der exakten Werte seien
an den Knoten angetragen.
c B. Möller
{ 31 {
Informatik III WS 2011/12
≥ 44 RR
Max
RRR
vvv
≤ 40
44 9
Min
{{ @@
9999
40 II w x 22
99
I ww
• Da der linke Nahbar von x bereits den Wert 40 hat, kann das zu
ermittelnde Minimum niht groer sein, tragt also zur oberhalb
stattndenden Maximumsbildung nihts bei.
• Damit ist der Wert von x unerheblih, brauht also niht berehnet zu werden.
Die α-Beshneidung vermeidet gerade die Berehnung solher niht
benotigter Maximumsknoten.
c B. Möller
{ 32 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
Die β-Beshneidung verlauft symmetrish fur Minimumsknoten wie
y im folgenden Graphen:
≤ 30 RR
Min
RRR
vvv
≥ 53
Max
30 9
{{ @@
9999
53 II w y 3
99
I ww
c B. Möller
{ 33 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
• Dies lasst sih nur mit erheblihem Aufwand einheitlih nah dem
Spieler parametrisiert formulieren.
• Daher sind hier die Suhmethoden f
ur den Rehner und den Menshen getrennt ausprogrammiert.
c B. Möller
{ 34 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
class Pair
{ public int value ;
public int best_move ;
static int remis
static int comp_win
static int comp_loss
= 0 ;
= 1 ;
= -1 ;
int board [] = {free,free,free,free,free,free,free,free,free} ;
int filled = 0;
Pair (int v, int m)
{ value = v ;
best_move = m ;
}
public Pair find_comp_move (int alpha, int beta)
{ if (board_full())
return undecided ;
else
{ Pair p = test_immediate_win(comp) ;
if (p.value == comp_win)
return p ;
else
{ int value = alpha ;
// Initialisierung
int start = first_free() ;
// fuer Maximumssuche
}
class PruneTicTac
{ public static int comp = 1 ;
public static int human = -1 ;
static int free = 0 ;
static Pair undecided = new Pair(0,-1) ;
c B. Möller
Wir verbessern nun unser Ti-Ta-Toe-Programm um die
α-β-Beshneidung.
{ 35 {
Informatik III WS 2011/12
c B. Möller
{ 36 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
int best_move = start ;
for (int i=start ; i < 9 && value < beta ; i++)
if (is_empty(i))
{ place(i, comp) ;
int response = find_human_move(value,beta).value ;
if (response > value)
{ value = response ;
// bisher besten Zug
best_move = i ;
// verbessern
}
unplace(i);
// Brett wiederherstellen
}
return new Pair(value,best_move) ;
}
}
}
{ 37 {
c B. Möller
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
c B. Möller
{ 38 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
if (response < value)
{ value = response ;
best_move = i ;
}
unplace(i);
}
return new Pair(value,best_move) ;
// bisher besten Zug
// verbessern
// Brett wiederherstellen
}
int first_free ()
{ for (int i = 0 ; i < 9 ; i++)
if (is_empty(i))
return i ;
return -1 ;
}
boolean is_empty (int i)
{ return board[i] == free ;
}
}
}
boolean board_full ()
{ return filled == 9 ;
}
c B. Möller
public Pair find_human_move (int alpha, int beta)
{ if (board_full())
return new Pair(remis,-1) ;
else
{ Pair p = test_immediate_win(human) ;
if (p.value == comp_loss)
return p ;
else
{ int value = beta ;
// Initialisierung
int start = first_free() ;
// fuer Minimumssuche
int best_move = start ;
for (int i=start ; i < 9 && value > alpha ; i++)
if (is_empty(i))
{ place(i, human) ;
int response = find_comp_move(alpha,value).value ;
void place (int pos, int player)
{ board[pos] = player ;
filled++ ;
}
{ 39 {
Informatik III WS 2011/12
c B. Möller
{ 40 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
void unplace (int pos)
{ board[pos] = free ;
filled-- ;
}
static int win (int player)
{ return (player==comp)?comp_win:comp_loss ;
}
int loss (int player)
{ return (player==comp)?comp_loss:comp_win ;
}
Pair can_complete (int player, int pos1, int pos2, int pos3)
{ if (board[pos1] == player && board[pos2] == player &&
board[pos3] == free)
return new Pair(win(player),pos3) ;
c B. Möller
{ 41 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
}
Pair test_immediate_win (int player)
{ Pair p = can_complete(player,0,1,2) ;
if (p.value == win(player)) return p ;
p = can_complete(player,3,4,5) ;
if (p.value == win(player)) return p ;
p = can_complete(player,6,7,8) ;
if (p.value == win(player)) return p ;
p = can_complete(player,0,3,6) ;
c B. Möller
{ 42 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
if (p.value == win(player)) return p
p = can_complete(player,1,4,7) ;
if (p.value == win(player)) return p
p = can_complete(player,2,5,8) ;
if (p.value == win(player)) return p
p = can_complete(player,0,4,8) ;
if (p.value == win(player)) return p
return can_complete(player,2,4,6) ;
;
;
;
;
}
public void print_board()
{ System.out.print(board[0]+" "+board[1]+" "+board[2]+" "+"\n") ;
System.out.print(board[3]+" "+board[4]+" "+board[5]+" "+"\n") ;
System.out.print(board[6]+" "+board[7]+" "+board[8]+" "+"\n") ;
}
c B. Möller
else if (board[pos1] == player && board[pos2] == free &&
board[pos3] == player)
return new Pair(win(player),pos2) ;
else if (board[pos1] == free && board[pos2] == player &&
board[pos3] == player)
return new Pair(win(player),pos1) ;
else return undecided ;
{ 43 {
Informatik III WS 2011/12
public static void main (String argv [])
{ PruneTicTac tt = new PruneTicTac() ;
Pair p = undecided ;
int aux = comp_win ;
while (!tt.board_full())
{ p = tt.find_comp_move(comp_loss,aux) ;
System.out.print("player: "+comp+"
best move: "+
p.best_move+"\n") ;
tt.place(p.best_move,comp) ;
if (tt.board_full())
break ;
aux = p.value ;
p = tt.find_human_move(aux,comp_win) ;
System.out.print("player: "+human+"
best move: "+
p.best_move+"\n") ;
c B. Möller
{ 44 {
Informatik III WS 2011/12
Backtracking (Zurücksetzen)
Backtracking (Zurücksetzen)
Weitere Verbesserungen ergeben sih, indem man
• Nahfolgestellungen in anderer Reihenfolge durhsuht, gema
einer weiteren Bewertungsfunktion,
• bei gewissen Stellungen weiter in die Tiefe suht als bei anderen.
tt.place(p.best_move,human) ;
aux = p.value ;
• Praktish werden bei α-β-Beshneidung statt O(n) Knoten nur
√
noh O( n) Knoten untersuht.
}
tt.print_board() ;
}
}
Beispiel 10.2.2 (Tic-Tac-Toe) Zieht der Computer am Anfang,
so reduziert sih die Zahl der Berehnungen/moglihen Stellungen
von 97162 auf 4493.
c B. Möller
{ 45 {
Informatik III WS 2011/12
c B. Möller
{ 46 {
Informatik III WS 2011/12
© Copyright 2024 ExpyDoc
