Square Occupation vs Mobility / Square Control

[Fguy64]

This post has a lot in common with a recent thread on determining values for piece square tables, but different enough to warrant it's own thread. For reference here is the thread on piece/square tables.

http://www.talkchess.com/forum/viewtopic.php?t=29825

OK, so piece/square tables are an easy way to assign values to positions based on the squares that the individual pieces occupy. The operative word here is assign. It's easy to assign a value, not so easy to come up with a meaningful value. But I guess that begs the question.

Anyways, my chess sense tells me that square occupation is a simplified way of representing more complex issues like square control or mobility. As a player I am more interested in square control and mobility, in that sense I see dealing with square occupation as something of a compromise to make programming easier. PST's make the programmatic assigning of values to pieces much easier, but it becomes more difficult to come up with meaningful values

Where this is all leading to is as follows...

It would be nice to be able to work directly with mobility and square control directly from within the evaluation function. It is easy enough to come up with algorithms that do so, but then you end up doing things that are normally done by search and MoveGen, which is looking at subsequent possible moves. So I have thought about incorporating piece square values determined at intermediate (non-leaf) nodes into evaluation as a way of dealing with mobility/square control, but I haven't tried anything. Intuition tells me I might be asking for trouble with that kind of thing. I also suppose that if one is directly evaluating mobility and square control at a leaf node, than that work might ne saved for re-use in some kind of a hash table or some such thing.

[bob]

This post has a lot in common with a recent thread on determining values for piece square tables, but different enough to warrant it's own thread. For reference here is the thread on piece/square tables.

http://www.talkchess.com/forum/viewtopic.php?t=29825

OK, so piece/square tables are an easy way to assign values to positions based on the squares that the individual pieces occupy. The operative word here is assign. It's easy to assign a value, not so easy to come up with a meaningful value. But I guess that begs the question.

Anyways, my chess sense tells me that square occupation is a simplified way of representing more complex issues like square control or mobility. As a player I am more interested in square control and mobility, in that sense I see dealing with square occupation as something of a compromise to make programming easier. PST's make the programmatic assigning of values to pieces much easier, but it becomes more difficult to come up with meaningful values

Where this is all leading to is as follows...

It would be nice to be able to work directly with mobility and square control directly from within the evaluation function. It is easy enough to come up with algorithms that do so, but then you end up doing things that are normally done by search and MoveGen, which is looking at subsequent possible moves. So I have thought about incorporating piece square values determined at intermediate (non-leaf) nodes into evaluation as a way of dealing with mobility/square control, but I haven't tried anything. Intuition tells me I might be asking for trouble with that kind of thing. I also suppose that if one is directly evaluating mobility and square control at a leaf node, than that work might ne saved for re-use in some kind of a hash table or some such thing.

Crafty's been doing something like this for quite a while. Our mobility calculation is not simply a "total reachable squares" for a piece. We take the squares the piece can reach, and add in a value for a specific square. For example, a knight that can reach e4 gets a better score than if it can reach a1, because a1 is an unimportant square in general.

There are ways to do this that are not very expensive, although they are a little complex.

[Fguy64]

This post has a lot in common with a recent thread on determining values for piece square tables, but different enough to warrant it's own thread. For reference here is the thread on piece/square tables.

http://www.talkchess.com/forum/viewtopic.php?t=29825

OK, so piece/square tables are an easy way to assign values to positions based on the squares that the individual pieces occupy. The operative word here is assign. It's easy to assign a value, not so easy to come up with a meaningful value. But I guess that begs the question.

Anyways, my chess sense tells me that square occupation is a simplified way of representing more complex issues like square control or mobility. As a player I am more interested in square control and mobility, in that sense I see dealing with square occupation as something of a compromise to make programming easier. PST's make the programmatic assigning of values to pieces much easier, but it becomes more difficult to come up with meaningful values

Where this is all leading to is as follows...

It would be nice to be able to work directly with mobility and square control directly from within the evaluation function. It is easy enough to come up with algorithms that do so, but then you end up doing things that are normally done by search and MoveGen, which is looking at subsequent possible moves. So I have thought about incorporating piece square values determined at intermediate (non-leaf) nodes into evaluation as a way of dealing with mobility/square control, but I haven't tried anything. Intuition tells me I might be asking for trouble with that kind of thing. I also suppose that if one is directly evaluating mobility and square control at a leaf node, than that work might ne saved for re-use in some kind of a hash table or some such thing.

Crafty's been doing something like this for quite a while. Our mobility calculation is not simply a "total reachable squares" for a piece. We take the squares the piece can reach, and add in a value for a specific square. For example, a knight that can reach e4 gets a better score than if it can reach a1, because a1 is an unimportant square in general.

There are ways to do this that are not very expensive, although they are a little complex.

OK, the bolded remark seems to validate what I am saying. It is in fact desireable to deal with mobility & square control directly within eval, but to do so inexpensively (efficiently) is not at all easy.

