Comparison of bitboard attack-getter variants

[tpetzke]

Hi Sven,

interesting comparison. I use magic bitboards in iCE, I used rotated ones before and even before that I had an 12x12 array.

I just want to add two things

(1) I don't think magic bitboards are more difficult than other techniques. Rotated bb are certainly but magic is not so tough.

(2) BitBoards shine in eval, so even if in the move generation something else would be faster I still would stick to the bitboards, as they help a lot in eval.

[Dann Corbit]

I guess that the lesson from this (assuming good implementations of each technique) is that it is utterly irrelevant which technique you choose.

[Henk]

Send it to Bayer (aspirins).

[hgm]

My main reservation towards magics is the large cache pressure it causes. This makes it look good in a sterile test environment like perft where the cache isn't used for anything else. But when you later start adding features to the engine that are also memory intensive, the combined cache pressure of magics and the new feature will slow the engine down so much that it offsets the benefits of the feature. So you will conclude that the feature isn't worth it, while in fact it could have been the magics that were not worth it.

Btw, I remember that Harald Luessen once did a similar test (on WB forum?), and that what came out best there was 'rotated indices', which you don't test now (and of which I also don't know exactly what it means).

[Sven]

My main reservation towards magics is the large cache pressure it causes. This makes it look good in a sterile test environment like perft where the cache isn't used for anything else. But when you later start adding features to the engine that are also memory intensive, the combined cache pressure of magics and the new feature will slow the engine down so much that it offsets the benefits of the feature. So you will conclude that the feature isn't worth it, while in fact it could have been the magics that were not worth it.

Btw, I remember that Harald Luessen once did a similar test (on WB forum?), and that what came out best there was 'rotated indices', which you don't test now (and of which I also don't know exactly what it means).

So according to you we are in severe trouble since many world-class engines use magic bitboards for attack generation although they better shouldn't ... Now what should they do? Use Kindergarten bitboards? Convert back to mailbox/0x88 or an attack-set based representation? What do you propose?

Regarding the "sterile test environment like perft", have you also read the other 50% of my post? It seems that tree search is not exactly "perft".

And if I would add static evaluation features then these would make use of the attack getters as well, to a certain degree, as in mobility, king safety (finding attacks to squares close to the king), and so on. Pawn structure evaluation will mostly be done via pawn hash. Which eval features are really memory intensive in your opinion?

[Karlo Bala]

My main reservation towards magics is the large cache pressure it causes. This makes it look good in a sterile test environment like perft where the cache isn't used for anything else. But when you later start adding features to the engine that are also memory intensive, the combined cache pressure of magics and the new feature will slow the engine down so much that it offsets the benefits of the feature. So you will conclude that the feature isn't worth it, while in fact it could have been the magics that were not worth it.

Btw, I remember that Harald Luessen once did a similar test (on WB forum?), and that what came out best there was 'rotated indices', which you don't test now (and of which I also don't know exactly what it means).

http://talkchess.com/forum/viewtopic.ph ... 11&t=16002

[hgm]

Indeed, that is the posting I remembered. It was on TalkChess after all. No wonder I could not find it on WB forum!.

[hgm]

So according to you we are in severe trouble since many world-class engines use magic bitboards for attack generation although they better shouldn't ... Now what should they do? Use Kindergarten bitboards? Convert back to mailbox/0x88 or an attack-set based representation? What do you propose?

Currently I consider the attack-set-based representation the most promising.

Regarding the "sterile test environment like perft", have you also read the other 50% of my post? It seems that tree search is not exactly "perft".

With only PST and no hash table I would not really call it memory-intensive... Of course it consumes time, which is why you see the impact of the attack getter go down in the search.

In an engine with very complex evaluation the attack getter might again become more important. The entire idea of bitboards is to make evaluation faster. For just PST + material a plain old 0x88 mailbox would probably be a lot faster than magic bitboards. But you did not try that. When Harald did the similar test I asked him about how his results compared to mailbox, but he told that could not be measured easily because of the inherently different logic in mailbox algorithms, which prevented them to be implemented as just plugging another module into the program.

Which eval features are really memory intensive in your opinion?

Table-driven SEE. Mate at a glance (and even worse, mate in 2 at a glance). Eval cache.

[hgm]

Perhaps it is helpful to also post Harald's results here:

Code: Select all

+----------------------------+-----------------------+--------------+-----------+
| Name                       | Inventor or Supporter | Table Size   | Test-Time |
+----------------------------+-----------------------+--------------+-----------+
| Rotated Bitboards (naive)  | Robert Hyatt          |   77.2 KByte |  87.78 s  |
| Rotated Bitboards (aligned)| ?                     |   35.0 KByte |  86.65 s  |
| Rotated Bitboards (switch) | (Harald Lüßen?)       |   14.9 KByte |  88.91 s  |
| Rotated Indices            | Alessandro Damiani    |  128.3 KByte |  78.93 s  |
| Exploding Bitboards        | Harald Lüßen          |    3.5 KByte | 101.79 s  |
| Magic Mult. (Kinderg.)     | Gerd Isenberg         |    9.7 KByte |  91.87 s  |
| Magic M. (Kinderg.) 32 bit | Gerd Isenberg         |    9.7 KByte |  81.37 s  |
| Sherwin Index              | Michael Sherwin       | 1402.4 KByte |  90.03 s  |
| Pradu Minimize Magic       | Pradyumna Kannan      |  844.0 KByte |  81.42 s  |
| Pradu Perfect Magic Hash   |  and                  |  627.4 KByte |  82.09 s  |
| Pradu Big                  | Lasse Hansen          | 2306.0 KByte |  82.33 s  |
| Kogge-Stone                | Steffan Westcott      |    0.0 KByte |  99.32 s  |
| Simple Shift               | --                    |    0.0 KByte | 110.25 s  |
| Naive Shift                | --                    |    0.0 KByte | 111.69 s  |
+----------------------------+-----------------------+--------------+-----------+

[ZirconiumX]

Sven, if you don't mind me asking, could you run a quick comparison of if the extra bit twiddling of this article is worth the unified implementation.

Gerd might find the article useful too, although whether it can be suitably vectorized is not in my field of expertise (I'm a musician...).

Matthew:out