dynamically modified evaluation function

[Gerd Isenberg]

Don't worry Mike. All the nice people here have a sense of humor
I didn't even want to mention your name , if I was not cornered to point where I am supposed to feel like a shameless pessimist. Apology is mine.

Anyway, I strongly agree with you that many experiments on the LMR have been done before crafty started using them. I also hope to get a piece of the cake too with the "in pv reduction" and "no history data " . You know ,lately the inventions of these kind of things have been smartly being awarded to people I don't know in the past No paper,source or even forum post. I really don't like this at all. I guess people like it better if it is credited to someone unknown.. History reductions were sole property of glaurung/fruit... nobody uses history now... and suddenly its credit went to the 70's.

So in short, I appreciate your effort and standing to them as much as you can.

cheers

No idea which people awarded you refer to. On LMR, after re-reading the Levy, Broughton, Taylor 1989 ICCA paper on search techniques in their dedicated commercial programs from the early/mid 80s, it seems to me not only fractional extensions should be credited to them, but also LMR.

David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1, pp. 10-21.

[Uri Blass]

Also on my ugly list is hashing. Practially it would be a lot easier to evaluate certain things dynamically through search. For instance how about giving a reward for number of checks? On the board I would always play the move which gave me the best attacking chances, even if there was nothing concrete in view.

Path dependent evaluation is bad because the premise is the path taken to reach the position is more important than what the eval says. Except for a few concepts used in the endgame, I do not see how that could be more important than the static eval.
For example in your example of evaluation of blocked positions, someone told me of a static way of evaluating some draw positions ("Averbahk's" rules IIRC) which happend to work more than I expected. Then I tried to incorporate the fifty move count in the eval too. It suddenly starts to mis-evaluate the blocked positions...

Yes well I don't think it is realistic to write static detectors for all the different kinds of fortresses. Even if you did it would probably be too slow to use.
By using the search you can classify a large number of positions without writing code or knowing any details about them. In the case of fortresses they have one thing in common: the winning side cannot make any progress. The search can tell us when progress has stopped by looking at repetitions or the 50 move counter.

If you are at +5 but nothing has happened for 10 moves maybe the static evaluation is being too optimistic.

If engines had this kind of knowledge we would probably be seeing less shuffling and maybe the engines would build fortresses themselves when in trouble.

Anyway fortress detection is just one possibility with search based evaluation, there are many others.

Yes and movei is using path dependent evaluation not for fortress and surprisingly I found that it is productive even with hash tables but I may have bugs in my hash implementation because there are cases when movei does not detect draw by repetition even if they do not happen often.

Using hash for pruning helped movei inspite of the bugs and I guess that I earned something like 50 elo by using hash for pruning.

