Strange results after change in positional representation

[bob]

OK, I discovered that increasing the board size disrupted my move ordering.

In the old system, I had managed to cram information on source square, destination square, promotion piece, and a sort key for move ordering all into one 32 bit integer, and I forgot that I only had 1 bit to spare.

By moving to a larger board, I added an extra bit to source and destination square indexes, and this pushed the most significant bit of my sort key off of the left end.

I'll have to rethink my scheme for storing move information during moveGen.

Thanks for all the suggestions.

You certainly should not need 32 bits if you are only talking about specific move info such as from and to squares. I store a move in 21 bits, 6 for from, 6 for 2, 3 for moving piece, 3 for captured piece, 3 for promote-to piece. You will need more than 6 for from, to, but 7 should do it.

[MattieShoes]

TSCP has a simple 32 bit structure if I remember right

struct move
{
char from
char to
char promote
char bitfield
}

That can be unioned with a 32 bit integer for easy comparison of moves

I think the bitfield contained data to make board updating easier...
pawn move
pawn push two squares
capture
castle
ep capture

then a simple bitfield&mask can tell you whether you need to remove a piece, promote a piece, recalculate pawn structure part of eval, set an ep square, promote a piece, etc. And of course it can be used to undo all that stuff too. Plus I think it was used for some basic move ordering (captures first, etc).

[Fguy64]

OK, I discovered that increasing the board size disrupted my move ordering.

In the old system, I had managed to cram information on source square, destination square, promotion piece, and a sort key for move ordering all into one 32 bit integer, and I forgot that I only had 1 bit to spare.

By moving to a larger board, I added an extra bit to source and destination square indexes, and this pushed the most significant bit of my sort key off of the left end.

I'll have to rethink my scheme for storing move information during moveGen.

Thanks for all the suggestions.

You certainly should not need 32 bits if you are only talking about specific move info such as from and to squares. I store a move in 21 bits, 6 for from, 6 for 2, 3 for moving piece, 3 for captured piece, 3 for promote-to piece. You will need more than 6 for from, to, but 7 should do it.

Noted. One of my brilliant ideas from a while back was to have my piece integers do double duty, representing both the pieces themselves and their material values, so I have +/- 90, 50, 30, 29, 10 in the position array, which makes for a nice quick evaluation of the material balance, while being large enough to provide for flexibility in assigning positional values that don't overwhelm the material values. So you can get an idea of where all my bits have gone.

Obviously I'm starting to see the limitations of this approach. But it should be easy enough to get past this little hurdle. I'll just scale by a number smaller than 10, small enough to free up a few bits.

onwards and upwards, Thanks as always for the tips.

p.s. to Matt, thanks for the tip. I'll add that to my list of ideas. Really this project is supposed to be a vehicle for me to learn java, so I like to try all the ideas, even my bad ones have value in the learning context.

[metax]

Noted. One of my brilliant ideas from a while back was to have my piece integers do double duty, representing both the pieces themselves and their material values, so I have +/- 90, 50, 30, 29, 10 in the position array, which makes for a nice quick evaluation of the material balance, while being large enough to provide for flexibility in assigning positional values that don't overwhelm the material values. So you can get an idea of where all my bits have gone.

Obviously I'm starting to see the limitations of this approach. But it should be easy enough to get past this little hurdle. I'll just scale by a number smaller than 10, small enough to free up a few bits.

onwards and upwards, Thanks as always for the tips.

p.s. to Matt, thanks for the tip. I'll add that to my list of ideas. Really this project is supposed to be a vehicle for me to learn java, so I like to try all the ideas, even my bad ones have value in the learning context.

Why not just take 'normal' values for the pieces and then look up the material values in a table. I am pretty sure that does not cost too much performance.

[hgm]

To efficiently handle the pieces, you would have to store the piece _numbers_ in the board, rather than the piece types. (I.e. all Pawns will have different encoding.) So you would have to do a table lookup anyway to figure out which type of piece it was, and you might as well look up directly what its value was.

In fact my engine HaQiKi D does not even look up what value it was, but looks up a piece-type code designed for differentially updating the material index, so that the new index could then be used to look up your new total material evaluation after you capture the piece. (I.e., if you want to know how much the _effective_ piece value was, you would have to subtract this from the previous total material evaluation.)

[bob]

OK, I discovered that increasing the board size disrupted my move ordering.

In the old system, I had managed to cram information on source square, destination square, promotion piece, and a sort key for move ordering all into one 32 bit integer, and I forgot that I only had 1 bit to spare.

By moving to a larger board, I added an extra bit to source and destination square indexes, and this pushed the most significant bit of my sort key off of the left end.

I'll have to rethink my scheme for storing move information during moveGen.

Thanks for all the suggestions.

You certainly should not need 32 bits if you are only talking about specific move info such as from and to squares. I store a move in 21 bits, 6 for from, 6 for 2, 3 for moving piece, 3 for captured piece, 3 for promote-to piece. You will need more than 6 for from, to, but 7 should do it.

Noted. One of my brilliant ideas from a while back was to have my piece integers do double duty, representing both the pieces themselves and their material values, so I have +/- 90, 50, 30, 29, 10 in the position array, which makes for a nice quick evaluation of the material balance, while being large enough to provide for flexibility in assigning positional values that don't overwhelm the material values. So you can get an idea of where all my bits have gone.

