## Implementing Multi pv

**Moderators:** bob, hgm, Harvey Williamson

**Forum rules**

This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

### Implementing Multi pv

Hi all,

How much different (harder) is it to implement multipv to a simple program like Vice? Do I need to just find all the possible moves at the root and then do iterative deepening on each one?

Something like:

Find all moves for position p

Iterate through depth

--Iterate through each possible root move and store all info

Thanks,

How much different (harder) is it to implement multipv to a simple program like Vice? Do I need to just find all the possible moves at the root and then do iterative deepening on each one?

Something like:

Find all moves for position p

Iterate through depth

--Iterate through each possible root move and store all info

Thanks,

### Re: Implementing Multi pv

That is the basic idea. Search the first move, save the PV, then set alpha back to whatever value you start at and search again. Now this move won't fail low and it will produce a PV.CDiddy wrote:Hi all,

How much different (harder) is it to implement multipv to a simple program like Vice? Do I need to just find all the possible moves at the root and then do iterative deepening on each one?

Something like:

Find all moves for position p

Iterate through depth

--Iterate through each possible root move and store all info

Thanks,

There are more efficient alternatives. IE search ALL moves and print the best PV. Then remove that move from the root move list and search all remaining moves again. You can repeat this N times to get the N best moves displayed...

- hgm
**Posts:**23718**Joined:**Fri Mar 10, 2006 9:06 am**Location:**Amsterdam**Full name:**H G Muller-
**Contact:**

### Re: Implementing Multi pv

What I did in Fairy-Max to implement multi-PV is increase alpha to bestScore - margin, rather than to bestScore, in the root. And of course make sure a new PV (found when score > alpha) is printed immediately when it is found, rather than at the end of the iteration. That was all.

### Re: Implementing Multi pv

So if I have multiPV set to 10 and their are 15 root moves for the position, I search all 15 root moves and get scores. I then re-search the 14 non-best root moves? Wouldnt the initial search have given the scores for all 15 root moves?bob wrote:That is the basic idea. Search the first move, save the PV, then set alpha back to whatever value you start at and search again. Now this move won't fail low and it will produce a PV.CDiddy wrote:Hi all,

How much different (harder) is it to implement multipv to a simple program like Vice? Do I need to just find all the possible moves at the root and then do iterative deepening on each one?

Something like:

Find all moves for position p

Iterate through depth

--Iterate through each possible root move and store all info

Thanks,

There are more efficient alternatives. IE search ALL moves and print the best PV. Then remove that move from the root move list and search all remaining moves again. You can repeat this N times to get the N best moves displayed...

### Re: Implementing Multi pv

No. You get the score for the BEST move. And if it wasn't ordered first, you will get a score for one or more moves that came before that one. But you can't be sure those are in the "ten best" until you have done the whole search. Pass 1 looks at all moves and finds the best. Pass 2 looks at the remaining 14 and finds the best. Etc. This is usually more efficient than trying to get a real score for EACH root move (by setting alpha back to -infinity after you get a score back). Because with that approach, you will spend a lot of effort and have to search every last root move with an open window to get the N best...CDiddy wrote:So if I have multiPV set to 10 and their are 15 root moves for the position, I search all 15 root moves and get scores. I then re-search the 14 non-best root moves? Wouldnt the initial search have given the scores for all 15 root moves?bob wrote:That is the basic idea. Search the first move, save the PV, then set alpha back to whatever value you start at and search again. Now this move won't fail low and it will produce a PV.CDiddy wrote:Hi all,

How much different (harder) is it to implement multipv to a simple program like Vice? Do I need to just find all the possible moves at the root and then do iterative deepening on each one?

Something like:

Find all moves for position p

Iterate through depth

--Iterate through each possible root move and store all info

Thanks,

There are more efficient alternatives. IE search ALL moves and print the best PV. Then remove that move from the root move list and search all remaining moves again. You can repeat this N times to get the N best moves displayed...

### Re: Implementing Multi pv

Some programs, e.g. stocfish, have a feature that allow them to do a search excluding some move from the root node.CDiddy wrote: How much different (harder) is it to implement multipv to a simple program like Vice?

with this feature the MultiPV search can be implemented this way:

Code: Select all

```
excluded move list = empty
for MultiPV lines:
do a root search without excluded moves
extract the PV
insert in the excluded move list the first move of the PV
```

### Re: Implementing Multi pv

You would only need to search the first N moves (the N best from the previous iteration) with an open window, then verify that the remaining moves are all worse than the current Nth best.bob wrote:No. You get the score for the BEST move. And if it wasn't ordered first, you will get a score for one or more moves that came before that one. But you can't be sure those are in the "ten best" until you have done the whole search. Pass 1 looks at all moves and finds the best. Pass 2 looks at the remaining 14 and finds the best. Etc. This is usually more efficient than trying to get a real score for EACH root move (by setting alpha back to -infinity after you get a score back). Because with that approach, you will spend a lot of effort and have to search every last root move with an open window to get the N best...

I don't know what would be most efficient, but doing N repeated searches, each further search excluding one more move, does not immediately strike me as the best way to do it.

### Re: Implementing Multi pv

the benefit of doing n search is that every search can be done with his own aspiration window. I don't know if this way of doing the MultiPV is better or worse. it's simply a different way

### Re: Implementing Multi pv

You can have individual aspiration windows for each move even if you don't make N passes over the root moves. This is what I do in texel:elcabesa wrote:the benefit of doing n search is that every search can be done with his own aspiration window. I don't know if this way of doing the MultiPV is better or worse. it's simply a different way :)

Code: Select all

```
for (int depth = 1; ; depth++) {
for (int mi = 0; mi < rootMoves.size(); mi++) {
if (depth == 1) {
alpha = -MATE0;
beta = MATE0;
} else if (mi < maxPV) {
alpha = rootMoves[mi].score - aspirationDelta;
beta = rootMoves[mi].score + aspirationDelta;
} else {
alpha = rootMoves[maxPV-1].score;
beta = alpha + 1;
}
pos.makeMove(rootMoves[mi].move);
int score = -negaScout(-beta, -alpha, 1, depth - 1);
pos.unMakeMove(rootMoves[mi].move);
while ((score >= beta) || ((mi < maxPV) && (score <= alpha))) {
if (score >= beta) {
beta += increment;
} else {
alpha -= increment;
}
pos.makeMove(rootMoves[mi].move);
score = -negaScout(-beta, -alpha, 1, depth - 1);
pos.unMakeMove(rootMoves[mi].move);
}
rootMoves[mi].score = score;
if ((mi < maxPV) || (score > rootMoves[maxPV-1].score)) {
tmp = rootMoves[mi];
int i = mi;
while ((i > 0) && (rootMoves[i-1].score < tmp.score)) {
rootMoves[i] = rootMoves[i-1];
i--;
}
rootMoves[i] = tmp;
}
}
}
```

### Re: Implementing Multi pv

in the code you show me there are iterative deepening, aspiration windows, multiPV and rootlevel search.

I have to read your code carefully, if I understood correcly:

you search the first MaxPV moves with an open windows ( base on previous scores)

then you search the remaining score with a closed window, if the result exceed beta then you do a new search with open window. This search will decide if there is a new good PV to be shown or not.

it's more or less a PVS where you search MaxPV PV.

I have to read your code carefully, if I understood correcly:

you search the first MaxPV moves with an open windows ( base on previous scores)

then you search the remaining score with a closed window, if the result exceed beta then you do a new search with open window. This search will decide if there is a new good PV to be shown or not.

it's more or less a PVS where you search MaxPV PV.