Accurate eval function

[bob]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

There also is a Glaurung version made by Tord with experimental "standard" evaluation function for these kind of experiments, there was a tournament in Polen I believe where programs competed all with the same evaluation function. You would have to ask others for the details about it. But conclusion seems to be that search depth is effectively increased with a better eval function. I suppose this is about the synergy between eval and search.

Regards,

Eelco

I believe the opposite. You can search far deeper with a material-only eval as the cutoff rate goes way up...

[Kempelen]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

Here we are not programmers.
Please ask your question in the programmers' subforum.

Matthias.

uppsss..... sorry....
Is there any admin here who can move the thread to programmers' subforum?

[Steve B]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

Here we are not programmers.
Please ask your question in the programmers' subforum.

Matthias.

uppsss..... sorry....
Is there any admin here who can move the thread to programmers' subforum?

Done
Regards
Steve

[Uri Blass]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

There also is a Glaurung version made by Tord with experimental "standard" evaluation function for these kind of experiments, there was a tournament in Polen I believe where programs competed all with the same evaluation function. You would have to ask others for the details about it. But conclusion seems to be that search depth is effectively increased with a better eval function. I suppose this is about the synergy between eval and search.

Regards,

Eelco

I believe the opposite. You can search far deeper with a material-only eval as the cutoff rate goes way up...

I think that this is not the interesting question.
I agree that with only material evaluation you can search deeper with the same number of nodes but nobody starts with only material evaluation
and it is easy to write piece square table that is significantly better than only material.

The interesting question is the following.
Suppose you start with some evaluation that is not obviously stupid and later improve your evaluation.

Can you search deeper with your new evaluation or the opposite?

I guess that you can test it with Crafty by seeing if new Crafty can search deeper than old Crafty when you need to have the same search rules and the same number of nodes for both versions.

Uri

[Uri Blass]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

That discussion was about the speed of search in a single, very special position (the opening position), and the point being made was actually that Glaurung searched this position fast because of its (at the time) very bad evaluation function, which allowed it to "refute" strong first moves like 1. c4 with a null move.

About the question asked in this thread: One of the characteristics of a good evaluation function is that it is "continuous", in the sense that in a quiescent position, the static evaluation should be approximately equal to the static evaluation after the strongest available move in the position. Continuity in this sense does improve the efficiency of the search, because the best move and PV won't change as much from one iteration to the next.

However, continuity is not a sufficient condition for a good evaluation function. It is possible to write an evaluation function which is very bad, but still has good continuity, and therefore makes the search efficient. As a trivial example, consider an evaluation function which always returns 0, regardless of the position. The evaluation function is perfectly continuous and gives a blazingly fast and efficient search, but it certainly wouldn't be good.

Tord

I think that the question is what you mean by good evaluation function.

Suppose evaluation A wins if you search same number of nodes and evaluation B wins if you search same depth(for the discussion you can assume some simple search algorithm of alpha beta with no reductions no null move and no extensions except check extensions like tscp is using).

Which evaluation do you consider as better?

I suspect that something like that is possible if evaluation B gives accurate numbers in 1/1000 pawns and evaluation A is almost the same as evaluation A but round the numbers to 1/100 pawns units.

Note that it is only a guess and I did not try to test it.

Uri

[Eelco de Groot]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

There also is a Glaurung version made by Tord with experimental "standard" evaluation function for these kind of experiments, there was a tournament in Polen I believe where programs competed all with the same evaluation function. You would have to ask others for the details about it. But conclusion seems to be that search depth is effectively increased with a better eval function. I suppose this is about the synergy between eval and search.

Regards,

Eelco

I believe the opposite. You can search far deeper with a material-only eval as the cutoff rate goes way up...

Okay Bob I think I can partially agree with that, the material only search would go deep because of good "continuity".

Some random thoughts, sorry if it does not make much sense: if the objective of the game was to gather as much material as possible and not about mating the king, material search only would be the more accurate evaluation function. And if you had an almost perfect evaluation function that took a million years to complete one position, the effective search depth would be still be lousy.

If you have a decent static evaluation so that a one ply search produces acceptable play, but it had the added quality that it never changes its mind over what is the best move (assuming this is at all possible) it would never play better with deeper searches because of perfect continuity. The move ordering would be perfect but also meaningless because search adds zero strength. But that also does not mean that a program is stronger the more it changes its mind about the best move and has totally random continuity the way Tord defined it. It would play random moves, as far as I can see.

If I had two evaluation functions not differing a lot and would not know which is the best, I would pick the one with the most consistent lines. However every program has to change its mind once in a while otherwise the search would have zero effect.

Regards,

Eelco

[bob]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

