Schach-Bitboards und Blocken
-
Hallo.
Offensichtlich bietet eine Repräsentation der Figuren / der gedeckten Felder etc. mittels Bitboards (hier 64-Bit-UInts) eine höhere Leistung. Nun beim Implementieren fällt mir eine kleine Aufgabe schwer. Ich möchte zum Beispiel prüfen ob der Läufer auf a7 dem König auf h1 Schach bietet, auf g2 jedoch ist ein Bauer, der diese Angriffsdiagonale des Läufers blockiert. Die Bitboards:
Angegriffen durch den schwarzen Läufer:
1-1----- -------- 1-1----- ---1---- ----1--- -----1-- ------1- -------1Positionen der weissen Bauern:
-------- -------- -------- -------- --11---- -1------ 1----111 --------Position des weissen Königs:
-------- -------- -------- -------- -------- -------- -------- -------1Gibt es effiziente und allgemeine Methoden diese Angriff-Bitboards wegen blockierenden Figuren zu beschränken? Dies soll auch für Türme / Damen möglich sein und ebenso wenn schwarz selbst eine Figur dazwischen stellt.
Wenn ich naiv die Felder durchiteriere, dann bringen die Bitboards nichts. Da wäre ich mit einer naiven Brett-Repräsentation mit einem Array der Felder gleich schnell.Gruss.
-
asfdlol schrieb:
Offensichtlich bietet eine Repräsentation der Figuren / der gedeckten Felder etc. mittels Bitboards (hier 64-Bit-UInts) eine höhere Leistung.
Aber nur, wenn man recht pfiffig ist und Sachen auch parallelisieren kann.
asfdlol schrieb:
Wenn ich naiv die Felder durchiteriere, dann bringen die Bitboards nichts. Da wäre ich mit einer naiven Brett-Repräsentation mit einem Array der Felder gleich schnell.
Genau.
asfdlol schrieb:
Gibt es effiziente und allgemeine Methoden diese Angriff-Bitboards wegen blockierenden Figuren zu beschränken?
asfdlol schrieb:
Nun beim Implementieren fällt mir eine kleine Aufgabe schwer. Ich möchte zum Beispiel prüfen ob der Läufer auf a7 dem König auf h1 Schach bietet,
Wozu wissen, ob ein Läufer schach bietet? Was Du brauchst, ist ein möglichst schneller Züge-Generator. Ok, kannst die Zielpositionen des Läufers mit dem feindlichen König ANDen und wenn !=0, dann steht er durch den Läufer im Schach.
asfdlol schrieb:
auf g2 jedoch ist ein Bauer, der diese Angriffsdiagonale des Läufers blockiert.
Ich schätze, Du bist im Gedanken gerade bei sowas https://chessprogramming.wikispaces.com/Classical+Approach
und überhaupt
https://chessprogramming.wikispaces.com/Sliding+Piece+Attacks#Single Sliding Piece Attacks-By Calculationasfdlol schrieb:
Gibt es effiziente und allgemeine Methoden diese Angriff-Bitboards wegen blockierenden Figuren zu beschränken? Dies soll auch für Türme / Damen möglich sein und ebenso wenn schwarz selbst eine Figur dazwischen stellt.
Naja, schwarz ist nicht das Problem, als erste Idee würde ich allen eigenen Steinen zusätzlich die 8 Nachbarn markieren
s=schwarzeSteine and not angreifenderLäufer; w=weißeSteine; s|=(s<<1)|(s>>1),s|=(s<<8)|(s>>8); bremsFelder=s|w;, und dann hält der Tumm/Läufer/Dame schon (einen dieser Schatten schlagend) genau ein Feld vor der eigenen Figur.
Schätze, Du magst jetzt ganz chessprogramming.wikispaces.com durchlesen.
-
volkard schrieb:
asfdlol schrieb:
Offensichtlich bietet eine Repräsentation der Figuren / der gedeckten Felder etc. mittels Bitboards (hier 64-Bit-UInts) eine höhere Leistung.
Aber nur, wenn man recht pfiffig ist und Sachen auch parallelisieren kann.
Ach, lediglich dann? Ich dachte, auch so ist die Variante schneller, da die Bitboards in ein Register passen und da man oft mit Bitweise-Operatoren arbeitet.
volkard schrieb:
Wozu wissen, ob ein Läufer schach bietet? Was Du brauchst, ist ein möglichst schneller Züge-Generator. Ok, kannst die Zielpositionen des Läufers mit dem feindlichen König ANDen und wenn !=0, dann steht er durch den Läufer im Schach.
Brauche ich nicht Funktionen, die von Stellung feststellen, ob sie Schach / Doppelschach / Schachmatt sind? Ich dachte mir, dass ich die brauche um darauf die Zuggenerierung und die Evaluation aufzubauen. Z.B. kann ich im Schach nicht einfach irgendwas spielen, sondern muss das Schach irgendwie verhindern. Und ausserdem muss ich ein Matt in 1 um jeden Preis verhindern, daher muss ich das Matt (was ja auch ein Schach ist) sehen können.
Und die Zielpositionen sind eben das, was ich nicht mit einfachen Bitweise-Operatoren hinbekommen habe. Irgendwie muss ich dort ja auch die Schatten, die andere Figuren werfen, rausnehmen.
volkard schrieb:
asfdlol schrieb:
auf g2 jedoch ist ein Bauer, der diese Angriffsdiagonale des Läufers blockiert.
Ich schätze, Du bist im Gedanken gerade bei sowas https://chessprogramming.wikispaces.com/Classical+Approach
und überhaupt
https://chessprogramming.wikispaces.com/Sliding+Piece+Attacks#Single Sliding Piece Attacks-By Calculationasfdlol schrieb:
Gibt es effiziente und allgemeine Methoden diese Angriff-Bitboards wegen blockierenden Figuren zu beschränken? Dies soll auch für Türme / Damen möglich sein und ebenso wenn schwarz selbst eine Figur dazwischen stellt.
Naja, schwarz ist nicht das Problem, als erste Idee würde ich allen eigenen Steinen zusätzlich die 8 Nachbarn markieren
s=schwarzeSteine and not angreifenderLäufer; w=weißeSteine; s|=(s<<1)|(s>>1),s|=(s<<8)|(s>>8); bremsFelder=s|w;, und dann hält der Tumm/Läufer/Dame schon (einen dieser Schatten schlagend) genau ein Feld vor der eigenen Figur.
Danke, hat mir schon geholfen.
volkard schrieb:
Schätze, Du magst jetzt ganz chessprogramming.wikispaces.com durchlesen.
In der Tat, jedoch brenne ich auch darauf, schlussendlich mal ein Spiel gegen meine eigene Engine zu spielen (auch wenn das noch ein langer Weg sein wird).
Aber dieses Wiki sieht sehr tief und ausführlich aus obwohl es für ein so spezifisches Thema ist. Wahnsinn.Noch eine Frage:
Später werde ich dann ja auch einen Suchbaum konstruieren. Ich denke, da wird pro Node ein Zusand des Spiels gespeichert. Das Zuggenerieren nur anhand von Bitboards stelle ich mir jedoch ineffizient vor (das Wiki bestätigt mich gewissermassen mit "Bitboard approaches often keep a 8x8 board to determine a piece by square, [...]."). Das 8x8-Board plus die acht Bitboards brauchen einiges an Speicher, und das dann für jeden Node... Wie soll der Zustand dann also aussehen?Danke schonmal.
-
asfdlol schrieb:
volkard schrieb:
Wozu wissen, ob ein Läufer schach bietet? Was Du brauchst, ist ein möglichst schneller Züge-Generator. Ok, kannst die Zielpositionen des Läufers mit dem feindlichen König ANDen und wenn !=0, dann steht er durch den Läufer im Schach.
Brauche ich nicht Funktionen, die von Stellung feststellen, ob sie Schach / Doppelschach / Schachmatt sind? Ich dachte mir, dass ich die brauche um darauf die Zuggenerierung und die Evaluation aufzubauen. Z.B. kann ich im Schach nicht einfach irgendwas spielen, sondern muss das Schach irgendwie verhindern. Und ausserdem muss ich ein Matt in 1 um jeden Preis verhindern, daher muss ich das Matt (was ja auch ein Schach ist) sehen können.
Du bist nicht dumm genug. Schach, Doppelschach, Matt, das alles festzustellen dauert ja 1000 Takte! Sei so dumm wie dein 6-jähriges Kinde, dem Du das Schachspiel beibringst: Es wird gespielt, bis ein König geschlagen wurde. Das machste einfach so, daß der König gleich 99 Bauern wert ist und machst genau gar nix. Fertig.
-
asfdlol schrieb:
Noch eine Frage:
Später werde ich dann ja auch einen Suchbaum konstruieren. Ich denke, da wird pro Node ein Zusand des Spiels gespeichert.Oder auch nicht. Bei Breitensuche müßtest Du (fast) alle Stellungen speichern. Bei Tiefensuche brauchste nicht.
Beispiel für rekursive Tiefensuche mit Ziehen und Zurücknehmen.
http://www.c-plusplus.net/forum/322028asfdlol schrieb:
Das 8x8-Board plus die acht Bitboards brauchen einiges an Speicher, und das dann für jeden Node... Wie soll der Zustand dann also aussehen?
Für den Baum brauchste nicht zu speichern, sondern nur für die "Hashtable", wo Du Dir bereits berechnete Stellungen mit Bewertung speicherst, um Zeit zu sparen. Dazu muss die Stellung nicht in dem Format vorliegen, das Du für schnelle Zuggenerierungen brauchst. Irgend ein eindeutiges Format lass Dir halt einfallen und führe das auch noch parallel mit. Naja, ganz so eindeutig muss das Format nichtmal sein, kannst auch hashen. Es bietet sich zobrist hashing an.
-
volkard schrieb:
Du bist nicht dumm genug. Schach, Doppelschach, Matt, das alles festzustellen dauert ja 1000 Takte! Sei so dumm wie dein 6-jähriges Kinde, dem Du das Schachspiel beibringst: Es wird gespielt, bis ein König geschlagen wurde. Das machste einfach so, daß der König gleich 99 Bauern wert ist und machst genau gar nix. Fertig.
Wie simpel es sein kann.
volkard schrieb:
[...]
Alles klar. Dann weiss ich nun wie ich das System etwa aufbauen muss. Ich bin noch relativ am Anfang (es sind erst ein paar simple Repräsentationen / FEN-Parser implementiert) und habe hiermit nur mal nachgefragt damit ich ein Gespür dafür bekomme, wie und was ich zu programmieren habe (nicht dass ich alles umsonst doppelt mache wenn ich nun eine sinnlose / langsame Methode wähle).
Ich werde mich dann mit der Zeit (wenn ich weiter bin) bestimmt noch einmal diesbezüglich melden. Danke.