Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / "Rotated bitboards is a trivial algorithm"
1 2 Previous Next  
- - By Banned for Life (Gold) Date 2013-09-11 15:10
Don't be an idiot. Rotated bitboards is a trivial algorithm. Like every other algorithm, it needs to be coded. You NEVER showed any code demonstrating that Vas had copied your rotated bitboard code, which you lied about over a thousand times. Just like you never showed any of the "large chunks of code" you claimed Vas had copied from Fruit.
Parent - - By bob (Gold) Date 2013-09-11 16:14
If it is "so trivial" why did it take until 1995 to show up?  We had bitboard programs in the early 70's....
Parent - - By Banned for Life (Gold) Date 2013-09-11 17:52 Edited 2013-09-11 18:36
Most folks weren't working with Cray and didn't get 64-bit machines until 2005. Mr. Kannan's stuff came out shortly thereafter...

[Edited to provide a better answer provided by an anonymous source]
Parent - - By bob (Gold) Date 2013-09-11 23:08
There were plenty of 64 bit platforms.  Several computer chess participants used a 64 bit cpu at the 1997 WMCCC in Paris.  Myself included.  Rotated bit boards came about in 1995, my idea.  I don't really remember who started research on the "perfect hashing" topic in computer science, but Pradu applied that concept to develop his magic multiply / table lookup approach to generate moves.  Circa 2007.

please...

BTW MY question was "if rotated bitboards are so simple, why did it take until 1995 for someone to come up with the idea?"  Bitboards were used in the early 70's in chess, and in Samuel's checker program 10 years earlier...  It is not a "simple idea".  It takes some thought, as does magic generation...
Parent - - By Banned for Life (Gold) Date 2013-09-12 04:20
There were plenty of 64 bit platforms.

There were not plenty of 64-bit platforms in 1995. Even fewer in the early 70s. It's not surprising that there was less interest in bitboards from the majority of developers that did not have access to 64-bit platforms.

Several computer chess participants used a 64 bit cpu at the 1997 WMCCC in Paris.  Myself included.

Yes, you and four other participants in the field of 34 used DEC Alpha platforms. Most of the entrees didn't have access to this hardware. Of course Junior easily won the tournament on a Pentium II.

BTW MY question was "if rotated bitboards are so simple, why did it take until 1995 for someone to come up with the idea?"

And the multipart answer is:
1) Not many developers had access to 64-bit hardware, and
2) Bitboards weren't a top level priority for a lot of developers interested in the commercial marketplace (because PCs weren't using 64-bit processors).

How many of the top finishers (Junior, Mchess and Shredder) were using rotated bitboards at the 1997 WMCCC in Paris?
Parent - - By bob (Gold) Date 2013-09-12 18:19
You DO realize that bitboards work on 32 bit machines?  Crafty was run on a 32 bit machine for YEARS.  You DO realize that chess 4.x did NOT have a 64 bit machine?  They had a 60 bit CDC Cyber 176 that required TWO words to store the 64 bit bitboards.

For your last question, who can answer?  Commercial guys don't exactly advertise what they are doing, as the private/academic types do...

In any case, 64 bit hardware is NOT a prerequisite for bitboards.  They work quite well on 32 bit hardware as well.  At least they did for several of us...
Parent - - By Banned for Life (Gold) Date 2013-09-12 19:28
In any case, 64 bit hardware is NOT a prerequisite for bitboards.  They work quite well on 32 bit hardware as well.  At least they did for several of us...

Rybka is available in 64-bit and 32-bit builds. On CCRL 40/40, the 32-bit version of Rybka 4.1 running single core is 3036, while the 64-bit version of Rybka 4.1 comes in at 3099, a difference of 63 Elo. Only a moron would run this engine on 32-bit hardware.
Parent - - By bob (Gold) Date 2013-09-12 20:08
Only a moron doesn't understand the issue.  You ONLY have 32 bit hardware.  Do you use mailbox or bitboard?  I chose bitboard.  It was STILL faster than mailbox.  Yes, on 64 bits it goes even faster, where the mailbox guys gain zero.  But on 32 bit hardware it STILL works just fine.

