Author: Vincent Diepeveen
Date: 14:04:09 04/09/01
Go up one level in this thread
On April 09, 2001 at 16:01:18, Andrei Fortuna wrote: >So far I've been rewarding some positional terms like passed pawns, connected >passed pawns and so forth, also I'm penalizing king unsafety - with pretty much >big scores, so to some positions the positional score gets outside an interval >[-X * PAWN_VALUE .. +X * PAWN_VALUE] where X is about 2 in my case. This hurts >in two areas : futility pruning and when I try to bail out of qsearch based on >material score + swap value + some constant value. Yes get rid of the futility pruning and other weird forward pruning assumptions. The more terms you have the worse such dubious algorithms work as they limit in fact the positional score a position can get and it will bigtime mess up move ordering so the speedup the evaluation gets because of it is usually compensated by the increase of nodes you need to search the tree. We still didn't talk about the dubiousness of it then. I always try all interesting moves in qsearch, no way to escape from that. Even if evaluation of this position is 3 pawns lower as alpha i still try pawn captures. Score can jump bigtime, also the search gets a better value back for this position when i try that pawn capture. The last is very important for my program at least. >What I want is to be keep the positional score inside that interval, that's easy >if I reduce the positional scores and drop those big bonuses/penalties but I'm >sure there are positions where the new small scores will make my program lose >(for example by not sacrificing a bishop to make way for a passed pawn). Most >occur in endgame (where futility is turned off) but there are quite a few >middlegame cases (especially the BAD_TRADE penalty for trading N+K for R+P will >add +/- 1 PAWN_VALUE to the material score) >What is the most common approach used for this problem ? Just ignore the big >bonuses and perhaps add some extensions in the idea that if the search doesn't >see it improving the score in the next plies it might be a false bonus to start >with ? I'm not very fond of this method. Keep the big bonuses and use futility The common approach is to get rid of futility pruning at a certain point, or simply accept a compromise. An interesting thing is lazy evaluation, as the problems of it are very similar to futility pruning. A possible compromise i found in tests was to increase the margin. When i measured the average *compensation* a position can get when a certain side is ahead of material, i figured out that a quick evaluation function (which did some big scores) was off by no more as 3 pawns in 99% of all positions, positions with passers i didn't try to estimate at all btw i always evaluated those full in the experiments. So then i tried a 'lazy evaluation' cutoff at 3.5 pawns. My big question was: what score to return for example if evaluation in this position is e and e+ 3.5 pawns <= alfa ? Must one return alpha, estimated evaluation or evaluation+3.5 pawns, when talking about e+margin <= alfa (idem story for e-margin >= beta) ? Of course by far best for move ordering is giving back estimated evaluation. Estimated evaluation is of course very risky to return whereas e+3.5 pawns is less risky though usually going to be very close to alpha and most safe to return is alpha itself. I tried in most experiments returning e+3.5 pawns. That was however hurting especially for positions which were found by king safety in testsets and even if i didn't care for that, then still the node increase was the big problem. At depths reached after a few minutes of search the searchtimes didn't get smaller. Like 10 ply i get quick with this trick, but then branching factor became huge. Now i always had a pretty cool branching factor for DIEP (unless i turn on about all extensions i can imagine, which are turned on nowadays in diep) In short this test which i tried for several years and sometimes i repeated it simply didn't work for me. It did increase my nodes a second, but didn't decrease my search times a ply at tournament level. >anyway, even knowing that in some cases it might be bad ? I definetely don't >like this approach, that's why I don't do futility right now. Any other >ideas/tips ? The tip is to closely look to how most commercial programs have been changing. From bigtime forward pruning and bigtime lazy evaluating programs many years ago, only nullmove seems the algorithm that survived last 10 years as pruning algorithm and will survive the future too. The other pruning mechanisms seem to get used less and less, and lazy evaluation and futility pruning is getting seen less and less too in nowadays engines. >P.S. : Is there a test suite that contains >= 90% positional tests ? I.e. not >(quick) material gains, but moves that will improve the position for the current Nearly all testsets are big tactical problems. A real interesting testset is for example reiter, but i doubt that your program is ready for it. Most programs solve several positions in the testset for the wrong reason, then the next version has again 50% chance to not solve the position. LCTII testset contains some anti nullmove positions which you can safely ignore, but also a few interesting positions to test at, though again i doubt whether most programs solve for example Bh3 for the right reason. This definitely isn't a move a program should play at 5 or 6 ply. Many positions are real hard positions which can be found by some wrong tunings of parameters (or exaggerated tunings) but there definitely is loads of material by getting some informator books and start analyzing games with comments from the strongest grandmasters on this planet! >player (like making an isolated pawn for the adversary, weakening opponent's >king safety, that kind of stuff) ? Many positions in testsets can be solved by king safety, like i do with DIEP sometimes. Tiger is an even clearer case of aggressive king safety. It solves many positions out of gs2930 for that reason without seeing the difficult and deep lines which all of the 2930 positions need IMHO before one should play the move. Testsets are made by non programmers and the big majority of nowadays positions only will weaken your engine or make a bigger patzer out of your engine if you tune for it, whereas positions which programmers use to debug their program usually are everything but publicly available. >P.P.S. : Sorry for my rusty language, I've been out of chess programming for a >number of months and now I find a little bit difficult to express my ideas. :)
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.