Warum steigt bei Schachengines die Zeit pro Zug an?

By Benno Hartwig Date 2013-09-02 07:59

2 Gedanken:
Die Zeit, die man braucht um einen Ply tiefer zu rechnen, hat sicher auch zu tun mit der Anzahl der in einer Stellung möglichen Züge. Die mag im Mittelspiel besonders groß sein.
Auch die Qualität der Zugsortierung könnte in verschiedenen Spielphasen unterschiedlich gut sein.

Benno
(was bei dir 5 bzw. 15. Minuten dauert, habe ich aber nicht verstanden)

By U. Haug Date 2013-09-02 09:03

[quote="Tom Paul"]
Z.B. im Mittelspiel braucht die Engine für einen Zug tiefer rechnen 5 min. für zwei 15 min. warum?
[/quote]

Hallo Paul,
der Zeitverbrauch steigt nicht linear mit der Rechentiefe an, sondern exponentiell!
Stell dir einfach mal vor, in jeder Stellung wären 30 verschiedene Züge möglich. Wenn du dann einen Zug und alle möglichen Gegenzüge berechnen willst, sind das dann bereits 30 * 30 = 900 Möglichkeiten. Entsprechend:
Zugtiefe 1:    30 Möglichkeiten
Zugtiefe 2:    900 Möglichkeiten
Zugtiefe 3:    27 000 Möglichkeiten
Zugtiefe 4:    810 000 Möglichkeiten
Zugtiefe 5:    24 300 000 Möglichkeiten
Zugtiefe 6:    729 000 000 Möglichkeiten
Du siehst, das steigt rasant. Darin liegt ein riesiges Problem für die Programmierer. Durch geschickte Tricks (z.B. Nichtberücksichtigung "offensichtlich" schlechter Züge und einiges mehr) wird ein etwas langsameres Ansteigen der Rechenzeit ermöglicht, aber linear ist es wie gesagt nicht. Das wäre sonst traumhaft: Suchtiefe 10 kann durchaus in einer Sekunde erreicht sein, aber Suchtiefe 50 dauert halt schon "ein bisschen" länger als fünf Sekunden...

Freundliche Grüße,

Ulrich

By Michael Scheidl Date 2013-09-02 09:05

Beispielsweise ein Durchschnitt von 30 Zugmöglichkeiten je Stellung ergibt für den nächsten Halbzug 30 Züge bzw. Äste des Suchbaumes, für den übernächsten (aus momentaner Perspektive) bereits 30*30 = 900. Aufgrund der Suchtechnik mit ihren diversen Abschneidungen und Reductions usw.usf. brauchen aktuelle Topengines zum Glück je Halbzug nur noch rund die doppelte Zeit wie zuvor. Früher war dieser Faktor viel größer, 5 bis 6 Mal soviel in den alten 1980er-Schachcomputern zum Beispiel.

Eine typische Reihe wäre: (Gesamtzeit bis: Halbzüge Rechentiefe)

Zeit   HZ.
-----------
0:30  23
1:00  24
2:00  25
4:00  26
(usw.)

In der Praxis läuft das natürlich nicht so gleichmäßig.

By Hauke Lutz Date 2013-09-02 15:50

Das sollte doch in gewisser Weise exponentiell sein, oder nicht?

By Benno Hartwig Date 2013-09-02 16:24

[quote="Hauke Lutz"]Das sollte doch in gewisser Weise exponentiell sein, oder nicht?[/quote]Isses doch auch.

By Hauke Lutz Date 2013-09-02 16:33

[quote="Benno Hartwig"]
[quote="Hauke Lutz"]Das sollte doch in gewisser Weise exponentiell sein, oder nicht?[/quote]Isses doch auch.
[/quote]

Oh Mann... ich sollte bevor ich etwas schreibe ein Käffchen trinken...

By U. Haug Date 2013-09-02 16:29

[quote="Hauke Lutz"]
Das sollte doch in gewisser Weise exponentiell sein, oder nicht?
[/quote]

Ich hatte es doch oben beschrieben: Die Rechenzeit steigt näherungsweise exponentiell mit der Suchtiefe.

Genau stimmt es nicht, da greifen etliche Programmiertricks, die in jedem Programm wieder ein wenig anders realisiert werden.