Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / Schachprogrammierung / Zuggenerator
- By Lothar Jung Date 2021-07-09 18:44
https://docplayer.org/154713688-Diplomarbeit-institut-fuer-informationsverarbeitung.html
- By Lothar Jung Date 2021-07-10 11:41 Edited 2021-07-10 11:48
Anschauliche Erklärungen eines Bitboard-Zuggenerator:

https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/

https://essays.jwatzman.org/essays/chess-move-generation-with-magic-bitboards.html

https://www.rhysre.net/fast-chess-move-generation-with-magic-bitboards.html

https://joeyrobert.org/2016/01/06/optimizing-move-generation/
- By Lothar Jung Date 2021-10-05 09:47
Hier die Perft Zuggeneration:

https://www.chessprogramming.org/Perft
- By Lothar Jung Date 2021-10-15 10:00 Edited 2021-10-15 10:03
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
Up Topic Hauptforen / Schachprogrammierung / Zuggenerator

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill