Author: Christophe Theron
Date: 11:39:57 11/07/00
Go up one level in this thread
On November 07, 2000 at 10:20:14, Robert Hyatt wrote:
>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.
>>
>>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...
>>
>>So, from a practical perspective, I'm with Christophe no this one. Have been
>>for a couple of years or more.
>>
>>cheers,
>>Peter
>
>
>To each his own, of course. I didn't find it much of a problem to do the big
>terms first, then the smaller ones, and finally the really small ones, which are
>actually (for me) the most expensive to compute because the small terms are
>computed for all pieces.
>
>However, think about this if you want to _really_ do it right (I did this in
>Cray Blitz, but not in Crafty): You can _easily_ compute the min and max value
>each piece can add to the positional score. And as you make moves that capture
>pieces, you can subtract the min/max value from that piece from an error
>estimate. And now your lazy eval can be _perfect_ because you know _exactly
>how big the largest or smallest positional score you can possible compute with
>the present pieces on the board.
I don't see how it could work unless all your evaluation is first order.
As soon as you have terms which involve the coordination of several pieces
together, it does not work anymore.
This is exactly the case in the king safety evaluation, which happens to have
big values in some cases for me.
Christophe
>Lots of ways to skin the same cat. I like the staged approach I use now. It
>requires less work when I retune the evaluation. The old approach required the
>manual computation of all the individual error terms for each piece. Which was
>a miserable exercise.
>
>But if you don't like lazy eval, do you do futility pruning in the q-search?
>this is the _exact_ same thing.
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.