Author: Chris Whittington
Date: 05:52:02 10/20/97
Go up one level in this thread
On October 20, 1997 at 02:29:25, Reinhold Gellner wrote: >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. This is a surprisingly well used solution. But increasing by 2 each iteration loses much of the advantage of iterating (guided search and 'small' incrementally deeper researches). You need to jump by two every two iterations, and find a method for what to do in the 'gap' iteration. Its also an advantage for an exchange-evaluator to stop on odd plies, rather than even. Its decisions that an as yet untaken piece is actually lost will be better taken if the piece is a computer piece (odd ply) than a human piece (even ply). Asymetric safety factor skandal for Komputers !. Best then is to jump by 2 ply every two iterations and use a pruning function over the final plies that is strong pruning the first iteration and weaker pruning the second - then jump two plies again and so on. Of course this is all gobbledegook for the fast/crafty/fritz paradigm since they (a) don't exchange evaluate and (b) have anything remotely like a pruning function operating over the higher plies. Gobbeldegook for the 'programmer-programmers', perfect sense for the 'chess player-programmers' :) Chris Whittington > >Reinhold
This page took 0 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.