Author: Robert Hyatt
Date: 10:35:13 08/27/01
Go up one level in this thread
On August 27, 2001 at 08:59:00, Robert Hyatt wrote: >On August 27, 2001 at 04:14:33, Tom Kerrigan wrote: > >>There are some issues here that have not received due attention. >> >>First, [as most of you already know,] part of DB's search algorithms and all of >>DB's evaluation function algorithms were implemented in custom VLSI chips. This >>made it phenominally fast and also means that it can't exist as a PC program >>(because you don't have the chips). However, PCs have general purpose >>processors, which means they can run any algorithm you can think of, so the idea >>of running DB on a PC isn't quite as stupid as most people seem to think, if >>you're talking about the algorithms. There are two issues at play when >>discussing implementing DB as PC software: >> >>1) Work involved. Speaking from experience, the time-consuming part of writing >>an evaluation function is not the actual coding, but instead deciding which >>terms to include and what their weights should be. If you already know _exactly_ >>what an evaluation function is supposed to do, (and the DB team does,) I bet >>implementing even the most complicated one would only take a couple of weeks. I missed that statement first time around, until someone sent me email. I don't know what kind of evaluation _you_ have written. But _mine_ was not a two week implementation project. None of mine have been two week projects. >>Moreover, I believe that most, if not all, of DB's evaluation function already >>exists as software. It takes months, if not years, to design a chip of this >>sophistication, and more months and millions of dollars to get it manufactured. You are behind times. First, ASICS don't cost "millions of dollars". Just read some of Hsu's old papers. The first run of the Deep Thought chips cost them a couple of thousand dollars, total. And second, it didn't take "years". After the first Kasparov match, Hsu took time off, then completely re-designed the chips to create the DB2 version, had the chips fabbed, and had everything working for the match one year later. Design, implementation, fab, testing, assembly, tuning, all in under one year. With all the design and testing done by one person. >>It's absurd to think that anybody would put this much effort and money into a >>project without first experimenting with the algorithms to see if they were any >>good. Additionally, it has been reported that the evaluation function was being >>tuned by the DB team long before they had any of their chips manufactured. >>Exactly what were they tuning, then, if not a software implementation? > > >According to what they have published, they were tuning the "weights". There >is a _huge_ difference between having code that will take weights and produce a >score based on a position, and having code that will do this in a chess engine. >The difference is the speed requirement. If the hardware can do over 1B >evaluations per second, and software can do 1000, then the two are certainly >not comparable if they are going to be used in a chess engine. > > > > >> >>2) Speed. Some would have you believe that DB's evaluation function was >>infinitely sophisticated and had every concievable term known to man implemented >>in it. So many terms that they literally didn't know what to do with all of them >>(i.e., a lot were zeroed out). This immense complexity is supposedly made >>possible by the custom hardware, and any software implementation would run so >>slow as to be worthless. Well, I don't believe this. This is basically calling Hsu a liar? I gave you the speed numbers above. Could you really run a 1K nps evaluation and draw any conclusions about how it would do 1M times faster? I know I can't. In Crafty, I analyze results in two distinct ways. First by looking at specific positions to see what the static evaluation says, and if I disagree then I find a way to fix it so that it agrees with me. Second by looking at games, which means searches, to see how the evaluation works with a search, to produce a "best" move. Sometimes the search is wrong. Sometimes the eval terms are too large or too small when factored in on top of the search. But I certainly can _not_ predict how this will work without playing games and watching. And I am not about to use one million seconds of cpu time to try to conclude how the real DB would look with just one second of searching... > >It really doesn't matter what you believe. Hsu publicly stated that they >used less than 50% of the evaluation hardware in the DB 2 chips, when they >were preparing for the Kasparov match. They simply didn't have time to get >everything tuned. I don't see any reason to make a statement like "I don't >believe this." What makes your opinion so valuable here, when you don't know >much at all about the team nor their product? > > > > >> It takes effort to >>implement an evaluation function term, and it takes much more effort to >>implement one in circuitry. Common sense says that the DB team only implemented >>terms they thought would be useful, and not every single one they could think >>of. Moreover, nobody can think of terms (in DB or otherwise) that are so >>computationally intensive that they would cripple a PC program. MChess's >>evaluation function is rumored to be phenominally complex, and it can still >>search thousands of nodes per second and compete with the best. The only example >>of an awe-inspiring DB evaluation term that Hyatt can think of is that DB >>assigns a bonus to a rook on a file that looks like it might open up. That could >>really mean anything, and several commercial programmers say they already have >>terms that do this. >> > > >Sorry, but you are way off the planet here. I've mentioned more things that >they do that are computationally complicated. King-side attacks is one that >they have mentioned more than once at their presentations. Knowing which >pieces directly attack squares around the king, which pieces indirectly attack >squares around the king, which squares around the king are weak/critical, etc. >All doable in software. I did some of this in Cray Blitz. But I don't in >Crafty because while it is doable, the computational cost doesn't seem to be >offset by the skill gained, when the cost is so high. > >Potentially open files is computationally costly to compute. I do some of >this in crafty because I felt it necessary to be able to recognize blocked >position (not just the trivial cases where pawns form a ram) and pawn lever >opportunities (or the lack thereof). Fortunately, for pawns, hashing saves >the day. DB takes that idea to other terms. They don't hash them, but they >compute them just as fast as we can hash them, which is a real advantage when >you know you can add anything to a pawn structure eval you want and know it >isn't going to slow you down. They just take this to the next level. > > > >>In other words, I don't think it would be especially difficult to run DB's >>algorithms on a PC. (It would be extremely interesting, too.) There are a few >>possible reasons why this hasn't happened yet: >> > > >Nobody said it would be difficult. However, in 1995, Cray Blitz could search >about 7M nodes per second on a 32 cpu Cray. Cray Blitz on the best available >CPU of that time could not search 1K nodes per second. I've reported this >before. This was caused by CB's reliance on vector hardware and high memory >bandwidth, something the PC of 1995 didn't have (and still doesn't have in 2001 >in fact). So yes, it can be done. Just like you can replace the engine in an >Indy car with a squirrel in a cage. But I'm not sure how interesting that would >be, other than you could study an indy car in very slow motion. > > > >>a) Lazyness or non-interest. Maybe the people on the team have moved on to other >>things or just don't feel like doing the work. > >Rather than laziness, what about "futility"? IE what would be the point? >They have access to the real hardware (DB Jr is still alive and well and >providing analysis from time to time at chess tournaments) so why would they >want access to something that is so slow as to be useless? > > > >> >>b) Legal issues. IBM might legally own the algorithms and not want to hand them >>over for this purpose. >> >>c) Reputation. Maybe the evaluation function really sucks as much as some people >>think, and releasing a program based on it would make DB the laughingstock of >>the computer chess community. Even if it's on par with that of the better >>commercial programs, some people will be disappointed that it isn't the >>revolutionary leap they expected. (There has been a TON of propoganda raising >>peoples' expectations.) > > >Your logic escapes me, totally. You think that a program that is designed >around special-purpose hardware could run on a PC, albiet maybe 1M times >slower. And if that played poorly, it would damage their reputation? Would >it damage the GNU compiler guys if I told the world their compiler can't play >chess worth a crap? They might point out that it wasn't exactly designed to >play chess in the first place, it was designed to turn some high-level formal >language into machine language for most architectures. > > > > >> >>Personally, I think the real reason is a combination of these three. >> >>The next major issue about DB that's been overlooked is its search algorithm. >>People know that it searched 200M NPS and Deep Fritz only searches 5M NPS. Well, >>that sounds amazing, but it's pretty meaningless to compare NPS rates unless >>you're talking about the same program. MChess used to beat up on Fritz pretty >>bad while searching a small fraction of the nodes. The Rebel vs. >>Crafty-at-an-absurdly-long-time-control matches show the same thing: a program >>with a better evaluation function or search can search fewer nodes than the >>competition and still win. > > >Earth to Tom. Better re-check. Ed won the first game in such a match. He >later played more and didn't win another game. This is in his chess 2010 >experiment, where in that experiment both programs had a long time per move, >not just one. > >Your conclusions are flawed, and based upon incorrect data. There was only >one game played in the "rebel vs crafty-at-an-absurdly-long-time-control" >"matches"... > > >> Most of the "information" we have about DB's search >>is speculation. We "know" they didn't use null-move [all the time]. We "know" >>they didn't do forward pruning [all the time]. We "know" they used singular >>extensions [some of the time]. We actually know for a fact that their search was >>massively parallel, meaning their "effective" NPS rates were much lower than >>200M. > >You might "know" that, but nobody else does. We "know" that their hardware >could search at a speed of over 1B nodes per second. Half the processors >searched at 2M, the other half at 24M. 480 * 2.2M > 1B. Hsu reported that >he could run the chess chips at about a 70% duty cycle with the SP hardware >platform. That turns into 700M nodes per second (or a bit more). Perhaps >his "200M" already factors in SMP losses. That's the only way I can see DB >getting down to 200M based on the numbers he published about its potential >speed, number of processors, etc. His PhD thesis claimed 20-30% efficiency >on the parallel search, which seems reasonable based on my 70% numbers with >full shared memory. That would mean his 200M is already a real lower estimate. > > > >> Maybe their search was phenominal, but it's equally possible that their >>search was crap and wasted 195M of those nodes, making it effectively as fast as >>Deep Fritz. Nobody has a clue, and if somebody claims to have a clue, well, >>inspect their sources with a fine-tooth comb. >> >>-Tom > > > >Good advice...
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.