About implementing MultiPV

[bob]

Hello,

I am trying to implement MultiPV in order to use my engine to analyse when I study, so I can take adventage myself in my chess knowledge and also been ready to see where my engine can be improved.

Now I have a couple of doubts about it. I know than a good method is search each move with a full window (alpha=-infinite, beta=infinite) so I could get each move value. So far so good, but I am having problems to send the pvs to the gui. If the move order is perfect multipv 1 then 2, and last 3 is send in correct order to the gui. What about if the 2nd move is a pv node? I thought I must send it with multipv 1 string; if so, What I send as multipv 2? and multipv 3? I am a little confused about how to send that info strings to gui and what order. It is clear to me when move order is perfect, but no for when a new best move is found.

Any help please?

thanks

first of all, the full window search is very expensive. Improvements are:
- store the exact score each iteration and use an aspiration window every time
- once you have found enough pvs (eg. move 6 and you are searching for 5 pvs) do zero-windows only and research in case of a fail-high

next the problem of the ordering. Once the order of the moves changes, you have to resend all the pvs to the gui that change place. eg. you are on move 6 and it turns out to be in fact #4, you have to resend all pvs from 4 to 6.

regards,
Edmund

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:

lets say you want 3pvs,

1st ply search all moves with infinite windows and store the exact score in a list.
in the next plys for the first 3 moves use a window of the previous exact score of the move +- aspiration window. From move 4 onwards use a zero window at the score of the move number 3.

I don't see how this would be less efficient than your posted approach.

The problem is that you search _every_ move with a window centered on the original score. But how can you tell which are the 3 best moves until you search _every_ move using that open window?

My way searches just a few moves with open window, most are searched with a null-window (I am assuming PVS type search), which produces a lot less work.

I am assuming the 3 best moves from the previous iteration will remain the 3 best moves. So only those are searched with an open window (score +- aspiration window) all the other ones are searched with a zero window and a research in case of a fail high (over the score of the 3rd best move)

The problem is, the assumption is not valid all the time. If you want a _real_ 3-move multi-pv option, you have to find the best 3 moves from all of the moves, at the final depth. Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper...

[Dann Corbit]

Hello,

I am trying to implement MultiPV in order to use my engine to analyse when I study, so I can take adventage myself in my chess knowledge and also been ready to see where my engine can be improved.

Now I have a couple of doubts about it. I know than a good method is search each move with a full window (alpha=-infinite, beta=infinite) so I could get each move value. So far so good, but I am having problems to send the pvs to the gui. If the move order is perfect multipv 1 then 2, and last 3 is send in correct order to the gui. What about if the 2nd move is a pv node? I thought I must send it with multipv 1 string; if so, What I send as multipv 2? and multipv 3? I am a little confused about how to send that info strings to gui and what order. It is clear to me when move order is perfect, but no for when a new best move is found.

Any help please?

thanks

first of all, the full window search is very expensive. Improvements are:
- store the exact score each iteration and use an aspiration window every time
- once you have found enough pvs (eg. move 6 and you are searching for 5 pvs) do zero-windows only and research in case of a fail-high

next the problem of the ordering. Once the order of the moves changes, you have to resend all the pvs to the gui that change place. eg. you are on move 6 and it turns out to be in fact #4, you have to resend all pvs from 4 to 6.

regards,
Edmund

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:

lets say you want 3pvs,

1st ply search all moves with infinite windows and store the exact score in a list.
in the next plys for the first 3 moves use a window of the previous exact score of the move +- aspiration window. From move 4 onwards use a zero window at the score of the move number 3.

I don't see how this would be less efficient than your posted approach.

The problem is that you search _every_ move with a window centered on the original score. But how can you tell which are the 3 best moves until you search _every_ move using that open window?

My way searches just a few moves with open window, most are searched with a null-window (I am assuming PVS type search), which produces a lot less work.

I am assuming the 3 best moves from the previous iteration will remain the 3 best moves. So only those are searched with an open window (score +- aspiration window) all the other ones are searched with a zero window and a research in case of a fail high (over the score of the 3rd best move)

The problem is, the assumption is not valid all the time. If you want a _real_ 3-move multi-pv option, you have to find the best 3 moves from all of the moves, at the final depth. Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper...

But if some other move is better it would fail high and get re-searched, no?

[Edmund]

Hello,

I am trying to implement MultiPV in order to use my engine to analyse when I study, so I can take adventage myself in my chess knowledge and also been ready to see where my engine can be improved.

Now I have a couple of doubts about it. I know than a good method is search each move with a full window (alpha=-infinite, beta=infinite) so I could get each move value. So far so good, but I am having problems to send the pvs to the gui. If the move order is perfect multipv 1 then 2, and last 3 is send in correct order to the gui. What about if the 2nd move is a pv node? I thought I must send it with multipv 1 string; if so, What I send as multipv 2? and multipv 3? I am a little confused about how to send that info strings to gui and what order. It is clear to me when move order is perfect, but no for when a new best move is found.

