Crafty questions

[Pablo Vazquez]

Hi Bob (or anyone else who reads this)

I have a few questions about crafty

1.- The invalid en passant square is represented by zero. Why not keep it as 64? Since set_mask[64] returns an empty bitboard, the conditional operator would be unnecessary.

2.- For the size of some arrays, you use MAX_PLY + 2. Why is this? Is it to avoid some kind of overflow?

3.- I see you eliminated special white and black code in recent versions of crafty. But in move generation, for non special moves like pawns and castling you could do something like for (piece = KNIGHT; piece <= KING...) and reduce the code further. Is there a reason not to do this?

4.- In move generation, to collect the moves you use last_one() for white and first_one() for black. I guess this is because that way, moves that attack the enemy camp get ordered first. But i have seen other people's code and they only use first_one() to collect the moves. Does it really make any difference?

Thanks

[bob]

Hi Bob (or anyone else who reads this)

I have a few questions about crafty

1.- The invalid en passant square is represented by zero. Why not keep it as 64? Since set_mask[64] returns an empty bitboard, the conditional operator would be unnecessary.

2.- For the size of some arrays, you use MAX_PLY + 2. Why is this? Is it to avoid some kind of overflow?

Yes. Particularly dealing with output so that I can call MakeMove() but not destroy any real search data since I do some of this while a search is "in progress"...

3.- I see you eliminated special white and black code in recent versions of crafty. But in move generation, for non special moves like pawns and castling you could do something like for (piece = KNIGHT; piece <= KING...) and reduce the code further. Is there a reason not to do this?

The way moves are generated is different for each piece type. I tried using an array of pointers to functions, which collapses movgen into something very small, but it was significantly slower... So while it is a good idea from a programming/documentation perspective, it is not good from a performance perspective and was discarded.

4.- In move generation, to collect the moves you use last_one() for white and first_one() for black. I guess this is because that way, moves that attack the enemy camp get ordered first. But i have seen other people's code and they only use first_one() to collect the moves. Does it really make any difference?

Thanks

it has two effects. First, I do want to move the most advanced pieces first, and secondly I want to produce the same tree if you just flip colors. If I always used last_one, then it would cause the node counts to change due to the asymmetry of the order...

As to the difference it makes, you should try it, it is easy enough to change in Crafty. The results will probably surprise you, and things will go slower as the trees will get bigger.

[Pablo Vazquez]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

[bob]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

No. Think about what happens. For the starting position, say the first white piece is on a1 and the only other one is on D4. The piece on A1 is a rook, the piece on D4 is the king. LastOne() will find the D4 piece first. But when you flip the sides around, now the Rook is on A8 and the King is on D5, and LastOne() now finds the rook move first, rather than the king move.

More importantly however is the fact that I want everything to be symmetric, and looking at the most advanced piece moves first has (for my program) produced the smallest trees. That's why I toggle MSB()/LSB() in crafty. And that is why, even in the current one-case-fits-all for move generation I still need to use MSB for white, LSB for black...

[michiguel]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

No. Think about what happens. For the starting position, say the first white piece is on a1 and the only other one is on D4. The piece on A1 is a rook, the piece on D4 is the king. LastOne() will find the D4 piece first. But when you flip the sides around, now the Rook is on A8 and the King is on D5, and LastOne() now finds the rook move first, rather than the king move.

More importantly however is the fact that I want everything to be symmetric, and looking at the most advanced piece moves first has (for my program) produced the smallest trees. That's why I toggle MSB()/LSB() in crafty. And that is why, even in the current one-case-fits-all for move generation I still need to use MSB for white, LSB for black...

If understand correctly, in move ordering you sort moves (indirectly by how they are generated) from more advanced to less advanced pieces, after killers, (I am sure). Correct?

Miguel

[Pablo Vazquez]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

No. Think about what happens. For the starting position, say the first white piece is on a1 and the only other one is on D4. The piece on A1 is a rook, the piece on D4 is the king. LastOne() will find the D4 piece first. But when you flip the sides around, now the Rook is on A8 and the King is on D5, and LastOne() now finds the rook move first, rather than the king move.

More importantly however is the fact that I want everything to be symmetric, and looking at the most advanced piece moves first has (for my program) produced the smallest trees. That's why I toggle MSB()/LSB() in crafty. And that is why, even in the current one-case-fits-all for move generation I still need to use MSB for white, LSB for black...