Feel free to try again...  changing the subject as it suits you.  Bitboards work quite nicely on 32 bit hardware...
Parent - - By Banned for Life (Gold) Date 2013-09-12 20:42
Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts. During the era of 32-bit PCs, the strongest engines for PCs were all running mailbox. These included fritz, junior, shredder, and fruit. Rybka was the first dominant PC chess engine to use rotated bitboards and that was because it was always a 64-bit engine with a 32-bit recompile to support the unwashed. I've already given an example of the huge loss from using the 32-bit compile, and Vas has stated that there is no speed advantage for 32-bit bitboards, agreeing with the statement you made when you were younger and smarter.
Parent - - By Rebel (****) Date 2013-09-12 20:51
Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts.

Absolutely.
Parent - By bob (Gold) Date 2013-09-12 21:09
I'm willing to bite.

1.  It has been proven beyond any doubt that bitboard move generation is just as fast as mailbox on 32 bit processors for the general case of "generate all possible moves."

2.  It has also been proven beyond any doubt that bitboard move generation is faster than mailbox when you just want to generate capture moves only, which is what happens in something like 90% of the search nodes, which make up the q-search.

Let's call those just a "slight advantage for bit boards".

What about evaluation?  Do you really want to argue that bitboards are not better?  The recently discussed mobility is one example.  table lookup, popcnt, and you are done using bitboards.  4 loops using mailbox.  Bitboards have a cost on 32 bit processors.  But it is not excessive if the programmer is careful.  Much of the evaluation is done using ANDs to check masks.  Doing two 32 bit ANDS is actually a good thing, because those are independent operations that can keep multiple pipes busy when data dependencies make it harder to do so in a traditional mailbox program.

I would simply say "difference between bitboard and mailbox is at least a break-even, and in general the bitboards STILL have a small edge, using 32 bit hardware.  For 64 bit hardware, this "edge" becomes a canyon where it is a significant advantage."
Parent - - By bob (Gold) Date 2013-09-12 21:01
Being the strongest does NOT imply mailbox is better.  My statement was about "speed advantage".  Specifically addressed at move generation.  There are definitely speed advantages, even on 32 bit machines, in the evaluation.  For example, one AND operation can answer the question "is this pawn passed"?  Takes loops on mailbox.  There are lots of such places.  That bit board breaks even in move generation speed on 32 bit hardware is a testament to its strength.
Parent - - By Banned for Life (Gold) Date 2013-09-12 21:30
The transition from using mailbox to using bitboards requires a paradigm shift that didn't occur en masse until 64-bit machines were the norm. Nobody can be expected to jump to a new technology that requires a large investment and offers little improvement.

Going full circle back to the beginning of the conversation, there were only a small number of developers working with bitboards prior to 1995, so it is not surprising that you stumbled on this innovation. After all, even a blind squirrel finds an acorn once in awhile.
Parent - - By bob (Gold) Date 2013-09-12 22:18
Of course no programs prior to 1995.  No Kaissa.  No chess 4.x.  No Duchess.  No Lachex.  No Samuels checker program.  Shoot, most of the things I remember really didn't exist in your alternate universe...

One CAN be a visionary and see 64 bits coming.  One CAN be a visionary and see parallel computing coming to everyone.  Some bury their heads in the sand...  Or in your case, in a darker and stinkier location..
Parent - - By Banned for Life (Gold) Date 2013-09-12 22:49
You're really an idiot. In 1995 there were very few developers using bitboards. Kaissa was gone. Chess 4.x was long gone. Duchess was long gone. Lachex was gone. And these are the best examples you can give?

During the early years of the millenium, Fritz wasn't using bitboards. Neither was Junior. Neither was Hiarcs. Neither was Shredder. Neither was Fruit. People didn't start flocking to bitboards until 64-bit PCs became ubiquitous with the introduction of 64-bit x86 extensions, which weren't commonly available prior to 2004.
Parent - - By bob (Gold) Date 2013-09-12 23:57
I gave some FAMOUS programs.  There were SEVERAL of us using bitboards in the 1995 era.  Dark Thought.  Crafty.  Chess Guru (Joel Rivat).  I'd have to go back to look up names, but bitboard was "alive and well"  Just because YOU didn't know about it doesn't mean OTHERS did not.  Most of us realized that 32 bit words worked just fine for bitboards, the advantages were STILL there, just not as pronounced as on 64 bit hardware.  The Alpha was over 10 years old in 2004.  Many of us "recognized the future" and "started working toward it in the present."
Parent - - By Banned for Life (Gold) Date 2013-09-13 01:03
Chess Guru is a 64 bits intensive program and performs poorly on 32 bits computers.

