Comparing 4 move generators: 0x88 vs 10x12 vs 10x12 + bitboards HYBRID vs Pure MAGIC BITBOARDS

[maksimKorzh]

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

I'd like to offer a video comparison of up to 4 move generators using different board representation solutions:

NOTE: most likely video would be interested for beginners only making first steps in chess programming
(I mean nothing new for 30+ years experienced GURUS)

Now for those who prefer READING above WATCHING videos I'd like to share the results here as well.

So, the preconditions are:

1. All move generators running from the initial chess position at the depth of 6 plies.
2. Move generators of Wukong, AikiChessBitboard & bbc (all 3 written by me) are compiled with "-Ofast" flag.
3. VICE is compiled from it's native make file.

Competitors are:

1. Wukong by CMK
- video tutorial series https://www.youtube.com/watch?v=rrLZVaQ ... 4FZgw5Ior0
- 0x88 array based board representation
- no piece lists
- copy/make approach

Code: Select all

Performance test:

    move 1: a2a3    4463267
    move 2: a2a4    5363555
    move 3: b2b3    5310358
    move 4: b2b4    5293555
    move 5: c2c3    5417640
    move 6: c2c4    5866666
    move 7: d2d3    8073082
    move 8: d2d4    8879566
    move 9: e2e3    9726018
    move 10: e2e4    9771632
    move 11: f2f3    4404141
    move 12: f2f4    4890429
    move 13: g2g3    5346260
    move 14: g2g4    5239875
    move 15: h2h3    4463070
    move 16: h2h4    5385554
    move 17: b1a3    4856835
    move 18: b1c3    5708064
    move 19: g1f3    5723523
    move 20: g1h3    4877234

    Depth: 6
    Nodes: 119060324
     Time: 20842 ms

2. VICE by Richard Allbert aka Bluefever Software
- video tutorial series https://www.youtube.com/watch?v=bGAfaep ... tZHVbT-2hg
- 10x12 array based board representationr
- piece lists
- make move/take back approach

Code: Select all

Starting Test To Depth:6
move 1 : a2a3 : 4463267
move 2 : a2a4 : 5363555
move 3 : b2b3 : 5310358
move 4 : b2b4 : 5293555
move 5 : c2c3 : 5417640
move 6 : c2c4 : 5866666
move 7 : d2d3 : 8073082
move 8 : d2d4 : 8879566
move 9 : e2e3 : 9726018
move 10 : e2e4 : 9771632
move 11 : f2f3 : 4404141
move 12 : f2f4 : 4890429
move 13 : g2g3 : 5346260
move 14 : g2g4 : 5239875
move 15 : h2h3 : 4463070
move 16 : h2h4 : 5385554
move 17 : b1a3 : 4856835
move 18 : b1c3 : 5708064
move 19 : g1f3 : 5723523
move 20 : g1h3 : 4877234

Test Complete : 119060324 nodes visited in 15555ms

3. AikiChessBitboard (VICE movegen + MAGIC BITBOARDS) by CMK
- bitboards + 10x12 array hybrid board representation
- piece lists
- pre-calculated attack tables
- make move/take back approach

Code: Select all

Starting Test To Depth:6
move 1 : a2a3 : oldnodes: 4463267
move 2 : a2a4 : oldnodes: 5363555
move 3 : b2b3 : oldnodes: 5310358
move 4 : b2b4 : oldnodes: 5293555
move 5 : c2c3 : oldnodes: 5417640
move 6 : c2c4 : oldnodes: 5866666
move 7 : d2d3 : oldnodes: 8073082
move 8 : d2d4 : oldnodes: 8879566
move 9 : e2e3 : oldnodes: 9726018
move 10 : e2e4 : oldnodes: 9771632
move 11 : f2f3 : oldnodes: 4404141
move 12 : f2f4 : oldnodes: 4890429
move 13 : g2g3 : oldnodes: 5346260
move 14 : g2g4 : oldnodes: 5239875
move 15 : h2h3 : oldnodes: 4463070
move 16 : h2h4 : oldnodes: 5385554
move 17 : b1a3 : oldnodes: 4856835
move 18 : b1c3 : oldnodes: 5708064
move 19 : g1f3 : oldnodes: 5723523
move 20 : g1h3 : oldnodes: 4877234

Test Complete : 119060324 nodes visited in 7751 ms

4. BBC by CMK (Pure MAGIC BITBOARDS)
- video tutorial series https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs
- bitboard board representation
- no piece lists
- pre-calculated attack tables
- copy/make approach

Code: Select all

