Author: Ratko V Tomic
Date: 00:56:14 10/14/99
Go up one level in this thread
>> 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). 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. > >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. 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. >> 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. > >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. 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.