My path dependent evaluation to encourage progress help for movei but maybe it is because of other ideas that I use and also because of the bugs in my hash implementation(one of the idea that I use is using changes in the evaluation function in my hard pruning decisions(return alpha instead of search based on the evaluation) and I am more aggresive in hard pruning when the remaining depth is small in case that the evaluation goes down relative to the evaluation 2 plies earlier.

[Daniel Shawul]

Gerd,
I do not have that paper so I can not read what is in there. The history reductions as first implemented have _history_ data in them, which was crucial in their original implementations. Collect the number of fail highs and fail lows, take ratios etc.. Why do they do that if they don't think it was necessary ? These is the whole part of history reductions. It is like you do not consider fail high reductions without eval(). It doesn't matter now the reductions are done with history or not.. the original implementation has it.
So the algorithm should be considered in its entirety. Do the SEX algorithm use the history in that way ?

[Daniel Shawul]

To make this more clear, originally all moves > 2 are treated equally. The "late moveness" came in later. So originally "UNITDEPTH" reduction for any move with that "intricately calculated history ratio" fails below a certain percentage. The "fail lowness" of the node was determined that way , not necessarily from its position in the move list, which I believe is very cruciual.
That algorithm could have worked for any move ordering (not necessarily history ordered), or even unordered move list except for the first 3...
Now it is different reductions based on location of move list (LMR).

[abulmo]

To make things clear, the move ordering can only play a role at the root. We collect the PV only for aesthetical reasons, it doesn't matter which move
is in the PV.

Are not PV moves future root moves? I used to believe that when ordering moves at root, the first move to consider is the best move known so far, which is usually a move that was in the PV (at least when the opponent played the guessed PV move).

Alpha-beta has only the bounds (the PV is aesthetics) that get transmitted from one part of the tree to the other.

I am not sure to understand. It sounds like the program has no memory of what has been done before and that the alphabeta bounds are the only information available. What are hashtables, killermoves, history tables, etc. made for?

Move ordering can play a role in the move selection process only at the root. The move with largest number of nodes is selected in case of equally good moves, if you order by nodes searched f.i.

Usually, the first move tried is the one coming up from the hashtable. And all other ordering heuristics play a role at some time to store a best move in a hashtable.

To really effect the move ordering as a way of move selection, you need to change the eval itself.

Of course, the eval itself is important, but it does not means that ordering has no influence.

For a selective search which doesn't visit all the possible moves, the story is different as already mentioned somewhere in this thread.

Which definitively makes move ordering of crucial importance.

[Daniel Shawul]

Not to distract away from the topic in this thread, I want to remind you that
we are talking about the very rare case of two moves equally being good, and a _brute force_
search. If one of the moves is a millipawn better than the other then that one will always be choosen.

Lets say you have two equally good moves at ply 8 with a score of +0.4. Alpha-beta
uses the scores only so no "order of move" information is transmited to the root or anywehere.
If you want that change the eval slighly f.i by its rank in the movelist or something similar, otherwise the root's score is either 0.4 or -0.4 if it is part of the pv.

I am not sure to understand. It sounds like the program has no memory of what has been done before and
that the alphabeta bounds are the only information available. What are hashtables, killermoves, history tables, etc. made for?

Those are move ordering enhancements which don't matter for brute force search at all.
They make the search faster but don't contriubte to the overall play.
Even if we talk about a selective search, the hashtable stores only score and _one_ move,
not the whole PV. Which also stresses the fact that Unless you modify that score with the path (PV) information below, then
it doesn't get transmited anywhere.

Usually, the first move tried is the one coming up from the hashtable. And all other ordering heuristics play a role at some time to store a best move in a hashtable.

Quote:
To really effect the move ordering as a way of move selection, you need to change the eval itself.

Of course, the eval itself is important, but it does not means that ordering has no influence.

Quote:
For a selective search which doesn't visit all the possible moves, the story is different as already mentioned somewhere in this thread.


Which definitively makes move ordering of crucial importance.

You seem to have missed we are talking about brute force again and again
I mentioned it in my first reply to the OP, and also Joona mentioned it as well in
his reply.

Hint for selective search : It is not that the move ordering is used as a kind of evaluation as implied
by the OP, but we are completely searching different trees. If you select only the first few good moves and
discard the rest,then chances are you can do one more iteration. Thus making the engine play stronger.
This is how the move ordering plays a role in the move selection, not because the search magically starts
to differentiate between two good positions where the eval says are equal. Move ordering is a major enhancement
to alpha-beta without changing its behaviour.

[Gerd Isenberg]

Gerd,
I do not have that paper so I can not read what is in there. The history reductions as first implemented have _history_ data in them, which was crucial in their original implementations. Collect the number of fail highs and fail lows, take ratios etc.. Why do they do that if they don't think it was necessary ? These is the whole part of history reductions. It is like you do not consider fail high reductions without eval(). It doesn't matter now the reductions are done with history or not.. the original implementation has it.
So the algorithm should be considered in its entirety. Do the SEX algorithm use the history in that way ?

Hallo Daniel,
yes, I will extend the brief summary of that paper which is still available as Back Issue.

They started the first iteration with SX (renamed to SEX in their second generation) of 10, incremented by 7 or 8 in consecutive iterations. In their first versions they only considered static move properties to determine the depth decrement SXDEC (SEXDEC) from 3 (first check) to 7 for tactical moves (also non captures but attacking moves), and 21 for forward and 24 for backward non-tactical moves, and recognized it did not work that well, since all non-tactical moves were reduced too much. They further mentioned experiments in Cyrus 68K, to evaluate and sort all the moves from a node being expanded, to assign a low SXDEC to the best non-tactical move and to determine the SXDEC values for its non-tactical siblings on the basis of the score differences.

They did not exactly state what they did in their second generation of that algorithm from SX to SEX in 1985-1988, history heuristic is not mentioned, which was introduced by Schaeffer in 1983. But definitely they gave an idea of fractional extensions as well as LMR in 1989, even if not called that way. As far as I know, the name LMR was proposed by Tord after Fruits success with History based pruning/reductions in that 2005 CCC post.

Cheers,
Gerd

[Daniel Shawul]

Hi Gerd,
I will get back to your post later but for now allow me to rumble on for a while to get
my perspective about reductions/prunings clearer.

First , we set out to determine which nodes are probable fail high or fail low. Then
we decide to reduce or prune those nodes to reduce effort. Methods used for this step
include the following in order of strength in my view.

Code: Select all

       a) order of moves
       b) fail high/low history  -> I am not sure where to place this as it is a dynamic feature
       c) eval()
       d) SEE
       e) qsearch
       f) reduced depth search

