Author: Vincent Diepeveen
Date: 13:38:44 07/29/03
Go up one level in this thread
On July 28, 2003 at 22:04:38, Keith Evans wrote: >On July 28, 2003 at 20:59:24, Vincent Diepeveen wrote: > >>On July 28, 2003 at 19:16:08, Keith Evans wrote: >> >>>On July 28, 2003 at 16:52:29, Vincent Diepeveen wrote: >>> >>>>On July 28, 2003 at 16:45:33, Keith Evans wrote: >>>> >>>>>On July 28, 2003 at 13:36:09, Vincent Diepeveen wrote: >>>>> >>>>>>Just compare the design of the move generator of Hsu with chrilly. It is a >>>>>>*massive* difference already. >>>>> >>>>>There are other statements that you made that I could discuss, but this one >>>>>caught my eye... >>>>> >>>>>What are you talking about? What's the difference? How do you know? You seem to >>>>>be implying that Chrilly did a better job than Hsu which I don't believe. >>>> >>>>Yes massive better. >>>> >>>>Hsu has written many articles. >>>> >>>>here is a summary of what Chrilly has said in way more words (voice) >>>>when he was staying here for a few days: >>>> >>>> Hsu was one of the first to make a move generator. He didn't write it in >>>> verilog but in the direct logics of the chip. Very incompatible method. >>>> Custom made by hand. It is incredible that he managed to write at such a >>>> low level anyway. However, a bad result from writing at such a low level is >>>> that the scale and size of the logics is so big that he must have >>>> lost oversight. I write in a more compatible language called Verilog and >>>> that is not comparable to C but way closer than the very 'assembly' way >>>> in which Hsu has written his logics at. It means in short that Brutus >>>> move generator therefore is very small. Note that i MUST make it small >>>> because i am commercial and more gates is more money to pay for. In the >>>> first chip i had just 50000 gates in total and that is very very little to >>>> get a chessprogram working in. >>>> From my viewpoint all the things i have seen so far is utmost beginners >>>> level. This is logical, They are hardware designers, not chessprogrammers. >>>> I focus upon the chess programming technical result. They had so much other >>>> problems to deal with from hardware viewpoint that we can not even compare >>>> it in that sense. >>>> >>>>Best regards, >>>>Vincent >>> >>>I only know of a few architectures that have been used for building hardware >>>move generators. >>> >>>1 - the Hitech style approach which is going to be very large. (Even with the >>>latest and largest FPGAs I don't think that you would get 64 Hitech chips into >>>one FPGA. It needs a ton of registers.) >>> >>>2 - the Belle style approach which returns moves in an MVV/LVA order and >>>potentially based on centrality - hardly random but not SEE. Despite what >>>Chrilly allegedly said, Hsu built an efficient move generator. You could fit a >>>lot of those on the latest chips at 0.18 micron or below - much more efficient >>>than anything going in an FPGA in terms of silicon area. It would also run quite >>>fast. Hsu suffered through doing a hand layout, but the result was a really >>>small move generator that would probably run insanely fast on today's >>>technology. >>> >>>3 - some obscure architectures which had basically random move ordering. (You >>>can find references in Ebeling's book.) >>> >>>Now from what you're saying I infer Chrilly came up with his own architecture. >>>Do you have any idea what makes it novel? From what you're saying he's not >>>planning on more than 2-3 plies of search in hardware so maybe he has a really >>>simple move generator that has basically random move ordering? >>> >>>-K >> >>ok here is facts >> a) DBII was more advanced than other tries like belle and some studentish >>tries. >> >>What you find efficient perhaps in commercial terms is still terrible >>inefficient. Some people are happy for example with bitboard move generator in >>software. Well at 32 bits architecture i'm 2.2 times faster generating moves >>than crafty. In fact around 73 million a second after 1.e4,e5 2.d4,d5 at a >>2.127Ghz K7. >> >>That's including general code (so my move generator is not written out for white >>and black, it is general code) and of course storage of moves and ordering >>scores to the RAM. >> >>That's how you must compare brutus and deep blue with each other. > ><snip> > >You never addressed my fundamental question which was in regards to hardware >move generation. I think that search is a separate topic. Yes there are certain >things that you would put in a move generator to support more efficient search, >but I'm talking about the core of the move generator here. Hsu and Chrilly had to deal of course with more complex reality. Move generation and a search are very closely related to each other. A fundamental problem of hardware is the inefficiency of the search. I will very clearly explain why. The average number of moves is 40 (when not in check). So if you search 4 ply in hardware then with a bad move ordering and no nullmove (deep blue didn't use nullmove) you search 40^4 = 2,560,000 nodes in alfabeta search. Then deep blue is doing a lot of checks in qsearch too and apart from that you have to try a lot of nonsense in qsearch anyway. In DIEP 80-85% of my nodes on average are in qsearch. In hardware that would be more like 90%. So this 2.5MLN is just 5% of the total number of nodes a 4 ply search eats worst case. this where a typical 4 ply search in software FULLWIDTH is for DIEP a couple of thousands of nodes. Sometimes you even get a transposition then it is 1 node :) Now the hardware guys do not have the luxury of a hashtable. But i hope you realize we are talking about a loss of a factor 1000 easily here. So that's why things cannot be modularized at all. In software you can. In hardware you can't because you cannot pick the best move out of the list each time. You can just have 1 value which tells you the previous moves which you searched in a clever way. That is a *very* inefficient way to generate moves. So you must add the move ordering to the move generation together. Add to this that Donninger has to deal with the nullmove which Hsu didn't use to prune. The most fundamental thing to have, this really is years 70 already, is killermoves. Deep Blue didn't use them. Not to mention a SEE. Even crafty is using that in its move ordering. Must i tell more about how fundamental it is to use it? In hardware your only option is to generate things in a certain fixed order. That's why move ordering and move generation are 1 and the same thing there. >The Deep Blue II move generator was more advanced than Belle, and maybe a little >bit more advanced than Marc Boule's move generator. Hsu likes to hint at a lot >of things, so maybe Marc's is just as advanced. (Also you have to ask the >question which is how many features of the Deep Blue chips were actually used >due to time constraints.) Now obviously when you look at the whole Deep Blue >chip there's a lot of stuff besides the move generator including eval and >search, but I'm not interested in that at the moment. > >What specifically is Chrilly doing in his move generator that makes you think >it's so advanced compared to Deep Blue and other Belle style move generators? > >Regarding 73 million moves generated a second on a 2 GHz K7 and this being twice >as fast as crafty. Where do you see these kinds of numbers? I don't see anything >anywhere close to this when running the perft test on a 3 GHz Xeon. (And I don't >think that there's _that_ big a difference between K7 and Xeon.) > >Regards, >Keith
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.