Performance test:

    move 1: a2a3    4463267
    move 2: a2a4    5363555
    move 3: b2b3    5310358
    move 4: b2b4    5293555
    move 5: c2c3    5417640
    move 6: c2c4    5866666
    move 7: d2d3    8073082
    move 8: d2d4    8879566
    move 9: e2e3    9726018
    move 10: e2e4    9771632
    move 11: f2f3    4404141
    move 12: f2f4    4890429
    move 13: g2g3    5346260
    move 14: g2g4    5239875
    move 15: h2h3    4463070
    move 16: h2h4    5385554
    move 17: b1a3n    4856835
    move 18: b1c3n    5708064
    move 19: g1f3n    5723523
    move 20: g1h3n    4877234

    Depth: 6
    Nodes: 119060324
     Time: 7140 ms

Maybe technical discussion room is more appropriate for this post, but let me explain the reason for posting it here, in general discussions:
1. Post serves as a promotion of Bitboard CHESS ENGINE in C ongoing series I'm currently covering on YouTube inspired by YOU GUYS!
2. Guys from tech room already know it hence won't be interested
3. This comparison is targeting novice auditory either not having chess engine development experience or those looking to where to kick start from.

Thanks for taking your time to watch video/read this post.
I'm very grateful to all of you guys who has recently subscribed to my YouTube channel!
https://www.youtube.com/channel/UCB9-pr ... subscriber

[ChessRenewal]

Very interesting comparison! Could you make the source code for AikiChessBitboard (VICE movegen + MAGIC BITBOARDS) available? Thanks.

[maksimKorzh]

Very interesting comparison! Could you make the source code for AikiChessBitboard (VICE movegen + MAGIC BITBOARDS) available? Thanks.

Hi ChessRenewal

Thanks for your feedback. The source code for AikiChessBitboard is something that I'm ashamed of at this moment. It's too rare (written for about 2 years ago), there're LOTS of redundancies, it has AWFUL code style - neither camelCase, nor python_style but some Weird_Collab instead - I just had no idea of how to make it right back in those days, but it's not even the biggest problems - it has even more redundancies from the code logic perspective, consider is square attacked function as it was initially implemented in AikiChessBitboard is:

Code: Select all

int Is_Square_Attacked (CHESS_BOARD *chessBoard, int sq, int side) {  //Is_Square_Attacked

	if (side == White) {
		
		if (AND (AND (blackPawn_Attacks [sq], chessBoard->whitePieces), chessBoard->pieces [wP]))
			return True;	
		
		if (AND (AND (Knight_Attacks [sq], ~chessBoard->blackPieces), chessBoard->pieces [wN]))
			return True;	
		
		if (AND (AND (bishopMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->blackPieces), chessBoard->pieces [wB]))
			return True;	
		
		if (AND (AND (rookMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->blackPieces), chessBoard->pieces [wR]))
			return True;	
		
		if (AND (AND (queenMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->blackPieces), chessBoard->pieces [wQ]))
			return True;	
		
		if (AND (AND (King_Attacks [sq], ~chessBoard->blackPieces), chessBoard->pieces [wK]))
			return True;	
	
	}
	else {
		
		if (AND (AND (whitePawn_Attacks [sq], chessBoard->blackPieces), chessBoard->pieces [bP]))
			return True;	
		
		if (AND (AND (Knight_Attacks [sq], ~chessBoard->whitePieces), chessBoard->pieces [bN]))
			return True;	
		
		if (AND (AND (bishopMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->whitePieces), chessBoard->pieces [bB]))
			return True;	
		
		if (AND (AND (rookMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->whitePieces), chessBoard->pieces [bR]))
			return True;	
		
		if (AND (AND (queenMagicAttacks (chessBoard->occupancy, sq), ~chessBoard->whitePieces), chessBoard->pieces [bQ])) 
			return True;
		
		if (AND (AND (King_Attacks [sq], ~chessBoard->whitePieces), chessBoard->pieces [bK]))
			return True;	
		
	}
	
	return False;
		
}

While a couple of days ago I've rewritten it removing unnecessary parts like this (works slightly faster now):

Code: Select all

