About implementing MultiPV

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

About implementing MultiPV

Post by Kempelen » Sun May 16, 2010 8:29 pm

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
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: About implementing MultiPV

Post by Chan Rasjid » Mon May 17, 2010 12:49 am

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
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
Don't believe when you're told "There's no free lunch!" There is Linux.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: About implementing MultiPV

Post by Edmund » Mon May 17, 2010 1:07 pm

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

User avatar
JVMerlino
Posts: 1035
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: About implementing MultiPV

Post by JVMerlino » Mon May 17, 2010 3:56 pm

Edmund wrote:
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
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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: About implementing MultiPV

Post by Edmund » Mon May 17, 2010 4:02 pm

JVMerlino wrote:
Edmund wrote:...
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
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: About implementing MultiPV

Post by bob » Mon May 17, 2010 4:53 pm

Edmund wrote:
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
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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: About implementing MultiPV

Post by Edmund » Mon May 17, 2010 5:31 pm

bob wrote:
Edmund wrote:
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
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.

User avatar
hgm
Posts: 24619
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: About implementing MultiPV

Post by hgm » Mon May 17, 2010 6:05 pm

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
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: About implementing MultiPV

Post by bob » Mon May 17, 2010 6:38 pm

Edmund wrote:
bob wrote:
Edmund wrote:
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
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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: About implementing MultiPV

Post by Edmund » Mon May 17, 2010 7:03 pm

bob wrote:
Edmund wrote:
bob wrote:
Edmund wrote:
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
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)

Post Reply