So does the complexity arise from finding an inexpensive way to place a higher value on a reachable e4 than a reachable a1? Or is it in finding an inexpensive way to find total reachable moves. It seems that even this simpler 2nd idea can be expensive.

So do these inexpensive methods that Crafty uses involve re-using the information on reachable squares as part of the next edition of moveGen?

[bob]

This post has a lot in common with a recent thread on determining values for piece square tables, but different enough to warrant it's own thread. For reference here is the thread on piece/square tables.

http://www.talkchess.com/forum/viewtopic.php?t=29825

OK, so piece/square tables are an easy way to assign values to positions based on the squares that the individual pieces occupy. The operative word here is assign. It's easy to assign a value, not so easy to come up with a meaningful value. But I guess that begs the question.

Anyways, my chess sense tells me that square occupation is a simplified way of representing more complex issues like square control or mobility. As a player I am more interested in square control and mobility, in that sense I see dealing with square occupation as something of a compromise to make programming easier. PST's make the programmatic assigning of values to pieces much easier, but it becomes more difficult to come up with meaningful values

Where this is all leading to is as follows...

It would be nice to be able to work directly with mobility and square control directly from within the evaluation function. It is easy enough to come up with algorithms that do so, but then you end up doing things that are normally done by search and MoveGen, which is looking at subsequent possible moves. So I have thought about incorporating piece square values determined at intermediate (non-leaf) nodes into evaluation as a way of dealing with mobility/square control, but I haven't tried anything. Intuition tells me I might be asking for trouble with that kind of thing. I also suppose that if one is directly evaluating mobility and square control at a leaf node, than that work might ne saved for re-use in some kind of a hash table or some such thing.

Crafty's been doing something like this for quite a while. Our mobility calculation is not simply a "total reachable squares" for a piece. We take the squares the piece can reach, and add in a value for a specific square. For example, a knight that can reach e4 gets a better score than if it can reach a1, because a1 is an unimportant square in general.

There are ways to do this that are not very expensive, although they are a little complex.

OK, the bolded remark seems to validate what I am saying. It is in fact desireable to deal with mobility & square control directly within eval, but to do so inexpensively (efficiently) is not at all easy.

So does the complexity arise from finding an inexpensive way to place a higher value on a reachable e4 than a reachable a1? Or is it in finding an inexpensive way to find total reachable moves. It seems that even this simpler 2nd idea can be expensive.

So do these inexpensive methods that Crafty uses involve re-using the information on reachable squares as part of the next edition of moveGen?

First, on the Cray, what we did was create a 64-word array where each word corresponds to a square. As we ran the eval, we added or subtracted values to this array so that when we were done with the first pass, we had an array that gave a general idea of which squares are important, which are not. For example, squares close to the opponent's king are important, squares around a passed pawn are important, etc. Then we computed the mobility as a bit-vector of 1's and 0's, 1's for each square a particular piece could reach. There was a neat "vector merge" instruction that would take that mask, and extract just those values from the 64-word vector, giving us a vector of length N where N was the number of 1 bits set, and the vector just contained the values for the squares that were set to 1 in the mask. We could sum these in a recursive vector reduction method to end up with one value.

For Crafty, since there is no "vector merge" approach, what I do is create a set of bitmasks for "equal-valued squares". Say, for a knight, you think e4/e5 and d4/d5 are the most valuable squares to attack and that they are equal. You create a bitmask with those 4 bits set, and a value to assign for each one you attack. Then say you think the ring around those 4 (c3, c4, c5, c6, d6, e6, etc) are the next most valuable. You create a bitmask with 1's on those squares, and a value. We end up with this:

BITBOARD knight_mobility[4], knight_mobility_value[4].

knight_mobility[0] has a set of 1 bits that match with the score in knight_mobility_value[0], etc.

I then just produce the bits a knight attacks, and in a loop from 0 to 3 I AND the attacks with the knight_mobility value, use PopCnt() on that result, and then add to the score the PopCnt(x) * knight_mobility_value. If you use the "ring" approach, there are only 4, so the loop executes 4 times for each knight, which is much less expensive than doing one loop iteration for each square the knight can reach. Bishops, rooks and queens are even more efficient since they attack many more squares. You simply decide how many different "square scores" you want, and then create an array of scores for those squares, and an array of masks for each group of squares, and away you go. We've been doing this in Crafty for quite a while. You can then do some tricks (as we do) by having a local cache for mobility scores so that, say, if the rank or file a rook stands on does not change, then the mobility will be the same and you can avoid the above loop completely. Most evaluations are done on positions where just one or two pieces or pawns have been moved, thanks to depth-first search, so that as we fan across the tips, little changes from one eval to the next.

Complex, as I said, but it slowed us down by zero the way it is currently done. That is, our NPS did not change at all.

[mcostalba]