Obviously I'm starting to see the limitations of this approach. But it should be easy enough to get past this little hurdle. I'll just scale by a number smaller than 10, small enough to free up a few bits.

onwards and upwards, Thanks as always for the tips.

p.s. to Matt, thanks for the tip. I'll add that to my list of ideas. Really this project is supposed to be a vehicle for me to learn java, so I like to try all the ideas, even my bad ones have value in the learning context.

You can do the same thing with p=1, n=2, b=3, r=4, q=5, k=6, and a small array pv[6] = {100 300 300 500 900 99999}; Then index into this array using the piece type to get the score.

[Fguy64]

OK, I discovered that increasing the board size disrupted my move ordering.

In the old system, I had managed to cram information on source square, destination square, promotion piece, and a sort key for move ordering all into one 32 bit integer, and I forgot that I only had 1 bit to spare.

By moving to a larger board, I added an extra bit to source and destination square indexes, and this pushed the most significant bit of my sort key off of the left end.

I'll have to rethink my scheme for storing move information during moveGen.

Thanks for all the suggestions.

You certainly should not need 32 bits if you are only talking about specific move info such as from and to squares. I store a move in 21 bits, 6 for from, 6 for 2, 3 for moving piece, 3 for captured piece, 3 for promote-to piece. You will need more than 6 for from, to, but 7 should do it.

Noted. One of my brilliant ideas from a while back was to have my piece integers do double duty, representing both the pieces themselves and their material values, so I have +/- 90, 50, 30, 29, 10 in the position array, which makes for a nice quick evaluation of the material balance, while being large enough to provide for flexibility in assigning positional values that don't overwhelm the material values. So you can get an idea of where all my bits have gone.

Obviously I'm starting to see the limitations of this approach. But it should be easy enough to get past this little hurdle. I'll just scale by a number smaller than 10, small enough to free up a few bits.

onwards and upwards, Thanks as always for the tips.

p.s. to Matt, thanks for the tip. I'll add that to my list of ideas. Really this project is supposed to be a vehicle for me to learn java, so I like to try all the ideas, even my bad ones have value in the learning context.

You can do the same thing with p=1, n=2, b=3, r=4, q=5, k=6, and a small array pv[6] = {100 300 300 500 900 99999}; Then index into this array using the piece type to get the score.

I like the idea, and I just might use it in a futue version, but I ended up going with something a little different for now, because it is less work given what I alrady have.

In my square centric approach, there are four pieces of information I need to store in a 32-bit integer, source square, destination square, promotion piece, and a sort key. This is a plan I have to stick with, at least for now.

the values in my position array are +/- 5, 14, 15, 25, 45, for White/Black P, N, B, R, K. So I reduced the scaling factor from 10 to five. Using these piece symbols in my position array allows me to calculate material balance by summing the position array.

so, with my 10x10 board we have source and destination square using 7 bits each, promotion piece uses 7 bits, and my sort key, which is 16*V-A, uses 10 bits, for a total of 31 bits. I can't use 32 bits because java does not support an unsigned integer.

in my 10x10 board, the outer border is fill with 1's.

So a typical block of code in moveGen looks something like the following pseudo code for movement of a black rook towards white...

Code: Select all

dest = src;
while( posn[ dest += 10] == 0 ) {
	addMove
}
if( posn[dest] > 1 ) addCapture

I suppose with these piece values I will hit the wall when it comes time for sophisticated positional evaluation, but this will keep me going for now.

[Fguy64]

To efficiently handle the pieces, you would have to store the piece _numbers_ in the board, rather than the piece types. (I.e. all Pawns will have different encoding.) So you would have to do a table lookup anyway to figure out which type of piece it was, and you might as well look up directly what its value was.

In fact my engine HaQiKi D does not even look up what value it was, but looks up a piece-type code designed for differentially updating the material index, so that the new index could then be used to look up your new total material evaluation after you capture the piece. (I.e., if you want to know how much the _effective_ piece value was, you would have to subtract this from the previous total material evaluation.)

At some point I know I will have to resort to a scheme that uses lookups for material value, But as discussed in my previous post I'm not quite ready for that yet.

[Fguy64]

OK, I discovered that increasing the board size disrupted my move ordering.

In the old system, I had managed to cram information on source square, destination square, promotion piece, and a sort key for move ordering all into one 32 bit integer, and I forgot that I only had 1 bit to spare.

By moving to a larger board, I added an extra bit to source and destination square indexes, and this pushed the most significant bit of my sort key off of the left end.

I'll have to rethink my scheme for storing move information during moveGen.

Thanks for all the suggestions.

You certainly should not need 32 bits if you are only talking about specific move info such as from and to squares. I store a move in 21 bits, 6 for from, 6 for 2, 3 for moving piece, 3 for captured piece, 3 for promote-to piece. You will need more than 6 for from, to, but 7 should do it.

So do you use the stored info for moved piece and captured piece for subsequent move ordering calculations then?

[metax]

So do you use the stored info for moved piece and captured piece for subsequent move ordering calculations then?

I would be surprised if not. As far as I know, Crafty uses MVV/LVA to order captures and this information is useful to do so.