Reinforcement Learning in der Schachprogrammierung Marco Block... n x x x o oo x xx x o x oo d4c4 a5a6 30%50% 40%20%

Reinforcement Learning in der Schachprogrammierung

Marco Block

...

n

x

x

x

o

o o

x

x xx

o

x

oo

d4 c4

a5 a6

30%50%

40% 20%

Marco Block Juni 2004

1.Einführung Schachprogrammierung (sehr kurz)

- Struktur von Schachprogrammen verstehen - Problematik der Spielqualität (Koeffizientenwahl)

Übersicht

- FUSC# && RL == Kasparov ?

2.Reinforcement Learning (RL) - Konzept und Einordnung in KI

3.KnightCap - erstes RL-Schachprogramm (erstaunliche Erfolge) - Studienarbeit

4.FUSC# - Open Source Projekt

Marco Block Juni 2004Marco Block Juni 2004

Schachprogrammierung

1.Einführung Schachprogrammierung (sehr kurz)

- Struktur von Schachprogrammen verstehen + Brettdarstellung + Evaluation + Zugwahl

- Problematik der Spielqualität (Koeffizientenwahl)

Marco Block Juni 2004Marco Block Juni 2004

SchachprogrammierungReinforcement LearningKnightCapFUSC#

Komponenten

Brettrepräsentation

010011011001 ...

Zuggenerator

n

Zugwahlalgorithmen

...

Stellungsbewertung

MaterialZentrierung der Figurenoffene Linienoffene DiagonalenLäuferpaarVorpostenFianchettierungRochadeEntwicklung ...

EröffnungsDatenbank







010011011001 ...

Zuggenerator

n

-4 -2 -3 -5 -6 -3 -2 -4

-1 -1 -1 -1 -1 -1 -1 -1

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

4 2 3 5 6 3 2 4

8x8-Brettdarstellung

Brettmatrix durchlaufen

Figur identifizieren

mögliche Zugfelder betrachten und Regelsatz befolgen

wenn Zug gültig in Zugliste speichern



0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

BitBoarddarstellung

011100 ... 00

111000 ... 00

1 =

64 BIT-Wort

+ Zuggenerierung sehr schnell+ Evaluationsfaktoren leicht in BitMuster giessbar (Königssicherheit)- keine „offiziellen“ Standards

BitBoards



Evaluation


Stellungsbewertung



Evaluation

0- +

Stellungsbewertung

∑ wi * fi(S)

10 * Material(S) + 2 * Mobilität(S) + ...

Faktoren - Material - Mobilität - gute/schlechte Figuren - starke/schwache Felder - Raum - Königsstellung - offene Linien/Diagonalen - Läuferpaar - Vorposten - Rochade - Bauernstruktur - Läufer gegen Springer - ...



Material

1.0

3.0

3.0

4.5

9.0

7x1.0

Weiss Schwarz

pnltrwq

2x3.0

2x3.0

2x4.5

1x9.0

37.0

7x1.0

2x3.0

2x3.0

2x4.5

1x9.0

37.0

0.0

0- +

pnvv:mltrwqk

Material - Figurenbewertungen (weisse Figurensumme - schwarze) - verwendeten Daten von Kasparov vorgeschlagen



Evaluation

Faktoren - Material - Mobilität - gute/schlechte Figuren - starke/schwache Felder - Raum - Königsstellung - offene Linien/Diagonalen - Läuferpaar - Vorposten - Rochade - Bauernstruktur - Läufer gegen Springer - ...

Stellungsbewertung

∑ wi * fi(S)

10 * 0.0 + 2 * Mobilität(S) + ...

0- +


konkrete Werterelativer Massstab


Problem: Welche Konfiguration ist die richtige? Gibt es überhaupt eine richtig Konfiguration? => Falls JA, dann müsste schachliches Wissen als eine lineare Funktion darstellbar sein! (sehr unwahrscheinlich ;) )

Evaluation

