probability to change your mind output

[Uri Blass]

I wonder if there is a program that always gives in the output not only the move that it considers but also some estimate for the probability that it is going to change its mind to that move in the relevant iteration.

I think that this is an output that correspondence players would like to see in order to decide if to stop the analysis or not stop the analysis(expected time to finish searching the move is also another interesting output).

It is possible to get an estimate for the probability to change your based on the following parameters
1)The number of the move in the move list(assuming good move order first moves have bigger probability than last moves).
2)The number of nodes that the program considered the move in this iteration divided by the total number of nodes that the program considered the same move in the previous iteration and I guess that if this number is bigger the program has better chances to change its mind.

3)The number of nodes that the program considered the move in previous iteration divided the number of nodes that the program used in previous iteration and again I guess that the probability is higher if the number is bigger.

4)The number of moves that the program already tried to refute the move and again I guess that the probability is higher if the number is bigger.

I guess that using 4 it may be possible also to show probabilities of 80% to change its mind and if a program refute d4 by d5 and now it finds that d5 is not a good refutation and the same for most of black moves then assuming good order of moves it is possible to be almost sure that d4 is going to fail high even before it failed high.

[Daniel Shawul]

I wonder if there is a program that always gives in the output not only the move that it considers but also some estimate for the probability that it is going to change its mind to that move in the relevant iteration.

I think that this is an output that correspondence players would like to see in order to decide if to stop the analysis or not stop the analysis(expected time to finish searching the move is also another interesting output).

Why not just check if the PV will change on the next iteration and disregard to which move it will switch to? That way you make decisions after completing each iteration not while searching it. In most cases that should be a control fine enough and is infact what I use in my engine. In your case, you want to get probablity of PV change and time to finish next iteration along with the PV i.e. (PV, probability, time). The first thing that comes to my mind is to use Multi-PV search with 2 best moves. You can compare the two scores to determine the chance of the second move overtaking the first. I think that is a much better parameter than looking at changes in sub-tree size. With root sorting using nodes, the second move tried is most likely the one that grows faster anyway.

To deterimine probability of PV change at iteration d+1 having searched d and d-1, we can take the maximum of the parameters you mentioned below for all the moves except the first. That is because having one move growing really fast is enough to lower the probability of PV change.

Code: Select all

     MAX( i ) = always 2 hence my suggestion Mulit-PV(2)
     MAX( nodes(mv_i,d) / nodes(mv_i,d-1))
     MAX( nodes(mv_i,d-1) / SUM(nodes(mv_i,d-1)))
     MAX( nmoves(mv_i) )

It is possible to get an estimate for the probability to change your based on the following parameters
1)The number of the move in the move list(assuming good move order first moves have bigger probability than last moves).
2)The number of nodes that the program considered the move in this iteration divided by the total number of nodes that the program considered the same move in the previous iteration and I guess that if this number is bigger the program has better chances to change its mind.

3)The number of nodes that the program considered the move in previous iteration divided the number of nodes that the program used in previous iteration and again I guess that the probability is higher if the number is bigger.

4)The number of moves that the program already tried to refute the move and again I guess that the probability is higher if the number is bigger.

I guess that using 4 it may be possible also to show probabilities of 80% to change its mind and if a program refute d4 by d5 and now it finds that d5 is not a good refutation and the same for most of black moves then assuming good order of moves it is possible to be almost sure that d4 is going to fail high even before it failed high.

[bob]

I wonder if there is a program that always gives in the output not only the move that it considers but also some estimate for the probability that it is going to change its mind to that move in the relevant iteration.

I think that this is an output that correspondence players would like to see in order to decide if to stop the analysis or not stop the analysis(expected time to finish searching the move is also another interesting output).

It is possible to get an estimate for the probability to change your based on the following parameters
1)The number of the move in the move list(assuming good move order first moves have bigger probability than last moves).

Maybe. Particularly if you re-sort between iterations based on node count. But it is nowhere near accurate enough. The second move's tree grows dramatically, most of the time, on the very iteration where it becomes best, not on the previous iteration. Which means you have to search it to realize it is going to replace the best move, not very helpful.

