Author: Jeremiah Penery
Date: 22:29:30 10/13/99
Go up one level in this thread
On October 13, 1999 at 22:00:32, Ratko V Tomic wrote: >>>Even the 18 plies in complex middle game (which may be 2-3 years off) still >>>hinge on the same old simple-minded evaluation of the terminal nodes. >> >>You think DB uses 'the same old simple-minded evaluation'? >> > >I would say the terminal node evaluation (excluding the table-base lookup, of >course) in any program is simple-minded comapared to human judgment. By itself, >this evaluation makes it roughly equivalent to one ply "search" setting, which >should lose to just about any chess player. > >Regarding DB vs other chess programmers, I would think that the best commercial >programs use more sophisticated algorithms than DB. That's human nature -- if >hardware will do 200 Mnps without programmer breaking a sweat, the drive to >conceive something new here to squeeze an extra 10 or 50 Mnps won't be nearly as >strong as if you're using 40 knps micro (as in case of Hiarcs on a 400 Mhz >Celeron). Thus the micro chess programmers have to think much harder to produce >the highest quality evaluation functions, while DB programmers can stuff almost >anything that comes to mind, Exactly. They can stuff 'anything that comes to mind' in their evaluation, because it'll still be the same speed. So why would they use a simple evaluation, when they can use a function of arbitrary complexity at the same speed? That's sort of the point of this thing: At 200M NPS, you still can't win if you have no knowledge (_especially_ against someone like Kasparov). >and very likely don't put nearly as much thought >and creativity into it as the micro guys do. As the saying goes, the necessity >is mother of invention. You have: A) A chess program, written by one of the best chess programmers there is, running on an ordinary desktop computer (Perhaps even a 700 MHZ Athlon). or B) A chess program, written by more than one of the best chess programmers there are, running on a supercomputer with hundreds of special-purpose chess-chips to evaluate in hardware what would take 100x longer on a general-purpose CPU. Also note that use of several GMs was employed to help tune and improve the evaluation. Would you take 'A' simply because he might put more thought into a 'creative' evaluation that would make the best use of the limited hardware? >>>If I (a mere 2100 player over a decade ago) can get Fritz 5.32 etc to just >>>shuffle rooks on the back rank with no clue what to do next, >> >>But if you let Fritz search more ply (15, 20, ...ply), it will eventually find >>something better to do than shuffle rooks. Other programs may not have this >>problem at all. >> > >Depends on type of positions. In some positions there is virtually no (humanly) >non-obvious tactics hinging critically on a move choice 20-30 plies earlier. >Whether at ply 20 Fritz will find something (that's still at least 5 years from >the current full depths, though), depends on what it is looking for. It may find >how to gain an attack on one extra square, which may mean nothing, or may even >make things worse 15 plies later. It will be looking for moves that will win. Even in Fritz (which has a relatively simple eval, I think), there are surely a lot more to the evaluation than finding squares which are attacked (And I'm not even sure Fritz, or any other program, does it like you describe.). >While deeper is on average better, if it were always better, the same program >running on a two times as slow machine would always lose to the program on the >faster machine. That's not true, though. If, say, the factor 2 in speed brings >70 ELO points, the (W-L)/(W+L)=70/400=0.175, giving then W/L= 1.42 or giving >percentage wins about 60% for the faster version. So quite a good deal of time >the shallower search gave _ultimately_ better moves. Part of this comes from the opening choice. If a machine comes out of book in a bad position (Even if it thinks it's doing well), it will lose to any reasonably played moves. For example, computers have a very difficult time playing the Benko Gambit as black, whether they're playing another fast computer, a slower computer, or any variety of human. If this opening is played in computer vs. computer, I'd say that white is very likely to win, even on much slower hardware. Part of it is also simple luck and probability. >Now if one were to develop more systematic theory (for human use) on what kind >of positions have such property and strategic methods to go along to produce >such positions, that could negate much of the computer depth gain. There are >also artificially constructed (for this purpose only) games where deeper search >produces mostly worse moves (than e.g. a random pick of moves). Actually, with a purely random evaluation function, a deeper search is better. Several have posted about this before. >The reason for all these counterintuitive phenomena is that minimax as used in >chess is not really picking the best among the exact values of the nodes but the >best of the guessed values (guessed by some rules of thumb, which are nowhere >near 100% valid). True, but the programs _think_ they're the best moves. >The programs also have no idea how much error is involved in >these estimates but treat them as if they were true values to be minimaxed. A >program will, without a second thought, go for massive complications, showing >near term win of additional material, even when their current material is >already winning for any half good player. A rational human player will convert >the advantage to a whole point in the most safe, least double edged way. This is not always the case. >>> You don't need the best move to win, just a good enough move (chess >> programmers don't seem to know this, as yet). >> >>So do you want the chess programs to say "Ok, I have 3 choices for moves, and >>all look like they're 'good enough'. I think I'll choose the one that I think >>is the worst of the 3, because it's still 'good enough'." ? >> > >No, I didn't say that. What I said is that if, say, a program sees a 12 ply sure >win of a piece, with otherwise quiet and "normal" position, then there is no >need to pursue alternatives to its choices which at ply 14 might gain a piece >plus pawn. Computers are better in tactical positions, so why would it want to win a piece in a 'quiet and "normal"' position when it could win more than a piece and be in a tactical position? >It should pursue deeper only the branch which it already discovered >winning a piece, to verify the gain isn't poisoned, So what if it is poisoned? It'll have to go find that 14-ply gain of piece+pawn after all. And it would have wasted all that time finding that the 12-ply thing was bad. >otherwise it should be happy >to have found one very likely way to the whole point. If you had a choice to be either +1 or +1.5, which would you choose? >Programs seem to calculate >as if your score will go up point and half if you can win in 30 moves instead of >45 moves. As of now, it won't, thus no need to waste its time (which may be >needed later in the game if the oponent tries something desperate) as if it >will. If it can win in 30 moves, why shouldn't it do it? Should it instead play sub-optimal moves so that it takes 45 moves to win? >(Of course, being happy with "good enough" would have to be turned off when >solving test suites, otherwise they might not find the solution.) :) >>A different move almost always is better if it's found at greater depth. > >If that were so, the same program on 400 Mhz PII would win "almost always" to >the program on 200 Mhz Pentium, and that's not the case at all, while in fact >the faster one will win only about 60% of games. See above. >>> I'll >>use your example: Say at depth 10, the program sees that it can do Qxb2, >>winning a pawn. If it searches to depth 11, say, it may see that it's getting >>attacked, since it doesn't have its queen to defend. So it picks a different >>move, that doesn't win the b2 pawn, but does prevent your attack. >> >>Is this not a better move, found because of greater depth? >> > >But at ply 1-9 it may have not seen a win of the pawn at all, so it wouldn't >have gotten drawn into the queenside pawn hunting at all. This is true. It is the difficulty of tuning an evaluation: One needs to be able to find attacking possibility, but also possibility to be attacked. Also, there is need to be not so materialistic so that you will try to win a pawn at all costs. >As suggested earlier, >it all depends on types of positions, and while the typical present-day human >style positions may be vulnerable to deeper search in a statistically >significant number of cases, I have no doubnt that a different style, from >openings to strategic guidlines, exist which would shift the probabilities >making the extra depth, while not necessarily do more harm, but at least do not >much good for the typical alpha-beta searcher. I'm sure this is true, but even if the deeper search doesn't find any more winning moves, it still may find slightly better moves, or moves that preserve a draw rather than ending in a slow loss. It will not appear that the deeper search is doing much good in these cases, but it is still almost certainly better than the shallower search. As you've said, there are times when a shallower search can find ultimately better moves. This is because the evaluation functions are inexact. With a perfect evaluation (if there is such a thing), a deeper search would _always_ be better than a shallow one. Jeremiah
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.