Author: Robert Hyatt
Date: 07:44:29 06/28/98
Go up one level in this thread
On June 28, 1998 at 07:02:15, Vincent Diepeveen wrote: I'm going to add my notes here rather than later as this is a long post with lots of stuff below, (quoted). two points: the original 20 ply suggestion for DB was and still is correct. They can't. And the math I gave below certainly supports that (since they don't do null-move and must live with a branching factor of 5.5 or so). Second, my math below was based on a branching factor of 3. I am now doing better than that after the heavy pruning I added in the q-search a year or so ago. 2.5 vs 3 is a big change when you are cmputing logarithms. My current analysis says that "current crafty" can do a 19 ply search, if it could search 200M nodes per second exactly as I search now. This isn't completely possible due to the architecture of deep blue (hash is not shared across all chess processors, they don't prune in q-search because they use MVV/LVA and generate one capture (or out of check) move at a time, etc.) So, after reading this old analysis, it is still correct. 20 plies is still out of reach, although one more hardware redesign, or quadrupuling the number of processors might bring that within reach. *IF* we could make the deep blue hardware do all the things I currently do (I do R=2 null move, their hardware can't do this at all, I prune losers in the capture search, they can't even estimate whether a move seems to lose material or not in the current hardware) it would be possible to do 20 plies. *as* the hardware exists, 20 was, and still is, not doable. Maybe that is a clearer statement, as if you read my most recent post, and the one vincent quoted, this isn't so clear. My most recent post simply said that *if* crafty could do 200M, it could hit 19 plies deep. But not on the current DB hardware due to the above limitations. I was a little careless in explaining everything I said, clearly enough so that it could not be interpreted in a way I didn't intend. Bob > >On June 27, 1998 at 15:42:53, Robert Hyatt wrote: > >>On June 27, 1998 at 10:15:40, Vincent Diepeveen wrote: >> >>>Hello Bob you're lately telling us a lot of new facts, >>> >>>I remember that some time ago (2 years perhaps?) >>>we already knew the DB speed. i claimed that getting 18-20 ply >>>would be no problem for them if they stripped some extensions, >>>improved move ordering and used nullmove. >>> >>>At that time you told your audience that getting 20 ply was >>>*impossible* and challenged me. >>> >> >>I don't recall *ever* saying 20 plies was "impossible". I might have >>said *impossible* using their search, because I know that they don't >>use null-move at all, based on comments from Hsu. Which means a branching >>factor of 5.5 roughly. If they used R=2 null move with the attending >>effective branching factor of 2.5 or so, 20 plies is doable. > >>If I could search 1,000 times faster *right now*. I would search to a >>depth of 12 + log (base 2.5) 1000. the log is approximately 7, which means >>where I do 10 now, I would do 17 at 200M nodes per sec. Where I would do >>12 now, I would do 19. The math is simple. THeir NPS is not new... > >> >>>Right now my program GETS 20 ply in several middlegame >>>positions after 24 hours of analyses (and i'm not referring to >>>positions where you need to make a forced move like recapture), >>>but i'm also in the pruning buiseness, so probably this doesn't count >>>in your eyes as some stupid variations get pruned by Diep. >>> >> >> >>what your program does doesn't matter. they aren't selective. you are. >>the searches aren't comparable in any sense of the word. >> >> >>>Note that very important is the fact that i'm having 80MB of ram now, >>>under NT i use 60MB of hash under DOS 64MB. It appeared that >>>big hashtables at analysis level give a lot (which is rather unsurprising). >>> >>>Now how big was my surprise when reading next: >>> >>>>Again... if DB used null-move R=2, with a search like mine, they would do 20+ >>>>plies in middlegame. They do extensions instead. I do 12 plies at 200K nodes >>> >>>How can they at hardware which is slower than was expected few years >>>ago (i still remember an email from one of the teammembers very well >>>where they expected to make a chip which got 5-10M nodes a second, >>>and that has become finally 2.5M) >>>get suddenly 20+ ply without my 'dubious' forward pruning, but with >>>the stuff discusses in RGCC, and they even could search deeper >>>in your opinion? >> >> >>their 2.5M NPS was most likely the result of spending a year to (a) make >>the eval hardware more complicated (b) adding checks to the q-search, which >>early versions didn't do and (c) detecting repetitions in the hardware, >>which older ones didn't do and (d) adding other things like endgame database >>probes into the hardware. >> >>I based 20 plies on *my* program. I generally do 12 in middlegame positions >>at 250K - 300K nodes per second. Going 1,000 times faster, with my current >>branching factor of around 2.5, that leads to a 19 ply search (or better) >>in equal positions, based on nothing but understanding that new depth = >>old depth + log(base 2.5) 1,000. >> >> >> >>> >>>This needs some explanation! >> >>already done.. >> >> >> >>> >>>>per second. They are 1,000 times faster... with a branching factor of roughly >>>>2.5, what is log base 2.5 of 1000? That's my search depth at that speed. So >>>>*obviously* they are doing something else. You compare your 12 plies to their >>>>12 plies. I say that's total hogwash. >>> >>>Ok ask IBM for old printouts of the match and we can easily compare their >>>mainlines to our mainlines. >>> >>>Don't do whether their 12 ply is in fact 24 ply or 13 ply. >>> >>>12 ply is 12 ply, if you use nullmove you run zugzwang risks. If you don't >>>do checks in q-search you even miss obvious mate threats last couple >>>of ply, if you prune a lot you might sometimes miss something like >>>heavy sacraficing for a mating attack; but lucky none of this all happened >>>in the games. >>> >>>Their 12 ply aren't more holy than mine 12 ply. I admit: i prune, so certain >>>stupid lines which might win might get pruned. There were no >>>difficult ! moves played by Deep Blue, no difficult sacrafices, no >>>mate in 40 announced, and win in 23 ply (23 ply for Diep: Kf1? in game >>>II, where Kh1! wins forced) was missed by Deep Blue. >> >> >> >>they don't do null move. they do do checks in qsearch. your point would >>be, after knowing that, ?? >> >>yet you continually get beaten by "crafty" which, according to you, has >>(a) a poor search; (b) poor evaluation; (c) no "mate" extensions; (d) no >>sophisticated selectiveness; (e) a simple and ineffective quiescence >>search. I'm afraid that in this case, 2+2 = 4. I'm doing *something* >>right, otherwise you are doing something *terribly* wrong. Either >>explanation is possible. But you ought to stop putting your program up >>as "the epitome of computer chess programs" when comparing what you can do >>to what Deep Blue (or another program) does. I tend to notice results, >>rather than chest-pounding and hand-waving. >> >>> >>>Yet it plays a horrible move which is only 1 ply deep (12.Bxg6? in game 4 >>>after the moves: >>> 1. e4 c6 2. d4 d6 3. Nf3 Nf6 4. Nc3 Bg4 >>> 5. h3 Bh5 6. Bd3 e6 7. Qe2 d5 8. Bg5 Be7 >>> 9. e5 Nfd7 10. Bxe7 Qxe7 11. g4 Bg6 12. Bxg6 hxg6) >> >> >>should I point out how many horrible moves *your* program plays in a >>game? Would that prove anything at all? When you post your games where >>you beat Kasparov here in CCC, I'll check 'em over for horrible moves. >> >>Exactly when can I expect to see those games? >> >> >> >>> >>>This move Bxg6 can be easily prevented if a program knows that >>>after hxg6 the simple pattern g6,g7,f7 open h-file is not a bad doubled pawn. >>> >>>This is a beginners fault of 1 ply. So how deep did Deep Blue search? >>> >>>Please test your programs at it. If i remember well this pattern is also in >>>psion. >>> >>>Vincent >> >>g6 g7 f7 *can* be a problem. It depends on white's h-pawn and whether he >>can get rid of it and use the open h-file. So you can't just say f7/g6/g7 >>is ok... because if white dumps his h-pawn, or rook lifts to e3-h3, black >>is in a *world* of difficulty. > >So you changed your opinion drastically. Sorry but i have to confront >you with an old article. In those days (januari 1996) you wrote next >(read especially the last section you wrote): > >---------------------------------------------------------------------------------------------------------------- >Subject: Re: Deep Blue vs. Kasparov >From: hyatt@willis.cis.uab.edu (Robert Hyatt) >Date: 1996/01/09 >Newsgroups: rec.games.chess.computer > >--> Vincent Diepeveen <vdiepeve@cs.ruu.nl> wrote: >--> >-->>I did not really expect anybody to believe me. But I had hoped for more >-->>positive responses. Seems like anytime someone that is not a well >-->>established chess programmer says anything about having some ideas, that >-->>only negative vibes are given in response... >--> >-->In this point i agree. >-->Few time ago i was shouting about sorting and ordering moves >-->should give the superprogramms much larger depths then they currently >-->get. >--> >-->It seems that i was correct. It appears that most commercial programms >-->and the stronger amateur programms have put a lot of work in move ordering, >-->and i'm not only talking about hashtablemove, killermove, but a lot more, >-->where the supercomputers only do the already published things... ...which >-->gives a bad move ordering. >--> >-->Also i told that getting 15+ to 20 ply should be no problem for >-->programms that can evaluate many million positions a second. >-->This also seems correct. In example calculations i used branching factor 4 >-->with recursive nullmove r=2, extensions for check, singular extensions. >-->and hashtables. >--> >-->Even my own young programm currently has got branching factor 3.76 above >-->10 ply (including first 10 ply). The number of alphabetacalls up to 10 >-->(including 10) is less then 2 million (about 1 to 1.4 million for 10 ply). >-->If i consider this to be overhead, then branching factor is even much better, >-->about 3.2, so guys... >--> >-->I have also a testprogramm, which i have no problems to mail around. >-->It only evaluates material. >--> >-->It searches from opening about 18 ply. no hashtable, >-->just nullmove and killermoves... ^8 >--> >-->As soon as guys read well, then they say: OHHHHHHHHHHH, but your programm >-->only evaluates material!!!!!!!!!!!!!!!! >-->So: Bishop = Knight = 3, Pawn = 1, King = OO, Rook = 4.5, Queen = 10. >--> >-->I suspect however that for EVERY evaluation, no matter how good it is, >-->of the position searching a certain depth there is a move ordering that >-->gives you a minimal alphabeta-tree! >--> >-->Anyone disagree that it is possible NOT to get 20 ply? >--> > >Yes. First, getting 14 (if you can do that in real positions) is >*not* "close to 20". you are 6 short, and at a very optimistic branching >factor of 3, this leaves you needing a factor of 3^6=729. Not much way >to wave your hands and magically order the tree to make that go away. > >In Crafty, I can reach 10 in a reasonable amount of time from the opening >position, but this is an artificial position where the q-search is very >small compared with positions that arise 10 moves down the game tree. >I haven't seen *any* program search 14 plies exhaustive in the middlegame >*including* deep blue, deep thought and cray blitz. In fact, I haven't >seen any that get a *real* 10 ply search in the middlegame, without some >selective pruning or heavy use of null-move, which reduces the effective >search depth. > >We all are practitioners of null-move searching, but, from experience, >it is *not* free. If I compare search depths between Crafty and Cray Blitz, >the comparison is very good, because CB used R=1, non-recursive, for a very >conservative null-move search, while Crafty uses the traditional R=2 >recursive form. however, for the same depth, Cray Blitz will win nearly >every game, because it doesn't make as many tactical mistakes. Luckily, >R=2 lets crafty search deeper than Cray Blitz in the same time, so it's an >ofsetting thing. I like R=2, because I search one ply deeper positionally, >although I make more positional/tactical mistakes due to null move pruning. >The extra ply seems worth it, although when I see some of the problems it >causes (classic position is BK at g8, BP's at h7 g6 f7, WB at f7, and the >WQ on the a6 diagonal so it can reach a6 and threaten mate at g7. null >move pruning will make this take at least a couple of extra plies to see, >because it won't realize that after Qh6, that playing a null may cut the >depth to 0 and it will overlook the mate threat. All of us see this >problem, once you play enough games that you start getting attacked. If >you take a problematic position, turn null move off, it will immediately spot >the threat and take action, not letting the null move blind it. > >-->If you don't, then i'll make the steps in the right deductive order for >-->you: >--> >-->a) assumption: For every evaluationfunction f on a certain >--> depth d there is a minimal alphabetatreetree > >True, Knuth/Moore proved this in their now-famous paper 20+ years >ago. The evaluation function has nothing to do with it however, For >the *same* tree, the search space is constant, regardless of the evaluation >you use, unless you somehow let the evaluation control the shape of the >tree by extending when eval >x or when eval < y for example. Otherwise, >everything's a constant. You may get two different paths, with two different >scores, but with exactly the same number of nodes, exception above noted >however. > >-->b) for a 'stupid programm' only evaluating material it is possible to >--> get 20 ply. f = (sum material(side) - sum material(other side)) >--> d = 20 > >I don't agree with this. there's been *plenty* of material-only tactical >searchers, *exactly none* have reached 20 plies, on some pretty fast >machines. See below for specific mathematical refutation. > >-->c) It is possible to get 20 ply with every programm if you have an excellent >--> ordering for 20 ply. > >I certainly don't agree with this. do the alpha/beta math: Rough approximation >20 plies, tree size=2*38^10 (2 times 38 to the 10th power where 38 is the >typical branching factor.) This is straight from Knuth/Moore and is directly >provable. Null move reduces this because it prunes away parts of the tree >without knowing that it is safe to do so. Many claim a factor of 20x when >using R=2 recursive null move, so lets take that. That gives >2*38^10 / 20 = 38^10/10. Personally, I don't have a clue of how to search >38^10 nodes. 38^4 is 2 million, 38^8 is 4 trillion. we are to 16 plies >now and Deep Blue might reach 4 trillion in an hour or two if it's lucky. >Then you get to multiply by 1444 again to get those last two 38's in there, >and that's not reachable, I don't care what kind of ordering you do. Good >ordering can take you very close to optimal alpha/beta search space, but it >*can't* take you below it. It's a clear lower bound to the total search >space, and there are two ways to solve this problem: (a) search faster or >(b) forware prune to reduce the "38" to a smaller number. Ordering won't >cut it. > >-- >Robert Hyatt Computer and Information Sciences >hyatt@cis.uab.edu University of Alabama at Birmingham >(205) 934-2213 115A Campbell Hall, UAB Station >(205) 934-5473 FAX Birmingham, AL 35294-1170
This page took 0.01 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.