UCI extension: nodestime

[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 I propose 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:

* nodestime
tells the engine to use nodes searched instead of wall time to account for elapsed time.


When nodestime is sent, the following 'go' command parameters change their meaning in the following way:

* wtime
white has x msec left on the clock, or has x nodes left to search if nodestime is set

* btime
black has x msec left on the clock, or has x nodes left to search if nodestime is set

* winc
white increment per move in mseconds if x > 0, or in number of nodes if nodestime is set

* binc
black increment per move in mseconds if x > 0, or in number of nodes if nodestime is set


The nice thing is that the only change required to the engine is to account for elapsed time no more in millisecs since search is started, but in nodes searched since search is started. All the remaining logic, and in particular all the time management remains unchanged as long as is computed as relative to the values of wtime and btime, as is the case in all the engines I know of. If the engine, as is usual, sends 'nodes' value as part of its 'info' message, then nothing more is required.


The job of the tournament manager is as well very easy.

The user set the GUI to use 'nodestime', for instance setting a nodes_per_seconds configuration parameter. This is not part of UCI protocol and is reported here just as an example. So assume user sets:

nodes_per_seconds = 800.000

and all the other parameters as usual. When the GUI sends the 'go' command, it has just to add parameter 'nodestime' and convert wtime and friends from millisecs to nodes:

wtime *= nodes_per_seconds;
btime *= nodes_per_seconds;
winc *= nodes_per_seconds;
winc *= nodes_per_seconds;

Upon receiving 'bestmove', the gui uses the last 'nodes' info received from engine to convert back from nodes to time:

elapsed_time = nodes * 1000 / nodes_per_seconds; // In millisecs

Then uses elapsed_time as the time spent by the engine to search the move.

The nice thing is that nodes_per_seconds doesn't need to be accurate, a gross approximation is enough because it only alters the effective TC. For instance if TC is set at 1 minute per game, and nodes_per_seconds is set at 800.000, while the real engine speed is of 1600000 nodes per second, the only effect is that the game will last on average half time, like if TC was set at 30 seconds per game.

[Evert]

I haven't compared in detail, but this reminds me of the "NPS" time-control option in CECP (a bit below http://www.gnu.org/software/xboard/engine-intf.html#8).

EDIT: I would suggest just adding it as a defacto UCI extension. It seems to be quite hard to get anything added to the official specs...

[mcostalba]

I haven't compared in detail, but this reminds me of the "NPS" time-control option in CECP (a bit below http://www.gnu.org/software/xboard/engine-intf.html#8).

Yes, it is similar...I have reinvented the wheel

Code: Select all

nps NODE_RATE
    The engine should not use wall-clock time to make its timing decisions, but an own internal time measure based on the number of nodes it has searched (and will report as "thinking output", see section 10), converted to seconds through dividing by the given NODE_RATE. Example: after receiving the commands "st 8" and "nps 10000", the engine should never use more that 80,000 nodes in the search for any move. In this mode, the engine should report user CPU time used (in its thinking output), rather than wall-clock time. This even holds if NODE_RATE is given as 0, but in that case it should also use the user CPU time for its timing decisions. The effect of an "nps" command should persist until the next "new" command. 

On one hand sending: 'nps NODE_RATE' does not force to change the meaning of wtime and friends, and this is a good thing. The engine has a little bit more work to do, but mainly just the conversion from millisecs to nodes in wtime and btime, so I would say is more than acceptable.

On the other hand the info required to be sent from the engine to the GUI is needlessy complicated in CECP. Eventually the engine does _not_ need to send anything unusual or diffrent from the common case as long as it sends it's 'info' message with included searched nodes at the end of the search. At least this is the case with UCI. I don't know xboard.

So an improvment over my initial proposal can be:

Code: Select all

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

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

[bob]

What about pondering?

[hgm]

On the other hand the info required to be sent from the engine to the GUI is needlessy complicated in CECP. Eventually the engine does _not_ need to send anything unusual or diffrent from the common case as long as it sends it's 'info' message with included searched nodes at the end of the search. At least this is the case with UCI. I don't know xboard.

I added this to the specs for the benefit of the 'nps 0' case, which was an alternative way to solve the problem that engines might not get equal time slices from the OS, which was accounting by CPU time used. In that case the engine must tell the GUI how much time it used, so that the GUI can update the clocks accordingly. If there would be an accurate way for an engine to measure its CPU usage, this might be preferable over the nodes system, as some engines run at very different nps in end-game and middle-game, so that playing by nodes would effectively alter the time management.

Your original proposal was equivalent to 'nps 1000', which would equate 1 node to 1 msec.

It would be more in the spirit of UCI to implement this as an engine-defined option rather than an extension of the 'go' command. There could be a spin option UCI_PlayByNodes to set the time-to-nodes conversion factor, where the default 0 means 'ply by wall-clock time'.

The advantage would be that the GUI could know whether the engine supported the option, and doesn't have to send 'go nodestime' blindly, and hope for the best.

[mcostalba]

It would be more in the spirit of UCI to implement this as an engine-defined option rather than an extension of the 'go' command. There could be a spin option UCI_PlayByNodes to set the time-to-nodes conversion factor, where the default 0 means 'ply by wall-clock time'.

I prefer to introduce 'nps NODE_RATE' as a parameter of 'go' command, firstly because it is more elegant and correct (an option is something the GUI sends to the engine and forgets, instead in this case the GUI is actively involved in properly accounting for elapsed time after every move) and also because, being UCI stateless, the GUI is free to change nps even after every move (instead an option is assumed to be sent at the game start, although not technically strictly required this is the usual convention).

Why you may want to change nps at every move?

Well this is another important change that can give flexibility to the GUI, for instance to adjust nps according to the average of the real nps of the engine in last series of moves, this would introduce a slow and stable drift of nps, increasing toward the endgame. Mitigating what is probably the biggest artifact of this scheme: the altered time management toward game end.

The other big limitation of this scheme is that the two engines are supposed to have the same speed. This is an a-priori constrain that is enforced sending the same nps value to both engines. One may send 2 different nps values to the 2 engines, for instance the average of the single engine nps of the last series of moves, but IMO this becomes too complicated and can eventually be investigated only as a second step.

So, given the above, I think this scheme poster-child is parameters tuning, where you self-play the engine against itself, altering just a bunch of parameters. In this case assuming engines speed is the same can be a practically safe assumption.

[mcostalba]

What about pondering?

Pondering is not affected by this change. Indeed when pondering, you are free to use all the time you want as long as the opponent has not moved.

[hgm]

I prefer to introduce 'nps NODE_RATE' as a parameter of 'go' command, firstly because it is more elegant and correct (an option is something the GUI sends to the engine and forgets, instead in this case the GUI is actively involved in properly accounting for elapsed time after every move) and also because, being UCI stateless, the GUI is free to change nps even after every move (instead an option is assumed to be sent at the game start, although not technically strictly required this is the usual convention).

That might have been good reasons if they were true. But they are not:

GUIs do not forget about options. When they set the opton Chess960, they do not forget that they were playing Chess960 and switch to normal Chess for the next move. When the send UCI_AnalyseMode they cannot forget that they are analyzing, and switch to playing a game when the user enters the next move. If they send OwnBook=true to the engine, they should remember to refrain from using the GUI book on the next moves. UCI_PlayByNodes would in fact be an option very similar to Ponder, which the GUI sends once to inform the engine's time-management logic that it will have to work a bit different. In the Ponder=true case because it will likely have ~1.5 times as much time available than the wtime and btime parameters on the 'go' command suggest, because of ponder hits.

That options can be set only at the beginning of the game is a total misconception. I don't know what gave you that idea. You can for instance switch pondering on and off at any time, (involving the Ponder option), or change the number of search threads at any time. It has actually been known that people changed the contempt factor of their UCI engine during a CCT game because the score looked drawish, but they thought their engine had the better chances. Interfaces will dutifully send any option change requested by the user to the engine at any time (even during search!), or send standard UCI options during a game when a change of the mode of operation (like switching from analyzing to playing) requires so. That you might want the virtual NPS rate to change during the game has no more bearing on the option-vs-command implementation issue than that you want to be able to switch pondering on or off on a move-by-move basis.

It would be very bad if there was no way for the GUI whether the engine supports certain optional commands or not. In the case of 'searchmoves' this causes pretty disastrous malfunction on engines that do not support it (i.e. most engines...). So lets not make that mistake again.

[mcostalba]

So lets not make that mistake again.

Sorry, but after reading your reply I am even more sure that my approach is better.

I will sum up all the new comments and suggestions here an on the SF forum in a separated post.

[hgm]

I'm not surprised. It doesn't matter much what you think, though. If you want Stockfish to be crap, its your call. But you shouldn't expect many other engines or GUIs to adopt a poorly working system that is wrong by design. But that is fine if you want Stockfish to live inside its own bubble...