Multi-variantion, WinBoard protocol and Polyglot

[H.G.Muller]

For the next WinBoard release it seems a good idea to improve support for multivariation. Currently this can be controlled by the user in WinBoard only through engine-defined options. In WinBoard this is OK, as the way WinBoard displays the variations in the Engine-Output window is not really dependent on wheter the engine is running in multi-variation mode or not. WinBoard simply displays every line the engine cares to spit out.

I plan to slightly improve the display algorithm for the benifit of multi-variation output, though. In stead of adding the most recent line to the top of the display in the Engine-Output window, I will let WinBoard sort the lines of the most-recent iteration by score, so that the line with the highest score will always be the top-most one. This can be done by inserting the new line not always at the top, but somewhat lower down when it is not the best. Note that for an engine that is not in multi-variation mode, the PVs will be spit out in increasing order anyway, so the sorting does not really interfere with that. So it can in fact be always on, and does not have to know if the engine is running in multi-variation mode or not.

However, I can imagine that other interfaces want to display the multi-variation output in another way, perhaps mixing lines of different depth, and for that purpose need to be aware of how many lines the user requests from the engine. As GUIs are not supposed to understand engine-defined options, this means that we should make multi-variation control a standard feature. I therefore wanted to propose to use

feature multivar=1

as an indication that the engine supports the GUI -> engine command

multivar N [score]

where N can be any number. The engine should, in reaction to this command, make its best effort to spit out (as normal Thinking Output) the N best moves of each iteration with an exact score. The optional parameter score indicates a score value, and tells the engine not to bother with moves that are more than the specified number of centi-Pawns below the best move. This means the number of lines actually sent can be lower than the requested number N. (This can happen anyway, of course, because there might be fewer than N legal moves in the current position.)

Note that it is quite normal that an engine sends more than N lines as well; in normal alpha-beta mode (N=1), an engine can also spit out new lines of Thinking Output every time it changes its root move because it found a better one. The parameter N is just a guideline for the engine not to invest any effort in evaluating more than N moves. But if, as a side effect of its algorithm, it happens to obtain more than the requested number, it is perfectly allowed (though not obliged) to send the extra lines as well.

The multivar command can be sent at any time. But, like any WB command, it is allowed to defer recognition of it until after the engine moved, when it is received while the engine is on move and thinking. In ponder or analyze mode it should be processed immediately (likely meaning a complete re-start of the search.) It pertains to all search output, be it thinking, pondering or analyzing. The new command resets the multi-variaton status of the engine to N=1.

Would it be possible / difficult to implement this in Polyglot, so that UCI engines supporting multi-variation search can immediately benefit from this protocol extension?

[F. Bluemers]

Well,multipv already works,using the uci multipv setting

Polyglot does not sort the lines,and as engines mostly(?) search best first and after that the next best,the lines are shown reversed.

Implementing multipv itself is not hard but I encountered a lot of suprises,so it needs testing.
f.i. After encountering a line searched with a lesser depth,the engine output screen would be cleared.
To force clearing the output screen you need to use this small "hack",sending a line with depth -1 or 0 or remember the latest depth send and go below.
The score option is not a part of uci,so if some engines use it ,it probably will become a kludge like the "cores" option.

[H.G.Muller]

Well, if you ask for, say, 4 lines and 100cP, and you can tell the UCI engine only about the 4 lines, ... Then, when it coughs up lines with sores 156, 132, 80 and -20, Polyglot could decide to not pass on the -20 line to WinBoard. Then the only poblem is that the engine might have wasted time on it.

I am not sure how the non-monotoneous depth-increase could occur. A multi-variation engine will first complete the searches of all N moves to depth D before it starts searching any move to depth D+1, not? It makes no sense do reduce the depth. If you go seaching another move at lower depth, due to hash hits, you re likely to effectively get the result a D+1 search anyway. So I imagined that a four-variation search first produces four variations of d=1, then four at d=2, then four at d=3... Are there really engines that do it differently?

[F. Bluemers]

Well, if you ask for, say, 4 lines and 100cP, and you can tell the UCI engine only about the 4 lines, ... Then, when it coughs up lines with sores 156, 132, 80 and -20, Polyglot could decide to not pass on the -20 line to WinBoard. Then the only poblem is that the engine might have wasted time on it.

Yes,or even totally ignore the score part?

I am not sure how the non-monotoneous depth-increase could occur. A multi-variation engine will first complete the searches of all N moves to depth D before it starts searching any move to depth D+1, not? It makes no sense do reduce the depth. If you go seaching another move at lower depth, due to hash hits, you re likely to effectively get the result a D+1 search anyway. So I imagined that a four-variation search first produces four variations of d=1, then four at d=2, then four at d=3... Are there really engines that do it differently?

One of the engines was Toga.Well,maybe it was even the only one,I don't recall.

[Teemu Pudas]

The score option is not a part of uci,so if some engines use it ,it probably will become a kludge like the "cores" option.

Rybka 3 is the only UCI engine that supports it AFAIK (MultiPV_cp). Aquarium and (?) the CB Rybka GUI recognize the option.

[F. Bluemers]

The score option is not a part of uci,so if some engines use it ,it probably will become a kludge like the "cores" option.

Rybka 3 is the only UCI engine that supports it AFAIK (MultiPV_cp). Aquarium and (?) the CB Rybka GUI recognize the option.

Yes I saw this option mentioned,but my guess is that as its not part of the uciprotocol other engines will name it differently,if they would implement it.