int Is_Square_Attacked (CHESS_BOARD *chessBoard, int sq, int side) {  //Is_Square_Attacked
    if ((side == White) && (pawn_attacks[Black][sq] & chessBoard->pieces[wP])) return True;
    if ((side == Black) && (pawn_attacks[White][sq] & chessBoard->pieces[bP])) return True;
    
    if (Knight_Attacks[sq] & ((side == White) ? chessBoard->pieces[wN] : chessBoard->pieces[bN])) return True;
    if (King_Attacks[sq] & ((side == White) ? chessBoard->pieces[wK] : chessBoard->pieces[bK])) return True;
    if (bishopMagicAttacks(chessBoard->occupancy, sq) & ((side == White) ? chessBoard->pieces[wB] : chessBoard->pieces[bB])) return True;
    if (rookMagicAttacks(chessBoard->occupancy, sq) & ((side == White) ? chessBoard->pieces[wR] : chessBoard->pieces[bR])) return True;    
    if (queenMagicAttacks(chessBoard->occupancy, sq) & ((side == White) ? chessBoard->pieces[wQ] : chessBoard->pieces[bQ])) return True;
	
	return False;	
} 

So I don't mind to share the source code with those interested, BUT I don't want to share it in public.
So if you want to obtain a copy being presented in a video, please contact me at freesoft.for.people@gmail.com and I'll send it to you (for free obviously)

Now as far as you actually got interested exactly in this part let me explain the idea behind the implementation:
1. Implement precalculated attacks tables for all pieces (just what I've already covered here:
2. Add 12 bitboards to represent chess pieces and 3 bitboards to represent occupancies for white/black/both
3. Incrementally update or copy/make all bitboards within make move
4. Replace existing is square attacked function with the one like shown above (is square attacked by LOOKUP is already faster than ON THE FLY)
5. Alter move generator, so that moves are picked up by LOOKUP instead of getting generated ON THE FLY

And you'll get the double performance boost just like shown in the video.

Btw, I have an idea to empower TSCP with magic bitboards (not sure if somebody done that before).
This would make the movegen faster at very least, but evaluation also can be made faster if relying on bitboards.
Will you personally be interested in having this sort of TSCP on bitboard "steroids"?

[Dann Corbit]

Btw, I have an idea to empower TSCP with magic bitboards (not sure if somebody done that before).
This would make the movegen faster at very least, but evaluation also can be made faster if relying on bitboards.
Will you personally be interested in having this sort of TSCP on bitboard "steroids"?

https://www.chessprogramming.org/Winglet
Also:
https://www.stmintz.com/ccc/index.php?id=298973

And from Tom's page http://www.tckerrigan.com/Chess/TSCP/Community/ :
Michael J Sherwin created a version of TSCP (1.81) with a bitboard move generator:
tscp181_mjs.zip

[maksimKorzh]

Btw, I have an idea to empower TSCP with magic bitboards (not sure if somebody done that before).
This would make the movegen faster at very least, but evaluation also can be made faster if relying on bitboards.
Will you personally be interested in having this sort of TSCP on bitboard "steroids"?

https://www.chessprogramming.org/Winglet
Also:
https://www.stmintz.com/ccc/index.php?id=298973

And from Tom's page http://www.tckerrigan.com/Chess/TSCP/Community/ :
Michael J Sherwin created a version of TSCP (1.81) with a bitboard move generator:
tscp181_mjs.zip

Thanks for letting me know!
Yup, would need to pick up some other array based "victim" in this case)))

[pedrox]

Btw, I have an idea to empower TSCP with magic bitboards (not sure if somebody done that before).
This would make the movegen faster at very least, but evaluation also can be made faster if relying on bitboards.
Will you personally be interested in having this sort of TSCP on bitboard "steroids"?

https://www.chessprogramming.org/Winglet
Also:
https://www.stmintz.com/ccc/index.php?id=298973

And from Tom's page http://www.tckerrigan.com/Chess/TSCP/Community/ :
Michael J Sherwin created a version of TSCP (1.81) with a bitboard move generator:
tscp181_mjs.zip

A link is indicated in Russell Reagan's message (https://www.stmintz.com/ccc/index.php?id=298973).

http://home.attbi.com/~rreagan/tscp_bb.zip

Somebody has the file?

Thank you.

[maksimKorzh]

Btw, I have an idea to empower TSCP with magic bitboards (not sure if somebody done that before).
This would make the movegen faster at very least, but evaluation also can be made faster if relying on bitboards.
Will you personally be interested in having this sort of TSCP on bitboard "steroids"?

https://www.chessprogramming.org/Winglet
Also:
https://www.stmintz.com/ccc/index.php?id=298973

And from Tom's page http://www.tckerrigan.com/Chess/TSCP/Community/ :
Michael J Sherwin created a version of TSCP (1.81) with a bitboard move generator:
tscp181_mjs.zip

A link is indicated in Russell Reagan's message (https://www.stmintz.com/ccc/index.php?id=298973).

http://home.attbi.com/~rreagan/tscp_bb.zip

Somebody has the file?

Thank you.

Valuable info. Thanks.

[OliverBr]

