Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Sun Sep 06, 2020 1:50 pm

Hey what's up guys, Code Monkey King's here.

Before anything else I'd like to pay a tribute to Gerd Isenberg who has kindly added some pages about me and my chess engines into a CPW:
CMK: https://www.chessprogramming.org/Maksim_Korzh
BBC: https://www.chessprogramming.org/BBC
THANKS YOU SO MUCH GERD!

Also I'd like to thanks all those of you guys who has inspired and supported me with this series.

Now let's get to the point.

I'm now working on Bitboard CHESS ENGINE in C YouTube series (the simplest to understand bitboard engine!):
https://www.youtube.com/watch?v=o-ySJ2E ... wfiWNI76Cs

Source code of the current development state:
https://github.com/maksimKorzh/chess_pr ... test/bbc.c
NOTE: make sure to compile with GCC. It's developed under linux but simultaneously cross compiled for windows, see makefile:
https://github.com/maksimKorzh/chess_pr ... t/makefile

A few words about the engine we're developing:
- bitboard board representation
- pre-calculated attack tables
- magic bitboards for generating sliding pieces attacks (including tutorial on how to generate magic numbers, based on idea by Tord Romstad)
- copy/make approach for making moves and taking them back
- make move function level of distinguishing between quite move and captures (for later quiescence search purposes)
- perft testing

some controversial implementations:
- global variables are used everywhere it's possible (see reasons WHY below)
- copy/make happens within a function stack (COPY -> MAKE -> COPY BACK)

A few words about the reasons behind the particular implementation (I know about OOP, encapsulation, passing pointers etc.):
- global variables are simplest to understand so viewer can focus on chess programming techniques instead of C programming best practices
- global variables save lots of source lines because no need for never ending initialization.
- current copy/make implementation is forced by the global variables and also saves some source lines

A few words about the purposes of creating this tutorial series and goals I'm targeting:
- low entry threshold (use only basic knowledge of C programming to avoid viewers getting distracted by advanced C programming techniques)
- create the simplest implementation of the complex magic bitboards based chess engine
- create as implementation agnostic as possible source code so anyone can USE THE IDEAS without any plagiarism
- create MODULAR engine, e.g. while implementing search & move ordering avoid touching code written before
- literally sacrifice almost anything for the TRUE DIDACTIC purposes

CURRENT DEVELOPMENT STATE:
We've just passed the perft test, so it's just the right time to JUMP IN for NEWCOMERS.
Assuming modular approach while writing this engine you don't need to know how move generator works in order to make use of it,
so you can kick start with actually making engine play chess via following upcoming tutorials!

NEXT STEPS:
- implement a minimal UCI interaction to debug search & evaluation in the GUI (extended UCI protocol is coming later)
- implement negamax search with alpha beta pruning (fail-hard framework)
- MVV/LVA/killer/history/PV heuristics for move ordering
- bitboard evaluation
- and much more...

