Author: Peter McKenzie
Date: 20:43:50 11/06/00
Go up one level in this thread
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
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.