About implementing MultiPV

[Kempelen]

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

[Chan Rasjid]

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

I don't understand why you talk about "ordering" and "perfect ordering", etc.

Let's first talk about a usual chess program with a single-pv. After each complete iteration at the root search, we must have a record (a way to know) of the "bestmove". The bestmove is the best play for the engine. Nearly all programs have (besides the single bestmove) a record of the "principal variation" or the PV which is a collection of the best play by both sides, one following another stating from the engine's bestmove. Most programs would record PV with the "triangular pv" implemetation with and array as :-

Code: Select all

 
move_type  pv[MAX_HEIGHT][MAX_HEIGHT];

The principal variation at root would be the sequence of moves (in my program):-
pv[0][0] (my bestmove),
pv[0][1] (opponents next best reply),
pv[0][2],
pv[0][3],
.... etc,

until terminated by 0.

If this is basically what you have, then move ordering does not matter. The bestmove in the root list need not be 1st in the list - it could well be the 5th in the list for an iteration. The important thing is we have to implement a method to "collect the PV" after every iteration at root.

My understanding of multi-pv is this:-
1) say we are at the nth iteration and after searching move 5 of the list, we have it as the bestmove and it MUST have the corresponding PV.
2) Then after searching move 9, we found that it is a "better" best move. We save the PV in 1) as the "next best PV". This move 9 is the current bestmove with the corresponding main PV. Searching on, the main PV may again have an improvement, etc.

So what multi-pv means is that, within an iteration at root, there could be a next best PV, next next best PV, .... main best PV.

I am not familiar with sending multiple lines of PVs to GUI.

Rasjid

[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

[JVMerlino]

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

Is that what GUIs typically require, resending multiple PVs when a later move turns out to be better? Strange....

The way Johan and I implemented it in Chessmaster was pretty simple and intuitive. Send the first N PVs, then send any later moves that turns out to be better than the current Nth move, and let the GUI do the sorting.

Or am I missing something in your description?

jm

[Edmund]

...

Is that what GUIs typically require, resending multiple PVs when a later move turns out to be better? Strange....

The way Johan and I implemented it in Chessmaster was pretty simple and intuitive. Send the first N PVs, then send any later moves that turns out to be better than the current Nth move, and let the GUI do the sorting.

Or am I missing something in your description?

jm

I tried that at first too and figured that Arena had difficulties with it. Always resending is definitely the safer way to go.

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

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

[hgm]

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

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

[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)