SUMMARY:
Most likely my work won't be interesting to experienced chess engine developers for I'm targeting the novice auditory.
I wish I could have this like tutorials back in those days when just started chess programming.
Current series is dedicated to everyone HAVING ISSUES with READING OPEN SOURCE chess engine's code.
(I'm starting understanding it after about 5 years of chess programming)
So even if you have a very basic understanding of C programming language (or coming from high level languages like JS or Python) these tutorials are just the case for you!
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
ChessRenewal
Posts: 13
Joined: Thu Jul 25, 2019 5:13 pm
Full name: Jay Warendorff

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by ChessRenewal » Sun Sep 06, 2020 10:36 pm

Your Bitboard Chess Engine in C YouTube series is marvelous. I am very interested in all of the details on how a bitboard chess engine works and your series has very detailed explanations which is exactly what I want to know. I am fairly new to C programming coming from having more experience in programming in a higher level language so I appreciate your focus on the chess programming rather than the C programming. Maybe after the initial version of the bitboard engine is completed, a second version can be made with more refined C language constructs if that would result in a speedup. But already it is very nice to see that move generation is significantly faster than in your array based chess engine. Now that you have implemented move generation, I especially look forward to your further development of the code having the engine beginning to make moves and later being able to play against other engines. Thank you very much!
Top
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Mon Sep 07, 2020 9:01 am

ChessRenewal wrote: ↑
Sun Sep 06, 2020 10:36 pm
 Your Bitboard Chess Engine in C YouTube series is marvelous. I am very interested in all of the details on how a bitboard chess engine works and your series has very detailed explanations which is exactly what I want to know. I am fairly new to C programming coming from having more experience in programming in a higher level language so I appreciate your focus on the chess programming rather than the C programming. Maybe after the initial version of the bitboard engine is completed, a second version can be made with more refined C language constructs if that would result in a speedup. But already it is very nice to see that move generation is significantly faster than in your array based chess engine. Now that you have implemented move generation, I especially look forward to your further development of the code having the engine beginning to make moves and later being able to play against other engines. Thank you very much!
Hi Chess Renewal

Thanks for such an inspiring feedback!
Maybe after the initial version of the bitboard engine is completed, a second version can be made with more refined C language constructs if that would result in a speedup
The style of C programming doesn't affect performance itself. It's the matter of techniques being involved. Say we could create take_back() function to save time on copying board state, but the trick is that BBC leave a HUGE field of improvements. It tries to implement the simplest techniques possible - those that are IMO best for DIDACTIC purposes. It's kind of like a bare minimum to make engine solid)

If you want to have a look at "real" code see fruit-reloaded:
https://github.com/Akusari/Fruit-reload ... master/src

Btw, I'm very tempted to know whether it would be as clear as BBC to you))) Please let me know! I just want to check my hypothesis on having big trouble in understanding of "best practices" code for beginners and non C programmers. Fruit reloaded is a fantastic didactic engine, probably the best one ever BUT I've started understanding it's code after years of practice)
Now that you have implemented move generation, I especially look forward to your further development of the code having the engine beginning to make moves and later being able to play against other engines.
Yup))) The most exciting topics are just about to begin) Just a few boring videos to connect engine to GUI so we could debug in GUI and then we go for search & evaluation watching how it becomes stronger and stronger!
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
ChessRenewal
Posts: 13
Joined: Thu Jul 25, 2019 5:13 pm
Full name: Jay Warendorff

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by ChessRenewal » Tue Sep 08, 2020 3:21 am

Fruit reloaded looks very interesting, but in terms of the level I am presently at in understanding C language programming and chess engine algorithms your bitboard engine with commented code and extensive video discussions is much more instructive for me now and probably for a long time to come. When you come to implementing algorithms such as the transposition table and others, please provide explanations of how they work. Your video series is certainly an invaluable contribution to all who would like to understand and make a chess engine!
Top
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Tue Sep 08, 2020 4:40 pm

ChessRenewal wrote: ↑
Tue Sep 08, 2020 3:21 am
 Fruit reloaded looks very interesting, but in terms of the level I am presently at in understanding C language programming and chess engine algorithms your bitboard engine with commented code and extensive video discussions is much more instructive for me now and probably for a long time to come. When you come to implementing algorithms such as the transposition table and others, please provide explanations of how they work. Your video series is certainly an invaluable contribution to all who would like to understand and make a chess engine!
I'll do my best! Thanks!
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Thu Sep 24, 2020 6:36 am

Hey what's up guys, Code Monkey King's here with a new update:

BBC has crushed TSCP in BLITZ 5+0!

-----------------BBC [new]-----------------
BBC [new] - TSCP : 11,0/16 11-5-0 (1010011110111011) 69% +139
-----------------TSCP-----------------
TSCP - BBC [new] : 5,0/16 5-11-0 (0101100001000100) 31% -139


PGN link: https://github.com/maksimKorzh/chess_pr ... C_TSCP.pgn
Video overview with comments on evaluation updates: https://www.youtube.com/watch?v=FLyedEriAcc

Output of ELOStat tool (based on above PGN):
Program Elo + - Games Score Av.Op. Draws

1 BBC [new] : 1721 216 192 16 68.8 % 1585 0.0 %
2 TSCP : 1585 192 216 16 31.2 % 1721 0.0 %

