dynamically modified evaluation function

[SuneF]

On the other hand I am prejudiced against null move, an algorithm that I feel is far uglier than history. History can do no damage, it's just advisory but null move is based on inserting an illegal move into the game tree, embracing zugzwang problems and other such ugliness. Nevertheless, I still have to use it because it works.

In order of ugliness, killer moves and history is not even on the list, these are powerful statistical concepts. GHI and null move is at the top of the ugly list.

I think very few of us really like null move, its inherent blindness makes the program look very stupid in certain positions. On the other hand it is very good at telling us what kind of threat the opponent has, although exploiting this in a clever way is difficult. If he threatens to take my queen I should do something about it, like moving it, but where to? Probably moving the queen would be a stronger move than capturing a pawn. However this calls for a very advanced move ordering scheme which is still on my todo-list.

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.

[Daniel Shawul]

It's silly that the search instability idea was used almost like a proof that the idea is no good. (It may be no good, but not for this reason.)

Wrong. History information is unreliable in the first place. LMR gains you a tad more than history does. The search instability is acceptable there like null move's is.
Now you pick on something that is very doubtful, add a search instablility like i never seen before, and expect it to work. Don't be surprized if some people are pessimistic about it.

The "potential" in the idea is the concept that evaluation is unreliable and history is more reliable (or less unreliable if you prefer.)

This is more than just tactics in my opinion. Obviously a move is usually bad if placed on a square where it is left hanging, but there are many evaluation concepts that are based on future tactics such as weak pawns, king safety, trapped pieces, and so on. History might capture this in a way that is especially appropriate to the local situation.

This path dependency of the eval is very nasty stuff. It will more or less break the hashing resulting in a lot of researching. And it probably gets worse the deeper you search.

I once tried draw detection heuristics of this kind, iirc the idea was that if alpha > 0 and we are repeating our side position, then evaluate as draw. This broke the hash pretty badly and it started detecting every tiny shuffle as a draw.

It seems that it is ok to let the search use information from the eval, but to let the eval use information from the search is very dangerous.

Sadly the hash really prevents a lot of interesting heuristics from working. Think how easy it would be to detect fortresses by simple "no progress" evaluation terms if we got rid of the hash.

Finally someone who sees it as it is !
The kind of randomness introduced by the history to eval very much sounds like something suitable for a MC type search. PVS/MTDf and eval() which changes every time a position is re-visited is a no no..
We don't use MC in chess except maybe in some endgame analyzers, and blocked positions to detect draws due to repetition and fifty move counters. For GO it is effective because it is difficult to design a deterministic evaluation.
I tried to write a GO engine once named Go!ndar but got frustrated with lack of eval terms. Even for checkers before I knew of alpha-beta, static evaluation, I was able to encode patterns which surprized some of my friends. No search just look up the pattern and make move. If it isn't there move the piece to a square that doesn't hung it up or give it as a free gift. It was actually difficult to beat for a beginner.

[Daniel Shawul]

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...

[bhlangonijr]

It's silly that the search instability idea was used almost like a proof that the idea is no good. (It may be no good, but not for this reason.)

Wrong. History information is unreliable in the first place. LMR gains you a tad more than history does. The search instability is acceptable there like null move's is.
Now you pick on something that is very doubtful, add a search instablility like i never seen before, and expect it to work. Don't be surprized if some people are pessimistic about it.

The "potential" in the idea is the concept that evaluation is unreliable and history is more reliable (or less unreliable if you prefer.)

This is more than just tactics in my opinion. Obviously a move is usually bad if placed on a square where it is left hanging, but there are many evaluation concepts that are based on future tactics such as weak pawns, king safety, trapped pieces, and so on. History might capture this in a way that is especially appropriate to the local situation.

This path dependency of the eval is very nasty stuff. It will more or less break the hashing resulting in a lot of researching. And it probably gets worse the deeper you search.

I once tried draw detection heuristics of this kind, iirc the idea was that if alpha > 0 and we are repeating our side position, then evaluate as draw. This broke the hash pretty badly and it started detecting every tiny shuffle as a draw.

It seems that it is ok to let the search use information from the eval, but to let the eval use information from the search is very dangerous.

Sadly the hash really prevents a lot of interesting heuristics from working. Think how easy it would be to detect fortresses by simple "no progress" evaluation terms if we got rid of the hash.

You might be right, but I would have to try this for myself.

One big problem I see is that it might simply slow down the search too much. The "ideal" move ordering would change from iteration to iteration.


A simple test is to try making random modifications of evaluation function weights (or the piece square tables) between iterations and see how it affects things.

I think the idea is sound. And I very much like fresh ideas.

While I have to agree with some here that changing dynamically the pst with the history - the way it is commonly presented in most programs (history[from,to]) - is not reliable for static evaluation purposes. In the other hand, fixing piece square values with a relevant information gathered through search will probably improve the quality of moves on the top of your move list. Although using these values to feed the static evaluation is something we need to do some tests to see how it would work.

