Implementing Multi pv

[CDiddy]

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,

[bob]

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,

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.

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]

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.

[CDiddy]

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,

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.

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

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]

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,

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.

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

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?

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

[elcabesa]

How much different (harder) is it to implement multipv to a simple program like Vice?

Some programs, e.g. stocfish, have a feature that allow them to do a search excluding some move from the root node.

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

the framework has to be included inside the iterative deepening framework

[syzygy]

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

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.

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.

[elcabesa]

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

[petero2]

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

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:

Code: Select all

    for (int depth = 1; ; depth++) {
        for &#40;int mi = 0; mi < rootMoves.size&#40;); mi++) &#123;
            if &#40;depth == 1&#41; &#123;
                alpha = -MATE0;
                beta = MATE0;
            &#125; else if &#40;mi < maxPV&#41; &#123;
                alpha = rootMoves&#91;mi&#93;.score - aspirationDelta;
                beta = rootMoves&#91;mi&#93;.score + aspirationDelta;
            &#125; else &#123;
                alpha = rootMoves&#91;maxPV-1&#93;.score;
                beta = alpha + 1;
            &#125;

            pos.makeMove&#40;rootMoves&#91;mi&#93;.move&#41;;
            int score = -negaScout&#40;-beta, -alpha, 1, depth - 1&#41;;
            pos.unMakeMove&#40;rootMoves&#91;mi&#93;.move&#41;;

            while (&#40;score >= beta&#41; || (&#40;mi < maxPV&#41; && &#40;score <= alpha&#41;)) &#123;
                if &#40;score >= beta&#41; &#123;
                    beta += increment;
                &#125; else &#123;
                    alpha -= increment;
                &#125;
                pos.makeMove&#40;rootMoves&#91;mi&#93;.move&#41;;
                score = -negaScout&#40;-beta, -alpha, 1, depth - 1&#41;;
                pos.unMakeMove&#40;rootMoves&#91;mi&#93;.move&#41;;
            &#125;
            rootMoves&#91;mi&#93;.score = score;

            if (&#40;mi < maxPV&#41; || &#40;score > rootMoves&#91;maxPV-1&#93;.score&#41;) &#123;
                tmp = rootMoves&#91;mi&#93;;
                int i = mi;
                while (&#40;i > 0&#41; && &#40;rootMoves&#91;i-1&#93;.score < tmp.score&#41;) &#123;
                    rootMoves&#91;i&#93; = rootMoves&#91;i-1&#93;;
                    i--;
                &#125;
                rootMoves&#91;i&#93; = tmp;
            &#125;
        &#125;
    &#125;

In the first iteration when depth=1, I search all moves with an open window to get an initial move ordering. In the following iterations (depth > 1) I use an aspiration window for the first N (maxPV) moves and an empty window for the remaining moves. The first N moves are kept in sorted order.

[elcabesa]

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.