Author: Robert Hyatt
Date: 07:10:51 10/14/99
Go up one level in this thread
On October 14, 1999 at 03:56:14, Ratko V Tomic wrote: >>> 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? > >More stuff in the evaluation won't necessarily improve choice. Lots of such >advice, like the folk wisdom, comes in pairs of opposite polarity (is it better >to be the "early bird" or make waste from haste etc). A well thought out and >finely tuned (to the context) function should do better than a mass of stuff not >as well tuned. A creative spark needed for this kind of black magic, as it were, >prefers those who are under greater contradictory constraints. > >> >>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. >> >> > >Otherwise same person, but in a harder situation will be more creative, so >they'll get more performance per unit of crunching power, no question about it. >As to the GM advice, well, it may be useful to the programmers in matters that >are of algorihmic nature (mostly the endgame techniques) or in tuning the >opening books (provided they have a good sense what fits the program otherwise). That is simply _totally_ wrong. Using micros, we decide what we want to eval, we try it, and decide whether the gain from the knowledge is worth the cost in search speed/depth. Hsu does the same, except rather than having to choose whether to use it or not due to speed, he decides whether to use it or not based on whether he wants to design the hardware to handle that. _EXACTLY_ the same issue, just in a slightly different context. If you really believe that others are more creative than the DB team, you are _sadly_ mistaken. >The other advice, of more strategic kind, it's not clear whether that kind of >knowledge will help or harm the program. Some principle which may loom important >to a GM (and maybe it is within his algorithm, much of which is subconscious, >though) may be expensive to compute and within program's algorithm it may be of >very little or no use, or even it may cause harm (e.g. ideas on indirect control >of center or of an isolated central pawn, which GM may like to have). > >It's like with "expert systems," it sounds better than it works. > In this case, it seems to have worked incredibly well, wouldn't you say? No other machine around can beat Kasparov in a match. No other machine can even beat a strong human given the position reached in game 6. Yet DB made it look easy. > > >> >>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. > >It doesn't have to be an objectivly bad position. It's enough that position >doesn't suit the evaluation function and as soon as it gets out of the book, the >program tries to undo the "damage" it thinks the book did. In fact it's >evaluation function simply didn't understand what was the point of the the >particular opening, what are the plans that should follow, what squares or lines >are more important in that line, what pawn should not be moved, what pieces kept >from exchanging etc. A good eval doesn't have opening positions that it can't handle. My program now plays fianchetto openings quite well, yet it didn't 3 years ago. Because it now has a better understanding of what is required. My favorite GM is trying to break it on both sides of the Kings Indian, to see what it can't follow very well. So far, as black, it is crushing him every game. > >Another problem that opening may have for a program is that there may be some >variation few moves beyond the book where deeper (but by necessity inexact) >evaluation misleads the program. It is an analog of opening traps in human >games, except that here the poisoned gift isn't an offer of a seemingly free >piece one or two moves ahead, but it may be some tricky combination 14 plies >deep that nobody ever thought of. In human oriented opening thery much of such >stuff is invisible (unknown even to specialists), like underwater rocks, waiting >to sink a brute searcher which discovers the "gaining" combination. hmmm.. I have seen 14 ply searches from crafty in the middlegame. I have seen DB go incredibly deep, with PVs well over 40 plies long. I doubt that will be a serious problem to them. > > >>> 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. > > >That may be the case in chess, but there are some artificially created games >where for certain types of seemingly plausible evaluation functions, a deeper >searcher performs systematically worse, the deeper it goes. Some examples of >such "pathology" (as it is called) are given in the book "Heuristics" by Judea >Pearl, 1994 Addison-Wesley, ISBN 0-201-05594-5 (in chapter 10.1 and 10.2, pages >346-360). The main cause of the patology in the example (Nau's board splitting >game) was the evaluation error propagation, which made the error larger as the >values are backed up the tree. > I don't think you will find that true of current programs. Maybe a rare exception position here and there, but _very rare_. And very fixable when we find them. > >> >>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? > >Well, in a "normal" position and piece ahead, it may win 999 out of thousand >games, and win in average 80 moves. With piece and pawn and a very dynamic >position (which may look quite good 10-14 plies ahead), it may win 950 games, >using 40 moves on an average win. The first is still better, even though it took >more moves. While indeed, it may be nicer to in win in 40 moves, program would >not know whether going for a complication with pawn gain within depth, will put >it within the 950 40 move games or the 50 games it will lose. > >The reason behind such effect is that the static evaluation (as applied at the >terminal nodes) has greater error in dynamic positions than in the quiet >positions. So the evaluation of having an extra piece in a quiet position may be >3 +/- 0.5, while evaluation of piece plus pawn in a dynamic position may be 4 >+/- 3 or some such. In the latter case, a greater part of the tail portion of >the true value (which is unknown) distribution get pushed into the opposite side >win. Of course, the larger part of the tail will also have greater value, >leading to quicker victory, but quicker victory brings no more ELO points than >the longer one. > that is why we have the quiescence search... to remove much of the dynamic stuff so that the position _is_ quiet when we evaluate it. This doesn't seem to be much of a problem today. >Of the commercial chess programs, as far as I can sense throuh play, only Rebel >has some appreciation of the error in the evaluation, and will pass the small >gain in a essentially won position, if the small gain will bring complication >(without there being any near term threat to it). (Ed might be able to confirm >whether it does it explicitly or such behaviour may be a beneficial side-effect >of something else.) > > > >>>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. >> >Well, in most normal situation, a piece gain will be fine and good enough for >the whole point. A bird in hand is better than two in a tree, so to speak. After >program finds a piece win at 12 ply, in a reasonably peaceful position, a hope >that it might find a pawn win, if only it chose a different initial move, with >two more plies of full width search of alternative initial moves, seems like >gambling a good time for small gain (which even among the rare cases where it >may be found, won't produce more game points than the piece-win branch, i.e. >both will win, the 14 ply piece+pawn will win quicker, but still just 1 >torunament point). The overall game point gain probability from the ambitious >strategy is basically compound probability, a product of two very small >probabilities, that there is such initial move (winning pawn + piece, visible in >14 plies, and which is different from the move winning piece only, visible in 12 >pies), with probability that the piece only move will ultimately lose the game >(which is a small probability) and piece plus pawn will win it. > > > >>>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? >> > >Of course, if I discover 2 lines, one gaining +1 the other +1.5 I'd pick the >better one. But the choices I was talking about had caveats. If a game result >mattered in some way (not a fun game played against a program in the privacy of >my home), and I have found +1 line already, and I don't know whether there is a >+1.5 gain, if only I were to choose a different initial move (if it is the same >initial move as +1, I don't need to find it now), unless I were to spend another >several minutes looking at the variations, I would take the +1 I already know, >rather than gamble valuable time on low odds hopes of finding even more. > > >>>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? >> > >If it will cost him a chunk of time to find whether there is a shorter win than >one already found, there is no sense in wasting that extra time, when the slow >win will earn you the same number of game or rating points as the quicker win. >If a game is important and I see a piece win, I don't spend time looking for >even greater material gain at that point, knowing I may need the time later, but >I assure myself that the pice gain will stick. Even if someone were to tell me >at that point that there is a tricky mate in 6, I would pass it, and rather play >for piece win and another 30 moves to bring the fruits of it, than waste 15 >minutes and likely not find a mate in 6, then blow the piece advantage later in >the time shortage panic. And in reality no one will tell you that there is a >mate in 6, and odds are generally near 1 that there isn't one. So, of course, I >wouldn't spend time looking for one. Odds are small that there is one and even >if it is one of those rare cases when there is one, odds are small I'll find it >(unless it's some forced sequence), and even if I were able to find it, odds >that the piece only advantage would have lost, while mate in 6 has won, are >small too. So the odds that looking for possible mate in 6 in a position I am a >piece ahead, I would score more game points are astronomically small, and given >the price (in time), on balance, with that strategy I would gain fewer game >points than with the less ambitious one.
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.