Computerschach mit monochromen Methoden ?

[Octopus]

Es wäre von Interesse zu erfahren, ob neben meiner Wenigkeit sich noch andere, in der Computerschach-Programmierung Aktive mit einem monochromen Ansatz befassen. Neben einer späteren besseren Wartbarkeit der Programme aufgrund des Wegfalls von Farben-Abfragen treten weitere Vorteile auf, wie etwa in der Doppelnutzbarkeit von Cache Entries in einer Transpositionstabelle insbesondere während der Eröffnungs-Phase, da dort vermehrt gespiegelte Stellungen auftauchen, die sich nach Nullmoves überdies auch beim Anzugsrecht entsprechen.

Ein wesentliches Merkmal des (hier von mir benutzten) monochromen Ansatzes ist, dass es zwei synchronisierte, einander gespiegelte Bretter gibt, die nur mehr die Figuren: Feind, K, B, S, L, T, D (und E, Z im 10x8 Fall) aufweisen. Details für eine Feind-Figur finden sich dann jeweils auf dem Spiegelbrett. Eine abgewandelte Form einer Post-Box-Struktur dient dort jeweils als Datenstruktur. Ob Bit-Board verwandte Darstellungen hier sinnvoll wären, kann ich mangels eigener Versuche nicht beurteilen. Auf jeden Fall wäre es zu begrüßen, von anderen, wie auch immer gearteten Ansätzen in der monochromen Computerschach-Programmierung zu erfahren.

[Gerd Isenberg]

Es wäre von Interesse zu erfahren, ob neben meiner Wenigkeit sich noch andere, in der Computerschach-Programmierung Aktive mit einem monochromen Ansatz befassen. Neben einer späteren besseren Wartbarkeit der Programme aufgrund des Wegfalls von Farben-Abfragen treten weitere Vorteile auf, wie etwa in der Doppelnutzbarkeit von Cache Entries in einer Transpositionstabelle insbesondere während der Eröffnungs-Phase, da dort vermehrt gespiegelte Stellungen auftauchen, die sich nach Nullmoves überdies auch beim Anzugsrecht entsprechen.

Ein wesentliches Merkmal des (hier von mir benutzten) monochromen Ansatzes ist, dass es zwei synchronisierte, einander gespiegelte Bretter gibt, die nur mehr die Figuren: Feind, K, B, S, L, T, D (und E, Z im 10x8 Fall) aufweisen. Details für eine Feind-Figur finden sich dann jeweils auf dem Spiegelbrett. Eine abgewandelte Form einer Post-Box-Struktur dient dort jeweils als Datenstruktur. Ob Bit-Board verwandte Darstellungen hier sinnvoll wären, kann ich mangels eigener Versuche nicht beurteilen. Auf jeden Fall wäre es zu begrüßen, von anderen, wie auch immer gearteten Ansätzen in der monochromen Computerschach-Programmierung zu erfahren.

Hallo Reinhard,
ich generiere und mache nur weiße Züge, und spiegel dabei das Brett mit Farbvertauschung.

zobrist(piece, square) == bswap(zobrist(piece xor color, square xor 56))

Ich benutze ein Quad-Bitboard mit "normalen" vertikalen 4-bit Figurencodes. Das ist flott on the fly geflippt. Deine Idee mit zwei Brettern und reduzierten Figurencodes ist sehr interessant.

Gruß,
Gerd

[Octopus]

... ich generiere und mache nur weiße Züge, und spiegel dabei das Brett mit Farbvertauschung.

zobrist(piece, square) == bswap(zobrist(piece xor color, square xor 56))

Ich benutze ein Quad-Bitboard mit "normalen" vertikalen 4-bit Figurencodes. Das ist flott on the fly geflippt. Deine Idee mit zwei Brettern und reduzierten Figurencodes ist sehr interessant. ...

Hallo Gerd,

eine farbliche Vereinheitlichung etwa der Zuggenerierung kann man so erreichen. Ich hatte das einmal eher formal über Templates versucht, die dann über die Farbinfo variierten. Man vermeidet so in beiden Fällen eine Redundanz bei der Code Erstellung und dessen Wartung und räumt so eine Reihe von unliebsamen Fehlerquellen aus. Allerdings scheint es auf diesem Weg noch schwierig zu sein, eine Redundanz der Speicherung farbsymmetrischer Stellungen in der Transpositionstabelle zu vermeiden. Diese kommen speziell in der Eröffnungsphase (sofern diese wie besonders bei randomisierten Strataufstellungen tatsächlich durchrechnet wird) und dann besonders bei der Verwendung von Nullmoves stark gehäuft vor.

