Controlled
Conspiracy Number
Search
Schriftliche Arbeit zur Erlangung
des Doktorgrades
des Fachbereichs Mathematik / Informatik
der Universit¨at-Gesamthochschule Paderborn
von
Ulf Lorenz
Fachbereich Mathematik / Informatik
Universit¨at GH Paderborn
Paderborn, Deutschland
Dezember 2000
2
Inhaltsverzeichnis
1 Einleitung 1
1.1 Spiele .................................... 1
1.2 Computerschach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Die Anf¨ange . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Modernes Computerschach . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Weitreichende Bedeutung . . . . . . . . . . . . . . . . . . . . . 5
1.3 Algorithmen und Software . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Minimax: Der Basisalgorithmus . . . . . . . . . . . . . . . . . . 7
1.3.2 Der
-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 N¨aherungsl¨osungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Conspiracy Number Search . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.1 Conspiracy Numbers (dt. Verschw¨orungszahlen) . . . . . . . . . 12
1.5.2 Conspiracy Number Search (CNS) . . . . . . . . . . . . . . . . . 13
1.5.3 Beobachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Ergebnisse dieser Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7 Aufbau dieser Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Definitionen und Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.8.1 Allgemeine Definitionen . . . . . . . . . . . . . . . . . . . . . . 19
1.8.2 Spezielle Definitionen . . . . . . . . . . . . . . . . . . . . . . . 22
2 Das Cc2s-Verfahren 25
2.1 Beschreibung des Cc2s-Algorithmus . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Conspiracy Numbers und blattdisjunkte Strategien . . . . . . . . 25
2.1.2 Metabeschreibung des neuen Vorgehens . . . . . . . . . . . . . . 27
2.1.3 Ein erstes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.4 Algorithmische Details . . . . . . . . . . . . . . . . . . . . . . . 30
ii Inhaltsverzeichnis
2.1.5 Komplexes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2 Hergeleitete Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.1 Vergleich zwischen der Cc1s und dem
-Algorithmus . . . . . . 46
2.2.2 Cc2s im Vergleich zu Auswahl-Expansion-Aktualisierung basier-
ten Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3 Heuristiken zur Beschleunigung . . . . . . . . . . . . . . . . . . . . . . 48
2.4 Experimentelle Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.4.1 Baumbeschneidungen und schnelle Bewertungen . . . . . . . . . 56
2.4.2 Form der Suchb¨aume . . . . . . . . . . . . . . . . . . . . . . . . 57
2.5 Beweise zu Kap. 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 Der Parallele Cc2s-Algorithmus 65
3.1 Hardware .................................. 66
3.2 Bekannte parallele Spielbaumsuchverfahren . . . . . . . . . . . . . . . . 69
3.2.1 Schnelle Zugerzeugung und Bewertung . . . . . . . . . . . . . . 69
3.2.2 Parallele Fenstersuche . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.3 Spielbaumzerlegung . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3 Spielbaumzerlegung beim Cc2s-Algorithmus . . . . . . . . . . . . . . . 72
3.3.1 Verwertung von Parallelit¨at . . . . . . . . . . . . . . . . . . . . . 72
3.3.2 Designentscheidungen bei der Lastverteilung . . . . . . . . . . . 74
3.4 Senderinitiierte parallele Cc2s-Suche . . . . . . . . . . . . . . . . . . . . 76
3.4.1 Grundversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4.2 Abgaben von Bewertungen . . . . . . . . . . . . . . . . . . . . . 87
3.4.3 Verteilte Transpositionstabelle . . . . . . . . . . . . . . . . . . . 88
3.5 Experimentelle Leistungsbewertung . . . . . . . . . . . . . . . . . . . . 89
3.5.1 Turniere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.2 BT2630 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.3 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.5.4 Speedupmessungen f¨ur senderinitiierte Cc2s . . . . . . . . . . . 94
3.5.5 Streuungsmessungen auf der HPCLine . . . . . . . . . . . . . . 100
4 Spielbaumsuche mit Fehlern 103
4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.1.1 Das Vorgehen der Anwender . . . . . . . . . . . . . . . . . . . . 104
4.1.2 Fehlermodelle anderer Autoren . . . . . . . . . . . . . . . . . . 104
Inhaltsverzeichnis iii
4.2 Spielbaumsuche ¨uber Bewertungen mit Fehlern . . . . . . . . . . . . . . 106
4.3 Spielbaumsuche ¨uber Bewertungen mit zuf¨alligen Fehlern . . . . . . . . 108
4.3.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3.2 Interpretation der Ergebnisse . . . . . . . . . . . . . . . . . . . . 112
4.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.5 Nachtrag: Modell und Wirklichkeit . . . . . . . . . . . . . . . . . . . . . 124
5 Zusammenfassung und offene Probleme 129
A Der BT2630-Test 131
B Literaturverzeichnis 135
Loading more pages...