Transcript
Backtracking (Zur¨ ucksetzen)
10
Backtracking (Zur¨ ucksetzen)
Backtracking (Zuru ¨cksetzen)
10.1
Grundlagen
Ablauf: • Implizit wird ein Baum mogli her Losungsansatze aufgebaut.
Prinzip: • Systematis hes
Explorieren aller eventuellen Losungsmogli hkeiten (exhaustive Su he) • mit Zur u ksetzen, falls ein Weg als ni ht zum Ziel fuhrend erkannt wird (z.B. im Irrgarten).
• F uhrt ein Kind eines Knotens ni ht zur Losung, wird zum Va-
ter zuru kgesetzt und es werden, falls vorhanden, weitere Kinder untersu ht. • Dies entspri ht der Tiefensu he DFS in Graphen; dort wird ebenfalls implizit ein Spannbaum erzeugt.
Dagegen sind beim dynamis hen Programmieren alle unterwegs bere hneten Werte essentiell fur das Gesamtergebnis. c B. M¨
oller
{1{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
{2{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Ein typis hes Beispiel ist die Beispiel 10.1.1 (Acht-Damen-Aufgabe) Stelle a ht Damen so
auf ein S ha hbrett, dass sie si h paarweise ni ht bedrohen. L¨ osung: • Setze eine Dame auf ein beliebiges Feld.
• Versu he nun, die restli hen so zu plazieren, dass die Aufgabe
gelost wird. • Geht dies ni ht, setze zur u k und versu he ein anderes Feld fur die vorige Dame. ⊓ ⊔
c B. M¨
oller
c B. M¨
oller
{3{
Informatik III WS 2011/12
Ents heidend ist, dass oft sofort, ohne in die Tiefe abzusteigen, • erkannt werden kann, dass ein Weg ni ht zum Ziel f uhrt bzw.
• si h keine Losung mit besserer Gewi htung als die bisher gefun-
denen bietet (bran h-and-bound). Dies ergibt in der Regel, wenn au h ni ht im s hle htesten Fall, eine erhebli he Bes hleunigung.
Beispiel 10.1.2 (Forts. Acht-Damen-Aufgabe) F ur die zweite
Dame s heiden alle Felder aus, die die erste bedroht.
c B. M¨
oller
{4{
⊓ ⊔
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
Schemaalgorithmus f ur Ba ktra king-Verfahren (erfolgreich ist eine globale Variable, die mit false zu initialisieren ist): public static void solve() ; { initialisiere Kandidatenwahl f¨ ur n¨ achsten Schritt ; do { w¨ ahle n¨ achsten Kandidaten ; if (annehmbar) { liste den Kandidaten auf ; if (L¨ osung unvollstaendig) { solve() ; // untersuche n¨ achste Suchbaumetage if (!erfolgreich) l¨ osche Kandidaten aus der Liste ; } else erfolgreich = true ; } } while (!erfolgreich && weitere Kandidaten) ; } c B. M¨
oller
{5{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Grundlage ist, dass si h in zulassigen Stellungen die Damen au h auf Auss hnitten des S ha hbretts ni ht gegenseitig bedrohen. • Damit ist folgende Verallgemeinerung mogli h:
• Betra hte zu beliebigem n ein n × n-S ha hbrett mit n Damen.
• Versu he nun dur h Rekursion, eine Losung f ur ein kleines Brett
zu einer Losung fur ein groeres zu erweitern.
c B. M¨
oller
{6{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
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 identi zieren und brau ht nur no h die Zeilenposition jeder Dame zu spei hern.
c B. M¨
oller
Wir geben nun ein Programm fur das A ht-Damen-Problem an.
{7{
Informatik III WS 2011/12
In der folgenden Java-Losung handeln die Damen \eigenverantwortli h": • Jede fordert ihre re hte Na hbarin auf, si h zulassig zu platzieren; • misslingt dies, s hreitet sie ein Feld in ihrer Spalte fort und wie-
derholt das Verfahren.
c B. M¨
oller
{8{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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¨ assige Stellung // f¨ ur Dame und Nachbarin
{ row = 1 ; if (neighbor!= null && neighbor.first() != 0) return testOrAdvance() ; return 1 ; }
c B. M¨
oller
{9{
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
public int next()
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
// berechne weitere zul¨ assige Stellung // f¨ ur 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¨
oller
{ 10 {
c B. M¨
oller
{ 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¨
oller
{ 12 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
10.2
Backtracking (Zur¨ ucksetzen)
Spiele
Ziel dieses Abs hnitts ist die Entwi klung einer Strategie fur das Spiel Re hner gegen Mens h.
Beispiel 10.2.1 (Tic-Tac-Toe, 3-Gewinnt) •
Idee: Zei hne die mogli hen Spielablaufe als Baum bzw. Graphen.
• Zur Analyse konnte man Tabellen verwenden, in denen alle
• Die Knoten entspre hen Stellungen, Kanten stehen f ur mogli he
Uberg ange gema den Spielregeln. • Versu he, mit dem Spannbaum des Graphen allein auszukommen, um mehrfa he Analyse glei her Stellungen zu vermeiden.
Bei optimalem Spiel beiderseits entsteht stets Remis. mogli hen 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 Bere hnung, ob eine Stellung si here Gewinn-, Remis- oder Verluststellung ist.
Fragestellung: Gibt es eine Strategie, die stets zu Remis bzw.
zum Verlust des Gegners fuhrt? { 13 {
c B. M¨
oller
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
10.2.1
c B. M¨
oller
{ 14 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Minmax-Strategie
Wir betra hten Spiele mit zwei Teilnehmern. • Die Spieler seien S1 (etwa der Re hner) und S2 (etwa der
Mens h). • Weiter verwenden wir eine ganzzahlige Bewertungsfunktion f ur Stellungen, etwa Wert 0 fur Remis, positive Bewertung fur si here Gewinnstellungen von S1 und negative fur si here Verluststellungen von S1. • Eine Stellung, f ur die die Bewertung sofort bestimmt werden kann, heit terminal. • F ur eine ni ht-terminale Stellung bere hnet man die Bewertung dur h rekursive Analyse aller Na hfolgestellungen unter Annahme von optimalem Spiel beider Gegner. c B. M¨
oller
{ 15 {
Informatik III WS 2011/12
• Ist in einer Stellung P der Spieler S1 am Zug, so bewertet er
rekursiv alle Na hfolgestellungen. Er zieht in eine Na hfolgestellung P ′ mit maximaler Bewertung. • In P ′ ist nun S2 am Zug. Er bewertet rekursiv alle Na hfolgestellungen von P ′ und zieht in eine mit minimaler Bewertung.
c B. M¨
oller
{ 16 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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 unents hieden (remis)
• 1 Computer gewinnt (comp win)
}
• -1 Mens h gewinnt (comp loss)
Damit ergibt si h 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¨
oller
{ 17 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
static int remis static int comp_win static int comp_loss
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
= 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¨
oller
{ 18 {
c B. M¨
oller
{ 19 {
} } } // Initialisierung // fuer Extremumssuche Informatik III WS 2011/12
c B. M¨
oller
{ 20 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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¨
oller
{ 21 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
boolean is_empty (int i) { return board[i] == free ; }
c B. M¨
oller
{ 22 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
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¨
oller
{ 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¨
oller
{ 24 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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¨
oller
{ 25 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
c B. M¨
oller
{ 26 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
• F ur Ti -Ta -Toe ist bei optimalem Spiel beiderseits stets Remis
garantiert. • Daher wird als Startfeld des Re hners Feld 01 bere hnet. • Dazu werden 97162 Stellungen untersu ht.
• Wenn der Mens h als erster am Zug ist, so werden 5185 Stellun-
gen gepruft, 9761 Stellungen, wenn er das Mittelfeld wahlt, und fur ein E kfeld 13233.
c B. M¨
oller
}
{ 27 {
Informatik III WS 2011/12
• F ur komplexere Spiele ist also der naive Minmax-Ansatz o enbar
ni ht mehr dur hfuhrbar. • Dort muss die Rekursion na h einer bestimmten Tiefe gestoppt werden, um dann auf eine genauere Bewertungsfunktion zuru kzugreifen. • Die G ute eines Spielprogramms wird von der Rekursionstiefe (Zugzahl der Vorausbere hnung) und der Genauigkeit der Bewertungsfunktion bestimmt.
c B. M¨
oller
{ 28 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
Wie lasst si h (zuna hst unabhangig von der Bewertungsfunktion) die Vorauss hautiefe verbessern? • Fasse Stellungen zu Klassen zusammen.
• Tabelliere bereits untersu hte Stellungen mit ihren Werten und
vermeide Neubere hnungen. • Eine sol he Tabelle heit Transpositionstabelle; sie wird meist dur h Hashing implementiert. Beispiel: Endspiele im S ha h: Man hat nur no h wenige Figuren,
daher werden hau g glei he Stellungen errei ht.
c B. M¨
oller
{ 29 {
⊓ ⊔
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
10.2.2
α-β-Beschneidung (Pruning)
Idee: S heide Na hfolgestellungen aus der Untersu hung aus, wenn
aufgrund der Vorges hi hte klar ist, dass sie keine Verbesserung bringen. Insbesondere konnte man in obigem Programm in der for-S hleife von find move die Abbru hbedingung verbessern zu i < 9 && better(player,win(player),value). Wir ordnen dies aber einem allgemeineren Ansatz unter.
{ 30 {
c B. M¨
oller
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
• Nun stehe Knoten x mit seinem Teilgraphen zur Untersu hung
Wir betra hten Spielgraphen, deren Knoten mit allgemeinen ganzen Zahlen markiert sind.
an:
• Wir bewerten zuna hst eine Stellung, d.h. einen Knoten, in dem
der Re hner am Zug ist. • Dieser Knoten soll als Wert das Maximum der Werte seiner unmittelbaren Teilgraphen erhalten. • Jeder Wurzelknoten eines sol hen 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¨
oller
{ 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 Na hbar von x bereits den Wert 40 hat, kann das zu
ermittelnde Minimum ni ht groer sein, tragt also zur oberhalb statt ndenden Maximumsbildung ni hts bei. • Damit ist der Wert von x unerhebli h, brau ht also ni ht bere hnet zu werden. Die α-Bes hneidung vermeidet gerade die Bere hnung sol her ni ht benotigter Maximumsknoten. c B. M¨
oller
{ 32 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
Die β-Bes hneidung verlauft symmetris h 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¨
oller
{ 33 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
• Dies lasst si h nur mit erhebli hem Aufwand einheitli h na h dem
Spieler parametrisiert formulieren. • Daher sind hier die Su hmethoden f ur den Re hner und den Mens hen getrennt ausprogrammiert.
c B. M¨
oller
{ 34 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
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¨
oller
Wir verbessern nun unser Ti -Ta -Toe-Programm um die α-β-Bes hneidung.
{ 35 {
Informatik III WS 2011/12
c B. M¨
oller
{ 36 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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¨
oller
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
c B. M¨
oller
{ 38 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
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¨
oller
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¨
oller
{ 40 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
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¨
oller
{ 41 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
} 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¨
oller
{ 42 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
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¨
oller
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¨
oller
{ 44 {
Informatik III WS 2011/12
Backtracking (Zur¨ ucksetzen)
Backtracking (Zur¨ ucksetzen)
Weitere Verbesserungen ergeben si h, indem man • Na hfolgestellungen in anderer Reihenfolge dur hsu ht, gema
einer weiteren Bewertungsfunktion, • bei gewissen Stellungen weiter in die Tiefe su ht als bei anderen.
tt.place(p.best_move,human) ; aux = p.value ;
• Praktis h werden bei α-β-Bes hneidung statt O(n) Knoten nur √ no h O( n) Knoten untersu ht.
} tt.print_board() ; } }
Beispiel 10.2.2 (Tic-Tac-Toe) Zieht der Computer am Anfang,
so reduziert si h die Zahl der Bere hnungen/mogli hen Stellungen von 97162 auf 4493.
c B. M¨
oller
{ 45 {
Informatik III WS 2011/12
c B. M¨
oller
{ 46 {
Informatik III WS 2011/12
