OpenChess

Hi all, I've had the idea of using an incremental update of the sides movelists rather than regenerating them from scratch after each makemove. Has this idea been explored, and if so are there references to it, or was it discarded? Either way I'd like to hear other's thoughts on the subject.

The concept is that at the beginning of the game a movelist for each side is generated and then incrementally updated from then on.
When a makemove is executed the movelists would need updating. Perhaps the updates could be delayed until 2 plies had been moved (rather than at every sing ply). The key components would be the piece that moved, the fromSq and the destSq. The piece that moved because it requires a new set of moves generating; the fromSq because of potential unblocking of friendly pieces, and moves through the now vacated square(both sides); similarly for the destSq.

Thanks for any feedback on this (as far as I'm aware) novel approach.

Graham....

It has been tried many times in the past. But it does have a problem.

Complexity. When you move a single piece, you have to check for sliders that pass through the vacated square since they now attack additional squares, and you have to check for sliders that pass through the destination square since that square is now blocked. That is a lot of checking, and it can easily turn out to be slower than just direct re-calculation, and the code will be a good bit larger, which is cache unfriendly.

Yes I had a feeling that when it comes down to raw speed this would loose out to incremental changes. It seems unnatural to waste knowledge gained earlier in a game, but there must be items that are worth "remembering"? One just has to be selective when it comes to rediscovering vs. storage cost + calc. deltas (etc.)

Are there items (knowledge) that are typically worth the trade-off? I know material is an item most engines increment/decrement rather than recalculate over and over.

Thanks,
Graham....
PS It has been 30 years since I last attempted a chess program, in Pascal with no bitboards, alpha-beta, and avoiding what is now called iterative deepening like the plague.

GrahamA wrote:Hi all, I've had the idea of using an incremental update of the sides movelists rather than regenerating them from scratch after each makemove. Has this idea been explored, and if so are there references to it, or was it discarded? Either way I'd like to hear other's thoughts on the subject.

I have been thinking about this for years, and even made some partial attempts at implementing it. Recently all surviving previous ideas 'came together' to a very promising design, the framework of which was discussed on TalkChess. Basically the idea is this:

* As ~85% of the tree nodes are Queiescence Search, only worry about captures
* Represent the move list as a bitmap, where every bit represents an (attacker, victim) pair
* The bits are assigned in MVV/LVA order, so that they can be searched in the order they are extracted
* You can return from the node as soon as you reach the futile victims
* Captures are added/deleted to the list by setting/clearing the corresponding bit
* A similarly formatted set of pseudo-captures (i.e. protection of your own pieces) will be kept as well

This would be done in combination with a data structure that keeps track of the distance of each occupied square to the nearest obstacle in every direction. This is easy to update on captures, as you only have to 'connect' the diametrically opposite obstacles by adding their distances to the evacuated square. And easy to restore, as the now-empty square will keep pointing to the items that were changed.

This data structure is then used to efficiently generate slider captures for a piece in its new location, or to elongate existing slider captures over the evacuated square: the slider captures to the evacuated square can be masked out of the captures set, and after determining the attacker its attack direction and subsequently the new victim in that direction can be determined, and the bit in the captures set corresponding to the new (pseudo-)capture can then be set.

As a side effect the incremental update of the (pseudo-)captures set allows cheap incremental update of the mobility: the number of moves each piece has can be kept in the piece list, and on elongating a slider move the extra distance can be added to the slider as well as to the total (after weighting). The move count of a moved or captured piece can then easily be subtracted from the total, and the number of moves in its new location would then be added.

As information on captures and pseudo-captures would be available on a per-to-square basis, it would be very easy to determine which captures are 'bad' (you could feed the set of attackers and protectors to a SEE function, or simply designate any H x protected L as 'dubious'), and postpone its search to a second iteration through the captures set.