10 * Material(S) + 2 * Mobilität(S) + ...

11 * Material(S) + 2.5 * Mobilität(S) + ... ???Lösung (bisher): Für professionelle Schachprogramme => Grossmeister engagiert, kritisiert Bewertung

Lösung (KnightCap): Temporale Differenz auf Blattknoten



TD & Brettspiele V

TD()-Algorithmus dafür da, den Parametersatz w k zu lernen.

Also den Vektor so zu approximieren, dass er gegen die optimaleStrategie konvergiert.



BishopPairKnight_OutpostSupported_Knight_OutpostConnected_RooksOpposite_BishopsOpening_King_AdvanceKing_Proximity

Rook_Pos

Pos_QueensideBishop_MobilityQueen_MobilityKnight_SMobilityRook_SMobilityKing_SMobility

Unsupported_PawnPassed_Pawn_ControlDoubled_Pawn

Evaluation

StellungsbewertungsfaktorenBishopPairKnight_OutpostSupported_Knight_OutpostConnected_RooksOpposite_BishopsOpening_King_AdvanceKing_ProximityBlocked_KnightDraw_ValueNo_MaterialBishop_XRayRook_PosPos_BasePos_QueensideBishop_MobilityQueen_MobilityKnight_SMobilityRook_SMobilityKing_SMobilityThreatOverloaded_PenaltyQ_King_Attack_OpponentNoQ_King_attack_OpponentNoQueen_File_SaftyAttack_ValueUnsupported_PawnPassed_Pawn_ControlDoubled_PawnOdd_Bishop_Pawn_Pos

King_Passed_Pawn_SupportedPassed_Pawn_Rook_SupportedBlocked_EPawnPawn_AdvanceKing_Passed_Pawn_DefencePawn_DefenceMega_Weak_PawnCastle_BonusBishop_OutpostSupported_Bishop_OutpostSeventh_Rank_RooksEarly_Queen_MovementMid_King_AdvanceTrapped_StepUseless_PieceNear_Draw_ValueMating_PositionsEnding_King_PosKnight_PosPos_KingsideKnight_MobilityRook_MobilityKing_MobilityBishop_SMobilityQueen_SMobilityPiece_ValuesOpponents_ThreatQ_King_Attack_ComputerNoQ_King_Attack_Computer

Queen_File_SaftyPiece_Trade_BonusPawn_Trade_BonusAdjacent_PawnUnstoppable_PawnWeak_PawnBlocked_PawnPassed_Pawn_Rook_AttackBlocked_DPawnPawn_AdvancePawn_Advance2Pawn_PosIsolated_PawnWeak_Pawn_Attack_Value

... und viele viele mehr !

Evaluation sehr aufwendig und demnach „teuer“



Algorithmen


Zugwahlalgorithmen

...


Brute-Force-Methode

Shannon-A-Strategie (Brute-Force)

- Tiefensuche bis zu einer vorgegebenen festen Suchtiefe

- Minimax-Idee: Weiß maximiert, Schwarz minimiert Nachfolger

-8 -5 3 -12 7 3 28 -4 17

W am Zug

S am Zug

W am Zug

Bewertungsroutine an den Blättern



Brute-Force-Methode

-8 -5 3 -12 7 3 28 -4 17

-8 -12 -4

W am Zug

S am Zug

W am Zug







Brute-Force-Methode

-8 -5 3

-4

-12 7 3 28 -4 17

-8 -12 -4

W am Zug

S am Zug

W am Zug







Alpha-Beta-Algorithmus

-8 -5 3

-8

W am Zug

S am Zug

W am Zug


Alpha = - 8 [ MinWert , MaxWert ]


- Abschneiden von unwichtigen Ästen des Spielbaumes

- Alpha-/Beta-Werte bilden Erwartungsfenster




-8 -5 3 -12

-8

W am Zug

S am Zug

W am Zug


Alpha = - 8 [ - 8 , MaxWert ]







-8 -5 3 -12

-8 -12

