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
About implementing MultiPV
Moderators: hgm, Rebel, chrisw
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
-
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: About implementing MultiPV
I don't understand why you talk about "ordering" and "perfect ordering", etc.Kempelen wrote: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
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
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: About implementing MultiPV
first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: About implementing MultiPV
Is that what GUIs typically require, resending multiple PVs when a later move turns out to be better? Strange....Edmund wrote:first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
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
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: About implementing MultiPV
I tried that at first too and figured that Arena had difficulties with it. Always resending is definitely the safer way to go.JVMerlino wrote:Is that what GUIs typically require, resending multiple PVs when a later move turns out to be better? Strange....Edmund wrote:...
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: About implementing MultiPV
There is a simpler (and more efficent) approach.Edmund wrote:first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
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.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: About implementing MultiPV
I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:bob wrote:There is a simpler (and more efficent) approach.Edmund wrote:first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
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.
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.
-
- Posts: 27825
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: About implementing MultiPV
In Fairy-Max I implemented multi-PV simply by writing
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).
Code: Select all
if(score > alpha) {
alpha = score - marginMultiPV;
PrintPV();
...
}
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: About implementing MultiPV
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?Edmund wrote:I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:bob wrote:There is a simpler (and more efficent) approach.Edmund wrote:first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
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.
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.
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.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: About implementing MultiPV
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)bob wrote: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?Edmund wrote:I just read my post again and see that it was pretty inprecise. Sorry for that. The procedere I ment was the following:bob wrote:There is a simpler (and more efficent) approach.Edmund wrote:first of all, the full window search is very expensive. Improvements are:Kempelen wrote: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
- 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
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.
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.
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.