Incremental update

[Sven]

But even an "attackers-set engine" uses either of the two main board representations: mailbox or bitboards.

Well, not necessarily. There are other representations, like storing individual ranks, files and diagonals in memory cells. Very competitive for 16x16 boards, for instance.

My A, B, C, D list is about chess on 8x8 boards only. Classical bitboard techniques are mainly out of scope for other board sizes, so bringing those into the discussion does not help. For a general-purpose engine that is able to play many different variants I would certainly agree that non-bitboard engines are superior. However, there is also a lot of interest in competetive 8x8 chess, and I would consider it counter-productive to discuss about two very contrary goals at the same time: competetive 8x8 chess vs. other board sizes.

First thing is, your last remark sounds as if you would not see a difference between B and D, I hope I misunderstood that since board representations are still a big difference which I believe to be crucial for certain parts of the engine.

Well, if the board representation is hardly ever used for anything, it should not be very important what it is. I hope you agree with that. If captures and mobility are directly done from the attackers set, Pawn structure from the Pawn hash, material eval from a material table indexed by the material key... Well, not much use for any board, so far...

You seem to ignore the need to know which squares are occupied by which color and piece type in order to update *anything*, even for updating attackers-sets you need that information. So why that talk against board representation? You simply won't do without it.

Now my claim, and I think also Bob's, is that it is hard even for an optimized implementation of D to be superior to C, mostly due to the inherent redundancy of maintaining all existing attackers-sets where you can always retrieve the few relevant ones very cheaply with common bitboard technology.

As Bob pointed out, you are not nearly there, after that. After this retrieval you would have the moves, but you would not automatically have them in the correct order. So you would have to sort them in a different order. Which cannot be done with shifts and bitwise boolean operations. So you would have to extract them into a move list...

Why is the order so important? Each move gets a score for move ordering (MVV/LVA etc.), so the generation order is mostly irrelevant, except for identical scores. Generating moves in the "correct order" is not a hard requirement. In many cases (in a mature engine) move ordering is also done on a very different level: you start with the hash move provided it is a legal move, without even generating a single move, and only if you don't get a cutoff from it you generate captures, of which there are only relatively few ones so retrieving them one at a time based on their move score is still a cheap operation.

We should not forget that we would need clearly defined measurement rules. We could measure:
a) perft speed (same hardware, single-threaded, with bulk counting, no hash table);
b) NPS of a material+PST only tree search (same hardware, single-threaded, no hash table, no pruning etc.);
both for a variety of positions with given depths.

Well, perft is not a realistic measure of engine speed, as too much emphasis is on checking legality of the moves in the final ply, while engines usually do better with pseudo-legal moves. (b) is unrealistic because it leaves out mobility, which is one of the most expensive evaluation terms. So I would go for an engine with material + PST + mobility. Writing that based on incremental attackers sets (and whatever board representation is most convenient; I don't expect it to matter much) is on my to-do list.

But unfortunately that list is rather long...

Our experiences about superiority of generating pseudo-legal vs. legal moves differ, that's ok for me and also does not matter here. I would always vote for measuring both perft speed and engine search speed. Including mobility would be ok for me, obviously, since it favors the bitboard fans even more - see Bob's reply

[hgm]

My A, B, C, D list is about chess on 8x8 boards only. Classical bitboard techniques are mainly out of scope for other board sizes, so bringing those into the discussion does not help.

That other techniques are highly superior on larger boards of course does not mean they cannot be used on 8x8 boards, or even be faster there than conventional bitboards. (E.g. on 32-bit architectures, or architectures without multiply instruction.)

You seem to ignore the need to know which squares are occupied by which color and piece type in order to update *anything*, even for updating attackers-sets you need that information. So why that talk against board representation? You simply won't do without it.

Most of the time this information would be implied by the capture set, where every capture or pseudo-captures goes between occupied squares, the actual squares being obtained from the piece lists of the associated attacker/victim. At other times (elongation of discovered slider moves) the info would come from the view-distance table, which directly point you to the next occupied square. The only place that comes to mind where I would need to access board information would be for generating Knight (or other oblique leaper) moves from the new location of a moved Knight. (Orthogonal and diagonal movers would get this info from the view-distance table.) The information needed at that point is which piece (not piece type!) is standing on a possible target square. This suggests that mailbox would be highly superior, as with classical bitboards you would have to iterate through the boards to even figure out what the piece type is at a given location, let alone the actual piece. But Knight moves will hardly ever dominate the tree.

Why is the order so important? Each move gets a score for move ordering (MVV/LVA etc.), so the generation order is mostly irrelevant, except for identical scores. Generating moves in the "correct order" is not a hard requirement. In many cases (in a mature engine) move ordering is also done on a very different level: you start with the hash move provided it is a legal move, without even generating a single move, and only if you don't get a cutoff from it you generate captures, of which there are only relatively few ones so retrieving them one at a time based on their move score is still a cheap operation.

Extracting moves takes time. Assigning a sort key to them takes time. Sorting them takes time. Everything you mention takes time... OTOH, doing nothing doesn't take any time at all.

Including mobility would be ok for me, obviously, since it favors the bitboard fans even more - see Bob's reply

Sure. It wouldn't mean much if you couldn't even beat them on there home turf.

[zd3nik]

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.

I recently created an engine (https://github.com/zd3nik/Clunk) that uses an array based board representation and incrementally updated attack tables. And it's pretty fast: perft rate ranges from 30 million to 80 million leafs/sec. And average node rate in middle game play is around 1 - 1.2 million nodes/second. This is on an i5 laptop (single thread).

The attack tables allow it to generate captures quickly, so it's invaluable in quiescence search. So it's cost isn't too high for qsearch, it actually improves qsearch performance considerably. It also provides a relatively cheep way of calculating piece mobility and pin detection.

I specifically created this engine to see for myself whether all the claims about array based board representations with incrementally updated attack tables could be just as fast as bitboard engines (spurred on by another thread on this forum). And what I ended up with was much faster than I anticipated.

However, I then made a clone of Clunk (named Bumblebee) and replaced the array representations with bitboards and no inc updated attack tables and the bitboard version is faster by about 15-20%.

Anyway, my 2 cents is: stick with bitboards if your primary goal is speed. But you can make the inc updated attack table work and still be plenty fast so don't write the idea off entirely. At least a couple of the older top tier engines used it quite successfully AFAIK. And while Clunk ain't no top tier engine, it's plenty fast.

PS. sorry for jumping into this conversation in such an old spot.