Nice Math - Strange Conclusions

[Gerd Isenberg]

from the actual ICGA Journal March 2008

Move Generation with Perfect Hash Functions
by Trevor Fenner and Mark Levene

Issue is sliding piece attacks. The paper is quite interesting, stunning modulo math. The authors map masked and normalized (shifted to bit zero) files, diagonal or antidiagonal occupancies to vectors of eight (or nine) consecutive bits, quite similar as kindergarten bitboards does.

They use modulo 514 for the diagonals and modulo 257 for the anti-diagonals to get 8 (or even nine for the diagonals) bits as an index. That can be done most efficiently by reciprocal multiplication - this is how vc2005 implements the mod for x64 processors. One 64*64=128 bit mul, one shift and one further imul, sub. Of course using 64-bit div to get the remainder burns even more cycles.

Code: Select all

% 514
 mov	 r11d, r10 ; masked diagonal
 mov	 rax, ff00ff00ff00ff01H
 mul	 r10
 shr	 rdx, 9
 imul	edx, 514 ; 00000202H
 sub    r11d, edx

% 257
 mov	 r11d, r10 ; masked diagonal
 mov	 rax, ff00ff00ff00ff01H
 mul	 r10
 shr	 rdx, 8
 imul	edx, 257 ; 00000101H
 sub    r11d, edx

Kindergarten-Bitboards uses one 64*64=64-bit multiplication...

Code: Select all

 mov	 rax, 0101010101010101H
 imul	rdx, rax
 shr	 rdx, 56

... for the same purpose. Looks a bit cheaper.

Despite huge rook-tables most prefer magic-bitboards over kindergarten, since it covers both lines of a rook or bishop in one run with only one and, mul, shift->lookup.

My question is - how can they conclude they are competitive over magic-botboards - if they even can not beat kindergarten-bitboards by margins - not to mention table size and inner six bit only? To compare a Matlab 32-bit implementation with a loop-version to get the sliding attacks? Because Sam Tannous claimed small improvement over rotated with some high level hashing directories - and Bob Hyatt reported similar performance of rotated versus magic in crafty?

Strange conclusions, for Reference see Bob's post the authors mention in their paper:
http://64.68.157.89/forum/viewtopic.php ... 41&t=16002
Further references:
http://chessprogramming.wikispaces.com/ ... ctionaries
http://chessprogramming.wikispaces.com/Magic+Bitboards
http://chessprogramming.wikispaces.com/ ... +Bitboards

Did I miss something on superfast matlab modulo?

Cheers,
Gerd

[Gerd Isenberg]

Some quotes from the paper:

As reported in Hyatt (2007), the rotated and magic bitboard methods are of comparable performance, and Tannous (2007) claims just a small improvement of the direct lookup method over rotated bitboards. It is easy to see that, in terms of the number of computer operations, the efficiency of our method will be similar to that of direct lookup. Thus we are justified in claiming that the computational efficiency of our method is comparable to the others.

...

Our method improves on the state of the art by providing a general method for efficient bitboard move generation for sliding pieces (not restricted to chess) that: (i) avoids maintenance of auxiliary bitboards, as in the rotated bitboard method, (ii) does not depend on built-in system features, such as the associative arrays in the direct lookup method (and moreover these hash functions are not guaranteed to be perfect, so collisions may occur), and (iii) does not use a hash function generated by a non-trivial and possibly very long computation, such as the magic bitboard method, and which may not always be perfect for a given number of bits in the index (Kannan, 2007).

I am still stunned by this scientific academical paper. How can they ignore denser tables by inner six bit. How can they ignore perfect hashing by kindergarten bitboards which obviously faster and more compact computation? How can they ignore processing multiple lines by magic bitboards in one run? Arggg!

They claim to use perfect hashing, but map a remainder range of 0..513 or 0..256 to the 0..255 occupancy index - which implies an additional indirection for perfect byte-indices or - leaves some gaps in the attack lookups (negligible for the mod 257 case).

[hgm]

They can ignore that because it was never published in a scentific journal, and they are obvious 'ivory-tower' theorists not aware of what is going on in the field (and perhaps even in their computer). And the referees are probably of the same kind.

In science this happens all the time. People from one field think they have made a World-shocking discovery, that happens to be known for decades in another field they are not aware of, and publish it like they deserve a Nobel prize. And unfortunately the referees are picked from their own field, and are thus equally ignorant, and let it pass.

I encountered a good example of this a few years ago, where some mathematical physiscist, working on the theory of 'random media', made a lot of noise about their 'discovery' of an 'omnidirectional reflector', a mirror that would have near 100% reflection no matter from what direction you send the light on it. They published it in one of the two most high-level and prestigeous scientific journals (Science), and their invention was even discussed in an editorial comment. Then a month later, there was a letter from an engineer working in some obscure optics manufacturing plant, and it basically said: "Oh, that? Yes, we used to sell that some ten years ago. But there was not enough demand for it, so we now took it out of our catalog!".