Any help please?

thanks

first of all, the full window search is very expensive. Improvements are:
- store the exact score each iteration and use an aspiration window every time
- once you have found enough pvs (eg. move 6 and you are searching for 5 pvs) do zero-windows only and research in case of a fail-high

next the problem of the ordering. Once the order of the moves changes, you have to resend all the pvs to the gui that change place. eg. you are on move 6 and it turns out to be in fact #4, you have to resend all pvs from 4 to 6.

regards,
Edmund

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:

lets say you want 3pvs,

1st ply search all moves with infinite windows and store the exact score in a list.
in the next plys for the first 3 moves use a window of the previous exact score of the move +- aspiration window. From move 4 onwards use a zero window at the score of the move number 3.

I don't see how this would be less efficient than your posted approach.

The problem is that you search _every_ move with a window centered on the original score. But how can you tell which are the 3 best moves until you search _every_ move using that open window?

My way searches just a few moves with open window, most are searched with a null-window (I am assuming PVS type search), which produces a lot less work.

I am assuming the 3 best moves from the previous iteration will remain the 3 best moves. So only those are searched with an open window (score +- aspiration window) all the other ones are searched with a zero window and a research in case of a fail high (over the score of the 3rd best move)

The problem is, the assumption is not valid all the time. If you want a _real_ 3-move multi-pv option, you have to find the best 3 moves from all of the moves, at the final depth. Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper...

Ofcause it can be wrong, but then it researches and knows better in the next iteration. Thats how PVS works. Anyway PVS is better than an alpha-beta search without it. My suggestion is just a generalization of the PVS algorithm.

"Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper..."

Thats what the zero-window searches for the remaining moves are there for. These verify that the 3 chosen moves are actually better than the rest.

[jwes]

In Fairy-Max I implemented multi-PV simply by writing

Code: Select all

if(score > alpha) {
    alpha = score - marginMultiPV;
    PrintPV();
    ...
}

in the root, in stead of the usual alpha = score. When marginMultiPV = 0 this works as a nomal search (printing a PV every time it changes).

While this is simple and arguably more useful, MultiPV has been defined as exactly n PVs, where n is a configuration value.

[bob]

Hello,

I am trying to implement MultiPV in order to use my engine to analyse when I study, so I can take adventage myself in my chess knowledge and also been ready to see where my engine can be improved.

Now I have a couple of doubts about it. I know than a good method is search each move with a full window (alpha=-infinite, beta=infinite) so I could get each move value. So far so good, but I am having problems to send the pvs to the gui. If the move order is perfect multipv 1 then 2, and last 3 is send in correct order to the gui. What about if the 2nd move is a pv node? I thought I must send it with multipv 1 string; if so, What I send as multipv 2? and multipv 3? I am a little confused about how to send that info strings to gui and what order. It is clear to me when move order is perfect, but no for when a new best move is found.

Any help please?

thanks

first of all, the full window search is very expensive. Improvements are:
- store the exact score each iteration and use an aspiration window every time
- once you have found enough pvs (eg. move 6 and you are searching for 5 pvs) do zero-windows only and research in case of a fail-high

next the problem of the ordering. Once the order of the moves changes, you have to resend all the pvs to the gui that change place. eg. you are on move 6 and it turns out to be in fact #4, you have to resend all pvs from 4 to 6.

regards,
Edmund

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:

lets say you want 3pvs,

1st ply search all moves with infinite windows and store the exact score in a list.
in the next plys for the first 3 moves use a window of the previous exact score of the move +- aspiration window. From move 4 onwards use a zero window at the score of the move number 3.

I don't see how this would be less efficient than your posted approach.

The problem is that you search _every_ move with a window centered on the original score. But how can you tell which are the 3 best moves until you search _every_ move using that open window?

My way searches just a few moves with open window, most are searched with a null-window (I am assuming PVS type search), which produces a lot less work.

I am assuming the 3 best moves from the previous iteration will remain the 3 best moves. So only those are searched with an open window (score +- aspiration window) all the other ones are searched with a zero window and a research in case of a fail high (over the score of the 3rd best move)

The problem is, the assumption is not valid all the time. If you want a _real_ 3-move multi-pv option, you have to find the best 3 moves from all of the moves, at the final depth. Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper...

But if some other move is better it would fail high and get re-searched, no?

Suppose last iteration move A has score of +100, move B has a score of +50 and move 3 has a score of 0. All other moves have unknown scores <= 0. At the current (next) iteration, suppose the scores change:

A=+100, B=+30, C=0, D=150, E=+120.

How do you pick up E so that your 3 best are D, E and A? You find D first, and now E fails low.

There is no way to "short-change" this process unless you are willing to give up accuracy. The above would come up as D=150, A=100 and B=30. E would be missing, which is an error. If you can accept that error, then it is OK. But the error is _significant_.

