UCI extension: nps NODE_RATE

[mcostalba]

When running more games in parallel, or simply when running a game with a background process, due to how OS scheduling works, there is no guarantee that the CPU resources allocated evenly between the two players. This introduces noise in the result that leads to unreliable result and in the worst cases can even invalidate the result. For instance in SF test framework we avoid running from clouds virtual machines because are a known source of very unstable CPU speed. To overcome this here is proposed a simple extension to UCI protocol, aimed at being minimal invasive easy to implement both for engine authors and tournament managers.

The idea is to use searched nodes instead of time, and to convert time to/from nosed searched in as few places as possible.

So, starting from current protocol:

http://wbec-ridderkerk.nl/html/UCIProtocol.html

I propose to add to the 'go' command definition the following line:

Code: Select all

* nps NODE_RATE 
tells the engine to use nodes searched instead of wall time to account for elapsed time. Nodes searched will be converted to elapsed seconds through dividing by the given NODE_RATE (given in nodes per second)

This mimics the similar option in CECP http://www.gnu.org/software/xboard/engine-intf.html#8 although there are some differences, for instance nps = 0 in our case it simply means nps adjusted time is disabled and engine falls back on standard wall time.

Upon receiving 'nps NODE_RATE' parameter, the engine will account for elapsed time using searched nodes. As an example this is a possible implementation of the adjusted_now() function:

Code: Select all

  TimePoint adjusted_now() {

    if (!Search::Limits.nps)
        return now(); // Falback on usual system wall time 

    return SearchTime + RootPos.nodes_searched() * 1000 / Search::Limits.nps; // In msec, SearchTime is the beginning of the search
  }

The engine will replace now() with adjusted_now() in all the time management formulas. This is the only change required. In particular the 'info' message sent to GUI will still be sent unchanged, with 'time' set with the usual wall time and 'nodes' set with real searched nodes.

Upon receiving 'bestmove', the GUI will account for the engine consumed time in the following way:

Code: Select all

elapsed_time = nodes * 1000 / NODE_RATE; // In milliseconds

Where 'nodes' is the last 'nodes' value, sent by the engine with 'info' message.

LIMITATIONS

There are 2 main limitations with this scheme.

1) Engine speed should be known to be the same for both engines in advance, otherwise you have to deal with added complexity (sending 2 different nps to the 2 engines, measuring average speed over the last moves series, etc.)

2) Because nps is fixed while, in real engines, the nps increases toward endgame, this introduces an artifact that is equivalent to an altered time management. Namely it is like the time management gives less available time than what should be in standard case.


The second limitation can be mitigated measuring the average real nps
of the last series of moves and updating the sent nps, this introduces
a slow and stable drift, increasing nps toward the endgame,
compensating, at least partially, the altered time management
artifact.

I think the poster-child of this scheme is parameter tuning, where you
can almost safely assume that engines speed is the same.



GUI SIDE

Just for better clarifying, here is described a possible implementation from the tournament manager side, for instance cutechess.

Cutechess should add a new command line parameter:

-nodestime = x

where 'x' is the size of an internal FIFO called measured_nps, that is initialized with zero values.

cutechess enables the UCI 'nps NODE_RATE' extension and sends parameter 'nps' every time it sends 'go' command.

For the first 'x' moves nps is set to 0, and engines fallback to standard wall time. For the first 'x' moves cutechess gets the real nps after each engine's move and fills measured_nps FIFO.

Starting from move x+1, nps is set to the average of FIFO content, and this value is sent to both engines. The engines enable the adjusted time management and when, at the end of the search, bestmove is sent, cutechess uses the last sent 'nodes' info to calculate the accounted search time:

Code: Select all

elapsed_time = nodes * 1000 / NODE_RATE; // In milliseconds

cutechess continues to measuring the real nps after each move and adds the value in measured_nps, then recalculates the average nps that will be sent to engines at the next move.

An alternative to a FIFO, suggested by Michael Van den Berg, could be a simple low pass filter.

Code: Select all

new_nps=((n-1) * old_nps + measured_nps) / n

Here n is a constant which determines the response time and which roughly corresponds to the size of the FIFO.

[hgm]

Note that a feature like this has been part of WB protocol for years, and is used by XBoard/WinBoard to allow running engines that support it at a user-specified virtual node rate. XBoard does not make any attempt to adjust the node rate to the actual one; this would seem to just make the system less reliable, because it would become sensitive to performance glitches. So the envisaged use is that a virtual nodes rate is specified for each engine independently, based on the known characteristics of that engine under ideal conditions (e.g. benchmarked during low machine loading). Using this then guarantees the engine will always behave as if they were running under these conditions. (Providing you were running with ponder off.) This is of course just an implementation detail; GUIs can use the protocol as they see fit, and even offer various operating modes as alternatives.

