Diese Seite mit anderen teilen ...

Informationen zum Thema:
Forum:
ChessBits-Computerschachforum
Beiträge im Thema:
8
Erster Beitrag:
vor 16 Jahren, 4 Monaten
Letzter Beitrag:
vor 16 Jahren, 4 Monaten
Beteiligte Autoren:
Rafael B. Andrist, Lars Bremer

Zugsortierung an der Wurzel

Startbeitrag von Lars Bremer am 20.06.2001 22:15

Hi,

hat jemand ein paar Tips oder Links zum o.g. Thema für mich?

thx

Lars
Denkspiele

Antworten:

Hallo Lars

ich kann Dir einfach mal sagen, wie ich es mache - allerdings ist mein Programm punkto Zugsortierung nicht besonders gut:

Der Zugsortierung an der Wurzel kommt v.a. dann besondere Bedeutung zu, wenn man Iterative Deepening verwendet, deshalb setze ich das im Folgenden voraus.

1. beim ersten Mal werden die Züge wie bei jedem beliebigen Knoten des Suchbaumes sortiert (SEE, History- und Killer-Heuristic); zuerst wird natürlich der Zug aus dem Hash probiert
2. bei den darauffolgenden Malen werden die Züge nach der Anzahl der Knoten des jeweiligen Unter-Suchbaumes (das engl. subtree wäre hier viel einfacher und klarer :-), aber ich schreibs jetzt halt dt.) sortiert. Falls der beste Zug nicht die maximale Knotenzahl hat, gibt man ihm einfach eine Knotenzahl, die um 1 höher ist als das Maximum. Dieses Verfahren stammt von Prof. Hyatt; die Lösung taktischer Probleme soll damit etwas schneller gelingen. Ich habe zwar nur eine geringe Verbesserung festgestellt, aber immerhin.

Gruss

Rafael B. Andrist

von Rafael B. Andrist - am 21.06.2001 12:22
Hi,

so einfach ist das? Einfach nach Knotenzahl? Ich hatte gedacht, da gibt es noch wilde Tricks :)) Muß ich mal probieren. THX!

Lars
Denkspiele


von Lars Bremer - am 22.06.2001 09:10
Lars Bremer schrieb:
>
> Hi,
>
> so einfach ist das? Einfach nach Knotenzahl? Ich hatte gedacht,
> da gibt es noch wilde Tricks :)) Muß ich mal probieren. THX!
>
> Lars

Man kann es natürlich auch noch komplizierter machen, aber soweit ich weiss, kommt dabei nichts Besseres heraus. Die Idee ist ja auch irgendwie einleuchtend: je "interessanter" ein Zug ist, um so mehr Knoten hat er. Z.B. führt das klassische Läuferopfer auf h7 zu Verwicklungen, die analysiert werden müssen. Ab einer gewissen Suchtiefe sieht man dann die Kompensation bzw. den Gewinn. Dazu ist es sinnvoll, die "interessanten" Züge unmittelbar hinter dem aktuell besten Zug einzuordnen. Wenn diese gewinnen, kann prakt. der ganze restliche Baum abgeschnitten werden.

Rafael B. Andrist

von Rafael B. Andrist - am 22.06.2001 16:30
Hi,

>Die Idee ist ja auch irgendwie einleuchtend: je "interessanter" ein Zug ist, um so mehr Knoten hat er.

Das finde ich gar nicht so einleuchtend, schließlich sind die Züge, deren Wert nicht exakt bestimmt wird, doch relativ zufällig bez. Knotenzahl (wann und wo im Baum gibt's Cutoffs). Und nur weil es in best. Stellungen viele annährend gleichwertige Züge gibt, was zu vielen untersuchten Knoten führen kann, heißt das ja nicht, daß diese Varianten "interessanter" sind aus Programmsicht.
Es würden mir aber auch Gründe dafür einfallen, man (ich zumindest) liegt bei sowas oft mal daneben :)
Eher würde ich annehmen, daß das was mit Hasheinträgen zu tun hat, wenn eine Sortierung nach Knoten effizienter ist.

cu

Lars
Denkspiele


von Lars Bremer - am 22.06.2001 17:32
Lars Bremer schrieb:
>
> Hi,
>
> >Die Idee ist ja auch irgendwie einleuchtend: je
> "interessanter" ein Zug ist, um so mehr Knoten hat er.
>
> Das finde ich gar nicht so einleuchtend, schließlich sind die
> Züge, deren Wert nicht exakt bestimmt wird, doch relativ
> zufällig bez. Knotenzahl (wann und wo im Baum gibt's Cutoffs).
> Und nur weil es in best. Stellungen viele annährend
> gleichwertige Züge gibt, was zu vielen untersuchten Knoten
> führen kann, heißt das ja nicht, daß diese Varianten
> "interessanter" sind aus Programmsicht.

Die Methode ist vor allem für die Lösung taktischer Probleme effizient.

> Es würden mir aber auch Gründe dafür einfallen, man (ich
> zumindest) liegt bei sowas oft mal daneben :)
> Eher würde ich annehmen, daß das was mit Hasheinträgen zu tun
> hat, wenn eine Sortierung nach Knoten effizienter ist.

Da kann ich hingegen mir nun nicht genau vorstellen, worauf Du hinaus willst.

Rafael B. Andrist

von Rafael B. Andrist - am 22.06.2001 17:49
Hi,

ich meinte, daß wichtige Stellungen eher in der Hashtabelle landen. Dürfte aber zumindest bei Schachprogrammen wegen der großen Anzahl der Züge nicht so zutreffen.

cu

Lars
Denkspiele


von Lars Bremer - am 23.06.2001 09:11
Lars Bremer schrieb:
>
> Hi,
>
> ich meinte, daß wichtige Stellungen eher in der Hashtabelle
> landen. Dürfte aber zumindest bei Schachprogrammen wegen der
> großen Anzahl der Züge nicht so zutreffen.
>
> cu
>
> Lars

Dass kommt natürlich dann auf das Hash-Replacement-Vefahren an, das man verwendet. Die Knotenzahl als Kriterium soll ja auch da am besten sein. Ich begnüge mich hier jedoch mit einer Kombination aus Suchtiefe und Alter des Eintrages, da ich die Suchtiefe sowieso speichern muss, und die Knotenzahl wieder mindestens 32 Bit wegschnappen würde, falls ich die auch diese mitspeichern würde. Und ein Eintrag im Hash sollte ja möglichst klein sein.

Wenn der Hash optimal funktioniert und die PV inkl. Window für jeden Zug der an der Wurzel gespeichert ist, sind durch Zugsortierung nach Knotenzahl im Durchschnitt nicht viel mehr als ein paar Prozent zu holen, in einigen Stellungen aber vielleicht bis zu 30% (Schätzwert).

Rafael B. Andrist

von Rafael B. Andrist - am 23.06.2001 09:22
Zur Information:
MySnip.de hat keinen Einfluss auf die Inhalte der Beiträge. Bitte kontaktieren Sie den Administrator des Forums bei Problemen oder Löschforderungen über die Kontaktseite.
Falls die Kontaktaufnahme mit dem Administrator des Forums fehlschlägt, kontaktieren Sie uns bitte über die in unserem Impressum angegebenen Daten.