More uses for magics?
Moderators: hgm, Rebel, chrisw
-
Jacob
More uses for magics?
I was looking through Pradu's magic move generator and it got me thinking; what if instead of returning a bitboard for a given square and occupancy, you return a score with a smaller data-type based on such factors as mobility and piece-placement? For rooks you could even pre-compute scores for open/half-open files and the like. With a one-byte score, the bishop database is only 32kb, and 256kb for the rook database.
-
Michael Sherwin
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: More uses for magics?
AFAIK, there is nothing new in what you propose.
Nice thinking though!
Nice thinking though!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
Jacob
Re: More uses for magics?
Oops :-/, I'm still fairly new to all of this, so it'd probably be best to keep quiet, hehe,... Thanks for letting me know.
-
Michael Sherwin
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: More uses for magics?
Don't be quiet. What if it really was new, then we wouldn't find out about it!Jacob wrote:Oops :-/, I'm still fairly new to all of this, so it'd probably be best to keep quiet, hehe,... Thanks for letting me know.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
Jacob
Generalized bitboard pawn moves
Then if one day a new beta program comes out that smokes Rybka, you'll know why =). ... I feel a bit intimidated too since I'm just a high school graduate among all you professional programmers :-/.Don't be quiet. What if it really was new, then we wouldn't find out about it!
Another idea I had was a way to generate pawn moves without separate cases for black and white. The basic principle is simple enough; for white pawns, the pawn bitboard is shifted and compared to the occupancy. For black pawns, the occupancy is shifted by the same amount and compared to the pawn bitboard. I used a 17 element array to store my piece bitboards, which allows me to use some simple algebra to generate the pawn moves.
Here's some code:
Code: Select all
U32* GenNonCaptures(U32* list)
{
U64 pc, moves;
int sqr[2]; // from, to
// ...
// - Pawns forward one -
pieces[TEMP] = (pieces[xoccu_wp[side]] << 8)
& pieces[xoccu_bp[xside]];
moves = pieces[TEMP] & xprom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 8;
AddMove(sqr[0], sqr[1], pos[sqr[0]]);
}
moves = pieces[TEMP] & prom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 8;
AddUnderProm(sqr[0], sqr[1], PROM|side, 0);
}
// - Pawns forward two -
moves = ((pieces[xoccu_tmp[side]] & mask_5_3[side]) << (8 << xside))
& pieces[xoccu_tmp[xside]];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 16;
AddMove(sqr[0], sqr[1], pos[sqr[0]]);
}
return list;
}Code: Select all
U32* GenCaptures(U32* list)
{
U64 pc, moves;
int sqr[2]; // from, to
// ...
// - Pawns forward one -
pieces[TEMP] = (pieces[xoccu_wp[side]] << 8)
& pieces[xoccu_bp[xside]];
moves = pieces[TEMP] & prom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 8;
AddProm(sqr[0], sqr[1], PROM|side, 0);
}
// - Pawns seven-shift -
pc = ((pieces[woccu_wp[side]] & 0xFEFEFEFEFEFEFEFEULL) << 7)
& pieces[boccu_bp[xside]];
moves = pc & xprom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 7;
AddCapt(sqr[0], sqr[1], PAWN|side, pos[sqr[1]]);
}
moves = pc & prom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 7;
AddProm(sqr[0], sqr[1], PROM|side, pos[sqr[1]]);
}
// - Pawns nine-shift -
pc = ((pieces[woccu_wp[side]] & 0x7F7F7F7F7F7F7F7FULL) << 9)
& pieces[boccu_bp[xside]];
moves = pc & xprom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 9;
AddCapt(sqr[0], sqr[1], PAWN|side, pos[sqr[1]]);
}
moves = pc & prom_mask[side];
while (moves) {
sqr[side] = PopLSB(&moves);
sqr[xside] = sqr[side] - 9;
AddProm(sqr[0], sqr[1], PROM|side, pos[sqr[1]]);
}
// - En Passant -
if (status[ply].ep_t) {
pc = pawn_attacks[xside][status[ply].ep_t] & pieces[PAWN|side];
while (pc) {
sqr[0] = PopLSB(&pc);
AddCapt(sqr[0], status[ply].ep_t, PAWN|side, EP_CAPT|side);
}
}
return list;
}-
Edsel Apostol
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: Generalized bitboard pawn moves
Hi Jacob,
Welcome to the club.
Hope you would be successful in your chess engine programming.
I am a chess engine author too and I'm looking for better ways to implement faster move and attack generations in my program.
There are a lot of pioneering work here regarding magic moves by Pradu Kannan, Michael Sherwin, etc..
I don't know which implementation is the best. I am currently using now the Kindergarten bitboard ideas for sliding pieces by Gerd Isenberg.
I am interested in your idea. Would you mind sharing your code and test results?
Edsel Apostol
Welcome to the club.
Hope you would be successful in your chess engine programming.
I am a chess engine author too and I'm looking for better ways to implement faster move and attack generations in my program.
There are a lot of pioneering work here regarding magic moves by Pradu Kannan, Michael Sherwin, etc..
I don't know which implementation is the best. I am currently using now the Kindergarten bitboard ideas for sliding pieces by Gerd Isenberg.
I am interested in your idea. Would you mind sharing your code and test results?
Edsel Apostol
Edsel Apostol
https://github.com/ed-apostol/InvictusChess
https://github.com/ed-apostol/InvictusChess
-
Michael Sherwin
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: Generalized bitboard pawn moves
Hi Jacob,
This is interesting! It may be very similar to the way Crafty does it, but I have not looked at Crafty's code for a couple of years now, so I can not be sure. I have saved this page and will study it more closely when I have some time.
OBTW, I am not a professional programmer. I am just a self taught amateur. And not even all that bright. I just wish that I had got started at your age!
This is interesting! It may be very similar to the way Crafty does it, but I have not looked at Crafty's code for a couple of years now, so I can not be sure. I have saved this page and will study it more closely when I have some time.
OBTW, I am not a professional programmer. I am just a self taught amateur. And not even all that bright. I just wish that I had got started at your age!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
Jacob
Re: Generalized bitboard pawn moves
Yes, it is similar to Crafty, except that Crafty generates white and black moves separately, and it doesn't use a single array for all the pieces.It may be very similar to the way Crafty does it, but I have not looked at Crafty's code for a couple of years now, so I can not be sure.
Here's the source to "Bitboard Perft". The magic move files are not my original source and were written by Pradyumna Kannan.
main.c
magicmoves.h
magicmoves.c
It can accept an fen-string (without quotes) as an argument or defaults to the start position and begins perfting infinitely. The fen-parsing is very primitive and should break on invalid fens
.Here are some results in 32-bit (Visual Studio 2006) and 64-bit mode (GCC under amd64 Fedora). My processor is a dual-core Conroe (not sure of the exact type) running at 3.4ghz. I'm comparing this to my chess engine, which are close to identical except that Étude generates white/black moves separately, is written in C++ with some classes, and doesn't use an array to store the piece boards. Both move generators generate legal moves, detect checks in leaf nodes, and generate a partial list of pins in the leaf nodes (pins against the side to move). They also use the debruijn hashing method for bitscans.
Test positions:
A: (depth 5) r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
B: (depth 7) r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1 (which can be compared to engines in another post).
C: (depth 6) rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Étude (64 bit):
A: 5. 193690690 (7.86s)
B: 7. 528388659 (20.59s)
C: 6. 119060324 (4.49s)
Bitboard Perft (64 bit):
A: 5. 193690690 (7.06s)
B: 7. 528388659 (18.41s)
C: 6. 119060324 (4.19s)
Étude (32 bit):
A: 5. 193690690 (13.39s)
B: 7. 528388659 (36.56s)
C: 6. 119060324 (8.11s)
Bitboard Perft (32 bit):
A: 5. 193690690 (14.08s)
B: (misplaced
)C: 6. 119060324 (8.63s)
I'm surprised that Bitboard Perft ran faster in 64-bit mode, I wonder if it has something to do with the compiler,... Or the increase in available registers?
-
Pradu
- Posts: 287
- Joined: Sat Mar 11, 2006 3:19 am
- Location: Atlanta, GA
Re: Generalized bitboard pawn moves
Hi Jacob 
Also you could try the Intel compiler for Linux, which is free. It seems to optimize better than GCC--atleast for my program.
For 64-bits you could try using intrinsics or processor instructions for the bitscan. It should be quite a bit faster on your processor:Jacob wrote:Yes, it is similar to Crafty, except that Crafty generates white and black moves separately, and it doesn't use a single array for all the pieces.It may be very similar to the way Crafty does it, but I have not looked at Crafty's code for a couple of years now, so I can not be sure.
Here's the source to "Bitboard Perft". The magic move files are not my original source and were written by Pradyumna Kannan.
main.c
magicmoves.h
magicmoves.c
It can accept an fen-string (without quotes) as an argument or defaults to the start position and begins perfting infinitely. The fen-parsing is very primitive and should break on invalid fens
Here are some results in 32-bit (Visual Studio 2006) and 64-bit mode (GCC under amd64 Fedora). My processor is a dual-core Conroe (not sure of the exact type) running at 3.4ghz. I'm comparing this to my chess engine, which are close to identical except that Étude generates white/black moves separately, is written in C++ with some classes, and doesn't use an array to store the piece boards. Both move generators generate legal moves, detect checks in leaf nodes, and generate a partial list of pins in the leaf nodes (pins against the side to move). They also use the debruijn hashing method for bitscans.
Code: Select all
#ifndef INLINE
#ifdef _MSC_VER
#define INLINE __forceinline
#elif defined(__GNUC__)
#define INLINE __inline__ __attribute__((always_inline))
#else
#define INLINE inline
#endif
#endif
#ifndef __64_BIT_INTEGER_DEFINED__
#define __64_BIT_INTEGER_DEFINED__
#if defined(_MSC_VER) && _MSC_VER<1300
typedef unsigned __int64 U64; //For the old microsoft compilers
#else
typedef unsigned long long U64; //Supported by MSC 13.00+ and GCC
#endif //defined(_MSC_VER) && _MSC_VER<1300
#endif //__64_BIT_INTEGER_DEFINED__
/*Note that MSC interprets long as a 32-bit type and GCC interprets long as a 64-bit type. However, both interpret int as a 32-bit type. This is why the prototype definition for the GCC implementation of the intrinsics use "int" instead of the "long" used in Microsoft's documentation.*/
#ifdef _MSC_VER
#include <intrin.h>
#pragma message("MSC compatible compiler detected -- turning off warning 4146")
#pragma warning( disable : 4146)
#if defined(_WIN64) || defined(__LP64__)
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
#define USING_INTRINSICS
#endif
#elif defined(__GNUC__) && defined(__LP64__)
static INLINE unsigned char _BitScanForward64(unsigned int* const Index, const U64 Mask)
{
U64 Ret;
__asm__
(
"bsfq %[Mask], %[Ret]"
:[Ret] "=r" (Ret)
:[Mask] "mr" (Mask)
);
*Index = (unsigned int)Ret;
return Mask?1:0;
}
static INLINE unsigned char _BitScanReverse64(unsigned int* const Index, const U64 Mask)
{
U64 Ret;
__asm__
(
"bsrq %[Mask], %[Ret]"
:[Ret] "=r" (Ret)
:[Mask] "mr" (Mask)
);
*Index = (unsigned int)Ret;
return Mask?1:0;
}
#define USING_INTRINSICS
#endifBitboard engines should naturally be faster on 64-bit processors because like you said you have 64-bit registers and operations. However, I guess 32-bit to 64-bit speedup can vary significantly between bitboard programs so it probably won't do much good trying to compare an engine's 32-bit to 64-bit speedup to other bitboard engines.Test positions:
A: (depth 5) r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
B: (depth 7) r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1 (which can be compared to engines in another post).
C: (depth 6) rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Étude (64 bit):
A: 5. 193690690 (7.86s)
B: 7. 528388659 (20.59s)
C: 6. 119060324 (4.49s)
Bitboard Perft (64 bit):
A: 5. 193690690 (7.06s)
B: 7. 528388659 (18.41s)
C: 6. 119060324 (4.19s)
Étude (32 bit):
A: 5. 193690690 (13.39s)
B: 7. 528388659 (36.56s)
C: 6. 119060324 (8.11s)
Bitboard Perft (32 bit):
A: 5. 193690690 (14.08s)
B: (misplaced
C: 6. 119060324 (8.63s)
I'm surprised that Bitboard Perft ran faster in 64-bit mode, I wonder if it has something to do with the compiler,... Or the increase in available registers?
-
Jacob
Re: Generalized bitboard pawn moves
Thanks, that's exactly what I've been looking forFor 64-bits you could try using intrinsics or processor instructions for the bitscan. It should be quite a bit faster on your processor:Code: Select all
(omitted code...) #if defined(__GNUC__) && defined(__LP64__) static INLINE unsigned char _BitScanForward64(unsigned int* const Index, const U64 Mask) { U64 Ret; __asm__ ( "bsfq %[Mask], %[Ret]" :[Ret] "=r" (Ret) :[Mask] "mr" (Mask) ); *Index = (unsigned int)Ret; return Mask?1:0; } #define USING_INTRINSICS #endif
. I only have 32-bit windows, but using the assembly under Fedora yields around a 5-10% speed increase in perft with make/unmake in leaf nodes, but up to 50% without the last make/unmake.Bitboard engines should naturally be faster on 64-bit processors because like you said you have 64-bit registers and operations.
I apologize, I wasn't very clear. I was surprised that Bitboard Perft ran faster than Etude in 64-bit mode but slower in 32-bit mode, considering that they're very, very similar, and Bitboard Perft seems to be doing more work in the move generation because of having to swap occupancy/piece boards for the generalized pawn move generation/etc. I'll try in the Intel compiler when I get a chance, thanks for the suggestion.
With the code updates (I'll get them uploaded tonight):
Code: Select all
r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
(compare to http://64.68.157.89/forum/viewtopic.php?t=13829)
(64 bit mode)
1. 14 0.00s
2. 192 0.00s
3. 3466 0.00s
4. 60120 0.00s
5. 1223784 0.04s
6. 24161970 0.80s
7. 528388659 16.87s
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
No make/undo in leaf nodes
1. 20 0.00s
2. 400 0.00s
3. 8902 0.00s
4. 197281 0.00s
5. 4865609 0.05s
6. 119060324 1.02s
7. 3195901860 26.52s
HG Muller's QuickPerft results for comparison:
perft(1)= 20 ( 0.000 sec)
perft(2)= 400 ( 0.000 sec)
perft(3)= 8902 ( 0.000 sec)
perft(4)= 197281 ( 0.000 sec)
perft(5)= 4865609 ( 0.046 sec)
perft(6)= 119060324 ( 0.844 sec)
perft(7)= 3195901860 (22.828 sec)
- Show quoted text -