What is the best way to create AttackTable in mailbox or 0x88 board representation.

[dangi12012]

The way I did it in 'the mailbox trials' caused a significant speedup in a virtually evaluationless test. Because it eliminated the need for making a move list, and sorting it. The captures could be directly extracted from the attack table, in the desired order.

How was Diep's attack map organized? I used an array indexed by victim, which would flag all attackers in a way so they would extract in LVA order.

Whats the speed of mailbox trials with enpassant etc. in terms of moves/s for kiwipete? I found out that many algorithms look promising but are completely destroyed when pinned pieces and enpassant/promotion are implemented too.

[hgm]

I think I actually did test it on KiwiPete. On my laptop I think it was something like 10Mnps. This was with futility pruning, though, which of course prunes away almost all 'zero-work' nodes. I did not implement e.p. capture or castling, as these would not significantly affect speed: they can only happen in full-width nodes, of which there occur only very few in the tree. (E.p. capture can only occur after a double push, which is a non-capture.)

[dangi12012]

I think I actually did test it on KiwiPete. On my laptop I think it was something like 10Mnps. This was with futility pruning, though, which of course prunes away almost all 'zero-work' nodes. I did not implement e.p. capture or castling, as these would not significantly affect speed: they can only happen in full-width nodes, of which there occur only very few in the tree. (E.p. capture can only occur after a double push, which is a non-capture.)

With no pruning and no movelist would be good to compare. Maybe someone should start an always running competition like tcec for movegenerators only - to always have the fastest algorithm known in terms of moves/s

Random FEN + Depth => how many ms taken = score

[hgm]

Since real engines would always prune, it is more relevant to compare with pruning. Besides, futility pruning is not really pruning, but just efficient implementation of stand-pat cutoff, in combination with lazy evaluation. Counting nodes that are not actually visited would be misleading, while performing additional effort to visit nodes just to count them would be unrealistic. Since futility pruning is often bulk pruning, in many cases you would not even know how many nodes you prune, because the moves are not generated yet.

So I used a search with futility pruning, not counting the pruned nodes as benchmark.

[dangi12012]

Since real engines would always prune, it is more relevant to compare with pruning. Besides, futility pruning is not really pruning, but just efficient implementation of stand-pat cutoff, in combination with lazy evaluation. Counting nodes that are not actually visited would be misleading, while performing additional effort to visit nodes just to count them would be unrealistic. Since futility pruning is often bulk pruning, in many cases you would not even know how many nodes you prune, because the moves are not generated yet.

So I used a search with futility pruning, not counting the pruned nodes as benchmark.

Why is it not seperated? The movegenerator enumerates - and the engine decides what move to expand?
It really seems like two different problem domains that are seperated.

One domain is enumerating all child moves of a position
The other is deciding which moves look promising enough to be enumerated

[diep]

The way I did it in 'the mailbox trials' caused a significant speedup in a virtually evaluationless test. Because it eliminated the need for making a move list, and sorting it. The captures could be directly extracted from the attack table, in the desired order.

How was Diep's attack map organized? I used an array indexed by victim, which would flag all attackers in a way so they would extract in LVA order.

Yes i can look this up HGM!

Scanning through pinned pieces diep did do already back end 90s by the way. As there is no difference there.
As we have a precalculated table that gives us next square and it automatically stops when it has to stop and automatically continues if we are at a piece that's potentially pinned so we scan further there anyway. Also improves our chessplay as in evaluation it doesn't like to do dangerous things there and put stuff behind a piece (which then would be pinned):

Hope my description in diep.h still is how it was back in 2012... ...

With bit 0 obviously as least significant:

bit 0..3 : number of attackers (0..15]
bit 4 : unused (at least in this description)
bit 5..14 : type of attacker and in older diep versions 5..7 was for xray (no longer needed as we scan through it anyway)
bit 15..30 : index attacker in piecelist - obviously the position in piecelist is a static position.

So bit 31 obviously also unused as i had standardized diep upon 'int' - which in x64 is not such a great idea anymore of course as int is slower if you use it to index something. Generates extra code and the L1i was already the weak point for Diep so every extra instruction was a big pain.

This easily loses 10% speed overal for Diep because it's outside the L1i at modern processors.

[hgm]

Why is it not seperated? The movegenerator enumerates - and the engine decides what move to expand?
It really seems like two different problem domains that are seperated.

One domain is enumerating all child moves of a position
The other is deciding which moves look promising enough to be enumerated

Because then you would also generate moves which you don't want to expand. Which is a waste of time. And you would have to decide that. Which wastes even more time.

[dangi12012]

Why is it not seperated? The movegenerator enumerates - and the engine decides what move to expand?
It really seems like two different problem domains that are seperated.

One domain is enumerating all child moves of a position
The other is deciding which moves look promising enough to be enumerated

Because then you would also generate moves which you don't want to expand. Which is a waste of time. And you would have to decide that. Which wastes even more time.

Well... how do mailslots decide which move to not expand without deciding? I dont want to highjack this thread maybe a different thread for that discussion. I am always interested in performance gains.

[hgm]

The 'mailbox trials' thread referred to in the beginning of this thread extensively discusses this.

But in short: the criterion for futility pruning (in QS and at d=1) is that the (piece-square) value of the piece that is captured will not raise the evaluation enough to have any hope that (possibly through changes in additional eval terms) the latter might exceed alpha. So you only have to extract the attacks on the pieces that are valuable enough to escape pruning from the attack map. E.g. if the current evaluation is 6 Pawns below alpha, capture of a Rook would be futile, and you would only extract the captures on the King, (which would cause a beta cutoff without search if one existed, so you don't really extract them, but just bulk-test for their absence), and then those on Queen (searching each of those), and when you haven't experienced a beta cutoff then, you are done and return a fail low. Captures of Rook and lower, or non-captures will never be generated in such a situation.

[diep]

The 'mailbox trials' thread referred to in the beginning of this thread extensively discusses this.

But in short: the criterion for futility pruning (in QS and at d=1) is that the (piece-square) value of the piece that is captured will not raise the evaluation enough to have any hope that (possibly through changes in additional eval terms) the latter might exceed alpha. So you only have to extract the attacks on the pieces that are valuable enough to escape pruning from the attack map. E.g. if the current evaluation is 6 Pawns below alpha, capture of a Rook would be futile, and you would only extract the captures on the King, (which would cause a beta cutoff without search if one existed, so you don't really extract them, but just bulk-test for their absence), and then those on Queen (searching each of those), and when you haven't experienced a beta cutoff then, you are done and return a fail low. Captures of Rook and lower, or non-captures will never be generated in such a situation.

Yeah well that is all assuming a very simple evaluation function.
Much better is to do the capture, carry it out, and have the next position do a full evaluation and return the value above beta there if that's the case.
There could be a king safety issue in place, or a apassed pawn that you captured, or a piece hung in the corner that suddenly no more is hung.
Better capture those pieces and see what evaluation is after it than to use futility pruning there.

If this simple method (futility pruning) works well for you - no hope to beat the ANN engines of course - you need to show up with a bit more sophisticated evaluation function to beat them.