From the description of chess guru on its 1997 tournament page


I've gone through the tournaments prior to 2004 when the AMD opterons with 64-bit extensions became readily available, and aside from people using very expensive DEC Alpha machines, there is no indication of any chess engines showing good results using bitboards on 32-bit hardware. My original statement was 100% correct. There was little interest in bitboards before 64-bit machines became mainstream, and those that were experimenting with them on mainstream 32-bit hardware were not successful in competitions. In fact, even the bitboard implementations running on expensive DEC Alpha 64-bit machines weren't all that impressive.

The future arrived in 2004, thanks to AMD, and with inexpensive, readily available 64-bit hardware, strong engines like Zappa and Rybka helped make bitboards popular. A few years later, many switched to using Mr. Kannan's technique and software.
Parent - - By bob (Gold) Date 2013-09-13 01:58
At the 1996 WMCCC event, Crafty, running on a 32 bit pentium pro box (Jakarta, Indonesia) and a crafty derivative (Gunda-1) finished in 4th and 5th places, running on 32 bit hardware.

You simply have no idea what you are talking about.

But then again, what's new about that???

The future had arrived LONG before 2004.
Parent - - By Banned for Life (Gold) Date 2013-09-13 02:49
In all of the tournaments prior to 2004 when 64-bit hardware became mainstream, the best you can dredge up on mainstream hardware is a fourth place finish in Jakarta behind three engines using mailbox, and you want to claim this shows superiority? What kind of clueless idiot are you anyway? You came in 18th in 2007, 12th in 2000, and 7th in 2001. But look on the bright side, you will never need to wonder again if one day there will be an event where 90% of the players are crafty versions...
Parent - - By bob (Gold) Date 2013-09-13 04:09
You REALLY don't have a clue about what is going on, eh?  Bitboard is a superior board representation.  It is better than mailbox on 32bit.  It is significantly better than mailbox on 64 bit.  That has NOTHING to do with the quality of chess the engine plays.  A REALLY GOOD bitboard implementation and a REALLY GOOD mailbox implementation will be about the same speed on 32 bit hardware, if you are just measuring Make/Unmake/MoveGen.  Bitboards pick up a small advantage in eval. 

what is wrong with you?
Parent - - By Banned for Life (Gold) Date 2013-09-13 05:44
It's too bad you can't accept the fact that 32-bit bitboard engines were not command and had a dismal tournament record. You're very good at lying, even to yourself...
Parent - - By Richard Vida (**) Date 2013-09-13 11:28

> the fact that 32-bit bitboard engines were not command and had a dismal tournament record


Nothing to do with using bitboards on 32 bit hw though. They didn't shine mostly because of weaker search.
Parent - - By bob (Gold) Date 2013-09-13 15:42
He has no clue.  Total waste of breath.
Parent - - By Banned for Life (Gold) Date 2013-09-14 06:07
You should get that baseball bat out and smack yourself in the face a few more times. It will improve your personality!
Parent - - By bob (Gold) Date 2013-09-14 06:22
Don't like the truth, eh?
Parent - - By Banned for Life (Gold) Date 2013-09-14 07:04
The truth? The truth is that you are a shameless liar who wrote the verdict for the ICGA's Rybka investigation claiming that Rybka's that competed in WCCC events had plagiarized Crafty, despite the fact that there was zero evidence then (and now) that that had occurred. The truth is that you are a shameless liar who got caught using Fruit's bishop PST table after excoriating Vas for using similar tables in his engine. The truth is that you claimed that there was "large chunks of copied code" in Rybka 1.0 Beta that have not been shown.
Parent - - By bob (Gold) Date 2013-09-14 17:27
No, the "truth" is that you formed a hypothesis that is provably false, namely that bitboard programs were not competitive on 32 bit hardware.  I gave you SEVERAL CCT results that directly prove your hypothesis false.  You want to claim that bitboard programs on 32 bit hardware were inferior to commercials that did not use bitboards.  Had NOTHING to do with bitboards.  Richard, who you seem to trust, pointed this out as well."  That is the "truth".  You have NO IDEA what you are rambling on and on about, but you do keep rambling anyway...
Parent - - By Banned for Life (Gold) Date 2013-09-14 17:59
No, the "truth" is that you formed a hypothesis that is provably false, namely that bitboard programs were not competitive on 32 bit hardware

