Author: Reinhold Gellner
Date: 23:29:25 10/19/97
Go up one level in this thread
On October 19, 1997 at 10:36:35, Robert Hyatt wrote: >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... :) To eliminate that problem, try increasing the search depth by 2 ply every iteration. Reinhold
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.