Author: Andrei Fortuna
Date: 16:51:37 04/09/01
Go up one level in this thread
On April 09, 2001 at 17:04:09, Vincent Diepeveen wrote: >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. As far as I can tell futility & co algorithms are sound provided that you are 100% sure that abs(eval_score-material_score) < maximum_positional_bound. The lower the bound the better, but if it's too low as it was already said in this thread it will wreck your king safety & so forth. Too bigger bound will make futility useless. In my eval() I cannot guarantee that all my scores returned will be bounded by a good enough value so I don't do futility anymore. >I always try all interesting moves in qsearch, no way to escape from that. May I ask if you do some non-captures too in your qsearch ? Other then checks I mean, I'm sure you do those IIRC from another thread. >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. I know the feeling, once upon a time I modified my qsearch to try all captures instead of only SEE-winning ones and my program started to play much cleaner chess. At the same time the search tree got much bigger and my program started to get to lower depths than before, which was unacceptable to me. >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. If you put the terms with the big scores in front of the eval and then do lazy eval there is no problem there. >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. Now that's an interesting idea : a function that will guestimate the maximum error due to big positional scores in a position, i.e. quickly identify which of the n big score elements are inside the position and return a superior bound. The problem is to identify those elements, which I'm not sure it can be done fast enough. >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) ? This is something I didn't think about before, it never occured to me to question which score to return in case of lazy eval, I always blindly returned eval. >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. I wasn't talking about forward pruning & lazy evaluation, I was talking about the more recent futility pruning. I see it as natural for all programs - now that enough cpu-power is available - to give up to not-so-theoretical-sound-tricks in favor of more accuracy. >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. Don't you mean forward instead of futility above ? >>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. I think it's not ready for it. I came to the point where I did most of the technical tricks I could in my program and I must greatly improve my eval function. The tests that I'm looking for are those that will show the knowledge weakneses in my evaluation, not the ability to think deep enough to see some gain. As an alternative I could and probably I will invite a chess master friend to my house for a weekend (I'm a weak chess player so I need expert help) and let Freyr play against some other engines much stronger and make my own set of positions where Freyr's knowledge can be improved, but it's a slow process and I was looking for a quick way to achieve the same goal.
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.