Page 1 of 1

Good examples for magic or rotated boards

Posted: Tue Oct 26, 2010 4:39 am
by jashwant
Hi,all.
I am a newbie..II've gone through http://chessprogramming.wikispaces.com and http://www.cis.uab.edu/hyatt/pubs.html and many other programming tutorials. They all cover most of the theoretical part but none of them have good pictorial examples. I am perhaps not a good learner or programmer but I want to know about this.... I have developed a small chess program between two player with 8*8 board but soon realised this would not be efficient for AI. I am switching to bitboards. I've got basic idea of bitboards (pawn,king,knight moves) but rotating bitboards or magic boards are too high for me :( . Can someone provide me a programming logic to build moves for bishop/rook (from rotated or magic boards ) ??? It will be very helpful if someone can teach magic boards as rotating boards are still seems as I can learn them :)

Re: Good examples for magic or rotated boards

Posted: Tue Oct 26, 2010 8:47 am
by RobertP
The easiest bitboard slider-attacks code to write is the standard or classical method:
http://chessprogramming.wikispaces.com/ ... l+Approach

Here's an implementation of RookAttacks().

Code: Select all

extern BitBoard gRayN[64], gRayE[64], gRayS[64], gRayW[64];

BitBoard RookAttacks( int fromSquare, BitBoard occupied ) 
{ 
	int        blockingSquare; 
	BitBoard   attacks, partAttacks, blockers; 
	
	attacks = gRayN[fromSquare]; 
	blockers = attacks & occupied; 
	if ( blockers ) 
	{ 
		blockingSquare = GetLowestBit( blockers ); 
		attacks ^= gRayN[blockingSquare]; // mask off beyond blocking square
	} 
	
	partAttacks = gRayE[fromSquare]; 
	blockers = partAttacks & occupied; 
	if ( blockers ) 
	{ 
		blockingSquare = GetLowestBit( blockers ); 
		partAttacks ^= gRayE[blockingSquare]; 
	} 
	attacks |= partAttacks; 
	
	partAttacks = gRayS[fromSquare]; 
	blockers = partAttacks & occupied; 
	if ( blockers ) 
	{ 
		blockingSquare = GetHighestBit( blockers ); 
		partAttacks ^= gRayS[blockingSquare]; 
	} 
	attacks |= partAttacks; 
	
	partAttacks = gRayW[fromSquare]; 
	blockers = partAttacks & occupied; 
	if ( blockers ) 
	{ 
		blockingSquare = GetHighestBit( blockers ); 
		partAttacks ^= gRayW[blockingSquare]; 
	} 

	return attacks | partAttacks; 
}  
BishopAttacks() is similar, with the obvious substitutions (gRayNW[], gRayNE[], gRaySE[], gRaySW[]).
These functions are quite easy to understand, which is important while you get used to bitboard programming. They will be much faster than your existing slider-attack code, which no doubt has loops.
At some later time you may want to try magic, as a minor optimization.

Robert P.

Re: Good examples for magic or rotated boards

Posted: Wed Oct 27, 2010 5:27 pm
by jashwant
Nice approach..At this time, I dont want any optimizations. First I want to complete my initial work.Then, I'll go for optimizations.

Thanks a lot for this approach.Made my way...and many thanks to your implementation :)

Re: Good examples for magic or rotated boards

Posted: Wed Nov 24, 2010 8:18 pm
by BB+
There was a comparative analysis of bitboard methods by Harald Lüßen a few years back. http://www.talkchess.com/forum/viewtopi ... 11&t=16002
As you can see, there are a number of different methods. For each method, there is a later post that gives the actual code. He notes that your mileage way vary, as all comparison were with his Elephant engine.

At the same time, code recycling happens a lot here. For instance, Bob chooses to adapt Pradu's code in Crafty, and VR does the same in Rybka 4 (both of these seem to be unacknowledged in the respective distributions, though Bob has mentioned his usage on various occasions -- Pradu simply says: "If you use this code in a product, an acknowledgment in the product documentation would be appreciated but is not required"), with the exact same magic multipliers, order of squares in the arrays, etc.

Re: Good examples for magic or rotated boards

Posted: Thu Dec 02, 2010 6:48 am
by hyatt
I'm glad you posted that. I am not sure why there was no reference to Pradu's work in Crafty's changelog in the comments. Probably because I had mentioned his name every time I mentioned my conversion to magic bitboards. In any case, I fixed this as I have always tried to cite anyone that provided code I used inside Crafty...

Pradu visited UAB for our first ACCA event at UAB (He was at Ga Tech I think) so I had the opportunity to discuss the magic stuff at length with him. And enjoyed the visit...

Re: Good examples for magic or rotated boards

Posted: Thu Dec 02, 2010 9:56 pm
by zwegner
BB+ wrote:There was a comparative analysis of bitboard methods by Harald Lüßen a few years back. http://www.talkchess.com/forum/viewtopi ... 11&t=16002
As you can see, there are a number of different methods. For each method, there is a later post that gives the actual code. He notes that your mileage way vary, as all comparison were with his Elephant engine.

At the same time, code recycling happens a lot here. For instance, Bob chooses to adapt Pradu's code in Crafty, and VR does the same in Rybka 4 (both of these seem to be unacknowledged in the respective distributions, though Bob has mentioned his usage on various occasions -- Pradu simply says: "If you use this code in a product, an acknowledgment in the product documentation would be appreciated but is not required"), with the exact same magic multipliers, order of squares in the arrays, etc.
Still no response to this?

I'd think the news that Vas is using open source code in Rybka 4 without acknowledgement would cause a bit of commotion. :)

Re: Good examples for magic or rotated boards

Posted: Fri Dec 03, 2010 12:23 am
by Jeremy Bernstein
zwegner wrote:
BB+ wrote:There was a comparative analysis of bitboard methods by Harald Lüßen a few years back. http://www.talkchess.com/forum/viewtopi ... 11&t=16002
As you can see, there are a number of different methods. For each method, there is a later post that gives the actual code. He notes that your mileage way vary, as all comparison were with his Elephant engine.

At the same time, code recycling happens a lot here. For instance, Bob chooses to adapt Pradu's code in Crafty, and VR does the same in Rybka 4 (both of these seem to be unacknowledged in the respective distributions, though Bob has mentioned his usage on various occasions -- Pradu simply says: "If you use this code in a product, an acknowledgment in the product documentation would be appreciated but is not required"), with the exact same magic multipliers, order of squares in the arrays, etc.
Still no response to this?

I'd think the news that Vas is using open source code in Rybka 4 without acknowledgement would cause a bit of commotion. :)
"If you use this code in a product, an acknowledgment in the product documentation would be appreciated but is not required". Vas isn't breaking any license agreements, if he's using this code. Might be a little rude, but that's bidnis.

Jeremy

Re: Good examples for magic or rotated boards

Posted: Fri Dec 03, 2010 2:45 am
by BB+
I'd think the news that Vas is using open source code in Rybka 4 without acknowledgement would cause a bit of commotion. :)
Well, Bob is technically doing the same, as I don't find a mention of Pradu (and/or Buzz) in the Crafty distribution. Pradu is also quite clear that it is permissible. It also seems (to me) that one really can't use Pradu's code "as a library" as it were [for instance, compile it separately and link in via an API, more like Nalimov] --- you have to hack it up to fit your needs. This said, it can't be that difficult to write independent magic multiplier code once the idea is known (and Tord has provided code to generate the mults if you need help with that); perhaps using Pradu's numbers could be nice at first if debugging, but I don't even think they are the "best known" values any more [though that can't really matter too much].