You are an illiterate imbecile. My statement was: "Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts." The validity of this statement is NOT challenged in any way by the tournament records, where Crafty on massively superior hardware did well in a few tournaments.

Perhaps if you learned how to read, you wouldn't be such a moron...
Parent - - By bob (Gold) Date 2013-09-15 01:20
YOU kept using the non-competitive argument, moron...

Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts. During the era of 32-bit PCs, the strongest engines for PCs were all running mailbox.

YOU were using the non-competitive argument.  Not me.  It was false.  I gave events where a bitboard program on 32 bit hardware finished ahead of commercial mailbox programs.  Your argument was invalid, and still is...
Parent - - By Banned for Life (Gold) Date 2013-09-15 02:02
Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts. During the era of 32-bit PCs, the strongest engines for PCs were all running mailbox.

This is a true statement, backed up by the ratings lists of the times. Your ability to compete well in a few tournaments where you had much stronger hardware than the top engines, while doing poorly in many others despite this advantage, did not mean that Crafty was one of the strongest engines in the 32-bit PC era. It wasn't.

You are a delusional idiot.
Parent - - By bob (Gold) Date 2013-09-15 14:17
Ratings have NOTHING to do with whether bitboards are better or worse.  How many times do I (and others) have to point this out?

You are a delusional self-centered moron.
Parent - By Ugh (*****) Date 2013-09-15 14:38
If your skills in diplomacy, leadership, negotiation and discussion were translated to governmental level, your country would have been at war with someone, somewhere ever since World War 2. Oh, wait a minute ....
Parent - - By Venator (Silver) Date 2013-09-15 15:18
You are a delusional self-centered moron.

You are really getting into your role, aren't you?

http://www.youtube.com/watch?v=rR_RFcVHiks
Parent - By Nick (*****) Date 2013-09-15 16:00
"He cannot be more cleverer then me" -- genius :lol:
Parent - - By Banned for Life (Gold) Date 2013-09-15 16:50 Edited 2013-09-15 17:40
Ratings have NOTHING to do with whether bitboards are better or worse.

This line of reasoning is why Crafty is 500 Elo behind the leaders...
Parent - - By cipri (**) Date 2013-09-15 18:53
I dont know why you still repeat all the time yourself, with crafty being now weaker than other engines. I don't see exactly what your target is.

In analogy, I imagine a student going to an oral exam of higher mathematics, and saying "not intelligent stuff", and the professor, shows/proves that it's wrong what the student is saying. And the student is answering: yes, but you are bold.
Well, might be true, but that is not the point, nobody was saying it's not true.

I imagine, laughing about crafty, is as silly, as laughing about the theory of general relativity of einstein, just because, today, GRT is far more powerful and more elegant, and being mastered by many scientists.
Parent - By Banned for Life (Gold) Date 2013-09-15 19:56
In analogy, I imagine a student going to an oral exam of higher mathematics, and saying "not intelligent stuff", and the professor, shows/proves that it's wrong

Really? Bob is constantly telling us how much cleverer he is than the rest of us, and how original Crafty is, and how he's never taken any ideas from any other engines, and how he doesn't take detailed notes, and how he is the world's greatest programer and knows more about chess engines than anyone else, and especially that code copying thief Vas (the guy who stole his lawnmower and hid it under his porch). The only problem with these claims is that Bob's engine is not competitive. We have a saying here to describe this situation: "All hat, no cattle".

