Incremental update

[ZirconiumX]

Having debugged my program enough to get a correct perft result for most positions, I now face an issue: speed, or lack thereof.

Obviously, copy-make probably isn't an ideal implementation, but a profile shows my program is spending 60% of its time recalculating the attack tables, which probably doesn't help much either.

I've trawled through the CPW , but haven't found anything related to safe incremental update situations, I.e. times in which you can be sure that you're not moving a pinned piece.

Maybe I'm missing something obvious.

Matthew:out

[hgm]

Well, attack tables are known do be quite expensive. I don't know what exactly you store in those tables, so it is hard to say if that could be updated incrementaly.

For me testing for pins comes as a sort of free side effect from testing for being in check. You first test alignment of enemy sliders with your King. Most sliders will not be aligned, and that excludes them both as checkers and pinners. Occasionally they are aligned, and then you check if the ray was blocked or empty. If it is empty you have a check, if it was blocked by a single piece and that piece was yours, it is pinned, (so that moving it off the ray might put you in check), and if the single blocker was his, you are subject to a discovered-check threat (unhealthy, and probably worth an extension).

[ZirconiumX]

Well, attack tables are known do be quite expensive. I don't know what exactly you store in those tables, so it is hard to say if that could be updated incrementaly.

My attack tables are piece set based - for each square, I have a 32-bit int with each bit corresponding to a piece or pawn attacking that square. Check detection can be done in a single line of code.

For me testing for pins comes as a sort of free side effect from testing for being in check. You first test alignment of enemy sliders with your King.

So basically I just need to check that the piece isn't pinned?

I was just worried about situations where the attacks aren't so straightforward like this ad hoc position:

[D] 8/3k4/2n5/8/8/8/1K2Q3/8 b - -

Where after Ne5 or Ne7, the queen's attack squares will be incorrect. Perhaps I'd have to also update the squares for each square attacker in addition to the moving piece.

Most sliders will not be aligned, and that excludes them both as checkers and pinners. Occasionally they are aligned, and then you check if the ray was blocked or empty. If it is empty you have a check, if it was blocked by a single piece and that piece was yours, it is pinned, (so that moving it off the ray might put you in check), and if the single blocker was his, you are subject to a discovered-check threat (unhealthy, and probably worth an extension).

Matthew:out

[hgm]

Yes, absolutely. Possible moves can change for many reasons in Chess:

* mover starts from new location
* piece is captured
* slider is blocked by mover
* slider is discovered by mover
* slider is discovered by e.p. victim

So apart from removing the old moves of the moving piece and adding the new moves, you would have to remove the moves of the victim. This is often most conveniently done by maintaining a 'present' mask, with which you AND the attackers sets whenever you use them, as ANDing is pretty cheap, and it saves you updating all the squares where the captured piece could move to. I once used that technique even for removing the old moves of the mover, by assigning a new bit to it. There usually is no reason why white and black attackers need to be packed into the same memory word, so you would have plenty of unused bits even in a 32-bit attackers set. You can use those for re-assigning bits to moving pieces close to the leaves, and only change to actually resetting the bits of the old moves when (say) remaining depth > 8 (i.e. in 0% of the nodes).

But you still have to treat blocking/discovering of sliders. Mask away the non-slider bits from the attackers set of the from- (or to-)square, locate the sliders that remain (often none), determine their direction of attack, step along the ray downstream of the from- (or to-)square in this direction, and flip the attack bit for that slider in the attackers set of the thus-visited squares until you hit a board edge or occupied square.

I found this a bit expensive and hardly worth it for unoccupied squares. So the design I currently favor is to only keep the attackers sets for occupied squares. You then don't have to scan the entire ray to board edge or blocker, but can just jump to the end of it immediately to change the attackers set there. This brings you in trouble on moves to empty squares (i.e. non-captures), as you would not have an attackers set for the to-square in that case. So you have no idea which sliders attack it, or even what the nearest neighbor is in each of the 8 directions from there. So you would have to generate that info from scratch, by scanning in 4 directions to the nearest obstacle, and using the nearest-neighbor info in the opposite direction from that occupied square to locate the antipode. But that is still competitive, because non-captures are rare in the tree, while for captures you would not have this problem. While updating all the attackes set for empty squares on every move, just because something might land on them, is pretty expensive.

[brtzsnr]

Don't worry about move generation speed for now. Instead concentrate on adding a IsValid(move) function. Once you add transposition table and reuse the hash move the move generation will become much less of an issue.