[bob]

Hello,

I am trying to implement MultiPV in order to use my engine to analyse when I study, so I can take adventage myself in my chess knowledge and also been ready to see where my engine can be improved.

Now I have a couple of doubts about it. I know than a good method is search each move with a full window (alpha=-infinite, beta=infinite) so I could get each move value. So far so good, but I am having problems to send the pvs to the gui. If the move order is perfect multipv 1 then 2, and last 3 is send in correct order to the gui. What about if the 2nd move is a pv node? I thought I must send it with multipv 1 string; if so, What I send as multipv 2? and multipv 3? I am a little confused about how to send that info strings to gui and what order. It is clear to me when move order is perfect, but no for when a new best move is found.

Any help please?

thanks

first of all, the full window search is very expensive. Improvements are:
- store the exact score each iteration and use an aspiration window every time
- once you have found enough pvs (eg. move 6 and you are searching for 5 pvs) do zero-windows only and research in case of a fail-high

next the problem of the ordering. Once the order of the moves changes, you have to resend all the pvs to the gui that change place. eg. you are on move 6 and it turns out to be in fact #4, you have to resend all pvs from 4 to 6.

regards,
Edmund

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:

lets say you want 3pvs,

1st ply search all moves with infinite windows and store the exact score in a list.
in the next plys for the first 3 moves use a window of the previous exact score of the move +- aspiration window. From move 4 onwards use a zero window at the score of the move number 3.

I don't see how this would be less efficient than your posted approach.

The problem is that you search _every_ move with a window centered on the original score. But how can you tell which are the 3 best moves until you search _every_ move using that open window?

My way searches just a few moves with open window, most are searched with a null-window (I am assuming PVS type search), which produces a lot less work.

I am assuming the 3 best moves from the previous iteration will remain the 3 best moves. So only those are searched with an open window (score +- aspiration window) all the other ones are searched with a zero window and a research in case of a fail high (over the score of the 3rd best move)

The problem is, the assumption is not valid all the time. If you want a _real_ 3-move multi-pv option, you have to find the best 3 moves from all of the moves, at the final depth. Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper...

Ofcause it can be wrong, but then it researches and knows better in the next iteration. Thats how PVS works. Anyway PVS is better than an alpha-beta search without it. My suggestion is just a generalization of the PVS algorithm.

"Think how wrong you would be if you just assume that the best move from the previous iteration is best and always just play that rather than going a ply deeper..."

Thats what the zero-window searches for the remaining moves are there for. These verify that the 3 chosen moves are actually better than the rest.

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

[jwes]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

[hgm]

While this is simple and arguably more useful, MultiPV has been defined as exactly n PVs, where n is a configuration value.

Not in WinBoard! There is is just an engine-defined option, and Fairy-Max allows you to configure the margin in centi-Pawn, rather than the number of PVs.

It seems useful to be tolerant to deviation of the number of requested PVs in UCI as well. What would you do if n=3, and there is only a single legal move (or two)? Have the GUI hang or shut down the engine because it did not comply with the requested number?

There is some cheating going on here anyway, as usualy engines send a new PV as son as they have one. So usually UCI engines sen more than 3 PVs if you request 3. E.g. if during the search two of the moves that failed low in the previous iteration now fail high, they send 5 PVs. Actually they send 5x3 = 15 PVs, because they think that 15 is closer to the requested 3 as 5 is. Silly protocol!

[michiguel]

While this is simple and arguably more useful, MultiPV has been defined as exactly n PVs, where n is a configuration value.

Not in WinBoard! There is is just an engine-defined option, and Fairy-Max allows you to configure the margin in centi-Pawn, rather than the number of PVs.

It seems useful to be tolerant to deviation of the number of requested PVs in UCI as well. What would you do if n=3, and there is only a single legal move (or two)? Have the GUI hang or shut down the engine because it did not comply with the requested number?

There is some cheating going on here anyway, as usualy engines send a new PV as son as they have one. So usually UCI engines sen more than 3 PVs if you request 3. E.g. if during the search two of the moves that failed low in the previous iteration now fail high, they send 5 PVs. Actually they send 5x3 = 15 PVs, because they think that 15 is closer to the requested 3 as 5 is. Silly protocol!

How do you send multi PV in winboard (from a wb engine)? I could not find anything in the protocol and only some discussions related to polyglot in the WB forum

Miguel

[hgm]

A=+100, B=+30, C=0, D=150, E=+120.

How do you pick up E so that your 3 best are D, E and A? You find D first, and now E fails low.

E will not fail low, as +120 > +30 (the score of B, the 3rd move so far after D and A). When you want exactly n PVs, the root alpha is updated to the score of the n-th move so far, not the score of the best. Just like Fairy-Max updates alpha to score - margin, because it wants to get exact scores for every move that lies within margin from the best, rather than the best n.