Author: Christophe Theron
Date: 22:22:05 11/06/00
Go up one level in this thread
On November 06, 2000 at 23:43:50, Peter McKenzie wrote:
>On November 06, 2000 at 22:18:13, Robert Hyatt wrote:
>
>>On November 06, 2000 at 16:43:26, Christophe Theron wrote:
>>
>>>On November 06, 2000 at 13:17:34, Bruce Moreland wrote:
>>>
>>>>On November 06, 2000 at 11:59:49, Christophe Theron wrote:
>>>>
>>>>>Tiger uses several different pruning mechanisms (some are well-known, some are
>>>>>more obscure) in combination with each other. Usually when you do that you
>>>>>weaken your program. Part of my work has been to teach these pruning algorithms
>>>>>how to live together without burning the house.
>>>>>
>>>>>In the past 5 years I have worked 80% of the time on search, and I believe I
>>>>>have "invented" several interesting pruning mechanisms. I'm pretty sure however
>>>>>that other programmers have "invented" them as well, but maybe nobody else
>>>>>managed to have all of them working together?
>>>>
>>>>I think you are probably on the right track with this.
>>>>
>>>>>I do a little of root processing for obvious things. But most of my evaluation
>>>>>is done in the leaves. For example, king attack evaluation is done in every
>>>>>node.
>>>>>
>>>>>My make/unmake routines update evaluation terms incrementally instead of
>>>>>computing everything from scratch at each node. It is much more difficult to
>>>>>work like this, because your make/unmake routines become pretty complex.
>>>>>
>>>>>Just one example: evaluation of "rooks on open files". The term is re-evaluated
>>>>>if the program sees that the move:
>>>>>* moves a rook
>>>>>* moves a pawn on another file
>>>>>* captures a rook
>>>>>* captures a pawn
>>>>>
>>>>>So you can imagine what a mess it is when you add 20 or 30 additional terms...
>>>>>But it works. This is also why bitboards would not help me much.
>>>>
>>>>I tried a simple form of this recently. If you hash pawn structures you can get
>>>>that information pretty quickly, so it is easy to write an incremental evaluator
>>>>if you evaluate pieces only via their location and relationship with pawns.
>>>
>>>
>>>
>>>I indeed store specific informations designed to speed up the evaluation update
>>>in my Pawn hash table.
>>>
>>>With the "rook on open file" example, the evaluation of the term is just playing
>>>with some bit fields set up in the pawn structure evaluation, it's not very
>>>expensive.
>>>
>>>
>>>
>>>
>>>>But
>>>>that kind of eval is very simple and misses a lot of nuances. For instance,
>>>>rook on the 7th should be more potent based upon the location of the enemy king.
>>>> It sounds like you are talking about something more complex.
>>>
>>>
>>>
>>>Yes. The terms I update in make/unmake are second order terms.
>>>
>>>
>>>
>>>
>>>>I've thought about building some sort of dependency tree but I couldn't figure
>>>>out a fast and manageable way to implement this. That would be really cool if
>>>>it could be done, because you could add terms, hook up a few wires, and the
>>>>program could manage the whole thing itself.
>>>
>>>
>>>
>>>I did not design the whole thing right from the start. It started as a very
>>>simple evaluation in which I added terms little by little, trying to insert new
>>>bits of code as elegantly as possible into the existing structure.
>>>
>>>I did not like the idea to have my eval code and make/unmake code interleaved at
>>>first, but it turned out to be the only way to do it efficiently. Make/unmake
>>>handles information that can be directly used to update the evaluation, it does
>>>not make sense to have a separate update eval code retrieving those informations
>>>once make/unmake has been executed.
>>>
>>>
>>>
>>>>As of now mine is a tip evaluator, it just goes through the piece lists and does
>>>>it, mostly. Some stuff is kept incrementally but it's not important stuff.
>>>>
>>>>>I almost don't use lazy eval. Obviously, it would not be work with Gambit
>>>>>Tiger's huge positional evaluation of king safety.
>>>>
>>>>I did have working lazy eval until recently. I had some big-term unavoidable
>>>>stuff I did at the beginning, but some other stuff was pretty expensive but
>>>>couldn't produce really big terms. So if I knew that I was out of the window,
>>>>and the rest of the eval couldn't get me back within it, I could prune out some
>>>>pretty expensive stuff.
>>>>
>>>>As of now I'm doing king safety last, so that does sort of throw the lazy eval
>>>>idea out.
>>>
>>>
>>>
>>>Above a given level, lazy eval prevents you to improve your program. Lazy eval
>>>is a poisoned gift.
>>>
>>>And maybe the reason why most programmers don't want to or even cannot give huge
>>>values to some positional terms.
>>>
>>
>>
>>This is simply _wrong_. Lazy eval can work no matter what you do with large
>>positional scores, _if_ you do it right. I have positional scores that go
>>way over a queen. I have no problems with lazy eval at all. You just arrange
>>the scoring code to do the big items first. Then, as you refine the eval, you
>>can lazy-out along the way...
>>
>>Everybody has used this forever. It might take a bit of work, but I don't
>>see it being any different than using alpha/beta, _if_ it is done right.
>
>Bob, I agree with you in theory but in practice I found that it just wasn't
>worth it. In my eval, alot of the big terms are the most expensive to calculate
>so I wouldn't gain alot anyway.
That's exactly what I was going to post.
It is logical to think that the positional terms that have very big weights have
to be attributed very carefully, so they are likely to require more
computational effort.
One example of this is king safety: you have to take into account many different
things including the kind of position, the structural protection, coordination
of the attackers and coordination of the defenders, then mix them all together,
and so this is one of the most expensive term to evaluate.
Of course, if you force your king safety eval to be in the [-0.9;+0.9] range,
then you can use a small lazy eval window and you'll have to call the KS code in
less than 10% of the positions seen.
But if you allow the KS eval to range in the [-9;+9] range, then you'll call the
KS code in more than 80% of the nodes, making lazy eval almost useless.
>I also found that if I was experimentally scattering big terms around my eval, I
>would keep having to re-arrange the eval function for purposes of lazy
>evaluation which was a hassle and made it easy to introduce bugs.
>
>Another thing was that some types of pruning work better without lazy eval...
Yes! Lazy eval introduces more inconsistencies between re-searches, and badly
confuses some pruning algorithms.
>So, from a practical perspective, I'm with Christophe no this one. Have been
>for a couple of years or more.
:)
Christophe
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.