First, on the Cray, what we did was create a 64-word array where each word corresponds to a square. As we ran the eval, we added or subtracted values to this array so that when we were done with the first pass, we had an array that gave a general idea of which squares are important, which are not. For example, squares close to the opponent's king are important, squares around a passed pawn are important, etc. Then we computed the mobility as a bit-vector of 1's and 0's, 1's for each square a particular piece could reach. There was a neat "vector merge" instruction that would take that mask, and extract just those values from the 64-word vector, giving us a vector of length N where N was the number of 1 bits set, and the vector just contained the values for the squares that were set to 1 in the mask. We could sum these in a recursive vector reduction method to end up with one value.

This weighted mobiliy counting is very interesting, although it seems very heavy to calculate if you don't have a specific hardware instruction as in the case of Cray.

I then just produce the bits a knight attacks, and in a loop from 0 to 3 I AND the attacks with the knight_mobility value, use PopCnt() on that result, and then add to the score the PopCnt(x) *

Instead this seems very slow Just counting the bits is already one of the slowest things we do in evaluation and evaluation is the slowest part of SF, so multiplying by 4 the computational load of an already heavy part seems too much.

You can then do some tricks (as we do) by having a local cache for mobility scores so that, say, if the rank or file a rook stands on does not change, then the mobility will be the same

Why ? perhaps some other piece occupied/left the same rank /file so mobility is affected also if the rook didn't change the file.

[bob]

First, on the Cray, what we did was create a 64-word array where each word corresponds to a square. As we ran the eval, we added or subtracted values to this array so that when we were done with the first pass, we had an array that gave a general idea of which squares are important, which are not. For example, squares close to the opponent's king are important, squares around a passed pawn are important, etc. Then we computed the mobility as a bit-vector of 1's and 0's, 1's for each square a particular piece could reach. There was a neat "vector merge" instruction that would take that mask, and extract just those values from the 64-word vector, giving us a vector of length N where N was the number of 1 bits set, and the vector just contained the values for the squares that were set to 1 in the mask. We could sum these in a recursive vector reduction method to end up with one value.

This weighted mobiliy counting is very interesting, although it seems very heavy to calculate if you don't have a specific hardware instruction as in the case of Cray.

I then just produce the bits a knight attacks, and in a loop from 0 to 3 I AND the attacks with the knight_mobility value, use PopCnt() on that result, and then add to the score the PopCnt(x) *

Instead this seems very slow Just counting the bits is already one of the slowest things we do in evaluation and evaluation is the slowest part of SF, so multiplying by 4 the computational load of an already heavy part seems too much.

You only have to count the bits every 100 calls or so due to the cache trick I mentioned. Also, as of Core I7 and beyond, we have a hardware popcnt instruction that is _very_ fast. As I mentioned, when we added this to Crafty it did _not_ slow us down one nps, because of the mobility cache we use.

You can then do some tricks (as we do) by having a local cache for mobility scores so that, say, if the rank or file a rook stands on does not change, then the mobility will be the same

Why ? perhaps some other piece occupied/left the same rank /file so mobility is affected also if the rook didn't change the file.

You didn't read what I wrote. If the rank/file the rook sits on does _not_ change, neither does the rooks mobility. All we care about is the status of the occupied squares on the specific rank and file, and so long as that is constant, so is mobility.

[mcostalba]

You didn't read what I wrote. If the rank/file the rook sits on does _not_ change, neither does the rooks mobility. All we care about is the status of the occupied squares on the specific rank and file, and so long as that is constant, so is mobility.

Ok. I understood the _rook_ does not change the rank/file, sorry

[Tord Romstad]

You only have to count the bits every 100 calls or so due to the cache trick I mentioned. Also, as of Core I7 and beyond, we have a hardware popcnt instruction that is _very_ fast.

Perhaps, but on the Core i7 and beyond everything is very fast, and any decent program like Crafty or Stockfish is virtually unbeatable no matter what you do. The important thing these days is how you perform on very low-end hardware, and there bitcounting is unfortunately still very slow.

[bob]

You only have to count the bits every 100 calls or so due to the cache trick I mentioned. Also, as of Core I7 and beyond, we have a hardware popcnt instruction that is _very_ fast.

Perhaps, but on the Core i7 and beyond everything is very fast, and any decent program like Crafty or Stockfish is virtually unbeatable no matter what you do. The important thing these days is how you perform on very low-end hardware, and there bitcounting is unfortunately still very slow.

While I don't run on iphones and such, I do test on 32 bit boxes, and the mobility stuff we do doesn't hurt there either. By design, of course. The primary trick is to not do any more bit-counting that is essential. We seem to be pulling that off based on speed.

[Uri Blass]

You only have to count the bits every 100 calls or so due to the cache trick I mentioned. Also, as of Core I7 and beyond, we have a hardware popcnt instruction that is _very_ fast.

Perhaps, but on the Core i7 and beyond everything is very fast, and any decent program like Crafty or Stockfish is virtually unbeatable no matter what you do. The important thing these days is how you perform on very low-end hardware, and there bitcounting is unfortunately still very slow.

I disagree here.
Crafty and Stockfish may be virtually unbeatable by humans but not by other chess programs like rybka.

Uri