Perhaps we should do something similar here: write a letter to the editorial board of the ICGA Journal to point out that Kindergarten bitboards are old hat.

[Gerd Isenberg]

They can ignore that because it was never published in a scentific journal, and they are obvious 'ivory-tower' theorists not aware of what is going on in the field (and perhaps even in their computer). And the referees are probably of the same kind.

In science this happens all the time. People from one field think they have made a World-shocking discovery, that happens to be known for decades in another field they are not aware of, and publish it like they deserve a Nobel prize. And unfortunately the referees are picked from their own field, and are thus equally ignorant, and let it pass.

I encountered a good example of this a few years ago, where some mathematical physiscist, working on the theory of 'random media', made a lot of noise about their 'discovery' of an 'omnidirectional reflector', a mirror that would have near 100% reflection no matter from what direction you send the light on it. They published it in one of the two most high-level and prestigeous scientific journals (Science), and their invention was even discussed in an editorial comment. Then a month later, there was a letter from an engineer working in some obscure optics manufacturing plant, and it basically said: "Oh, that? Yes, we used to sell that some ten years ago. But there was not enough demand for it, so we now took it out of our catalog!".

Hehehe...

Perhaps we should do something similar here: write a letter to the editorial board of the ICGA Journal to point out that Kindergarten bitboards are old hat.

Very good, I already sent an email to the editorial board...

[michiguel]

They can ignore that because it was never published in a scentific journal, and they are obvious 'ivory-tower' theorists not aware of what is going on in the field (and perhaps even in their computer). And the referees are probably of the same kind.

In science this happens all the time. People from one field think they have made a World-shocking discovery, that happens to be known for decades in another field they are not aware of, and publish it like they deserve a Nobel prize. And unfortunately the referees are picked from their own field, and are thus equally ignorant, and let it pass.

I encountered a good example of this a few years ago, where some mathematical physiscist, working on the theory of 'random media', made a lot of noise about their 'discovery' of an 'omnidirectional reflector', a mirror that would have near 100% reflection no matter from what direction you send the light on it. They published it in one of the two most high-level and prestigeous scientific journals (Science), and their invention was even discussed in an editorial comment. Then a month later, there was a letter from an engineer working in some obscure optics manufacturing plant, and it basically said: "Oh, that? Yes, we used to sell that some ten years ago. But there was not enough demand for it, so we now took it out of our catalog!".

Hehehe...

Perhaps we should do something similar here: write a letter to the editorial board of the ICGA Journal to point out that Kindergarten bitboards are old hat.

Very good, I already sent an email to the editorial board...

Gerd, what is not published, it does not exist, and there are good reasons for academics to behave that way. What is published passed a reviewing process, what is not didn't. What I really encourage you to do is to publish your work and include whoever contributed it significantly as a co-author. It should not be difficult after all the fantastic work you did.

Miguel

[Gerd Isenberg]

Gerd, what is not published, it does not exist, and there are good reasons for academics to behave that way. What is published passed a reviewing process, what is not didn't. What I really encourage you to do is to publish your work and include whoever contributed it significantly as a co-author. It should not be difficult after all the fantastic work you did.

Miguel

Thanks Miguel, for your kind words. I am more a reporter and supporter of other people's ideas such as Steffan Westcott, Pradu Kannan, Ryan Mack and others. Not to mention our rotated bitboard pioneer Bob Hyatt.

Back to the issue of the academical paper. The authors mentioned magic bitboards and Pradu's paper - so they should be aware how it works, to test their approach against it. Instead they reported some progress versus a loop-approach inside a 32-bit Matlab environment!

Is such an implication-chain - based on own assumption and quotes from one distinct source each with different implementations (C, interpreted Python hashmaps, Matlab32), without own proof - sufficient and typical for academical papers as well?

• 1) rotated and magic bitboard methods are of comparable performance
  2) small improvement of the direct lookup method over rotated bitboards
  3) It is easy to see that the efficiency of our method will be similar to that of direct lookup.

To justify in claiming that the computational efficiency of our method is comparable to the others? I guess "comparable" is intended as competitive

Gerd

[Pradu]

Thanks Miguel, for your kind words. I am more a reporter and supporter of other people's ideas such as Steffan Westcott, Pradu Kannan, Ryan Mack and others. Not to mention our rotated bitboard pioneer Bob Hyatt.

More like the initiator and expert of many bitboard ideas. Lasse Hansen came up with his idea from your postings on separated direction attacks correct?

