Author: Vincent Diepeveen
Date: 04:02:15 06/28/98
Go up one level in this thread
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.