(I used TSCP's classical time control rating as "start rating param" - is that correct?)

Here're some typical games:




BBC's YouTube series is going on!
We're going to add more evaluation features soon!
Join: https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
User avatar
mvanthoor
Posts: 776
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by mvanthoor » Thu Sep 24, 2020 9:28 am

BBC does not run perft(7) correctly, but perft(6) does work. I compiled the engine on Windows (under MSYS2), with the following results.

- Replaced your UCI-loop with this:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(6);
result, correct for perft(6)

Code: Select all

Depth: 6
Nodes: 119060324
Time: 4110
Then:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(7);
Result:

Code: Select all

 Depth: 7
Nodes: -1099065436
Time: 223063
Rustic's output for:

Code: Select all

./rustic.exe --perft 7
(It runs all the depths, up to and including the requested depth, just like iterative deepening, in preparation of a hash table addition.)

Code: Select all

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (4 ms, 49320250 leaves/sec)
Perft 5: 4865609 (120 ms, 40546741 leaves/sec)
Perft 6: 119060324 (2968 ms, 40114664 leaves/sec)
Perft 7: 3195901860 (79147 ms, 40379317 leaves/sec)
Total time spent: 82239 ms
Execution speed: 40370558 leaves/second
Author of Rustic.
Releases | Code | Docs
Top
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Thu Sep 24, 2020 10:15 am

mvanthoor wrote: ↑
Thu Sep 24, 2020 9:28 am
 BBC does not run perft(7) correctly, but perft(6) does work. I compiled the engine on Windows (under MSYS2), with the following results.

- Replaced your UCI-loop with this:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(6);
result, correct for perft(6)

Code: Select all

Depth: 6
Nodes: 119060324
Time: 4110
Then:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(7);
Result:

Code: Select all

 Depth: 7
Nodes: -1099065436
Time: 223063
Rustic's output for:

Code: Select all

./rustic.exe --perft 7
(It runs all the depths, up to and including the requested depth, just like iterative deepening, in preparation of a hash table addition.)

Code: Select all

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (4 ms, 49320250 leaves/sec)
Perft 5: 4865609 (120 ms, 40546741 leaves/sec)
Perft 6: 119060324 (2968 ms, 40114664 leaves/sec)
Perft 7: 3195901860 (79147 ms, 40379317 leaves/sec)
Total time spent: 82239 ms
Execution speed: 40370558 leaves/second
Thanks for info! I guess something wrong with node count assuming it's negative, most likely not enough bits in long integer.
Anyway thanks you for report!
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
User avatar
maksimKorzh
Posts: 630
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:
Contact maksimKorzh

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by maksimKorzh » Thu Sep 24, 2020 10:16 am

mvanthoor wrote: ↑
Thu Sep 24, 2020 9:28 am
 BBC does not run perft(7) correctly, but perft(6) does work. I compiled the engine on Windows (under MSYS2), with the following results.

- Replaced your UCI-loop with this:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(6);
result, correct for perft(6)

Code: Select all

Depth: 6
Nodes: 119060324
Time: 4110
Then:

Code: Select all

parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
perft_test(7);
Result:

Code: Select all

 Depth: 7
Nodes: -1099065436
Time: 223063
Rustic's output for:

Code: Select all

./rustic.exe --perft 7
(It runs all the depths, up to and including the requested depth, just like iterative deepening, in preparation of a hash table addition.)

Code: Select all

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (4 ms, 49320250 leaves/sec)
Perft 5: 4865609 (120 ms, 40546741 leaves/sec)
Perft 6: 119060324 (2968 ms, 40114664 leaves/sec)
Perft 7: 3195901860 (79147 ms, 40379317 leaves/sec)
Total time spent: 82239 ms
Execution speed: 40370558 leaves/second
But how do you like the games??
Wukong Xiangqi (Chinese chess engine + apps to embed into 3rd party websites):
https://github.com/maksimKorzh/wukong-xiangqi

Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
Top
User avatar
mvanthoor
Posts: 776
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Bitboard CHESS ENGINE in C: YouTube series by Code Monkey King

Post by mvanthoor » Thu Sep 24, 2020 10:28 am

maksimKorzh wrote: ↑
Thu Sep 24, 2020 10:16 am
 But how do you like the games??
The games are fine :) Consistently beating TSCP is one of the goals of most engine developers when they are just starting out. I hope the two games you've posted are not 'accidents', and that you can actually win a 100 game match against TSCP. If so, you can estimate your engine's approximate strength. (TSCP is rated around CCRL 1700). You should now set up a gauntlet tournament to see where your engine falls. Don't just try to improve your results against TSCP, or you might end up tuning your engine to explicitly defeat TSCP and perform worse against other engines.
Author of Rustic.
Releases | Code | Docs
Top
Post Reply

Return to “Computer Chess Club: General Topics”