TalkChess.com

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

 
move_type  pv[MAX_HEIGHT][MAX_HEIGHT];

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

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

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

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

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.

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.

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.