Before going for this I think it would be really helpful revisiting history heuristics alternatives/improvements. I remember a very nice and productive thread http://www.talkchess.com/forum/viewtopic.php?t=29611 where HGM, Marco, Hyatt and Edsel Apostol were discussing new ways of doing that. The modern search algorithms are so selective and it goes so deep that the history table becomes very saturated - and meaningless.
Summarizing, one may draw from the whole thread that we need to construct a history indexed also by the material balance in order to make it more reliable. HGM suggested creating "chunks" in which you would update history according to a depth range: [1-5][6-10]... something like that. Edsel suggested something more interesting - in my point of view - which is index the history table also by the number of remaining pawns on the board. You should have a look - if you still haven't.

The point is having a more reliable history heuristic is very important to make the idea work. I will give a try on this in the next days.

[Michael Sherwin]

On the other hand I am prejudiced against null move, an algorithm that I feel is far uglier than history. History can do no damage, it's just advisory but null move is based on inserting an illegal move into the game tree, embracing zugzwang problems and other such ugliness. Nevertheless, I still have to use it because it works.

In order of ugliness, killer moves and history is not even on the list, these are powerful statistical concepts. GHI and null move is at the top of the ugly list.

I think very few of us really like null move, its inherent blindness makes the program look very stupid in certain positions. On the other hand it is very good at telling us what kind of threat the opponent has, although exploiting this in a clever way is difficult. If he threatens to take my queen I should do something about it, like moving it, but where to? Probably moving the queen would be a stronger move than capturing a pawn. However this calls for a very advanced move ordering scheme which is still on my todo-list.

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.

Using hash to only store the best move gives more than just doing cutoffs. Cutoffs are kind of minor really. So, if there are ideas that are good if it were not for the hashing of cutoffs then maybe do not use hash for that purpose. For a long time Movei only used hash for move ordering, so, maybe Uri can tell us how much elo he gained when he added pruning to Movei's hash function.

[abulmo]

Well, for this discussion, score == eval() (depth=0 search). So if the eval is the same for both moves,
I am saying it doesn't matter which move we pick.

This is only true if the evaluation is perfect. With an imperfect evaluation, it may happen that one of the two moves is actually better, i.e. make you win the game and the other one no. In that case, a good move ordering may pick up the right move and make the program stronger despite of its poor quality evaluation.

[SuneF]

Using hash to only store the best move gives more than just doing cutoffs. Cutoffs are kind of minor really. So, if there are ideas that are good if it were not for the hashing of cutoffs then maybe do not use hash for that purpose. For a long time Movei only used hash for move ordering, so, maybe Uri can tell us how much elo he gained when he added pruning to Movei's hash function.

Transpositions play a major role in the endgame, far more than LMR or null move. I don't think you can ever get 35+ plies without a TT.
In the middlegame though I think there is some prospect.

[jwes]

On the other hand I am prejudiced against null move, an algorithm that I feel is far uglier than history. History can do no damage, it's just advisory but null move is based on inserting an illegal move into the game tree, embracing zugzwang problems and other such ugliness. Nevertheless, I still have to use it because it works.

In order of ugliness, killer moves and history is not even on the list, these are powerful statistical concepts. GHI and null move is at the top of the ugly list.

I think very few of us really like null move, its inherent blindness makes the program look very stupid in certain positions. On the other hand it is very good at telling us what kind of threat the opponent has, although exploiting this in a clever way is difficult. If he threatens to take my queen I should do something about it, like moving it, but where to? Probably moving the queen would be a stronger move than capturing a pawn. However this calls for a very advanced move ordering scheme which is still on my todo-list.

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.

Using hash to only store the best move gives more than just doing cutoffs. Cutoffs are kind of minor really. So, if there are ideas that are good if it were not for the hashing of cutoffs then maybe do not use hash for that purpose. For a long time Movei only used hash for move ordering, so, maybe Uri can tell us how much elo he gained when he added pruning to Movei's hash function.

I have been doing endgame analysis and find exactly the opposite.

[SuneF]

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.

[Daniel Shawul]

Well, for this discussion, score == eval() (depth=0 search). So if the eval is the same for both moves,
I am saying it doesn't matter which move we pick.

This is only true if the evaluation is perfect. With an imperfect evaluation, it may happen that one of the two moves is actually better, i.e. make you win the game and the other one no. In that case, a good move ordering may pick up the right move and make the program stronger despite of its poor quality evaluation.

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. Alpha-beta has only the bounds (the PV is aesthetics) that get transmitted
from one part of the tree to the other. 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.

To really effect the move ordering as a way of move selection, you need to change the eval itself.
No escape from that because alpha-beta has the bounds only (not where its location in the move ordering is).
Changing the eval with information from the path introduces other problems though.

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