| Autor |
Beitrag |
fuulf
Beiträge: 24
|
Verfasst: Di 13.04.10 00:46
Hallo,
wenn man ein Schachprogramm mit unoptimierter Alpha-Beta-Suche schreibt und zum Ausrechnen beim Spielstart bei einer Tiefe von 6 Zügen (also 3 Spielzüge vom Spieler und 3 Züge vom Gegenspieler werden im Suchbaum berücksichtig) mit einem AMD Phenom(tm) 9650 Quad-Core Processor 2.30 GHz knappe 2 Minuten benötigt werden, stimmt dann was mit der Implementierung nicht, oder ist das normal, dass das so lange dauert? Moderiert von  Narses: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Di 13.04.2010 um 09:58
|
|
Thorsten83
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 13.04.10 14:20
Hi,
hast du mal mitgezählt, wie viele Stellungen bewertet werden?
Ich würde mal darauf tippen dass die Implementierung ziemlich langsam ist, wie repräsentierst du das Spielbrett, wie generierst du Züge?
Ein beliebter Fehler ist auch
  Quelltext
statt
Quelltext
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Di 13.04.10 14:36
Sagen wir mal so: mein Ansatz war ähnlich langsam (eher noch lahmer), als ich mal damit rumgespielt habe.
Man darf also annehmen, dass die erstbeste naive Implementation immer so lahm ist 
Langsam war damals vor allem die Zuggenerierung, die Bewertung war (obwohl ich das anders vermutet hatte) nicht so das Problem. _________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Di 13.04.10 18:14
hi 
Also erstmal musst du natürlich vom Quadcore nur den einen Core rechnen. 
Wenn du magst, kannst du den Quelltext hier mal hochladen. Ich habe selber mal ein Schachprogramm geschrieben und mich deshalb mit Optimierungen für aß beschäftigt - bin aber nur bis zur IDE gekommen, bis ich herausgefunden habe, dass man starke Schach-Engines kostenlos herunterladen und per Protokoll im Programm verwenden kann(Rybka, etc.). Wie viel diese Optimierungen ausmachen, würde mich mal interessieren: Rybka2.2 x64(Multithreading) schafft bei mir auf i5 Quad @2.67GHz folgendes:
Analyse der Startstellung
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
| FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Rybka 2.2 64 bit:
2 00:00 442 452.608 +0,05 Sb1c3
3 00:00 648 663.552 +0,15 Sb1c3
4 00:00 1.032 1.056.768 +0,13 Sb1c3
5 00:00 2.042 130.688 +0,05 Sb1c3 Sb8c6
6 00:00 3.885 248.640 +0,05 Sb1c3 Sb8c6 Sg1f3
7 00:00 10.588 230.683 +0,08 Sb1c3 Sb8c6 Sg1f3 Sg8f6
8 00:00 19.785 256.453 +0,04 Sb1c3 Sg8f6 Sg1f3 e7e6 d2d4
9 00:00 29.643 242.835 +0,08 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 e7e6
10 00:00 56.477 246.095 +0,09 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 e7e6 d4d5
11 00:01 256.119 270.935 +0,06 Sb1c3 d7d5 e2e3 Sg8f6 Lf1b5+ Lc8d7 Sg1f3 Ld7xb5 Sc3xb5 a7a6
11 00:01 274.464 264.892 +0,11 e2e4 Sb8c6 Sg1f3 Sg8f6 Sb1c3 d7d5 e4xd5 Sf6xd5 Lf1c4 Lc8e6
12 00:01 316.418 262.783 +0,05 e2e4 Sb8c6 Sg1f3 Sg8f6 Sb1c3 e7e5 Lf1c4 Lf8c5 00
13 00:02 615.665 288.531 +0,04 e2e4 Sb8c6 Sg1f3 e7e5 Sb1c3 Sg8f6 Lf1c4 Lf8c5 00 00
14 00:03 1.075.407 328.231 +0,05 e2e4 Sb8c6 Sg1f3 e7e5 Sb1c3 Sg8f6 Lf1c4 Lf8c5 00 00 d2d3
15 00:07 3.122.431 411.554 +0,04 e2e4 e7e5 Sb1c3 Sg8f6 Sg1f3 Sb8c6 Lf1c4 Lf8c5 00 00 d2d3 d7d6
15 00:10 4.437.541 429.615 +0,10 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 d7d5 g2g3 Lc8f5 Sf3h4 Lf5g4 Lf1g2 e7e6
16 00:16 7.573.981 485.980 +0,05 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 d7d5 g2g3 g7g6 Lf1g2 Lf8g7 00 00 Sf3e5
17 00:24 12.955.941 531.845 +0,06 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 d7d5 g2g3 g7g6 Lc1f4 Sf6h5 Lf4g5 Lf8g7 Lf1g2 00
18 00:52 27.605.229 538.330 +0,07 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 d7d5 g2g3 g7g6 Sf3e5 Lf8g7 Lf1g2 00 00 Lc8f5
19 01:27 49.376.177 575.572 +0,05 Sb1c3 Sg8f6 Sg1f3 Sb8c6 d2d4 d7d5 Lc1f4 Sf6h5 Lf4e3 g7g6 g2g3 Lf8g7 Lf1g2 00
19 02:46 91.393.909 562.559 +0,05 e2e4 e7e5 Sb1c3 Sg8f6 Sg1f3 Sb8c6 Lf1b5 Lf8c5 Sf3xe5 Sc6xe5 d2d4 a7a6 Lb5a4 Lc5d6
20 06:07 208.831.786 582.049 +0,07 e2e4 e7e5 Sg1f3 Sb8c6 Sb1c3 Sg8f6 Lf1b5 Lf8c5 00 00 Sf3xe5 Sc6xe5 d2d4 Lc5d6 |
lg, _________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
fuulf 
Beiträge: 24
|
Verfasst: Mi 14.04.10 19:15
Hallo,
ich würde den Quelltext eigentlich gerne einstellen, aber wenn es gut läuft will ich es vielleicht noch als Schulleistung verticken (notenmäßig) und wenn das dann schon vorher online war, wird einem dann ja manchmal vorgeworfen, man hätte es einfach nur von jemandem aus dem Internet kopiert.
Optimierung ist natürlich wichtig, aber ich denke am wichtigsten ist zunächst mal, dass es sich wirklich um eine korrekte Alpha-Beta-Suche handelt.
Ich hab mal ausgewertet, wieviele Bewertungen durchgefüht werden. Es handelt sich um die Startstellung und es wird der Zug für den Spieler unten mit den weißen Figuren ausgerechnet. Die Suchtiefe gibt die Anzahl der berücksichtigten (Halb-)zügen an. So werden beispielsweiße bei einer Suchtiefe = 3 der Zug von Weiß, der Gegenzug von Schwarz und der darauffolgende Gegenzug von Weiß in den Spielbaum aufgenommen. "MiniMax-Wert" steht für den Zahlenwert, der am Ende gefunden wurde. Dabei ist aus Sicht des Spielers Weiß der Zug umso besser, je größer der Wert. Eine Einheit steht für einen zu erwartenden Materialvorteil von einem Bauern.
Hier die Auswertung:
Quelltext
1:
2:
3:
4:
5:
6:
7:
| Suchtiefe | Bewertungen | Cutoffs | Alpha-Cutoffs | Beta-Cutoffs | MiniMax-Wert
1 | 20 | 0 | 0 | 0 | 0
2 | 514 | 19 | 19 | 0 | -9
3 | 2103 | 149 | 19 | 130 | -5
4 | 70711 | 2483 | 2241 | 242 | -14
5 | 574992 | 118320 | 2467 | 115853 | -9
6 | 27959133 | 679119 | 598632 | 80487 | -13 |
Gibt es dafür eigentlich eine offizielle Tabelle, wie es richtig sein müsste?
Könnte das überhaupt sein, dass der MiniMax-Wert selbst bei ungerader Suchtiefe negativ ist? Und dass es bei einer Suchtiefe von 6 weniger Beta-Cutoffs als bei der Suchtiefe 5 gibt?
|
|
Thorsten83
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mi 14.04.10 22:25
Hey,
da stimmt irgendwas überhaupt nicht...
Mit 2 Halbzügen kann der Gegner ja auf jeden der 20 Züge von Weiß mit 20 Gegenzügen reagieren, daher sollte der komplette Spielbaum nur 400 Blätter haben...
Eine Tabelle kann's nicht geben, da die Anzahl der Stellungsbewertungen davon abhängt, wie die Züge sortiert und auch bewertet werden.
Als Größenordnung: Ein Alphabeta mit perfekter Zugsortierung braucht 2*b^(d/2)-1 Stellungsbewertungen für eine Suche mit gerader Suchtiefe d, wenn jeder der Spieler IMMER b Züge zur Auswahl hat.
|
|
GuaAck
Beiträge: 378
Erhaltene Danke: 32
Windows 8.1
Delphi 10.4 Comm. Edition
|
Verfasst: Di 20.04.10 22:23
Hi,
der alpha-beta-Algorithmus ist verzwickter als er gelegentlich in der Literatur dargestellt wird. Ich hatte das einmal an der übersichlichen Situation "1r5q/1p5b/8/8/4n3/4R3/8/4R2R w - - 0 1" untersucht. Näheres anbei, vielleicht hilft es.
Gruß Guenther
Einloggen, um Attachments anzusehen!
|
|
JoelH
Beiträge: 806
Erhaltene Danke: 17
Win10
Delphi Alexandria 11.2 Patch 1
|
Verfasst: Sa 19.06.10 11:43
| fuulf hat folgendes geschrieben: |
Könnte das überhaupt sein, dass der MiniMax-Wert selbst bei ungerader Suchtiefe negativ ist? Und dass es bei einer Suchtiefe von 6 weniger Beta-Cutoffs als bei der Suchtiefe 5 gibt? |
Die Antwort kommt vielleicht spät aber ich bastle auch gerade an einem Programm, ds diesen Algo verwendet, auch wenn es nicht Schach spielt, sondern ein spielerisches Eigengewächs.
Aber zu den Fragen,
Ja, das mit den negativen Werten kann schon sein, wenn eine Seite wirklich schlecht steht bringen auch gute Züge nur noch wenig. U
nd das mit dem Alpha/Beta-Cuttoff-Wechsel ist auch richtig, da ja immer für die "andere Seite" optimiert wird ergibt sich das so. Zumindest hab ich das mit den Alpha/Beta so verstanden.
Vielleicht eine Seite die dir bei der Programmierung helfen kann
chessprogramming.wikispaces.com/_________________ mfg. Joel
|
|
|
