Author: Tom Likens
Date: 21:18:23 04/14/02
Go up one level in this thread
Some comments interspersed below and maybe a little food for thought :) On April 14, 2002 at 12:08:05, Vincent Diepeveen wrote: >On April 13, 2002 at 17:00:05, Amir Ban wrote: > >>On April 12, 2002 at 15:04:54, Tom Likens wrote: >>>I probably shouldn't comment, since this topic seems to have become >>>a religious debate, still... >>> >>>As an ASIC/Analog IC engineer I can guarantee you that hardware done >>>"right" will blow away software everytime. No offense to the chess software >>>programmers (of which I am one :), but custom hardware wins hands down. >>>Unlike the recent debates on FPGAs, an ASIC solution gets the full benefits of >>>the speed. When Hsu claimed Deep Blue was running at X-MHz, guess what, >>>it *was* running at X-MHz!! This debate about speed is crazy. Deep Blue >>>was done in 0.6u technology. That is ancient, modern ASICs are 0.13u copper >>>processes, with 0.1u just around the corner. Hsu could get a staggering jump >>>in speed by just doing a dumb shrink on his design- more than likely an order >>>of magnitude (and probably more). And if he improved the basic hardware >>>design, ... well who knows?! >>> >> >>Hardware is almost by definition faster than software, but is much less flexible >>and that practically makes it much less attractive. The design cycle is roughly >>6 months, and this means that a PC programmer can try in one evening what a >>dedicated-hardware designer can try in a year. > >agreed. > Granted software offers the ultimate in flexibility, but as always there are ways to work around the limitations of the hardware. For example, often in order to test a new design (especially microprocessors designs) many ASIC designers will create both a verilog model and a C model of the design. The verilog model contains all the timing checks needed while the C model is a cycle-for-cycle accurate simulator that ignores timing but tests full functionality. The verilog simulations are slow (especially the gate-level sims), but the C model runs orders of magnitude faster. New ideas could be tried using the C model simulator very late in the game. Using Synopsys or Ambit (boolean synthesis software) would allow changes to be rolled in even late in the course of the development. Of course, this *is* limited since you have to settle on a design eventually and as Amir pointed out the design cycle is probably at least six-months. In actually, this is probably optimistic since backend test is usuallly the critical path to getting a chip done and test takes a looooong time). Still if this was managed correctly it would allow changes to be made as the system's performance and bottlenecks were understood fine-tuned. Did Deep Blue use this type of technique, probably not but that doesn't mean that it couldn't be applied productively in the future. >>This is not a practical way to develop, so in practice a hardware design would >>try to be flexible and be governed by adjustable parameters, and clearly the DB >>designers tried to do that. But this flexibility means the hardware needs to >>adopt some model and so limits what it can do. > >>E.g. it can be seen from the description of DB97 that a big part of the chip >>evaluation was piece-square tables (called "piece placement array"), which makes >>sense, because you can roll so many evaluation terms into that. It's clear that >>these tables were not generated on the chip, which means that they were >>calculated on the nodes and downloaded to the chip. This means quite a lot of >>strain on the nodes, on the datapaths from the nodes to the chips, and >>ultimately it means that evaluation was really done in the nodes' software. It >>also means DB was far from being a true node evaluator. > >I was not amazed DB97 had a very weak evaluation. The many bad moves >it played each game this was already clear. Because most persons on this >planet do not see this as proof though, it was even possible to snow this >aspect under at the CCC here. Programming teams knew better of course... I'm truly not being inflammatory when I ask this, (and I do bow to you concerning pure chess matters since you *are* a FM, which I think is a heck of an accomplishment) but what really terrible moves did Deep Blue make in the match with Kasparov? Game 2 was impressive, and its play in some of the other games was also pretty good. Well, at least according to Kasparov, but- he's probably not the most objective person to ask. I have a number of books on the match and they don't mention that many blunders. >Note most programs >of today are complete gods compared to the 97 version of them. So comparing >a 2002 program with an old thing from 97 is not exactly fair in relative >terms, but in absolute terms it is fair and then we see clearly this >testing aspect. > >Deep Blue 1997 is nothing more than an improved deep blue 1. Searching >1 ply deeper or so and having more evaluation and seemingly especially >tuned for endgame. > >>If you consider the challenge and the problems they had, it's easy to understand >>why they made such compromises. To implement all evaluation on the chips >>directly (as some would have you believe they did) simply does not make >>practical sense. > >This does make sense when we would talk about a program like DIEP. >I get 60000 nodes a second single chip on a fast K7. From those >only a very small part are full evaluations. In short if i look how >many clocks i lose to a single evaluation, doing this in parallel on >a chip would be very interesting. >Of course there are two small problems here > - i do not know how to write verilog Trust me if you can write a chess program learning verilog will be a piece of cake. The real trick is getting a feel for what can and cannot be done in silicon. Settling on a non-friendly silcon design could be an expensive mistake. Many things that are expensive in software are basically free in hardware. A good example of that is bit-swizzling operations. Kiss the whole FirstOne/LastOne bitboard debate good-bye. Is 64-bits the "natural" size for a chess engine, well then make everything 64-bits wide. > - i can't afford a dollar or 10 million to do it. Yeah, the cost to do it "right" are ridiculous. Mask NRE costs alone for a 0.13 micron chip at TSMC are roughly $1 million. A seat of synopsys costs 100k+ The Avant! place and route software is another million (and let's not forget the salary of the poor ASIC engineers who actually have to do the work). Yep, 10 million feels about right. > Some guess they can make a 0.18 micron chess chip for just 5 million > dollar. That's the lowest estimate. Most estimates from hardware > designers is near 10 million dollar. > >>In the end, despite the advantages of a hardware design, the problem is that >>getting the hardware right takes 90% or more of your resources. When there is so >>much you can and should do in software, it's not obvious to me that this is the >>best way to make progress. > >It is not so hard to write for hardware nowadays, but i need to note that >Hsu didn't program in a programming language like there are nowadays for >hardware. Hsu has written his design on one of the lowest levels possible, >so completely incompatible and completely unreadable to improve. > >If a new chip was made in verilog now, like chrilly has made brutus, >then obviously things are quite a bit simpler when talking about testing >and verification. Verilog and logic synthesis are definitely the way to go for a custom ASIC at least if you want to have any shot at making that six-month schedule :) >A big problem of doing a program like DIEP in FPGA is the price of around >$2000-5000 a chip (again estimates range here programmer A says $2000 others >say it's $5000) because of the many logics needed. And don't forget the cost of all the software to make those FPGAs into anything other than expensive sand. Really, the bottom line on a lot of this is that software offers maximum flexibility while hardware solutions offer maximum speed for *specialized* applications. A good example of that is the Data Encryption Standard algorithm. Because it is a defined set of operations it can be custom built into an ASIC and out-perform all software solutions by many orders of magnitude. The trick (IMHO of course) is to combine the best of both worlds. Determine the areas in chess that won't change, such as move generation, and hard-code them in an ASIC. The search tree itself offers another possible item that could be implemented in silicon or at least major portions of it. Everything that gets done in silicon because (relatively) free timewise when compared to the software portions of the program. Creating a multi- tiered approach would seem to offer significant benefits (if the details could be worked out- of course the devil is *always* in the details!!) >It runs then of course with little RAm, which means you can't even >use killermoves, let's not discuss the slow hashtables. Hashtables >are simply impossible to do in FPGA i get the impression without slowing >down incredibly. > >Imagine that a chip is doing roughly against 3 million nodes a second. > >No way to combine that easily with RAM. Well, er... it depends on the where the RAM is. If it's on-chip RAM then it will be running at full-speed. An todays ASICs are being loaded with more and more RAM all the time. 8-Megabits of on-chip RAM are becoming common, (not cheap, mind you just more common). > >Even combining it with the fast and very expensive SRAM is not simple. > >Of course in what Hsu used, ASIC this is way easier to do from theoretical >viewpoint. In reality things are not so simple though. > >So on paper there is a huge potential here, but the practical chance of >it getting used is near zero. No one is going to invest between 5 and >10 million dollar to produce a chess chip. Alas, this is probably true. The mass market doesn't seem to be there. It's way to easy to turn on the TV than study chess or even the more esoteric (but to me rewarding) field of computer chess. IBM funded it because they wanted the publicity of beating the world champion. >If some chip makes it, then it will be a new version of brutus. > >The amazing thing here is that both junior, nimzo are complete monsters >with regard to nodes a second. Adding to that, that junior is using the >latest softwaretoys (SMP) and that brutus will have major problems to >get *any* speedup out of a dual setup and run at like 30Mhz or similar. > >This whereas the huge speed at modern CPU for junior and potentially >nimzo is counted in millions of nodes a second and hashtable is intensively >used here. >So it is a mystery to me why from all persons on this planet Chrilly is >making a program in hardware. Idem for Hsu. DB97 clearly was a simple >program. If he would run in software he would get a huge number of >nodes a second too, completely removing the need for hardware. > >It would make sense for DIEP to get hardware. It doesn't make sense to >put a program from chrilly or hsu in hardware. They suck too much in >chess. True, but even bad programs get good if they are fast enough. Taken to the limit a material-only evaluator with infinite speed would be unbeatable as would a program with god-like positional sense that only looked ahead one move, ala Reti. In-between these two boundary cases lie some pretty strong programs. >preprocessing definitely is outdated nowadays. Only one program >is managing to keep up, simply by luck that opponents play stupid moves. > >In chess the weakest chain is important thing. Junior's weakest chain >is anything but weak. That's why it's world champion. Not because of >'brilliant moves'. Junior simply showed and will probably keep showing >how far away chessprograms are from perfect play. > >The future is definitely there for the non-preprocessors. putting >all that knowledge in a chip definitely in theory very rewarding. > >However some half solution where it is put in hardware but >not using hashtables and not using things like killermoves >that is obviously no solution. > >We all agree here. > >>By the way, while Hsu & company can now use 0.2 or lower technology, so can any >>ordinary programmer who wrote his program for the 486 and now can run it on over > >Estimated project costs: $10 million > >>1 GHz. There's no advantage to the hardware guys in this respect. Actually it's >>their disadvantage. This happened to Hitech, another hardware design that was >>very fast in its prime but by the mid-nineties was surpassed by off-the-shelf >>PC's. > > >>>As far as positional items go. Hsu and his team were bright guys with FULL- >>>TIME grandmasters on the team (who were being paid by IBM no less). It was >>>their *job* to come in every day and make Deep Blue a better chess playing >>>computer (talk about Nirvana ;) I find it hard to believe that Deep Blue >>>didn't have a reasonable grasp (at least as good as the micros) of the main >>>positional ideas of chess. Did it understand everything, of course not, but >>>I bet it was damn good (just ask Kasparov). >>> >>>The current batch of software programmers are good, maybe some of the >>>best ever but frankly when talking about Deep Blue it is *not* a level >>>playing field. The deck is heavily stacked against the PCs. >>> >> >>There are grandmasters participating in other programs on a regular basis and >>nobody argues that this proves that the programs are awesome. > >the influence of those GMs in the program code is neglectible. I talk >daily to grandmasters and some have my program. They know nothing from >computerchess and will never know. The few 'tips' they give all are >useless as they show heuristics which 'by accident' were true in their >game, but not in the general case are true. > >having a FM title myself is a lot more helpful. Granted I could see cases where a Grandmaster could be more hinderance than help. Still if you worked with them everyday and possibly tied some type of monetary bonus system to the work, (say like a paycheck :) I bet we would all be pleasantly surprised how much computer chess and computer chess concepts they could learn. I do agree though that ultimately the programming skill of the program's author is more important than the assistance they receive from 3rd parties. The sad truth of all this is that we'll never answer the question of Deep Blue's ultimate strength since IBM took their ball and went home. Still it is fun to speculate isn't it!? regards, --tom > >>Amir
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.