Yes, i know that using only FirstOne() or LastOne() won't produce the same tree when flipping colours but i also think that toggling will not work. For example if you had rook on a1, knight on h1 and king on d4, and you sort moves for white using LastOne() you get this order of moves: king(d4), knight(h1) and rook(a1). Now you flip colours and sort moves for black using FirstOne() and you get this: king(d5), rook(a8) and knight(h8). So the order has changed

[wgarvin]

Yes, i know that using only FirstOne() or LastOne() won't produce the same tree when flipping colours but i also think that toggling will not work. For example if you had rook on a1, knight on h1 and king on d4, and you sort moves for white using LastOne() you get this order of moves: king(d4), knight(h1) and rook(a1). Now you flip colours and sort moves for black using FirstOne() and you get this: king(d5), rook(a8) and knight(h8). So the order has changed

It's true that it won't produce the exact same tree, because it is equivalent to mirroring the board both vertically AND horizontally, rather than just mirroring it vertically (which is what you want to do when you flip the piece colors).

On the other hand, with the exception of castling, you can always mirror a board horizontally and still have a legal chess position. (This symmetry is always used in endgame tables, for example). So I think Bob's method still produces a tree which is exactly equivalent to this mirrored position. Any differences would only show up when you have two pieces of the same type on the same rank. I suspect the effects of this on the order of the generated moves are much less noticable than if you didn't flip the order around at all.

Gerd Isenberg uses a different method in his engine, where he actually flips the colors on every move, so that in effect instead of "white" and "black", his colors are "side-to-move" and "side-not-to-move". So when flipping the colors, he also flips his bitboards vertically (using bswap instructions) but not horizontally. So Gerd's method always gives the exact same tree for a position, regardless of which player is to move.

However, it relies on a good byte-swapping method for the bitboards. On x86-64, bswap seems pretty good. On a PPC chip or similar, you could swap two bitboards at a time with a vector permute instruction. There might be some SSE way of doing it for x86, though I don't know if its worth the trouble over just using bswaps.

[bob]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

No. Think about what happens. For the starting position, say the first white piece is on a1 and the only other one is on D4. The piece on A1 is a rook, the piece on D4 is the king. LastOne() will find the D4 piece first. But when you flip the sides around, now the Rook is on A8 and the King is on D5, and LastOne() now finds the rook move first, rather than the king move.

More importantly however is the fact that I want everything to be symmetric, and looking at the most advanced piece moves first has (for my program) produced the smallest trees. That's why I toggle MSB()/LSB() in crafty. And that is why, even in the current one-case-fits-all for move generation I still need to use MSB for white, LSB for black...

If understand correctly, in move ordering you sort moves (indirectly by how they are generated) from more advanced to less advanced pieces, after killers, (I am sure). Correct?

Miguel

Not completely right. I generate moves in the "stock order", which moves the most advanced piece first, starting with knights, then bishops, then rooks, queens, kings and finally the pawn pushes... Within each piece type the moves are generated for the most advanced piece of that type first, and the moves are then produced to move to the most advanced square first.

This is really only important after all the usual ordering tricks down thru killers are tried, so this is "the rest of the moves in at least some semblance of an order that is repeatable".

[bob]

Ok, thanks for the answers.

But i still don't understand the last point. When you use first_one you are scanning the board from a1 to h8 and with last_one its the opposite. But if you want the same tree with flipped colours, wouldn't you need to scan the board from a8...h8, a7..h7 ... a1...h1?

No. Think about what happens. For the starting position, say the first white piece is on a1 and the only other one is on D4. The piece on A1 is a rook, the piece on D4 is the king. LastOne() will find the D4 piece first. But when you flip the sides around, now the Rook is on A8 and the King is on D5, and LastOne() now finds the rook move first, rather than the king move.

More importantly however is the fact that I want everything to be symmetric, and looking at the most advanced piece moves first has (for my program) produced the smallest trees. That's why I toggle MSB()/LSB() in crafty. And that is why, even in the current one-case-fits-all for move generation I still need to use MSB for white, LSB for black...

Yes, i know that using only FirstOne() or LastOne() won't produce the same tree when flipping colours but i also think that toggling will not work. For example if you had rook on a1, knight on h1 and king on d4, and you sort moves for white using LastOne() you get this order of moves: king(d4), knight(h1) and rook(a1). Now you flip colours and sort moves for black using FirstOne() and you get this: king(d5), rook(a8) and knight(h8). So the order has changed

Correct, but note that I try the most advanced pieces first, either way, which was my goal to be symmetric. I don't want to generate aggressive moves for one side first, and passive moves for the other...