W am Zug

S am Zug

W am Zug


Alpha = - 8 [ - 8 , MaxWert ]

< - 8 !






Zugsortierung

-8 -5 3

-4

28 -4 17

-8 -4

Schlechter Fall:

28 -4 17

-4

-8

-4 -8

Bester Fall:

< - 4 !

Zugsortierung

- iteratives Suchverfahren

- Transpositions-, Killerzug- und Historytabellen




diverse Programmiertricks

- selbstlernendes Eröffnungsbuch- Hashtables- heuristische Zugsortierungen- KillerMoves - parallele Suche- Ruhesuche- iterative Suche- NullMoves- weitere Heuristiken...


Reinforcement Learning

2.Reinforcement Learning (RL) - Einordnung in die KI + Bestärkendes oder Halbüberwachtes Lernen + Dynamische Programmierung + Monte Carlo + Temporale Differenz

- Beispiel: Tic-Tac-Toe



Lernstrategie I

1. überwachtes Lernen

2. unüberwachtes Lernen

- „Ziel wird vom Lehrer vorgegeben“- Neuronale Netze (BackPropagation)

- „System klassifiziert nach eigenem Ermessen“- EM, LBG

3. Reinforcement Learning- „System (Agent) findet durch Ausprobieren und Rückmeldung (Reinforcement-Signal) aus der Umwelt eine optimale Strategie, um Ziele innerhalb seiner Umgebung zu erreichen“- „halbüberwachtes Lernen“ [Zhang]- Dynamische Programmierung, Monte Carlo, Temporale Differenz



Lernstrategie II

Agenten, die immer oder niemals weiterforschen, werden stets scheitern.



Beispiel: Tic Tac Toe

o

o-Zug

o-Zug

x-Zug

x-Zug

x-Zug

1. Tabelle V(s) erzeugen mit (Zustand s Bewertung)

Wahrscheinlichkeit zu gewinnen

Gewinnstrategie

1 Sieg, 0 Niederlage, 0.5 Remis

2. Es werden viele Partien gespielt

- meistens besten Zug wählen- gelegentlich aber experimentieren! (zufällige Auswahl)- während des Spiels wird Werte- funktion verändert (Belohnung)- vorheriger Zustand verschiebt sich etwas in Richtung des nachfolgenden

...

...

...

x

ox

xx

x

x

x

o

o

o o

x

x

x

x

x xx

o

x

oo

x-SIEG

...Belohnung

Belohnung

Belohnung

0.5

0.5

0.5

0.5

0.5

0.5

1.0

0.7

0.6

0.51


3.KnightCap - erstes RL-Schachprogramm (Studienarbeitauszug) + Erfolg + Struktur

KnightCap



Historie

„Open Source Projekt“ von Jonathan Baxter, Andrew Tridgell und Lex Weaver

Reinforcement Learning eingesetzt Evaluations-Koeffizienten „getunt“

Motivation: Tesauros TD-Gammon schlägt Weltmeister

Startrating von 1650 in 3 Tagen (308 Spiele) auf 2150

+ Eröffnungsbuch+ weitere Programmierraffinessen

KnightCap hat ein Niveau von über 2500 (max 2575)

KnightCap unkommentiertes, kryptisches C



Struktur

Brettdarstellung:ToPiecesBoard


010011011001 ...

Zuggenerator

001000 ... 00

32 BIT-Wort

wDame

wSpringer

wLäufer

wTurm

Figur j greift Feld i an.



Struktur

Zugwahlalgorithmus:

- MTD(f) = weiterentwickelter AlphaBeta-Algorithmus mit minimalem Fenster

- einige Heuristiken (Killerheuristik, ...)

Zugwahlalgorithmen

...



Struktur