Then you decide to either

Code: Select all

       1) reduce
       2) prune

Now when you combine these two you get all sorts of pruning/reduction methods

At fail high nodes, we have

Code: Select all

       - fail high reductions (c & 1)
       - standard null move (f & 2)
       - null move reductions (f & 1) -> Omid's paper
       - static null move pruning (c & 1)
       - futility pruning (c & 2)
       - razoring (c & 1) | (e & 2) I am not sure

At fail low

Code: Select all

       - History reductions (b & 1)
       - late move reductions(LMR) (a & 1)
       - History pruning (b & 2)
       - late move pruning(LMP) (b & 1)

I am sure there are more ..
Credit has been given to anyone who came up with any of the combinations it seems.
It sometimes bogles my mind of the difference between doing reductions at fail high or fail low nodes.
It seems there is only a "make move" between them. If you don't decide to prune at a fail high node and make
a move, at the next ply you get fail low nodes. So where do you do it? It seems some of them sure overlap ..

regards,
Daniel

[Daniel Shawul]

Edit: razoring & futility prunig goto methods of fail low nodes not the first group.

[Daniel Shawul]

From your summary, I understand that they used

- static properties of moves (is it check,passed pawn push etc...). This is shared
pretty much by all the pruning/reduction methods I mentioned in the other post. These moves are candidates
for extension not reduction or pruning.

- they sorted the moves and reduced differently depending on the location in the move list. This I guess
deserves them late move reduction (LMR)

- Lack of history data for reduction decisons means they don't own history reductions. It doesn't matter it
is not working good now. They also said their method of LMR did not work for them at the time they tried
it but we still gave them credit to it. It works well now. Same story for history reductions too.
Most of us belive they don't work that well for reductions now, some still do. If one day someone comes up
with a better way of collecting history like for example multiple history tables at different depths, then
the credit should still go to those who first use history for reduction purposes. Don't you agree ?

About Tord's post, I guess he felt that since history was not working that well and it was a reduction not pruning, it is better to change the name.
I do not want to speak for someone else so I think it is better to ask him.
Should we consider LMR,LMP,HR,HP variants or not ? If we have to be pedantic and stick to normal trend, then yes.

In general I think history reductions (HR) should be considered different from late move reductions (LMR) to avoid
these confusions. I would really like your opinion on my other post which listed different pruning methods which were
credited to different people.

thanks
Daniel