Zuggenerator

By Lothar Jung Date 2021-10-15 10:00 Edited 2021-10-15 10:03 Upvotes 1

Hier ein Thread auf TalkChess über einen sehr schnellen Bitboard-Zuggenerator:

http://talkchess.com/forum3/viewtopic.php?f=7&t=78352#p908018

I would like to release the sourcecode to the fastest Chess movegenerator I was able to write during the last 2½ years.
It is able to generate 2 Billion Moves per Thread per Second. No Hashing is used - and it still is single threaded.

What makes it so fast is summarized below - but in short: Make/Unmake and a Movelist is not needed and 2x slower than a visitor pattern - which is even more powerful and faster and implemented in this movegen. Also expanding the enumeration template for color to include enpassant and all castling squares helps a lot!

Summary:
Explanation Article: https://www.codeproject.com/Articles/53 ... egenerator
Sourcecode: https://github.com/Gigantua/Gigantua
Linux/Windows Binary: https://www.codeproject.com/KB/Articles ... nLinux.zip

It is a Bitboard movegenerator. As it turns out incremental bitboards are slower for this type of generator. Remembering previous from | to square is more expensive than recalculating many of the moves. It is possible to add that to the sourcecode easily and maybe I will merge the exploration branches in the future.

It uses heavy template instantiation with a template inlined "callback" function. What makes this so fast is that you dont need a movelist anymore for this approach. When a legal move is encountered it instantly is decided what to do with it. Expand more - Store - Or sort into a list of good moves. All possible with this approach.

The pin and checkmask is what makes bitboards so good. With a handful of & operations all moves are pruned to only cointain legal moves. An I mean all moves. Even the most ugliest of pinned - prevention of promotion - or check double check pin combos are almost free and certainly branchless!

Also what I think no one implemented before me: Enpassant and Castling are moved to a Boardstate Template. You can input any fen - the appropriate template is called with a single switch and off you go enumerating. The cost of a single switch at the very start of enumerating saves billions of noop instructions for castling / enpassant. The Boardstate contains: Moving Color, HasEnpassant, 4 Castling Squares. Which makes the C++ compiler emit 64 functions for all 6 independent flags.

The beauty of this is that the current color implemented as a template removes all lookups like pawn move direction etc. Code checks for Castling are only in the assembly if it is possible to castle. Once a Rook / King moves - Not a single instruction is used for castling. Not even a single if. It gets if constexpr pruned away.

The reciever for all possible moves are 8 Methods that are named after each piece and movetype - and the from - to squares are there for you in bitboard form. So its almost free to count all castling moves etc. It wont even add a single if instruction. This approach needs no movelist at all - but you can still store the move inside the callback.

What I would like for you the reader to do: Try to find any mistakes or slow stuff in my code. Tear it apart - think about it - ideally comment below with ideas how to make it faster - or better send a pull request into the github repo!
https://github.com/Gigantua/Gigantua

Compile with Visual studio or Linux - Clang -march=native -std=c++20 -lstdc++ -O3 Gigantua.cpp -flto -o giga_clang

Greetings! - Daniel Inführ

References:
http://www.talkchess.com/forum3/viewtop ... =7&t=78230

By Lothar Jung Date 2023-07-16 17:23 Edited 2023-07-16 17:34

Ein Bitboard-Zuggenerator ist eine Methode, um alle möglichen Züge in einem Schachspiel effizient zu generieren. Er verwendet Bitboards, um das Schachbrett kompakt darzustellen, wobei jedes Bit einem Feld auf dem Brett entspricht.

Die Datenstruktur des Schachbretts in einem Bitboard-Zuggenerator besteht aus insgesamt 12 Bitboards: 6 für die eigenen Figuren und 6 für die gegnerischen Figuren. Jedes Bitboard hat eine Größe von 64 Bits, da das Schachbrett aus 64 Feldern besteht. Die Gesamtgröße der Datenstruktur beträgt somit 768 Bits (12 * 64).

Die Algorithmen zur Abfrage des Bitboard-Zuggenerators basieren auf Bitwise-Operationen, die auf den Bitboards angewendet werden. Die grundlegenden Operationen umfassen AND, OR, XOR und NOT. Diese Operationen werden verwendet, um die möglichen Züge einer Figur zu berechnen, indem sie die Bitboards der eigenen Figuren sowie der gegnerischen Figuren kombinieren und Bitmuster vergleichen.

Die Algorithmen zur Abfrage des Bitboard-Zuggenerators verwenden Schleifen, die über die einzelnen Felder des Schachbretts iterieren und die Bitwise-Operationen auf die entsprechenden Bitboards anwenden. Durch die effiziente Nutzung von Bitwise-Operationen können alle möglichen Züge einer Figur in einem einzigen Durchlauf über das Schachbrett berechnet werden.