Years ago, when Vas frequented the forum and was one of its most prolific posters, we had much more informative discussions about chess engines, sometimes with other developers (e.g. Gian-Carlo Pascutto, Dr. Muller, Uri, etc.), and sometimes with experts in specific areas (e.g. Uly for persistent hash). Today, we have Bob's nonsense...
Parent - - By bob (Gold) Date 2013-09-16 01:03
Has NOTHING to do with who is ahead of whom, actually.  But I realize that is a bit beyond your ability to comprehend, as to why...
Parent - By Banned for Life (Gold) Date 2013-09-16 01:44
You are 500 Elo behind the leaders because the leaders understand the important elements of a chess engine much better than you do. It's as simple as that. Of course your massive ego won't accept this...
Parent - By Banned for Life (Gold) Date 2013-09-14 05:52
Nothing to do with using bitboards on 32 bit hw though. They didn't shine mostly because of weaker search.

This is true, but it's certainly possible that one of the reasons that these engines had a weaker search was because their developers spent too much time on implementing and experimenting with bitboards, and too little time working on improving their search. Vas claimed that he would have been even farther ahead of the pack with Rybka 1.0 beta if he hadn't spent so much time on bitboard tricks in the period from 2003 to 2005.

In any event, bitboards were not very common during the 32-bit era, nor were any of the engines that used them particularly competitive.
Parent - - By bob (Gold) Date 2013-09-13 15:45
Actually, you are just very good at being ignorant.  I won't waste any more time trying to educate you, just continue living in that self-induced fugue.  If you think an idea/concept is no good just because the program using it does poorly, you really do not understand software at all.  Big surprise...
Parent - By Banned for Life (Gold) Date 2013-09-14 06:04
I won't waste any more time trying to educate you

Don't worry, you aren't educating anybody, you stupid, ugly redneck. I feel really sorry for your students.

If you think an idea/concept is no good just because the program using it does poorly, you really do not understand software at all.

Your argument that good ideas are not correlated with stronger engines is just plain stupid and explains why Crafty on single core still hasn't caught up with Rybka 1.0 Beta.
Parent - - By marcelk (***) Date 2013-09-12 19:13
At that time (January 1997) there were 3 bitmap programs: Crafty, Spector and Dark Thought. Chess 4.x had retired by then but had used them as well. Others have tried but given up.

As bob put it at the time, the concept was at best break even on 32-bits systems with rotated boards, and a loss otherwise. Crafty was designed for the Cray architecture, we can read in even older posts. But PC's with 64 bits were going to change everything in favour of bitmaps. Those weren't available to the common man at that time yet of course.

The problem with them was that until the development of the "rotated bitmaps" there was a big efficiency penalty that made them costly to maintain, and this scared many away after they tried and didn't like the speed.

When I say bitmaps, by the way, I don't mean programs that might use a pawn bitmap to map the locations of pawns, or a program like Cray Blitz that had a "occupied squares" bitmap that was useful for detecting attacks...  I'm talking about a full bitmap implementation where moves are generated by using bitmaps exclusively.

It is a historic post, in which Bob goes on to explain that mobility is "ballyhoo" in a chess engine.
Parent - - By user923005 (****) Date 2013-09-12 19:52
It really took 64 bit operating systems to make the bitboards a big win.
When the CPU was in 32 bit mode, the native 64 bit instructions had to be from the MMX registers (if at all).
Now that we have 64 bit operating systems, bitboards are the big winners.

Chess Tiger, in its heyday, smoked the bitboard competition.  Same, of course, but with an exclamation point, for Fruit.
Parent - By Banned for Life (Gold) Date 2013-09-12 20:01
And shredder? When did that go to bitboards?
Parent - - By bob (Gold) Date 2013-09-12 20:15
doing 64 bit logical operations on 32 bit hardware is pretty much trivial.  In fact, we used 32 bit operating systems for years, with gcc's "long long" support, which let is use 64 bit values even though the hardware didn't directly support them.  Crafty was using this in late 1994 when it was first written, running on sun-3's which used the motorola 680x0 32 bit processors or on the Intel pentium (original, prior to pro).
Parent - - By user923005 (****) Date 2013-09-14 17:53
When 64 bit integers were manipulated via emulation rather than hardware, bitboards were not a clear win over 0x88 and other array techniques.  However, everybody knew, even at the time, that bitboards would be a big win on 64 bit hardware running in 64 bit mode.  And guess what:
http://www.computerchess.org.uk/ccrl/4040/rating_list_pure.html
http://www.husvankempen.de/nunn/40_40%20Rating%20List/40_40%20MPVersion/rangliste.html

