BitBoards for Chess

[Zacariaz]

Just a short question which I haven't been able to get an answer to anywhere else.

The usual way of representing a chess board using bit boards:

Code: Select all

WhitePawns
BlackPawns
WhiteRooks
BlackRooks
WhiteKnights
BlackKnights
WhiteBishops
BlackBishops
WhiteQueen
BlackQueen
WhiteKing
BlackKing

12 64 bit variable. Makes sense all right, however, there is an alternate approach:

Code: Select all

Pawns
Rooks
Knights
Bishops
Queens
Kings
WhitePieces
BlackPieces

So we're down to 8 64 bit variables.

Obviously fx. BlackPawns = Pawns & BlackPieces

I've been trying to investigate any significant drawbacks, but without any luck. Apparently no one have ever thought about the second approach before or the drawbacks should be so obvious that there's no need to mention them.

Well, I don't see any significant drawbacks.

Should any of you have enlightening comments on this, it'll be very much appreciated.


Best Regards.

[Thomas]

Hi,
That's seems to be a good enough proposition and saves some memory.But the main question would be,assume that you used the above data represenation and then does it add more complexity while creating the minimax tree?, does this make the static evaluation function for each position more complex? Does this representation make searching the state space more complex?

Long time,since I have worked with problems like these.Pardom me in case of any ignorance.Also excuse my poor English.
--Thomas

[NickJohnson]

It's undoubtedly much slower, since you have to search every time you want to move a piece or check whether a capture was made. Either way, there's no real reason to be optimizing: 64 bytes or a few nanoseconds are not enough to worry about in a game of chess, so in this case, choose the simplest implementation.

[Solar]

Either way, there's no real reason to be optimizing: 64 bytes or a few nanoseconds are not enough to worry about in a game of chess, so in this case, choose the simplest implementation.

It does make a difference when you are working on a chess AI - the faster it does the calculations, the better it can play.

[NickJohnson]

Either way, there's no real reason to be optimizing: 64 bytes or a few nanoseconds are not enough to worry about in a game of chess, so in this case, choose the simplest implementation.

It does make a difference when you are working on a chess AI - the faster it does the calculations, the better it can play.

Okay, in that case speed does matter. However, for chess, the simpler of the two algorithms is actually the much faster one (constant vs. linear time), so either way "optimizing out" 64 bytes per board is not a worthwhile endeavor. You could simply switch from qwords to bytes for each space and get an even better result.

[JamesM]

Either way, there's no real reason to be optimizing: 64 bytes or a few nanoseconds are not enough to worry about in a game of chess, so in this case, choose the simplest implementation.

It does make a difference when you are working on a chess AI - the faster it does the calculations, the better it can play.

Okay, in that case speed does matter. However, for chess, the simpler of the two algorithms is actually the much faster one (constant vs. linear time), so either way "optimizing out" 64 bytes per board is not a worthwhile endeavor. You could simply switch from qwords to bytes for each space and get an even better result.

Ahem, how does his change cause the change from constant to linear time? It only adds one bitwise AND per state evaluation, and ANDs are pretty much instantaneous. I don't understand your "switching from qwords to bytes" either - it takes 64 bits to represent a bitboard (8x8 = 64 spaces).

@OP: I can't see anything wrong, however - time is more important than memory. In an iterative deepening search (which minimax, alpha-beta and negascout all are) you only maintain full bitboard sets for each state on the fringe - meaning that the number of states you maintain in memory at any one time is significantly (read: log to base (branch factor - something large) of the number of states you visit in total).

So, time is more of the essence, and although you only add one extra AND, it gets executed MANY times. So it might be worth sticking with the original formula

[Zacariaz]

I'm glad to see that this discussion is still going on.

I am aware that, in theory anyway, the regular approach is more efficient, however, I've never really done anything like this before and thus don't know exactly what pros and cons there may be, other than that the second approach uses more cycles.

In any case, it's almost always easy to find drawbacks, but it's really the advantages, if any, I'm interested in. It would seem there's none, other than the fact that I like to go with as few variables as possible

[NickJohnson]

@JamesM: Whoops, sorry: I was thinking of something else I guess. I haven't had much sleep lately...

[JamesM]

Also, good to see you back Zacariaz - haven't seen you for years!

[Zacariaz]

Also, good to see you back Zacariaz - haven't seen you for years!

I do pop by from time to time, but since I realised that I'm not a prospecting OS programmer, I tend to forget about this forum unless I need expert advice of course