Back to the issue of the academical paper. The authors mentioned magic bitboards and Pradu's paper - so they should be aware how it works, to test their approach against it. Instead they reported some progress versus a loop-approach inside a 32-bit Matlab environment!

I haven't read the paper (yet) but I also don't think MatLab is a representative environment to test speeds for different hashing schemes. A direct comparison to rotated and magic in C in chess programs (perhaps Crafty and other opensource bitboard ones) would be representative.

Is such an implication-chain - based on own assumption and quotes from one distinct source each with different implementations (C, interpreted Python hashmaps, Matlab32), without own proof - sufficient and typical for academical papers as well?

• 1) rotated and magic bitboard methods are of comparable performance
  2) small improvement of the direct lookup method over rotated bitboards
  3) It is easy to see that the efficiency of our method will be similar to that of direct lookup.

To justify in claiming that the computational efficiency of our method is comparable to the others? I guess "comparable" is intended as competitive

Gerd

[wgarvin]

They reported timings from MatLab? That sounds useless, very few chess engines are written in MatLab...

They should have written theirs in C and tested it against the real-world code in various open-source chess engines.

Also, I strongly suspect that this "if it isn't published, it doesn't exist" thing is nonsense. There are lots of papers out there that mention the ideas behind a practical working implementation written by someone else. There's no reason they couldn't have dug around a bit and found out what "state of the art" in this area was, and done their comparisons against that.

..except that then they might not have had anything "worth publishing"?

[michiguel]

They reported timings from MatLab? That sounds useless, very few chess engines are written in MatLab...

They should have written theirs in C and tested it against the real-world code in various open-source chess engines.

Also, I strongly suspect that this "if it isn't published, it doesn't exist" thing is nonsense....

That's how experimental science work. Unless comp. sci. have a completely different culture, you cannot claim anything if you did not publish it in a peer review journal. Anyway, I did not read the article and it seems to be that the problem goes beyond that.

... There are lots of papers out there that mention the ideas behind a practical working implementation written by someone else. There's no reason they couldn't have dug around a bit and found out what "state of the art" in this area was, and done their comparisons against that.

That creates a problem, because they will be talking about a procedure that is not publish, and they will have to describe it entirely. That would be like a paper inside a paper. They cannot cite it, because it is nowhere. Also, since it is not published, it has not been peer reviewed and how do you know that those techniques are state of the art?
Brief ideas or results can be commented as "personal communication" or "unpublished results", but the whole set of new techniques is not possible!
Documentation is a very important part of the academic process because it grows from previous information. It is like the legal system, you can start talking about someone is guilty once it has been convicted, not before.

..except that then they might not have had anything "worth publishing"?

That is a possible scenario.

Miguel

[bob]

They can ignore that because it was never published in a scentific journal, and they are obvious 'ivory-tower' theorists not aware of what is going on in the field (and perhaps even in their computer). And the referees are probably of the same kind.

In science this happens all the time. People from one field think they have made a World-shocking discovery, that happens to be known for decades in another field they are not aware of, and publish it like they deserve a Nobel prize. And unfortunately the referees are picked from their own field, and are thus equally ignorant, and let it pass.

I encountered a good example of this a few years ago, where some mathematical physiscist, working on the theory of 'random media', made a lot of noise about their 'discovery' of an 'omnidirectional reflector', a mirror that would have near 100% reflection no matter from what direction you send the light on it. They published it in one of the two most high-level and prestigeous scientific journals (Science), and their invention was even discussed in an editorial comment. Then a month later, there was a letter from an engineer working in some obscure optics manufacturing plant, and it basically said: "Oh, that? Yes, we used to sell that some ten years ago. But there was not enough demand for it, so we now took it out of our catalog!".

Hehehe...

Perhaps we should do something similar here: write a letter to the editorial board of the ICGA Journal to point out that Kindergarten bitboards are old hat.

Very good, I already sent an email to the editorial board...

Gerd, what is not published, it does not exist, and there are good reasons for academics to behave that way. What is published passed a reviewing process, what is not didn't. What I really encourage you to do is to publish your work and include whoever contributed it significantly as a co-author. It should not be difficult after all the fantastic work you did.

Miguel

I completely agree. It is easy for us to criticize, but I am not a member of every discussion board related to chess, but I am a member of the ICGA and read the journal as it comes out. If something is not published, how would one know it exists? Although I must add that I have had more than one NSF proposal get shot down for this very reason, because someone on the review panel knew of similar research that was not public, which makes it impossible to cite or use.

That's the only reason I wrote the rotated bitboard paper, and why I am also going to do a parallel search paper on how Crafty works, just so it becomes well-documented and nobody will have to reinvent the same wheel again.

The magic stuff ought to be documented in a journal article as well. I'd be more than willing to help if needed, but the two leaders of the development should really document it...