Stellungsbewertungsfaktoren:BishopPairKnight_OutpostSupported_Knight_OutpostConnected_RooksOpposite_BishopsOpening_King_AdvanceKing_ProximityBlocked_KnightDraw_ValueNo_MaterialBishop_XRayRook_PosPos_BasePos_QueensideBishop_MobilityQueen_MobilityKnight_SMobilityRook_SMobilityKing_SMobilityThreatOverloaded_PenaltyQ_King_Attack_OpponentNoQ_King_attack_OpponentNoQueen_File_SaftyAttack_ValueUnsupported_PawnPassed_Pawn_ControlDoubled_PawnOdd_Bishop_Pawn_Pos

Stellungsbewertung


King_Passed_Pawn_SupportedPassed_Pawn_Rook_SupportedBlocked_EPawnPawn_AdvanceKing_Passed_Pawn_DefencePawn_DefenceMega_Weak_PawnCastle_BonusBishop_OutpostSupported_Bishop_OutpostSeventh_Rank_RooksEarly_Queen_MovementMid_King_AdvanceTrapped_StepUseless_PieceNear_Draw_ValueMating_PositionsEnding_King_PosKnight_PosPos_KingsideKnight_MobilityRook_MobilityKing_MobilityBishop_SMobilityQueen_SMobilityPiece_ValuesOpponents_ThreatQ_King_Attack_ComputerNoQ_King_Attack_Computer

Queen_File_SaftyPiece_Trade_BonusPawn_Trade_BonusAdjacent_PawnUnstoppable_PawnWeak_PawnBlocked_PawnPassed_Pawn_Rook_AttackBlocked_DPawnPawn_AdvancePawn_Advance2Pawn_PosIsolated_PawnWeak_Pawn_Attack_Value

BishopPairKnight_OutpostSupported_Knight_OutpostConnected_RooksOpposite_BishopsOpening_King_AdvanceKing_Proximity

Rook_Pos

Pos_QueensideBishop_MobilityQueen_MobilityKnight_SMobilityRook_SMobilityKing_SMobility

Unsupported_PawnPassed_Pawn_ControlDoubled_Pawn

Blocked_EPawnPawn_Advance

Castle_BonusBishop_OutpostSupported_Bishop_OutpostSeventh_Rank_RooksEarly_Queen_Movement

Knight_PosPos_KingsideKnight_MobilityRook_MobilityKing_MobilityBishop_SMobilityQueen_SMobilityPiece_Values

Unstoppable_PawnWeak_PawnBlocked_Pawn

Blocked_DPawn

Pawn_PosIsolated_Pawn

Stand: August 2003

- KnightCap- FUSC# V1.09



Struktur

Besonderheiten:

- Nullmoves- Hashtables- Asymetrien- kann auf Parallelrechner betrieben werden- 4 Stellungstypen: Eröffnung, Mittelspiel, Endspiel, Mattstellungen- evolutionäres Eröffnungsbuch


4.FUSC# - RL goes to Fusc# + Einbettung von RL (KnightCap) + KnightCap-Experimente + Fusc#-Experimente

- Diplomarbeit + Erweiterung: Stellungsklassifikator

FUSC#-Projekt


Wiederholung

- Problematik: Evaluierung einer Stellung

- Reinforcement Learning + „... durch Ausprobieren und Rückmeldung der Umwelt“

- Backgammon sehr gut für TD() geeignet + kleine Stellungsänderung kleine Bewertungsveränderung + komplexe Evaluationsfunktion möglich

- Schach eigentlich nicht für TD() geeignet + kleine Stellungsänderung grosse Bewertungsveränderung + schnelle, lineare Bewertungsfunktion nötig (MinMax) + TD-Leaf() scheint eine Lösung zu sein (Baxter, Tridgell, Weaver -> KnightCap)

- Ziel: Evaluationsvektor w lernen



Daten vorbereiten

Stellungsfolge+HauptVarianten :...

X1 X2 XN

für Evaluation nur eigene Stellungen

Alpha-Beta als Zugwahlalgorithmus,Hauptvariante wird gespeichert

Partie: Fusch–Internetgegner 0-1

...

P1 P2 P3 P4 P2N

