Implementing Multi pv

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.
CDiddy
Posts: 3
Joined: Tue Jul 26, 2016 2:39 am

Implementing Multi pv

Post by CDiddy » Fri Jul 29, 2016 3:44 am

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

Re: Implementing Multi pv

Post by bob » Fri Jul 29, 2016 3:53 am

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

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

Re: Implementing Multi pv

Post by hgm » Fri Jul 29, 2016 6:23 am

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
Posts: 3
Joined: Tue Jul 26, 2016 2:39 am

Re: Implementing Multi pv

Post by CDiddy » Fri Jul 29, 2016 9:41 pm

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

Re: Implementing Multi pv

Post by bob » Sat Jul 30, 2016 12:24 am

CDiddy wrote:
bob wrote:
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,
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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Implementing Multi pv

Post by elcabesa » Sat Jul 30, 2016 7:37 am

CDiddy wrote: 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
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Implementing Multi pv

Post by syzygy » Sat Jul 30, 2016 11:34 am

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...
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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Implementing Multi pv

Post by elcabesa » Sat Jul 30, 2016 12:24 pm

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
Posts: 587
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: Implementing Multi pv

Post by petero2 » Sat Jul 30, 2016 1:37 pm

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 :)
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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Implementing Multi pv

Post by elcabesa » Sat Jul 30, 2016 2:16 pm

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.

Post Reply