Polyglot already supported this XBoard feature in an approximate way for UCI engines by translating the available clock times to a "go nodes" command, which was the closest approximation offered by UCI.

The proposed implementation, to make UCI support this through a new qualifier in the 'go' command seems a bad solution. This because there would be no way for the GUI to know whether the engine supports the command, and whether it actually accepted it. (As UCI specs do not provide for error messages, and force an engine to silently ignore whatever they don't understand.) So it lays the responsibility for correct use entrirely on the user. This might be fine for authors wanting to use it on their own engine, but very undesirable for releasing it on the general population of engine/GUI users.

I have therefore implemented this in a different way now in Polyglot, through the addition of a new UCI standard option "UCI_PlayByNodes". This "spin" option, when announced by the engine, will be set with the desired virtual node/sec rate, or to 0 (the default value) to switch the feature of, and use wall-clock time. The presence of the engine option can be used by the GUI to enable this feature towards the user.

[Daniel Mehrmann]

Hi Marco!

Please note that your source url, about the UCI specification, is outdated already.
The timestamp is april 2004 and the latest offical version from SMK is april 2006. (Download http://download.shredderchess.com/div/uci.zip)

Basicly it's an good idea and my suggestion is to send this idea to SMK too and/or to other chess software companies like Chessbase.

Regards,
Daniel

[mcostalba]

I would like to avoid to start an endless discussion. So I just summarize here my points of why is not used an UCI option.

1) This mode is very technical and tricky, for instance gives totally broken results if used to pit 2 random engines with (as is usual) different nps. So the user _should_ really know what he is doing. This is not just an option that pops up in the option list and the random user checks/unchecks the box. Actually, I think it is bad choice a random user sees this option because it can only hurt himself.

2) It is strictly connected to time info and, in general case, changes from move to move, as is time info. So it goes together with wtime, btime.

3) It is true that technically I can change an option at every move (as I had already stated), but this is _not_ the idiomatic way of how options are used. Indeed there is no known option that naturally changes at every move.

4) If the GUI _really_ wants to know if nps is supported (but in my opinion GUI _should_ not know and _should_ remain agnostic), it is very easy. Just send 'go wtime 1000 nps 1'. If engine returns immediately it supports it, otherwise not. But this is only a dirty trick for a non-issue, because GUI should _not_ care about this: it is totally up to the user because is an advanced and very developer oriented feature, to handle with care in a controlled environment.

[hgm]

The user should certainly know what he is doing. But that should not be a reason to make it as difficult as possible for him to get the required knowledge. Even expert users will not be able to smell whether a certain version of an engine supports this, and running the engine from the command line and typing 'uci' should give him all information on the capabilities of the engine, without running cumbersome tests. You could also find out whether an engine supports Chess960 by settng up a test position where the engine can only escape Checkmate by Fischer castling, and seeing whether the engine produces a mated score or not when set to search it. Yet UCI supports a Chess960 option. (Which from the viewpoint of the engine is totally redundant, as it can see from the castling field in the position FEN whether it is playing Chess960 or not.) Protocols that would force GUIs to resort to such hideous kludges to determine engine capabilities for the purpose of warning users that they are attempting to do something that will not work just suck...

In general you would not want this info to vary from move to move anymore than you would want the Ponder option (which also only affects the interpretation of the time left) to vary from move to move. Yes, if you really want to do uncommon things, you can do that, and there are no ill effects whatsoever of doing it. Normally the need to re-send an option for every move is a good indication that you are trying to do something odd, that was not the intended use of the feature. That is not different here.

GUIs can already adapt the time they send as wtime and btime on a move-by-move basis in any way they want, to make sure that time/NODE_RATE has exactly the value they want. No reason at all to both send time and NODE_RATE on a move-by-move basis.

[hgm]

Another acceptable method would be to make the UCI_PlayByNodes a check option, and let the engine use a fixed conversion factor between time and nodes, e.g. 1 msec = 1000 nodes. The GUI can then take care of tweeking the parameters of wtime and btime in the go command to get the desired effect, and would automatically do that on a move-by-move basis. That would eliminate redundant parameters from the 'go' command, where you would send a separate A and B whener the engine just needed A/B, and then has to calculate that by itself. Making the engine perform such a calculation would only make sense if one of A and B were fixed, to save you the trouble of sending it every time. If both vary, the GUI had better do the calculation by itself.

[Aleks Peshkov]

Under polyglot support it is possible to create a new, a better, a modern and clever fish-protocol, and many programmers would accept and support it.

But, please, do not make a "bit better" UCI for Stockfish. Incest testing did not need a text protocol, it did not even need separate engine files.

UCI is the first choice for modern engines mainly because it did not changed for ten years. Fortunately a few later added options did not spoil unity of compatible engines.