(Evaluationsvektor w wird benutzt)

beste, forcierte Stellung



E[x] = Stellungsbewertung der Stellung x mit Evaluationsvektor w bestehend aus n Stellungsfaktoren lineare Funktion: w1f1(x) + w2f2(x) + w3f3(x) + ... + wnfn(x)

Arbeitsweise von TD-Leaf()

Reward {-400, 0, 400}

4 Bauern im Vorteil als SiegKnightCap {-1,0,1}

Stellungsfolge+HauptVarianten(HV) :

...X1 X2 XN

E1 E2 EN

Evaluationswerte auch gespeichert

E[N] := -400for i:=1 to N-1 do td[i] := E[i+1] - E[i] go in HV[i] compute pd[i] go out HV[i]end ivectorUpdate

Lernalgorithmus:

w1f1(xi) + 0*f2(xi) + 0*f3(xi) + ... + 0*fn(xi)0*f1(xi) + w2f2(xi) + 0*f3(xi) + ... + 0*fn(xi)0*f1(xi) + 0*f2(xi) + w3f3(xi) + ... + 0*fn(xi) ...0*f1(xi) + 0*f2(xi) + 0*f3(xi) + ... + wnfn(xi)

pd[i] =

Evaluationsvektor w auf diesen Berechnungen basierend erneuernund anschliessend normalisieren (auf Bauernwert 100)



Temporale Differenz

x1 , ..., xN-1, xN eigene Stellungen unserer Partie.

x1

x2

xN-1

xN

J~(x1, w)

J~(x2, w)

J~(xN-1, w)

J~(xN, w) := r(xN)

td[1]

td[N-1]

„ich stehe besser, ergoerwarte ich einen Sieg...“

Modifizierung :

positive td[i] - auf 0 setzen, es sei denn KnightCap sagt den richtigen Zug des Gegners voraus

negative td[i] - bleiben unverändert (eigene Fehler)



VectorUpdate bei TD()

Aktualisierung des Evaluationsvectors w :

Lernrate Gradient gewichtete Summe der Differenzen im Rest der Partie



LeafNodes

A

4

C

4

F

4

L4

Tiefe d

xtl

xt

MinMax + TD() = TD-Leaf()



VectorUpdate bei TD-Leaf()

Aktualisierung des Evaluationsvectors w :



Welches wählen?

x1 xN

=1:

xt

x1 xN

0<<1:

xt

Gewichtung der Differenzenim Rest der Partie

x1 xN

=0:

xt

heuristisch: =0.7(bis Fehler einen Effekt hervorruft)

td[t]



VectorUpdate

t > 0:

Stellung xt wurde vermutlich unterbewertet w‘ = w + pos. Vielfaches des Gradienten J~(xt, w‘) > J~(xt, w)

t < 0:

Stellung xt wurde vermutlich überbewertet w‘ = w + neg. Vielfaches des Gradienten J~(xt, w‘) < J~(xt, w)

kurz: tAktualisierung des Evaluationsvectors w :

was muss ich ändern

um wieviel



Fazit: TD() -> TD-Leaf()

TDLeaf():

TD():



KnightCap Experimente I

- alle Koeffizienten auf 0, Material auf Standard 1=Bauer, 4=Springer und Läufer, 6=Turm und 12=Dame

- nach 25 Spielen besitzt KnightCap ein rating von 1650 (+-50)

- TD-Leaf nun „on“ mit =0.7 „heuristisch gewählt“ und =1.0 „grosse Sprünge“

- 3 Veränderungen wurden vorgenommen: + J‘(xi

l,w) wurde konvertiert zu einem Wert zwischen –1 und 1 mit vi

l=tanh[ J‘(xil,w)]

+ dt=vt+1l - vt

l wurde modifiziert, negative Werte von dt wurden nicht verändert, alle positiven temporalen Differenzen wurden auf 0 gesetzt + der Bauernwert wird mit 1 als Basiswert fixiert