5. OliThink5 / OliPerft (Kindergarten Bitboards)

- independent developed bitboard representation
- no piece lists
https://github.com/olithink/OliThink/bl ... oliperft.c

1. Without hash:

Code: Select all

Pa2-a3: 4463267
Pa2-a4: 5363555
Pb2-b3: 5310358
Pb2-b4: 5293555
Pc2-c3: 5417640
Pc2-c4: 5866666
Pd2-d3: 8073082
Pd2-d4: 8879566
Pe2-e3: 9726018
Pe2-e4: 9771632
Pf2-f3: 4404141
Pf2-f4: 4890429
Pg2-g3: 5346260
Pg2-g4: 5239875
Ph2-h3: 4463070
Ph2-h4: 5385554
Nb1-a3: 4856835
Nb1-c3: 5708064
Ng1-f3: 5723523
Ng1-h3: 4877234

Nodes: 119060324 cs: 51 knps: 232539

0.51 seconds, 232 mnps

2. With hash:

Code: Select all

Nodes: 119060324 cs: 43 knps: 271208

0.43 seconds, 271 mnps

[mvanthoor]

...

thanks for this post I'll have to download the bitboard chess engine and compare it with Rustic on my own computer. (I'll compile it myself in MSYS2 / GCC, at the fastest speed setting, with --target-cpu set at "Skylake", just as with my own engine.) I'm curious to see a speed comparison on the same computer.

5. OliThink5 / OliPerft (Kindergarten Bitboards)

- independent developed bitboard representation
- no piece lists
https://github.com/olithink/OliThink/bl ... oliperft.c

1. Without hash:

Code: Select all

Pa2-a3: 4463267
Pa2-a4: 5363555
Pb2-b3: 5310358
Pb2-b4: 5293555
Pc2-c3: 5417640
Pc2-c4: 5866666
Pd2-d3: 8073082
Pd2-d4: 8879566
Pe2-e3: 9726018
Pe2-e4: 9771632
Pf2-f3: 4404141
Pf2-f4: 4890429
Pg2-g3: 5346260
Pg2-g4: 5239875
Ph2-h3: 4463070
Ph2-h4: 5385554
Nb1-a3: 4856835
Nb1-c3: 5708064
Ng1-f3: 5723523
Ng1-h3: 4877234

Nodes: 119060324 cs: 51 knps: 232539

0.51 seconds, 232 mnps

2. With hash:

Code: Select all

Nodes: 119060324 cs: 43 knps: 271208

0.43 seconds, 271 mnps

As you said your engine uses a legal-only move generator, I assume you're using bulk counting? That is a MASSIVE nps count. (Personally I count 'leaves found per second'; do you count every node you traverse, or only the leaves with regard to speed?)

Also... the speed of the computer is of great importance of course.

[OliverBr]

As you said your engine uses a legal-only move generator, I assume you're using bulk counting? That is a MASSIVE nps count. (Personally I count 'leaves found per second'; do you count every node you traverse, or only the leaves with regard to speed?)

On the leafs, it's only counting the legal moves, not actually generating it.

Also... the speed of the computer is of great importance of course.

Hardware is not that importan, as it looks like one 1 core.
The result comes from: "gcc8 64bit AMD EPYC 7502P 1/32-Core Processor", which looks stunning, but only 1 core is being used.
On my i7-8850H MacBookPro it's about 80% performance (of course only 1 core being used, too).

This move generator has been built in 2008 with the main purpose to be as fast as possible. I invented an own style of bitboard representation. Later I learned it is called "Kindergarten bitboard".

The performance gain since 2008 may be interesting (using hash):

Code: Select all

/* OliPerft 1.0.5 - Bitboard Magic Move (c) Oliver Brausch 16.Sep.2020, ob112@web.de */
/* oliperft 6 "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
Nodes: 8229523927 cs: 1156 knps: 711527 (gcc8 64bit AMD EPYC 7502P 1/32-Core Processor)
Nodes: 8229523927 cs: 1526 knps: 539145 (gcc4 OSX i7 8850H 2.6 GHz)
Nodes: 8229523927 ms: 40610 knps: 202647 (VS2005 64bit AMD64 4600+) (1.0.2)
Nodes: 8229523927 ms: 64860 knps: 126881 (VS2005 32bit AMD64 4600+) (1.0.2)
Nodes: 8229523927 ms: 97251 knps: 84621 (gcc4 32bit AMD Opteron 1210HE) (1.0.2)

the last 3 lines and version 1.0.2 are from 2008 with hardware of that time. The speed for 1 core increased only about a factor 3 in 12 years. Who had ever thought this?