2)The number of nodes that the program considered the move in this iteration divided by the total number of nodes that the program considered the same move in the previous iteration and I guess that if this number is bigger the program has better chances to change its mind.

This is actually a pretty good random number generator. Tried several variations, but there is no consistency.

3)The number of nodes that the program considered the move in previous iteration divided the number of nodes that the program used in previous iteration and again I guess that the probability is higher if the number is bigger.

same as previous suggestion, in terms of results so far.

4)The number of moves that the program already tried to refute the move and again I guess that the probability is higher if the number is bigger.

Generally "refute" would be the number of ply=2 moves searched to reject the ply=1 move? Someone else suggested this type of idea, but again, it is not consistent. Sometimes you might search 5 moves to refute the move and not change your mind, the next time you might just search all but one and still not change your mind, or vice-versa. I've been experimenting a bit with variations of this, but nothing useful so far.

I guess that using 4 it may be possible also to show probabilities of 80% to change its mind and if a program refute d4 by d5 and now it finds that d5 is not a good refutation and the same for most of black moves then assuming good order of moves it is possible to be almost sure that d4 is going to fail high even before it failed high.

Good luck. I've been working on that for several months, now. To date, I have tried some things that work in some cases, but fail miserably in others. Remember the discussion on easy/hard moves? A "hard move" would be a position where you expect to change your mind, where an "easy move" would be a position where you don't". I am still playing around with ideas, collecting all sorts of data, to try to find some algorithmic way of recognizing exactly what you are talking about.

The idea of the refutation not working is one I have been looking at. The problem is, where does the "refutation move" come from? The previous iteration via the trans table? Might work for the second or third move, but what about moves near the tail of the move list? It is likely there is no TT entry for them by the time we get there, so we have to try more than one move to refute, even though the move is still lousy...

[bob]

I wonder if there is a program that always gives in the output not only the move that it considers but also some estimate for the probability that it is going to change its mind to that move in the relevant iteration.

I think that this is an output that correspondence players would like to see in order to decide if to stop the analysis or not stop the analysis(expected time to finish searching the move is also another interesting output).

Why not just check if the PV will change on the next iteration and disregard to which move it will switch to? That way you make decisions after completing each iteration not while searching it. In most cases that should be a control fine enough and is infact what I use in my engine. In your case, you want to get probablity of PV change and time to finish next iteration along with the PV i.e. (PV, probability, time). The first thing that comes to my mind is to use Multi-PV search with 2 best moves. You can compare the two scores to determine the chance of the second move overtaking the first. I think that is a much better parameter than looking at changes in sub-tree size. With root sorting using nodes, the second move tried is most likely the one that grows faster anyway.

Slow your search down by at least a factor of two (two-best)? Doesn't it make more sense to just search normally and go one ply deeper?

To deterimine probability of PV change at iteration d+1 having searched d and d-1, we can take the maximum of the parameters you mentioned below for all the moves except the first. That is because having one move growing really fast is enough to lower the probability of PV change.

Code: Select all

     MAX( i ) = always 2 hence my suggestion Mulit-PV(2)
     MAX( nodes(mv_i,d) / nodes(mv_i,d-1))
     MAX( nodes(mv_i,d-1) / SUM(nodes(mv_i,d-1)))
     MAX( nmoves(mv_i) )

It is possible to get an estimate for the probability to change your based on the following parameters
1)The number of the move in the move list(assuming good move order first moves have bigger probability than last moves).
2)The number of nodes that the program considered the move in this iteration divided by the total number of nodes that the program considered the same move in the previous iteration and I guess that if this number is bigger the program has better chances to change its mind.

3)The number of nodes that the program considered the move in previous iteration divided the number of nodes that the program used in previous iteration and again I guess that the probability is higher if the number is bigger.

4)The number of moves that the program already tried to refute the move and again I guess that the probability is higher if the number is bigger.

I guess that using 4 it may be possible also to show probabilities of 80% to change its mind and if a program refute d4 by d5 and now it finds that d5 is not a good refutation and the same for most of black moves then assuming good order of moves it is possible to be almost sure that d4 is going to fail high even before it failed high.