For incremental move generation I do: first attacks (with bitboards it's easy), then quiet moves. In majority of cases I don't have to generate the later.

[ZirconiumX]

Don't worry about move generation speed for now. Instead concentrate on adding a IsValid(move) function. Once you add transposition table and reuse the hash move the move generation will become much less of an issue.

This IsValid() function would probably be making the move then checking for opponent king in check, which I already do.

For incremental move generation I do: first attacks (with bitboards it's easy), then quiet moves. In majority of cases I don't have to generate the later.

Yeah, I can understand that.

Matthew:out

[hgm]

For incremental move generation I do: first attacks (with bitboards it's easy), then quiet moves. In majority of cases I don't have to generate the later.

I get the impression that there is some confusion on what is meant by 'incremental', in this thread. It seems to me that you are talking about what is generally called 'staged move generation', not generating all moves at once, but move class by move class, so that in case of a cutoff you save time by not having to generate for the later classes.

But before we were discussing 'incremental' in the sense of deriving an attack map in one node from the attack map from the parent node.

Note that when you want to keep an attack map, even just doing the hash move is not particularly cheap, because you still have to update the attack map, which involves generating moves not only of the moved piece, but also of the pieces it blocks or discovers. (Or of all pieces if you don't do it incrementally, but from scratch.)

[jdart]

I think incremental update of attack information is a loser, speed wise.

Programs spend most of their time near the leaves of the search tree. A lot of times when you make a move, it is immediately cut off, for example because the static eval in the qsearch is too high. So you don't even get to use the attack information, or most of it. I only generate attacks as needed.

The only thing I do incrementally is to update the hash signature, bitboards, and a material balance structure, which is used heavily in the eval. Undo reverses all these changes.

Another speed enhancement I have is to make pruning decisions before calling doMove. This requires computing "in check" status before a move is made, using the move information and board state. Most of the time this is fast but some complex and rare cases like castling have to be handled by just computing attacks. Even though do/undo move is fast for me I think it is a win to skip it when you are just going to prune anyway.

--Jon

[hgm]

Programs spend most of their time near the leaves of the search tree. A lot of times when you make a move, it is immediately cut off, for example because the static eval in the qsearch is too high. So you don't even get to use the attack information, or most of it. I only generate attacks as needed.

But that sounds just like a poor implementation. The trick is of course to only update the attack map when you are going to use it. Furthermore, the update can be split into a friendly and an enemy update (compared to the side that moved). To know if you have attacks that are worth following up in QS you only need the enemy update. Which is the cheapest one, as it does not include the altered moves of the mover, but just victim (which is taken care of by simply clearing a bit in the presence mask) and discovering of the enemy slidermoves (in typical positions much rarer than discovering of own pieces). And even the enemy update is only needed if the lazy evaluation did not cause a stand-pat cutoff.

My currently favored design doesn't really store the attackers info in board format, but in piece-list format, where each bit in a set represents an (attacker, victim) pair, sorted in MVV/LVA order, so that it can directly serve as (sorted)move list.

[bob]

Programs spend most of their time near the leaves of the search tree. A lot of times when you make a move, it is immediately cut off, for example because the static eval in the qsearch is too high. So you don't even get to use the attack information, or most of it. I only generate attacks as needed.

But that sounds just like a poor implementation. The trick is of course to only update the attack map when you are going to use it. Furthermore, the update can be split into a friendly and an enemy update (compared to the side that moved). To know if you have attacks that are worth following up in QS you only need the enemy update. Which is the cheapest one, as it does not include the altered moves of the mover, but just victim (which is taken care of by simply clearing a bit in the presence mask) and discovering of the enemy slidermoves (in typical positions much rarer than discovering of own pieces). And even the enemy update is only needed if the lazy evaluation did not cause a stand-pat cutoff.

My currently favored design doesn't really store the attackers info in board format, but in piece-list format, where each bit in a set represents an (attacker, victim) pair, sorted in MVV/LVA order, so that it can directly serve as (sorted)move list.

Where I found incremental update to be not so good was when I started encountering these very deep search depths. If you sum all the incremental update costs in a 30+ ply search it can easily exceed the cost of computing something when you actually need it. And if you wait until you actually need it, sometimes you don't actually need it due to alpha/beta... a procrastinators dream scenario, put it off hoping it never has to be done, and often it doesn't...

Note I am mainly talking about evaluation incremental update here, as opposed to move generation. I did incremental stuff, ala' Slate/Atkin when I first started. Rotated bit boards made it faster to compute as needed and eliminate the incremental attack stuff.