Zusätzlich zu den grundlegenden Operationen können weitere Optimierungen und Erweiterungen implementiert werden, wie z. B. die Verwendung von magischen Bitboards für Sliding-Piece-Züge (Turm, Läufer, Dame) oder das Generieren von Pseudo-Zügen zur Vorabberechnung von Angriffsinformationen. Diese Techniken verbessern die Effizienz des Zuggenerators weiter.

Hier ist ein vereinfachtes Beispiel für den Zuggenerator eines Turms:

1. Erzeuge ein Bitboard, das die Positionen der eigenen Türme auf dem Schachbrett repräsentiert.
2. Verwende Bitwise-Operationen, um die möglichen Zugrichtungen des Turms zu ermitteln.
3. Für jede Zugrichtung erzeuge ein Bitboard, das die erlaubten Zielfelder für den Turm in dieser Richtung repräsentiert.
4. Kombiniere alle Bitboards der möglichen Zugrichtungen, um die Gesamtmenge der erlaubten Zielfelder zu erhalten.
5. Überprüfe, ob die Zielfelder von eigenen Figuren besetzt sind oder von gegnerischen Figuren geschlagen werden können, um die gültigen Züge zu filtern.
6. Generiere die tatsächlichen Zugkoordinaten aus den gültigen Zielfeldern und speichere sie für die weitere Verwendung.

Die Verwendung von Bitboards und Bitwise-Operationen ermöglicht es dem Bitboard-Zuggenerator, schnell und effizient alle möglichen Züge zu berechnen. Dies ist in der Schachprogrammierung, insbesondere für KI-Engines und andere Schachsoftware, von großer Bedeutung.

Bitboards sind eine effiziente Methode zur Repräsentation des Schachbretts in der Schachprogrammierung. Sie ermöglichen die kompakte Speicherung von Informationen über die Positionen der Schachfiguren auf dem Brett mithilfe von Bits. Jedes Bit im Bitboard repräsentiert ein Feld auf dem Schachbrett, und die Bitmuster in den Bitboards geben an, welche Felder von den Schachfiguren besetzt sind.

Die Datenstruktur der Bitboards besteht aus mehreren Bitboards, die die Positionen der verschiedenen Schachfiguren repräsentieren. Jedes Bitboard hat eine Größe von 64 Bits, da das Schachbrett aus 64 Feldern besteht. Die einzelnen Bitboards werden verwendet, um die Positionen der eigenen Figuren und der gegnerischen Figuren getrennt zu speichern.

Der Bitboard-Zuggenerator verwendet die Bitboards, um effizient und schnell alle möglichen Züge für die Schachfiguren zu berechnen. Durch die Anwendung von Bitwise-Operationen auf den Bitboards werden die möglichen Zugrichtungen, erlaubten Zielfelder und Kollisionen mit eigenen oder gegnerischen Figuren ermittelt. Zusätzlich können spezielle Techniken wie magische Bitboards für Sliding-Piece-Züge oder das Generieren von Pseudo-Zügen zur Vorabberechnung von Angriffsinformationen implementiert werden, um die Effizienz des Zuggenerators weiter zu verbessern.

Um nur legale Züge zu generieren, werden nach der Berechnung der potenziellen Züge zusätzliche Überprüfungen unter Verwendung von Bitwise-Operationen und Masken durchgeführt. Diese Überprüfungen umfassen die Überprüfung der Gültigkeit der Zielfelder, die Kollision mit eigenen Figuren, das Schlagen gegnerischer Figuren und gegebenenfalls die Sicherheit des eigenen Königs.

Die Verwendung von Bitboards und Bitwise-Operationen ermöglicht es dem Bitboard-Zuggenerator, schnell und effizient alle möglichen Züge zu berechnen, während zusätzliche Überprüfungen sicherstellen, dass nur legale Züge generiert werden. Dies ist in der Schachprogrammierung, insbesondere für KI-Engines und andere Schachsoftware, von großer Bedeutung.

Bitboards bieten eine leistungsstarke und effiziente Möglichkeit, Schachpositionen und Züge zu repräsentieren und zu verarbeiten. Sie sind ein Kernkonzept in der Schachprogrammierung und ermöglichen fortschrittliche Funktionen wie die Bewertung von Positionen, die Suche nach den besten Zügen und die Entwicklung von Schach-KI-Engines. Durch die Nutzung der Bitboards können Schachprogramme schnell und effizient reagieren und den Spielern eine starke und herausfordernde Schachpartie bieten.