Bitboard engines top the all the charts and it is not a coincidence.  When I first read the article on rotated bitboards (I did not have an ICGA membership, so it took a while for me to get ahold of the article) I remember that I thought it was brilliant.  I had previously written special unrolled rotation matrices for graphics systems and some rotations are very easy like 90, 180, 270 degrees.  But it never occurred to me to apply these rotations to a bitboard of chessmen.  Really good ideas often seem trivial after we have seen them.  How about this one by Einstein:

E = M*C^2

Or how about this one:

-1 = e^(pi * i)

Simple, yet beautiful.  And both formula sat around in the folds of reality without anyone seeing them for a very long time.

So my summary of rotated bitboards is:
A brilliant idea whose time came and were an invention of one Dr. Robert Hyatt.

Things are not wrong or bad or stupid just because they came from Bob.  If people make unreasonable arguments against Bob, why should they complain if Bob makes unreasonable arguments also?

So I think that arguments should be chosen wisely and I think that both sides should listen.  And when something is not wrong, we should admit it and say, "That's not wrong."

IMO-YMMV
Parent - - By Banned for Life (Gold) Date 2013-09-14 18:13 Edited 2013-09-14 18:22
The argument was over the statement: "Your assertion that bitboards are better than mailbox on 32-bit systems is not backed up by the facts." Bob has shown no evidence disputing the accuracy of this assertion.
Parent - - By user923005 (****) Date 2013-09-14 18:23
I don't think anyone really knows if they could have been better on 32 bit operating systems and 32 bit hardware.  On 32 bit operating systems, before the MMX 64 bit instructions, the strongest chess engines were array based.  But was it due to the underlying structures or to the better evaluation or due to better search?  Perhaps better programmers spending more time with bigger teams and more resources.  Who knows?

I also do not think that we have any accurate benchmarks on such systems that tested the individual components so that we know.

The advantage of bitboards is not just the speed on 64 bit hardware.  They are also built in piece lists, that have to be separately maintained on array based systems.  They are also handy for some evaluation terms.  So the idea of better or worse is very unclear to me.  And I don't think it matters very much.  We all know that bitboards are better than arrays today (unless some brilliant idea shows that concept to be wrong).
Parent - By Banned for Life (Gold) Date 2013-09-14 18:37
I don't think anyone really knows if they could have been better on 32 bit operating systems and 32 bit hardware.  On 32 bit operating systems, before the MMX 64 bit instructions, the strongest chess engines were array based.  But was it due to the underlying structures or to the better evaluation or due to better search?  Perhaps better programmers spending more time with bigger teams and more resources.  Who knows?

Mailbox was certainly helped by the fact that more resources were being expended on it than on bitboards. With equal resources, bitboards would have certainly have been more competitive. In many cases, the best technology can't overcome more mature inferior technology. Was the Otto engine really the best technology for automobiles?

The advantage of bitboards is not just the speed on 64 bit hardware.  They are also built in piece lists, that have to be separately maintained on array based systems.  They are also handy for some evaluation terms.  So the idea of better or worse is very unclear to me.  And I don't think it matters very much.  We all know that bitboards are better than arrays today (unless some brilliant idea shows that concept to be wrong).

I have no argument with any of this, but given the time and effort required to switch from mailbox to bitboards, and the lack of a decisive advantage on 32-bit machines, it was a reasonable decision for developers who wanted the strongest engines to concentrate on other areas. This changed when 64-bit computers became the norm.
Up Topic Rybka Support & Discussion / Rybka Discussion / "Rotated bitboards is a trivial algorithm"
1 2 Previous Next  

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill