Upload
manfried-katch
View
109
Download
2
Embed Size (px)
Citation preview
AG SchachprogrammierungFUSC#Stand: Mai 2004
FUSC#-Projektgruppe
d4 c4
a5 a6
30%50%
40% 20%
e4
60%
Schachprogrammier AG
Inhalt
Überblick
Gründung der AG Schachprogrammierung
Wie sieht das Innenleben eines Schachmotor aus ° Brettdarstellung ° Evaluation ° Algorithmen ° Mensch versus Maschine ° Eröffnungsbücher ° UCI-Protokoll
weitere Projekt-Planung
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Mai 2004
Turnier-Tabelle:1.Dauth, Benjamin 2290 2.Düster, Christian 2100 3.Domingo, Miguel 2038 4.Lane, Robin 13005.Steffen, Rico 19716.Kuprat, Thomas 19757.Burghardt, Michael 19758.Martin, Mario 19009.Trösch, Thomas 216610.FUSC# V1.07 140011.Kärcher, David 136812.Minski, Martin 202413.Rauch, Felix 135014.Schaller, Peter 175015.Wölter, Ulrich 130016.Remmo, Abdulrahim 1300
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier (V 1.10) buggi, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Mai 2004
Pseudonym :)
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Gründung der Projektgruppe C#, OpenSourceDebütversion (V 1.03) Ruhesuche, Killermoves, Hashtables, Heuristiken, iterative Suche, PVInternetdebüt (V 1.06) Transparenz, Stellungsbewertungerstes offizielles Internet-Turnier erster Sieg, 7te von 8 EnginesLange Nacht der Wissenschaften (V 1.07) Klassendiagramm, Dokumentation, Experimente mit Neuronalen NetzenFusch spielt bei schach.de (V 1.09) rating 1800-1900zweites offizielles Internet-Turnier buggy, 21ter von 23
14.Oktober 2002
1.März 2003
1.Juni 2003
11.Juni 2003
14.Juni 2003
20.September 2003
Januar 2004
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Gründung der AG
Mai 2004
Turnier-Tabelle:1 Matheus 2.3
2 Drunken Master 1.0
3 BigLion 2.23k
4 DelphiMax 2.8
5 Asterisk 0.4b
6 Madeleine 0.2
7 Taktix 2.23k
8 WJChess 1.52
9 EnginMax 5.11c
10 KKFChess 2.6.2
11 Aice 0.64
12 Celes 0.77c
13 ChessAlex 1.2b7
14 Simontacchi 1.81a
15 Silke 1.2.1209
16 Alfil v403.1
17 Polar Engine 1.3
18 Gaia 1.1
19 Piranha 0.5
20 Eagle 0.2.7c
21 FUSC# v1.10
22 Cassandre 0.24
23 Trex 1.8.5
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Projektgruppe
Homepage http://page.mi.fu-berlin.de/~fusch/
Mitgliedschaft Eintragen in die Mailingliste und zu den Treffen erscheinen (kleiner Vortrag)
aktive Mitglieder:
Maro Bader, Andre Rauschenbach, Johannes Buchner, Andreas Gropp, Christian Düster (HU), Falko Krause, Christian Ehrlich, Ben-Fillippo Krippendorff und Marco Block
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Projektgruppe
Sourcecode http://page.mi.fu-berlin.de/~fusch/
- integriertes CVS
- Gruppe schachs
- Tutorial online
Mai 2004pageant
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Projektgruppe
Arbeitsumgebung auf dem Maniac-Server bereitgestellt
- MS Visual Studio 2002
- .NET V1.0
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Schachprogrammierung
Brettrepräsentation
010011011001 ...
Zuggenerator
wn
Stellungsbewertung
MaterialZentrierung der Figurenoffene Linienoffene DiagonalenLäuferpaarVorpostenFianchettierungRochadeEntwicklung ...
Eröffnungs-Datenbank
Mai 2004
Zugwahlalgorithmen
...
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
8x8 Board
Mai 2004
-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
Brettrepräsentation
010011011001 ...
Zuggenerator
wn
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
BitBoards
• Idee: 64-bit-Variablen 64 Schachfelder !
• „bitboards“ zur Brettdarstellung• „1“ bedeutet: Feld belegt• „0“ bedeutet: Feld frei• für jeden Figurentyp eigenes
„bitboard“ als Representation• AND, OR Operationen etc. zur
schnellen, quasi „parallelen“ Zuggenerierung
• Ausblick: potentiell mehr Schachwissen in bitboards integrieren (z.B. „Züge in die Nähe des Königs“)
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 b8 c8 d8 e8 f8 g8 h8 #7
a7 b7 c7 d7 e7 f7 g7 h7 #6
a6 b6 c6 d6 e6 f6 g6 h6 #5
a5 b5 c5 d5 e5 f5 g5 h5 #4
a4 b4 c4 d4 e4 f4 g4 h4 #3
a3 b3 c3 d3 e3 f3 g3 h3 #2
a2 b2 c2 d2 e2 f2 g2 h2 #1
a1 b1 c1 d1 e1 f1 g1 h1 #0
Das Brett in Bitboard-Darstellung
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
BitBoards
Beispiel:
Springerzüge[d3] & gegnerischeBauern 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00101000 00000000 00000000 01000100 & 00000000 => 00000000 000X0000 00000000 000X0000 01000100 11111111 01000100 00101000 00000000 00000000
Konkret:• Idee: schon im voraus z.B. „alle
möglichen Springerzüge von Feld d3“ berechnen und in einem bitboard abspeichern
• „Springerzüge[d3] & freieFelder“
• Erweiterung: „ Springerzüge[d3] & gegnerischeFiguren“ erzeugt Schlagzüge
• Problem: die bitboard-Darstellung eignet sich für die „ziehenden“ Figurentypen (Dame, Turm, Läufer) nur bedingt
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Rotated BitBoards
• Idee 1: für „ziehende“ Figuren alle möglichen Züge in Abhängigkeit vom Aussehen der jeweilig relevanten Linie/Diagonale schon vorher berechnen
• Idee 2: dafür „gedrehte“ Brettdarstellungen als „rotated bitboards“ speichern, so dass die Linie/Diagonalen dort sequentiell in einem byte vorliegen
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 a7 a6 a5 a4 a3 a2 a1 #7
b8 b7 b6 b5 b4 b3 b2 b1 #6
c8 c7 c6 c5 c4 c3 c2 c1 #5
d8 d7 d6 d5 d4 d3 d2 d1 #4
e8 e7 e6 e5 e4 e3 e2 e1 #3
f8 f7 f6 f5 f4 f3 f2 f1 #2
g8 g7 g6 g5 g4 g3 g2 g1 #1
h8 h7 h6 h5 h4 h3 h2 h1 #0
Die um 90° gedrehte Brett-Darstellung
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Fuschboards
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Evaluation
Mai 2004
Stellungsbewertung
MaterialZentrierung der Figurenoffene Linienoffene DiagonalenLäuferpaarVorpostenFianchettierungRochadeEntwicklung ...
Nur eine Stellung, ohne Schach- und Schlagzügekann positionell bewertet werden (->Ruhesuche).
Faktoren werden nacheinander identifiziert, bewertet(relativ zum Wert eines Bauern) und aufsummiert.
dynamische Faktoren - Entwicklung - Koordination - Figurendruck - schlechtstehende Figuren
0- +
statische 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 - ...
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Material
Mai 2004
1.0
3.0
3.0
4.5
9.0
7x1.0
Weiss Schwarz
pmnvltrwq
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- +
pmnvv:ltrwqk
Material - Figurenbewertungen (weisse Figurensumme - schwarze) - verwendeten Daten von Kasparov vorgeschlagen
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mobilität
Mai 2004
Mobilität - Figuren stehen besser, wenn sie mehr Zugmöglichkeiten haben - Problem: Dame besondere Rolle
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Bauernqualität
Mai 2004
Beispiel: Bauer
Freibauer + 1.0
gedeckt 0.1
isoliert - 0.5
Doppelbauer - 0.5
rückständig - 0.5
zentral + 0.1
3.67.4
+3.8
2x1.0 +
Weiss Schwarz
4x0.1 +
2x0.1 -
1x0.5 -
0x0.5 -
0x1.0 +
3x0.1 +
3x0.1 -
3x0.5 -
1x0.5 -
1x0.5 - 1x0.5 -
2x0.1 + 1x0.1 +
6x1.0 6x1.0
Was sind die genauen Werte?
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Algorithmen
Grundlagen - Spieltheorie: Schach ist Zwei-Personen-Nullsummen-Spiel - Nullsumme: „Was der eine gewinnt, verliert der andere“ - Spielbaum: Knoten = Position, Kante = möglicher Zug
Spielbaum:
W am Zug
S am Zug
W am Zug
Knoten
Kante
Zugwahlalgorithmen
...
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
W am Zug
S am Zug
W am Zug
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
W am Zug
S am Zug
W am Zug
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3 -12 7 3 28 -4 17
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
-8 -5 3 -12 7 3 28 -4 17
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
-8 -5 3 -12 7 3 28 -4 17
-8
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
-8 -5 3 -12 7 3 28 -4 17
-8 -12 -4
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Brute-Force-Methode
Erster Ansatz (Shannon-A-Strategie oder Brute-Force) - Alle legalen Züge einer Position verfolgen - Tiefensuche bis zu einer vorgegebenen festen Suchtiefe - Bewertung an den Endpositionen (Blättern) - Positive/negative Werte: Vorteile für Weiß/Schwarz - Minimax-Idee: W wählt Zug mit maximaler Bewertung, S wählt Zug mit minimaler Bewertung (jeweils bester Zug)
-8 -5 3
-4
-12 7 3 28 -4 17
-8 -12 -4
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Jede Partei spielt immerden für sich besten Zug.
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3
-8
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
[ MinWert , MaxWert ]
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3
-8
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ MinWert , MaxWert ]
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3
-8
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ - 8 , MaxWert ]
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3 -12
-8
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ - 8 , MaxWert ]
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
-8 -5 3 -12
-8 -12
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ - 8 , MaxWert ]
< - 8 !
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
-8 -5 3 -12 28 17 -9
-8 -12 -9
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ - 8 , MaxWert ]
< - 8 !
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Alpha-Beta-Algorithmus
Verbesserung (Alpha-Beta) - Problem: bei geringer Suchtiefe enorm große Knotenzahl (z.B. bei Suchtiefe 5 etwa 102 Mill. Knoten zu durchlaufen) - #innere Knoten << #Blätter (Bewertungsroutine nötig!) - deutliche Verbesserung: Alpha-Beta-Algorithmus - Idee: Erzeugung aller Stellungen nicht notwendig - Abschneiden von bestimmten unwichtigen Ästen des Baums - Alpha/Beta sind minimale/maximale Werte einer Tiefe
-8 -5 3
-8
-12 28 17 -9
-8 -12 -9
W am Zug
S am Zug
W am Zug
Bewertungsroutine an den Blättern
Alpha = - 8 [ - 8 , MaxWert ]
< - 8 !
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Zugsortierung
Weitere Verbesserung (Zugsortierung) - Komplexität von Alpha-Beta + schlechtester Fall: Baum gleich wie Brute-Force (n Positionen) + bester Fall: nur noch √n Positionen zu berechnen - Bester Fall: beste Züge jeweils immer zuerst berechnen - Deshalb: Zugsortierung von immenser Bedeutung - Ideen zur Zugsortierung: + iterative Suche + Hauptvariante + Transpositions-, Killerzug- bzw. Historytabelle
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Zugsortierung
Weitere Verbesserung (Zugsortierung) - Komplexität von Alpha-Beta + schlechtester Fall: Baum gleich wie Brute-Force (n Positionen) + bester Fall: nur noch √n Positionen zu berechnen - Bester Fall: beste Züge jeweils immer zuerst berechnen - Deshalb: Zugsortierung von immenser Bedeutung - Ideen zur Zugsortierung: + iterative Suche + Hauptvariante + Transpositions-, Killerzug- bzw. Historytabelle
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Zugsortierung
Weitere Verbesserung (Zugsortierung) - Komplexität von Alpha-Beta + schlechtester Fall: Baum gleich wie Brute-Force (n Positionen) + bester Fall: nur noch √n Positionen zu berechnen - Bester Fall: beste Züge jeweils immer zuerst berechnen - Deshalb: Zugsortierung von immenser Bedeutung - Ideen zur Zugsortierung: + iterative Suche + Hauptvariante + Transpositions-, Killerzug- bzw. Historytabelle
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Zugsortierung
Weitere Verbesserung (Zugsortierung) - Komplexität von Alpha-Beta + schlechtester Fall: Baum gleich wie Brute-Force (n Positionen) + bester Fall: nur noch √n Positionen zu berechnen - Bester Fall: beste Züge jeweils immer zuerst berechnen - Deshalb: Zugsortierung von immenser Bedeutung - Ideen zur Zugsortierung: + iterative Suche + Hauptvariante + Transpositions-, Killerzug- bzw. Historytabelle
-8 -5 3
-4
28 -4 17
-8 -4
Schlechter Fall:
28 -4 17
-4
-8
-4 -8
Bester Fall:
< - 4 !
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Zugsortierung
Weitere Verbesserung (Zugsortierung) - Komplexität von Alpha-Beta + schlechtester Fall: Baum gleich wie Brute-Force (n Positionen) + bester Fall: nur noch √n Positionen zu berechnen - Bester Fall: beste Züge jeweils immer zuerst berechnen - Deshalb: Zugsortierung von immenser Bedeutung - Ideen zur Zugsortierung: + iterative Suche + Hauptvariante + Transpositions-, Killerzug- bzw. Historytabelle
-8 -5 3
-4
28 -4 17
-8 -4
Schlechter Fall:
28 -4 17
-4
-8 -5 3
-4 -8
Bester Fall:
< - 4 !
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Voraussagendes Abschneiden (Forward Pruning) - bisherige Verfahren -> Ergebnis wie Brute-Force - Jetzt: Heuristiken suchen, die Züge / Äste abschneiden - Problem: gute Zügen können übersehen werden - Gute Heuristik: Kleines Risiko hoher Gewinn (weniger Knoten) - Erster Ansatz: Shannon-B-Strategie + Vorauswahl auf sinnvolle Züge in jeder Ebene + forcierte Varianten so tief wie möglich verfolgen + keine Bewertung bei möglichen Schlagzügen - Vorauswahl auf einige der möglichen Züge (wie der Mensch) schwierig, aber Sortierung sinnvoll (Alpha-Beta-Verfahren) - Zweite Idee nennt sich Ruhesuche: + Bewertung nicht stabil (z.B. nächster Zug verliert die Dame) + Ruchesuche ist normale Suche, aber nur Schlagzüge betrachtet + #Schlagzüge << #aller Züge (degeneriert nicht zu Suche!)
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
Ruhesuche
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Nullmove-Pruning
„Nichts-Tun“-Strategie - Mächtiges selektives Werkzeug ist Nullzug-Heuristik - Idee: Vor normalen Zügen wird ein Nullzug ausgeführt - Gegner macht so zwei Züge hintereinander (großer Vorteil) - Schlechte Züge sind damit schnell widerlegbar, da trotz doppeltem Zug nicht bester Zug (außerhalb des Fensters) - Selektivität, da nicht volle Suchtiefe bei Nullzug (z.B. t-2) - Nullzüge dürfen nicht gemacht werden, wenn: + Zugzwang-Stellungen (selten: Zugrecht unvorteilhaft) + Zwei Nullzüge hintereinander (Situation vor Nullzug gleich) + Position ist im Schach (Gegner könnte König schlagen) - Ergebnis: Programm kann bis zu 2 Halbzüge tiefer rechnen!!
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Selektivite Verfahren
„Nichts-Tun“-Strategie
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
FUSC#-Algorithmen
Algorithmen in FUSC# (aktueller Stand) - iterative Alpha-Beta-Suche - Zugsortierung via Hauptvariante, Killertabelle und Historytabelle (Experimente mit verschiedenen Parametern) - Verschiedene Varianten von Transpositionstabellen - Selektivität: Ruhesuche, „Razoring“ - Nullzug-Heuristik mit verschiedenen Parametern
Algorithmen in FUSC# (in Planung) - Verbesserung der Sortierung („Zugbewertung“) - Andere Heuristiken zur „Verschlankung“ des Baumes - Langfristig: Umsetzung eines Plans im Schach
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Warten auf Fehler
des Gegners Plan fassen
Gewinnstrategien im Schach
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Plan im Schach
- Unterschied zwischen Hobby- und Vereinsspieler
- Unterschied Taktik und Strategie
langfristige Planung des Spielverlaufes
Kombinationen
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Allgemeine Pläne
- generelle Pläne
- Flügel vs Zentrum- Unterschiedliche Rochaden- ...
- Bauernschwächen ausnutzen- Figuren besser stellen- „schlechte“ Figuren abtauschen- ...
- spezielle /kurzfristige Pläne
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Beispiele
• spezieller Plan • genereller Plan
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Wie erstellt man einen Plan
Beurteilung der Stellung
Eigenarten (Schwächen/Stärken)
Mögliche Pläne erfassen
Entscheidung für einen Plan
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Mensch versus Maschine
Brute-Force vs Intuition
Computer
+ keine taktischen Fehler im Berechnungshorizont
- begrenzter Horizont- Figuren werden bestmöglich positioniert
Mensch
+ Intuition und Erfahrung+ Selektive Suche+ keinen beschränkten Horizont
- macht Fehler- Konzentration
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Eröffnungsbücher
EröffnungsDatenbankSchachwissen aus mindestens 1500 Jahren steht zur Verfügung.
Ziel ist eine evolutionäre Eröffnungsdatenbank. Pfade werden aktualisiert, das Programm „lernt“ schlechte, bzw. gut Wege.
e4 d4 c4
e5 c5 e6statisch
dynamisch
e4 d4 c4
e5 c5 e6 a5 a6
70% 30%50%
90% 70%
70%
50% 40% 20%
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Eröffnungsbücher
EröffnungsDatenbankFUSC#-EvoBook
Mai 2004
- bla Idee: Hashtabelle bla bla bla
ZIEL: verteiltes FUSC#-EvoBook
- bla Idee: Hashtabelle bla bla bla
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
UCI/WinBoard
Mai 2004
UCI-Protokoll -> Kommunikation mit GUI
Fritzoberfläche
Schachmotor
Konsole
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
UCI/WinBoard
Mai 2004
UCI-Protokoll (Beispiel)
uciid name Shredder 5id author Stefan MKoption name Hash type spin default 1 min 1 max 128option name NalimovPath type string name c:\option name NalimovCache type spin default 1 min 1 max 32option name Nullmove type check default trueoption name Style type combo default Normal var Solid var Normal var Riskyucioksetoption name Hash value 32setoption name NalimovCache value 1setoption name NalimovPath value d:\tb;c\tbisreadyreadyokposition startpos moves e2e4 e7e5go infiniteinfo depth 1 seldepth 0info score cp 13 depth 1 nodes 13 time 15 pv f1b5 info depth 2 seldepth 2info nps 15937info score cp 14 depth 2 nodes 255 time 15 pv f1c4 f8c5 info depth 2 seldepth 7 nodes 255info depth 3 seldepth 7info nps 26437info score cp 20 depth 3 nodes 423 time 15 pv f1c4 g8f6 b1c3 info nps 41562....
stopbestmove g1f3 ponder d8f6
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Forschungsideen
DarkFUSC# neue Engine
Stellungsklassifikation n-dimensionaler Raum, Planvorgabe
Der Plan im Schach Züge, die strategischen Plänen entsprechen, werden höher bewertet
Einsatz von Neuronalen Netzen Zugvorhersage, Planvorgabe, Stellungsbewertung
Reinforcement Learning Anpassung des Evaluationsvektors, Erlernen der Pläne
FUSCH goes to Linux/Handy Portierung nach Linux mit mono
...
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Forschungsideen
Reinforcement Learning Anpassung des Evaluationsvektors
Mai 2004
Schachprogrammier AG
Ende
vielen Dank fürs zuhören ...
Mai 2004
Schachprogrammier AG
Gründung der AGSchachprogrammierung Brettrepräsentation Evaluation Algorithmen Mensch versus Maschine Eröffnungsbücher UCI/WinBoard weitere Planung
Hilfsfolie
Mai 2004