- nach 300 Spielen (in 3 Tagen) hatte KnightCap ein rating von 2150

Experiment 1



KnightCap Experimente

- Experiment wurde wiederholt aber in Abhängigkeit der Wurzelknoten- nach 300 Spielen hatte KnightCap ein rating von 1850 (signifikant kleinerer peak und langsame Konvergenz)

Experiment 2

- alle Koeffizienten auf Bauernwert=1- startrating=1250 nach 1000 Spielen rating=1550

- KnightCap vs. KnightCap- 11% Punkte für KnightCap(selfplay) nach 600 Spielen gegen KnightCap(humanplay) nach 300 Spielen

Experiment 3

Experiment 4



FUSC# Experimente

- Fusc# (damalige Version) konnte im Experiment keine Partie gewinnen

- Temporale Differenz schlug fehl Grund: keine Siege => Fusch zweifelt an allem; keine positiven Updates => neue Engine musste her + Darkfusch im Januar 2004 geboren + heute 350.000 Knoten pro Sekunde! (Ruffian 600.000 Knoten pro Sekunde)

- 1.Versuch mit RL: SAL von Michael Gherrity spielte gegen GNUChess => RL für Schach nicht geeignet

- Deep Blue verwendete RL (Match gegen Kasparov)!

Experimente


Le4!!


KommunikationSchachprogrammierungReinforcement LearningKnightCapFUSC#

UCI-Kommunikation

Fritz, Arena Konsole

UCI-Protokoll (Universal Chess Interface)


www.schach.dePseudonym :)



Diplomarbeit

- In welcher Korrelation liegen Spielstärke und erlernbare Faktorenanzahl?

- Was geschieht, wenn man die Sache auf die Spitze treibt und z.B. 1000 verschiedene Stellungstypen einführt? Jeder hat ca. 1500 Stellungsfaktoren => 1.500.000 zu erlernende Bewertungskriterien!!!

- Kann Fusch in annehmbarer Zeit die Koeffizienten mit „guten“ Werten füllen?

- Algorithmuserweiterung behebt Problem.

- Ist =0.7 wirklich der richtige Parameter?

- Wie muss sinnvoll konvergieren?

- Startkoeffizienten sinnvoll?

Fragen, Experimente:

Zusätzlich:- Guide, um dieses Lernverfahren in jeden Schachmotor zu bringen



SchachprogrammierungReinforcement LearningKnightCapFUSC# Stellungsklassifikator

x xx

x

x

oo

oo

o

---

-

-

- Stellungsmuster identifizieren

- Vektor bauen

EM-Algorithmus => Pool

Stellungen aus GM-DB

- Vektoren aufspannen

eine Evaluation für jede Stellungsklasse

Vorteil: Stellungen können viel besser evaluiert werden (Eröffnung, Mittel- und Endspiel zu grobe Einteilung)

Nachteil: Für jedes Stellungsmuster neue Klassifizierung


SchachprogrammierungReinforcement LearningKnightCapFUSC# RL „feiner“ nutzen

0.50

1.20

1.00

0.97

0.20

0.50

1.05

0.44

1.21

1.50

0.50

1.20

1.00

0.97

0.20

0.50

1.05

0.44

1.21

1.50

0.40

1.25

1.10

0.90

0.20

0.55

1.15

0.40

1.11

1.50

0.60

1.14

1.00

0.94

0.22

0.48

0.50

0.49

1.31

1.52

...

1 2 n

KnightCap FUSC#

4x1468 = 5872(74 angegeben ...)

1000x1500 = 1.500.000


Visual Eval 1.0

Reinforcement Learning Anpassung des Evaluationsvektors



vielen Dank fürs zuhören ...

das wars

http://page.mi.fu-berlin.de/~fusch/Fusc#http://www.schach.de/Schachserver

Documents

Reinforcement Learning in der Schachprogrammierung Marco Block... n x x x o oo x xx x o x oo d4c4 a5a6 30%50% 40%20%