Author: Robert Hyatt
Date: 07:36:35 10/19/97
Go up one level in this thread
On October 19, 1997 at 01:36:26, Christophe Theron wrote: > >On October 18, 1997 at 23:57:58, Robert Hyatt wrote: > >>On October 18, 1997 at 23:47:24, Willie Wood wrote: >>>I've noticed that some programs (incl mine) show a pv score oscillation >>>as the ply increase. >[snip] >> >>there are at least two things you can do: >> >>1. add some wtm (or btm) bonus, so that if one side gets 5 moves in a >>PV, but the other side only gets 4, that side gets the "on move" bonus. >[snip] >>2. selective programs can bias the selectivity to try for an even >>number >>of moves in the PV, or an odd number if you like the extra >>aggressiveness >>this gives. >[snip] > > >An interesting debate. The oscillation has at least 2 bad effects: > >1) If two or more among the best moves are evaluated very close, the >program could "randomly" choose one at an even ply depth, another one at >the next ply depth (doubling the time to complete that depth), and go >back to the first move at the next depth. So the total computing time >could be two or three times smaller without the oscillation (not on >every move, but often). All this time lost to get a move with 0.01 >points more! > >2) the time management algorithms can be confused by a "floatting" >score. I use a simple sheme that gives my program more time when the >score of the computed PV falls well below the score computed at the >previous ply depth. If you realize your move is bad, it could be wise to >take more time to see if there is a better one. If the oscillation is >strong, my program can believe it's going to make a mistake, and think >more, on every move. > >Of course, if the evaluation function was perfect, we would choose the >best move at ply 1, and have the right score from ply depth 1 to >infinite. So the oscillation of an evaluation function (among other >things) could be used to measure its "perfection". > >We cannot have a perfect evaluation. So I tried the following: > >1) As Bob said, give the side to move a slight bonus, assuming it surely >has a move to improve its score. Of course, this is false when the side >is in zugzwang. But it is false more often than that. In the middlegame, >the first case I remember is a knight in the middle of the board (Tiger >loves that). If it is your move, with white, and your knight is under >attack on e5, you have to put it back on f3, and your score will >decrease. So it is clear that adding a bonus in that case could make >things even worse. > >2) Ok, so generally the side to move could get a slight bonus EXCEPT >when it is under attack. But it is not wise in that case to leave things >without knowing what will happen. So if the side to move is under attack >at the end of the line, extend one more ply. Mr Shanon would be glad to >hear this. He said "evaluate only quiet positions", and most of the >programmers interpreted as "evaluate only if the side to move has no >good capture, promotion or check", ignoring if the other side has a good >capture/promotion/check itself! But doing such a "real quiescence >search" really gives huge trees (sorry Mr Shanon). I tried. Maybe you >could try doing it on just 1 or 2 plies. There are really good >commercial programs using this concept (no names). It fits well for >positional programs, and sometimes you see combinations faster (but on >average it is worse for tactical play). Yes, extending threats mainly >serves positional purposes! > > >I tried, and rejected both of the above. Today, I still have the >oscillation problem. I would be pleased to read other ideas from other >programmers... > > >- Christophe - As I said, this killed my MTD(f) tests, because to make this work well, the window (alpha,alpha+1) needs to be centered on the correct score, or very close to it. My scores vary a lot from iteration to iteration. on occasion. On other occasions they are quite stable. I gave up worrying about it... :)
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.