Tatsächlich scheint mir mein Ansatz aber noch radikaler und auch effizienter. Ein Farbwechsel wird einfach über die Vertauschung der Zeiger auf die beiden Bretter vorgenommen, etwa nur bei der (dann doppelten) Zugausführung ist eine Spiegelung von Koordinaten nötig, und man kann überdies eine Reihe von Perspektive abhängigen Informationen auf der jeweils relevanten Seite vorhalten.

Farbinformationen entfallen so komplett. Und bei der Zugdarstellung nach außen hin kann man sich aber zur Not auf das letzte Bit im Halbzugzähler beziehen.

Mein neues (noch unfertige) Programm zielt nicht so sehr darauf, im High-End Bereich mitzumischen. Vielmehr beabsichtige ich (ähnlich wie bei SMIRF) eine 8x8 und 10x8 mehrvarianten fähige Engine zu bauen, die trotz Verwendung von Nullmoves (aber ohne die typische bekannte Nullmove-Heuristik) präzise bleibt und insbesondere auch für Mattprobleme taugen wird.

Leider war ich eine Weile lang aus diversen Gründen in der Computerschachprogrammierung demotiviert. Nach weiter nun drei Todesfällen in der Familie in der letzten Zeit aber sollte mich so ein Projekt wieder auf neue, andere Gedanken bringen.

Gruß, Reinhard.

[Gerd Isenberg]

Ja, sehr gut deine Idee mit den zwei Brettern. Muss ich mir mal überlegen. Mein quadbitboard make mit SSE3 (demnächst AVX mit 256-bit YMM Registern) nebst {xor | add, and} mit precalc[fromAspects], [toAspects], byteswaps ist sauschnell, alles in SIMD registern ohne bedingte Sprünge. Nach Rep-test dann der prefetch mit dem frischen hashkey, und en passant "ausrollen" des quadbitboards mit füllweiser Attack und legaler Zug-Generierung. Fast alles SIMD, nur vier bedingte Blöcke bei Fesselungen. Dann kommt der Hashprobe hoffentlich aus dem L1.

Mit Bitboards hat man auch nicht mehr die immamente assymetrische Bitscan Reihenfolge beim Serialisieren von weissen und schwarzen Bitboards, wenn immer nur Weiß am Zug ist.

Sind bei deinen Zobrist key-Summen für "gebyteswappte" gespiegelte Figuren-päärchen, z.B. Zobrist[WB][a2] xor Zobrist[SB][a7] auch nur 32 Bits relevant? Ich scheine damit keine gravierenden Kollisionsprobleme zu haben.

Gerd

[Octopus]

Nun, ich bemerke eine sich noch immer stärker vertiefende Sympathie zu Bitboards! Da muss ich zugeben, dass ich ich Augenblick noch sehr weit entfernt davon bin, bis hinein in die Assembler-Ebene Optimierungen am Code vorzunehmen. Meine Priorität liegt jetzt eher darin, die technischen Verfahren effizienter und klopffester zu machen. Und noch arbeite ich immer mit mehrfach verketteten Figurlisten auf einer Art Post-Box Basis.

Der Zugriff in die Transpositionstabelle über Zobrist-artige Schlüssel wird (wie bereits in SMIRF) zweistufig ausgeführt: der erste 32-Bit Teil dient zur Berechnung des primären Suchindexes, der zweite dient der Verifikation (und ist Bestandteil der hinterlegten Daten) sowie der Identifizierung der gesuchten Daten bei (aktuell) vierfacher Assoziativität. Bislang hatte ich keine erkannten Kollisionen. Um das zu verifizieren hatte ich ausgiebig tiefe PerfT-Läufe in SMIRF vorgenommen, worin Zwischenergebnisse über die gleiche TT-Adressierung gepuffert wurden, und die bislang widerspruchsfreie Ergebnisse geliefert haben. Dieses werde ich im entstehenden Programmpaket natürlich wieder in gleicher Weise vornehmen.

Reinhard.