There also is a Glaurung version made by Tord with experimental "standard" evaluation function for these kind of experiments, there was a tournament in Polen I believe where programs competed all with the same evaluation function. You would have to ask others for the details about it. But conclusion seems to be that search depth is effectively increased with a better eval function. I suppose this is about the synergy between eval and search.

Regards,

Eelco

I believe the opposite. You can search far deeper with a material-only eval as the cutoff rate goes way up...

I think that this is not the interesting question.
I agree that with only material evaluation you can search deeper with the same number of nodes but nobody starts with only material evaluation
and it is easy to write piece square table that is significantly better than only material.

The interesting question is the following.
Suppose you start with some evaluation that is not obviously stupid and later improve your evaluation.

Can you search deeper with your new evaluation or the opposite?

I guess that you can test it with Crafty by seeing if new Crafty can search deeper than old Crafty when you need to have the same search rules and the same number of nodes for both versions.

Uri

Here is the basic idea: evaluation doesn't have a significant effect on the size of the tree. Other that to _increase_ it. Why? Because the shape of the general tree is dictated by alpha/beta and the PV/ALL/CUT nodes, which are dictated not by the evaluation, but by the tree search.

With a simple eval, it is likely you can produce near optimal move ordering (example is material only or material-only + pc/sq tables). As you add more knowledge, all you change is the scores, not the shape of the tree, unless your new evaluation causes some of your move ordering to be less accurate than it was before. I don't see any possible way to make an evaluation more complex, and not make the tree bigger. Otherwise you would gain little from your eval.

Sometimes an eval addition might reduce the tree, because you had some sucky move ordering and this somehow helps. Other times an addition will make the tree larger. But I don't see any rational way it can consistently reduce the size of the tree below that minimum established by the very simple eval.

[Uri Blass]

Assuming a "standard" implementation of common search techniques, does an accurate eval function help to reduce the search tree? I mean, as more accurate eval func more the tree is reduced?

I think the answer is yes, there was a thread in the programming subforum, over a year ago where it was described by Alessandro Scotti how Glaurung managed to search much deeper than Hamsters, he thought a main factor was null-move, and François Karr had done a similar experiment from which he concluded that better search depths in Glaurung compared to BugChess2 were for the most part due to a better evaluation!

I found back the original "Going crazy over Glaurung" thread.

There also is a Glaurung version made by Tord with experimental "standard" evaluation function for these kind of experiments, there was a tournament in Polen I believe where programs competed all with the same evaluation function. You would have to ask others for the details about it. But conclusion seems to be that search depth is effectively increased with a better eval function. I suppose this is about the synergy between eval and search.

Regards,

Eelco

I believe the opposite. You can search far deeper with a material-only eval as the cutoff rate goes way up...

I think that this is not the interesting question.
I agree that with only material evaluation you can search deeper with the same number of nodes but nobody starts with only material evaluation
and it is easy to write piece square table that is significantly better than only material.

The interesting question is the following.
Suppose you start with some evaluation that is not obviously stupid and later improve your evaluation.

Can you search deeper with your new evaluation or the opposite?

I guess that you can test it with Crafty by seeing if new Crafty can search deeper than old Crafty when you need to have the same search rules and the same number of nodes for both versions.

Uri

Here is the basic idea: evaluation doesn't have a significant effect on the size of the tree. Other that to _increase_ it. Why? Because the shape of the general tree is dictated by alpha/beta and the PV/ALL/CUT nodes, which are dictated not by the evaluation, but by the tree search.

With a simple eval, it is likely you can produce near optimal move ordering (example is material only or material-only + pc/sq tables). As you add more knowledge, all you change is the scores, not the shape of the tree, unless your new evaluation causes some of your move ordering to be less accurate than it was before. I don't see any possible way to make an evaluation more complex, and not make the tree bigger. Otherwise you would gain little from your eval.

Sometimes an eval addition might reduce the tree, because you had some sucky move ordering and this somehow helps. Other times an addition will make the tree larger. But I don't see any rational way it can consistently reduce the size of the tree below that minimum established by the very simple eval.

I agree that you can search deeper with only material evaluation because with only material evaluation most of the scores are the same so you more often get cutoff by the first move.

If you have piece square table evaluation then you usually get different scores for different moves so the factor of having the same score for different moves does not happen and it is not clear to me that you will get smaller depth by adding more knowledge to the evaluation.

I think that it is possible that a better evaluation can cause move ordering to be more accurate so you get more cutoff in the first move.

An extreme case that does not happen is when your evaluation is good enough to predict the result of the game.

In this case you get the always the best move first and clearly get a smaller tree because you always search best first.

It is practically impossible but it is possible that good evaluation can clearly push you to get the best move first more often and change your mind less often(because you more often find the best move at depth 1 without changing it).

Uri