TalkChess.com

The following should probably go under the header "quick and dirty kludges". (So just the sort of thing I like for micro-Max! )

The problem addressed is that calculating mobility in evaluation is quite expensive, while in search it is nearly available for free as a side effect of generating moves. Whenever you search a null move, you thus have available the mobility of both sides. This could be used to improve the evaluation in those nodes.

Unfortunately null moves are not done in QS, so you have this mobility term available only in ply-1 nodes, and their QS-daughters after null move. And in 1-ply nodes you don't really need an evaluation (you can't stand pat there), while even in the QS null-daughter you get it a bit late. (You can't stand pat before you have generated moves, but at least you can use the mobility-corrected eval for cutoff before searching them.)

But under the assumption that something is better than nothing, the daughters of the QS nodes could use the mobility eval term of their 1-ply or QS parents in their evaluation, rather than their (unavailable) own. This can be done by explicitly passing it with the Search call to QS, or, even simpler, by just adding it to the incrementally-updated material eval in the node where it was calculated. Having the entire QS tree using the same mobility term as its 1-ply root, is what I call 'static' mobility.

Now there are some things that obviously go awry in this scheme. Your, or your opponent's good mobility might depend on a piece that can be easily traded away, or is even hanging. It would be nice if the QS scores reflected that. But there is a poor-man's method to sort of incorporate that. In stead of updating the material eval as
You could add
where MST is a global 'mobility-square table' created in the 1-ply node when it calculated mobility in its move gen, storing the results per piece. So in fact you change the piece values with their mobilities, and make sure they take them along when they move in later moves. This makes 'semi-static' mobility, attached to the pieces rather than just the total evaluation. Of course you would have to restore the changes to the MST in UnMake().

In micro-Max, this scheme would be extra attractive, because QS after null move is forced to generate all moves before being allowed stand-pat anyway, because the null-move search is also used as check test (and cutoffs could make you miss a King capture, misjudging a mate as stalemate in the parent). So the semi-static mobility might not be 10% accurate, but is is almost completely free!

In an engine with a piece list the implementation of this would be even more straightforward:

At the last depth where you calculate true mobility (and its null-move daughter) you write the per-piece mobilities into an extra 'mobilityValue' field of the piece list, and in the entire sub-tree hanging from it this field would be added to the normal pieceValue field when you calculate the impact of captures on the score. The node that modifies the effective piece values this way would have to correct the incrementally updated material score for this change in effective piece values as well, before passing it on to the daughters.

Only because micro-Max does not have a piece list it becomes necessary to store the mobilityValue of the pieces in a board-like data structure, and move it around with the piece.

The only tricky thing is the null-move call: there you have to delegate incorporation of the opponent mobility into the incremental material score to the daughter node, as opponent mobility will only become known there. So it has to be added dependent on the condition that the node was reached through a null move.

Apart from this implementation detail, the prescription is quite transparent:
1) A move to a QS node will have to use the 'mobility-corrected' piece value for updating material score.
2) if that same move was made from a non-QS node, you will also have to correct the material score passed to it for total mobility balance of the current node.
(This assumes QS is the only depth where you do not null-move.)

hgm wrote:In an engine with a piece list the implementation of this would be even more straightforward:

At the last depth where you calculate true mobility (and its null-move daughter) you write the per-piece mobilities into an extra 'mobilityValue' field of the piece list, and in the entire sub-tree hanging from it this field would be added to the normal pieceValue field when you calculate the impact of captures on the score. The node that modifies the effective piece values this way would have to correct the incrementally updated material score for this change in effective piece values as well, before passing it on to the daughters.

Only because micro-Max does not have a piece list it becomes necessary to store the mobilityValue of the pieces in a board-like data structure, and move it around with the piece.

The only tricky thing is the null-move call: there you have to delegate incorporation of the opponent mobility into the incremental material score to the daughter node, as opponent mobility will only become known there. So it has to be added dependent on the condition that the node was reached through a null move.

Apart from this implementation detail, the prescription is quite transparent:
1) A move to a QS node will have to use the 'mobility-corrected' piece value for updating material score.
2) if that same move was made from a non-QS node, you will also have to correct the material score passed to it for total mobility balance of the current node.
(This assumes QS is the only depth where you do not null-move.)

You can also build mobility into the piece square tables by pre-processing them. You ignore pieces and just consider mobility with respect to pawns. Of course when a pawn moves or is captured everything changes, but if you are exploring alternatives to fully dynamic mobility this is one possibility.

Another possibility is to expand the pawn structure hash table to include piece square tables. When you encounter a new pawn structure you have an expensive routine that recreates them - including the "mobility with respect to pawns" built in. You could take the opportunity to not just calculate pawn structure but to put pieces where they belong with respect to the pawn structure. I'm not making any claims about how well this would work but it's something that might lead to a very fast program. If you don't hash kings into the pawn structure the hit rate is extremely high.

Don

Don wrote: Another possibility is to expand the pawn structure hash table to include piece square tables. When you encounter a new pawn structure you have an expensive routine that recreates them - including the "mobility with respect to pawns" built in. You could take the opportunity to not just calculate pawn structure but to put pieces where they belong with respect to the pawn structure. I'm not making any claims about how well this would work but it's something that might lead to a very fast program. If you don't hash kings into the pawn structure the hit rate is extremely high.

I do this in Jazz (more or less, I derive a key from the pawn hash key for each piece type, but it may include other terms, for instance the rank the (enemy) king is on for rooks). It works ok, but it's not particularly fast (but it is much faster than just recalculating the tables every time). I have some ideas for how to make it a bit faster but I haven't had time to sit down and try it out.

I've considered taking it out, or at least trying something else, when I thought that my evaluation was unduly slow. I haven't because doing so takes away something of the "uniqueness" in Jazz.

Evert wrote:

Don wrote: Another possibility is to expand the pawn structure hash table to include piece square tables. When you encounter a new pawn structure you have an expensive routine that recreates them - including the "mobility with respect to pawns" built in. You could take the opportunity to not just calculate pawn structure but to put pieces where they belong with respect to the pawn structure. I'm not making any claims about how well this would work but it's something that might lead to a very fast program. If you don't hash kings into the pawn structure the hit rate is extremely high.

I do this in Jazz (more or less, I derive a key from the pawn hash key for each piece type, but it may include other terms, for instance the rank the (enemy) king is on for rooks). It works ok, but it's not particularly fast (but it is much faster than just recalculating the tables every time). I have some ideas for how to make it a bit faster but I haven't had time to sit down and try it out.

I've considered taking it out, or at least trying something else, when I thought that my evaluation was unduly slow. I haven't because doing so takes away something of the "uniqueness" in Jazz.

One advantage of this system is that you can try for very sophisticated evaluation and anything you add is almost free. But there are limitations since you cannot do everything with respect to pawn structure.