Faster than Fancy magic: Hypercube Slider lookup [TEASER]

[dangi12012]

Bitboard methods compared

Hi

One year ago I did some tests with different bitboards. The postings are
lost but I will repost my results here, copying much of my old texts.

A lot of new methods for generating attack bitboards were discussed.
It was hard to catch up with all the new ideas. But I was very interested and today
I can proudly announce, that I implemented and tested different bitboard attack
generators.

This is the result:

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  |
+----------------------------+-----------------------+--------------+-----------+

All methods have the same output. Therefore I believe they searched the same
tree and there is no error in the implementation. The positions and output are:

All implementations are available if you request it.
Harald

This is a treasure trove! Thanks for pointing that out! I will add these to my comparison (with credit back to original inventor) and i will share it once its done! It will be interesting to see how these perform with modern compilers and modern processors.

Ah I just saw that the source is broken like Bitboard( const std::string &s ); what a shame
Do you still have the 15 year old sourcecode somehow?

[Harald]

Hi dangi12012

I found the remaining source of Elephant 1.07.
The comparison of bitboard attack algorithms was made with version 1.06 or 1.07.
The different bitboard attack generator sources still exist.
For a quick start look at the defines in bb_ifdef.h and bb_board.cpp.

I do not know if this source compiles and if the chess engine runs
or if a special test is called or whatever. I am too lazy to clean up the mess.
The state in which I left the old engine is unknown even to me.

Do you know a place where I can put this old source?
I have no own web page and I am not used to Github.
It would probably be best to put it in some archive somewhere.
Since I am writing at Elephant 2.0 every few months or years for a few days
the old engine is no longer important.

Now I have a zip file of the engine source but need real e-mail addresses
to send it as an attachment. My own e-mail is harald.luessen@gmx.de
to establish a contact.

[dangi12012]

Hi dangi12012

I found the remaining source of Elephant 1.07.
The comparison of bitboard attack algorithms was made with version 1.06 or 1.07.
The different bitboard attack generator sources still exist.
For a quick start look at the defines in bb_ifdef.h and bb_board.cpp.

I do not know if this source compiles and if the chess engine runs
or if a special test is called or whatever. I am too lazy to clean up the mess.
The state in which I left the old engine is unknown even to me.

Do you know a place where I can put this old source?
I have no own web page and I am not used to Github.
It would probably be best to put it in some archive somewhere.
Since I am writing at Elephant 2.0 every few months or years for a few days
the old engine is no longer important.

Now I have a zip file of the engine source but need real e-mail addresses
to send it as an attachment. My own e-mail is harald.luessen@gmx.de
to establish a contact.

Ah perfect I have recieved the sourcecode and updated the repo. I will be a visual studio 2022 project - and I have all the compiler errors fixed for now. Now the Linker errors need fixing.
The best part:
It will work soon and everything is here including the comparison code:


For the magic hashing I can see that you implemented an improvement that was discussed in 2006. Its really fun to look through that stuff!
http://www.open-aurec.com/wbforum/viewtopic.php?t=5997


Thanks and I will keep you posted.

[dangi12012]

linker errors fixed. Win32 build complete and running
To enable a 64 bit build I will uncomment the x86 assembly. (__asm does not exist in x64 mode)

Code: Select all

    __asm
    {
        mov eax, [DWORD PTR bb + 4]
        bsr eax, eax
        jne Upper
        mov eax, [DWORD PTR bb + 0]
        bsr eax, eax
        cmove eax, [zero_value]
        jmp Done
      Upper:
        add eax, 32
      Done:
    };

[dangi12012]

Last update today:
I fixed everything in the repo - could not get x64 build to work today. But Win32 build works fine!
Please take a look at it here: maybe you get x64 build to work too? Its just the linker thats complaining because #include xxx.cpp breaks the linker.
https://1drv.ms/u/s!AoDIyNlDG2QTg8c3m8x ... A?e=eScuK0


I also started incorporating the very good sampling of lookup algorithms into my hypercube repo:

Code: Select all

Megalookups/s:
Reference: 101.23MOps
KOGGE-STONE:    112.31MOps
MAGIC:  504.59MOps
PEXT:   855.02MOps
HYPER:  888.65MOps

Now I have so many algos that in sum they dont fit in L2 anymore. I will have to make a multi configuration project with #defines for every generator to not pollute cache and produce multiple executables. Thats great because with the linux perf tool i can measure if alu or cache is the limiting factor: Per Algorithm - and also what happens in a multithreaded scenario.
hyper normally is 1080MOps and pext is ~15% slower. Magic is the best algo from 2006 - so i have will get the current fancy-magic impl too but normally that was a tad slower than pext. We will see...
I am also happy that my very first espresso movegenerator seems to be almost as fast as kogge-stone.

I will keep this forum updated. hyper lookup looks very good so far

[hgm]

Ah I just saw that the source is broken like Bitboard( const std::string &s ); what a shame
Do you still have the 15 year old sourcecode somehow?

This looks like a consequence of the forum upgrade. The old forum software expanded the HTML character escapes on retrieving the messages, but the new software doesn't do that, because it already does it when storing the message. So messages stored before the upgrade, and retreived after it, never get expanded and show up corrupted.

I thought I installed a JavaScript program to fix this on the client side, however. Can you give me a link to the posting with the source code, so that I can test why that doesn't seemt to work?

[dangi12012]

Ah I just saw that the source is broken like Bitboard( const std::string &s ); what a shame
Do you still have the 15 year old sourcecode somehow?

This looks like a consequence of the forum upgrade. The old forum software expanded the HTML character escapes on retrieving the messages, but the new software doesn't do that, because it already does it when storing the message. So messages stored before the upgrade, and retreived after it, never get expanded and show up corrupted.

I thought I installed a JavaScript program to fix this on the client side, however. Can you give me a link to the posting with the source code, so that I can test why that doesn't seemt to work?

Its broken there: https://www.talkchess.com/forum3/viewto ... es#p140155

[dangi12012]

Update: Some new algos implemented in comparison.
I will generate the testing code that emulates different conditions like sparse full etc. Because that makes a difference in some algos.

Code: Select all

Megalookups/s:
Exploading:     121.65MOps
Reference:      138.42MOps
KoggeStone:     177.77MOps
BobMike:        358.22MOps
XorRookSub:     506.75MOps
FancyHash:      637.80MOps
Pext  :         926.28MOps
HyperLookup:    953.45MOps

[hgm]

Its broken there: https://www.talkchess.com/forum3/viewto ... es#p140155

That link is wrong: you use https, while TalkChess is on http. As a result the page cannot load anything that is http, which includes the scripts from my website that restore the code sections, or display FENs. If you would use the same URL as http the code would not have been corrupted.

[tcusr]

Its broken there: https://www.talkchess.com/forum3/viewto ... es#p140155

That link is wrong: you use https, while TalkChess is on http. As a result the page cannot load anything that is http, which includes the scripts from my website that restore the code sections, or display FENs. If you would use the same URL as http the code would not have been corrupted.

why not fix talkchess to use https?