- C 99.7%
- Makefile 0.3%
| Makefile | ||
| README.md | ||
| spy.c | ||
| src01.c | ||
| src02.c | ||
| src03.c | ||
| src04.c | ||
| src05.c | ||
| src06.c | ||
| src07.c | ||
| src08.c | ||
| src09.c | ||
| src10.c | ||
| src11.c | ||
WinBoard protocol driver
Chess programming lesson by H.G. Muller
Contribution by H.G. Muller to the WinBoard forum, converted to a Markdown document by R. Chastain.
Post by H.G.Muller 30 Apr 2011, 21:45
The thread with lessons still is at a disappointing "0 replies". Let me donate some code for a model WinBoard protocol driver.
People that want to convert their engine to a WinBoard engine are free to draw inspiration from it, or even use it verbatim.
|/********************************************************/
/* Example of a WinBoard-protocol driver, by H.G.Muller */
/********************************************************/
#include <stdio.h>
// four different constants, with values for WHITE and BLACK that
suit your engine
#define WHITE 1
#define BLACK 2
#define NONE 0
#define ANALYZE 3
// some value that cannot occur as a valid move
#define INVALID 666
// some parameter of your engine
#define MAXMOVES 500 /* maximum game length */
#define MAXPLY 60 /* maximum search depth */
#define OFF 0
#define ON 1
#define DEFAULT_FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"
typedef int MOVE; // in this example moves are encoded as an int
int moveNr; // part of game state; incremented by MakeMove
MOVE gameMove[MAXMOVES]; // holds the game history
// Some routines your engine should have to do the various essential things
int MakeMove(int stm, MOVE move); // performs move, and returns new side to move
void UnMake(MOVE move); // unmakes the move;
int Setup(char *fen); // sets up the position from the given FEN, and returns the new side to move
void SetMemorySize(int n); // if n is different from last time, resize all tables to make memory usage below n MB
char *MoveToText(MOVE move); // converts the move from your internal format to text like e2e2, e1g1, a7a8q.
MOVE ParseMove(char *moveText); // converts a long-algebraic text move to your internal move format
int SearchBestMove(int stm, int timeLeft, int mps, int timeControl, int inc, int timePerMove, MOVE *move, MOVE *ponderMove);
void PonderUntilInput(int stm); // Search current position for stm, deepening forever until there is input.
// Some global variables that control your engine's behavior
int ponder;
int randomize;
int postThinking;
int resign; // engine-defined option
int contemptFactor; // likewise
int TakeBack(int n)
{ // reset the game and then replay it to the desired point
int last, stm;
stm = Setup(NULL);
last = moveNr - n; if(last < 0) last = 0;
for(moveNr=0; moveNr<last; moveNr++) stm = MakeMove(stm, gameMove[moveNr]);
return stm;
}
void PrintResult(int stm, int score)
{
if(score == 0) printf("1/2-1/2\n");
if(score > 0 && stm == WHITE || score < 0 && stm == BLACK) printf("1-0\n");
else printf("0-1\n");
}
int main()
{
int stm; // side to move
int engineSide=NONE; // side played by engine
int timeLeft; // timeleft on engine's clock
int mps, timeControl, inc, timePerMove; // time-control parameters, to be used by Search
int maxDepth; // used by search
MOVE move, ponderMove;
int i, score;
char inBuf[80], command[80];
while(1) { // infinite loop
fflush(stdout); // make sure everything is printed before we do something that might take time
if(stm == engineSide) { // if it is the engine's turn to move, set it thinking, and let it move
score = SearchBestMove(stm, timeLeft, mps, timeControl, inc, timePerMove, &move, &ponderMove);
if(move == INVALID) { // game apparently ended
engineSide = NONE; // so stop playing
PrintResult(stm, score);
} else {
stm = MakeMove(stm, move); // assumes MakeMove returns new side to move
gameMove[moveNr++] = move; // remember game
printf("move %s\n", MoveToText(move));
}
}
fflush(stdout); // make sure everything is printed before we do something that might take time
// now it is not our turn (anymore)
if(engineSide == ANALYZE) { // in analysis, we always ponder the position
PonderUntilInput(stm);
} else
if(engineSide != NONE && ponder == ON && moveNr != 0) { // ponder while waiting for input
if(ponderMove == INVALID) { // if we have no move to ponder on, ponder the position
PonderUntilInput(stm);
} else {
int newStm = MakeMove(stm, ponderMove);
PonderUntilInput(newStm);
UnMake(ponderMove);
}
}
noPonder:
// wait for input, and read it until we have collected a complete line
for(i = 0; (inBuf[i] = getchar()) != '\n'; i++);
inBuf[i+1] = 0;
// extract the first word
sscanf(inBuf, "%s", command);
// recognize the command,and execute it
if(!strcmp(command, "quit")) { break; } // breaks out of infinite loop
if(!strcmp(command, "force")) { engineSide = NONE; continue; }
if(!strcmp(command, "analyze")) { engineSide = ANALYZE; continue; }
if(!strcmp(command, "exit")) { engineSide = NONE; continue; }
if(!strcmp(command, "otim")) { goto noPonder; } // do not start pondering after receiving time commands, as move will follow immediately
if(!strcmp(command, "time")) { sscanf(inBuf, "time %d", &timeLeft); goto noPonder; }
if(!strcmp(command, "level")) {
int min, sec=0;
sscanf(inBuf, "level %d %d %d", &mps, &min, &inc) == 3 || // if this does not work, it must be min:sec format
sscanf(inBuf, "level %d %d:%d %d", &mps, &min, &sec, &inc);
timeControl = 60*min + sec; timePerMove = -1;
continue;
}
if(!strcmp(command, "protover")){
printf("feature ping=1 setboard=1 colors=0 usermove=1 memory=1 debug=1");
printf("feature option=\"Resign -check 0\""); // example of an engine-defined option
printf("feature option=\"Contempt -spin 0 -200 200\""); // and another one
printf("feature done=1");
continue;
}
if(!strcmp(command, "option")) { // setting of engine-define option; find out which
if(sscanf(inBuf+7, "Resign=%d", &resign) == 1) continue;
if(sscanf(inBuf+7, "Contempt=%d", &contemptFactor) == 1) continue;
continue;
}
if(!strcmp(command, "sd")) { sscanf(inBuf, "sd %d", &maxDepth); continue; }
if(!strcmp(command, "st")) { sscanf(inBuf, "st %d", &timePerMove); continue; }
if(!strcmp(command, "memory")) { SetMemorySize(atoi(inBuf+7)); continue; }
if(!strcmp(command, "ping")) { printf("pong%s", inBuf+4); continue; }
// if(!strcmp(command, "")) { sscanf(inBuf, " %d", &); continue; }
if(!strcmp(command, "new")) { engineSide = BLACK; stm = Setup(DEFAULT_FEN); maxDepth = MAXPLY; randomize = OFF; continue; }
if(!strcmp(command, "setboard")){ engineSide = NONE; stm = Setup(inBuf+9); continue; }
if(!strcmp(command, "easy")) { ponder = OFF; continue; }
if(!strcmp(command, "hard")) { ponder = ON; continue; }
if(!strcmp(command, "undo")) { stm = TakeBack(1); continue; }
if(!strcmp(command, "remove")) { stm = TakeBack(2); continue; }
if(!strcmp(command, "go")) { engineSide = stm; continue; }
if(!strcmp(command, "post")) { postThinking = ON; continue; }
if(!strcmp(command, "nopost")) { postThinking = OFF;continue; }
if(!strcmp(command, "random")) { randomize = ON; continue; }
if(!strcmp(command, "hint")) { if(ponderMove != INVALID) printf("Hint: %s\n", MoveToText(ponderMove)); continue; }
if(!strcmp(command, "book")) { continue; }
// ignored commands:
if(!strcmp(command, "xboard")) { continue; }
if(!strcmp(command, "computer")){ continue; }
if(!strcmp(command, "name")) { continue; }
if(!strcmp(command, "ics")) { continue; }
if(!strcmp(command, "accepted")){ continue; }
if(!strcmp(command, "rejected")){ continue; }
if(!strcmp(command, "variant")) { continue; }
if(!strcmp(command, "")) { continue; }
if(!strcmp(command, "usermove")){
int move = ParseMove(inBuf+9);
if(move == INVALID) printf("Illegal move\n");
else {
stm = MakeMove(stm, move);
ponderMove = INVALID;
gameMove[moveNr++] = move; // remember game
}
continue;
}
printf("Error: unknown command\n");
}
return 0;
}
Last edited by H.G.Muller on 29 May 2013, 11:17, edited 4 times in total.
Post by H.G.Muller 01 May 2011, 09:24
Some explanations:
Basically, the protocol driver is an infinite loop with 4 sections in it:
while(1) {
if(ENGINE_ON_MOVE) THINK_AND_DO_MOVE;
PONDER_OR_ANALYZE;
READ_INPUT_LINE; // blocking input
HANDLE_INPUT_COMMAND;
}
We break out of this loop in section 4, when we handle the quit command.
The PONDER_OR_ANALYZE section only has to be present in engines advanced enough that they actually can ponder or analyze. It is not that this section itself is terribly complicated. The major difficulty is that it requires the engine function PonderUntilInput(color). This is basically your normal Search routine. But it does require this Search to be abortable at any time, not just when you happen to return to the root to change move there, or happen to start a new iteration. And it requires a method to check for the presence of input, without blocking when there happens to be none. This will be discussed later.
The other 3 sections are all essential. They cause the input commands to be processed one by one (= line by line), but after each command, it is checked if it is now the engine's turn (because commands can change the side to move, or the side the engine should play), and if it is, it will start thinking for as long as it seems wise, and then move. (I.e perform the move on its internal board, and print it.) In principle this checking if it is the engine's turn could be skipped after processing of commands that could neither alter the side to move or the side played by the engine, but it is convenient to be able to end the processing of a command with 'continue;' to jump back to the beginning of the loop. For reasons that will only become apparent when we discuss the details of pondering, the 'time' and 'otim' commands make an exception on this, and after they are processed we resume reading input immediately.
Note that this driver will block in the section that reads the input command for as long as there is no input, or the input line is not yet complete. The latter should never be a problem; GUIs using WB protocol will not maliciously pester their engines with partial lines (not terminated with a linefeed), and then wait for along time. So as soon as input starts, you can be sure to be able to read to the end of the line without much waiting. The only waiting can occur for the first input character of a command. Of course as long as you don't want the engine to ponder or analyze, waiting is not a big deal, as (after having moved) there is nothing else you could do anyway. Only after the next command there can be something to do.
The processing of the commands is most of the time extremely simple. They just set the value of a variable, which then later will affect the search. Not all commands have to be implemented. For instance, when your engne doesn't support pondering yet, it would be pointless to process the 'hard' and 'easy' commands to switch it on and off. The minimal set of commands you would need to implement to have an engine play games is:
- new
- go
- force
- INPUT MOVES
This would make the engine play, but it would not pay any attention to the time on its clock. So it would only work if you set the time control of the GUI to the one the engine happens to obey on its own initiative. Otherwise the engine would be flagged. So very desirable to also have are:
- level
- time
Something important has to be remarked about the INPUT MOVES. The model driver expects all input moves to be prefixed by 'usermove'. But this is not the default way the GUI will send moves. It will only do that for engines that have replied to the 'protover' command with 'feature usermove=1'. So either you would have to also implement the handling of the 'protover' command, or you would have to recognize input moves in a different way. In stead of the '!strcmp(command, "usermove")', you could for instance check if the second and fourth characters are digits. (WB protocol commands never contain digits.) Like
if(command[1] >= '0' && command[1] <= '9') {
int move = ParseMove(inBuf);
....
Next on the order of priorities would be to allow setting up of positions, through the 'setboard' command. Also here there is the complication that GUIs would not by default send the position in this format. Again you have to reply to the 'protover' command to acheive that, this time with 'feature setboard=1'. Answering to 'protover' with 'feature done=1' will greatly speed up starting your engine anyway, because otherwise the GUI will be waiting for (more) 'feature' commands for some time, before continuing. So I guess 'protover' deserves to be pretty high on the list of priorities. So we add:
- protover
- setboard
Another command that could speed up things, and smoothen operation, is the 'quit' command. When the engine does not respond to that, the GUI might wait some time, and then forcefully kill it. Which acheives the purpose, but does involve again unnecessary waiting time. And besides, handling 'quit' is totally trivial, so there really is no reason to postpone its implementation. Perhaps it should have gone with the first batch.
- quit
Post by H.G.Muller 08 May 2011, 19:31
After getting the basics of the interface working, it is time to have a closer look at pondering. For this the rotine PonderUntilInput() is required. This is basically a normal search st like you do when the engine is thinking. But one non-trivial novelty is that it has to be abortable at any time, as you don't know in advance when the opponent's move will arrive that makes you want to start doing something else. There are several ways to do it, and one of the simplest is to have a gobal variable 'abortFlag', which is cleart before any search, and tested after taking back a move. Something like:
int Search(...)
{
GenerateMoves();
for(ALL_MOVES) {
MakeMove();
score = -Search(...);
UnMake();
if(abortFlag) return 0;
// handle score, etc.
...
}
return bestScore;
}
Because this makes you return before you have done anything with the score returned from the next-higher level, it is actually not important what you return. You have to be sure to do this abort return after UnMake has completely restored the game state to what it was when you entered the node. Note, however, that in the root you have to be a little more careful, and make sure some valid score and move are returned. Usually you save the best move and score of the previous iteration for that purpose. If you save those in a place accessible to the caller of RootSearch(), there is actually no need to return anything when you actually return from RootScore(), and that also holds for the abort return.
int rootScore;
MOVE rootMove;
void RootSearch()
{
GenerateMoves();
for(depth=1; STOP_CONDITION; depth++) { // iterative deepening loop
bestScore = -INFINITY;
for(ALL_MOVES) {
MakeMove();
score = -Search(...);
UnMake();
if(abortFlag) return;
// handle score, etc.
...
}
// end of iteration
...
rootMove = bestMove;
rootScore = bestScore;
}
}
This way to abort a search can be used both during thinking and pondering. When thinking, you could set the abortFlag when the time you have been thinking approaches the 'never exceed' time limit, and when you are pondering you would set it based on thearrival of input. In both cases you would have to periodically check in the search for the termination condition. Because both checks are usually rather time consming, you don't want to do that in every node, but perhaps once every 1000 nodes. If you search 1 million nodes per second, that still means you check 1000 times per second, so you will be able to react pretty quickly. You could for instance make the check where you increment your node counter:
nodeCount++;
if( (nodeCount & 0x3FF) == 0 && TerminalCondition() ) abortFlag = TRUE;
This checks the TerminalCondition only if the 10 low-order bits of nodeCount are all zero, i.e. once every 1024 nodes.
When pondering, the TerminalCondition wold be that there is input pending. To test this without hanging if there is none, I use the routine
int InputWaiting()
{
#ifdef WIN32
DWORD cnt;
static HANDLE hInp = NULL;
if(hInp == NULL) hInp = GetStdHandle(STD_INPUT_HANDLE);
return !PeekNamedPipe(hInp, NULL, 0, NULL, &cnt, NULL) || cnt > 0;
#else
static fd_set rset;
static struct timeval timeout = {0, 0};
FD_ZERO(&rset);
FD_SET(0, &rset);
if(select(1, &rset, NULL, NULL, &timeout) < 0) printf("error X\n");
if (FD_ISSET(0, &rset)) return 1;
#endif
return 0;
}
The conditional chooses between the Windows and Linux code. I should add that the Windows code assumes that the input is a pipe, as it would be when the engine runs under a GUI, and would not work if the input is a 'terminal'. So with this code the engine would stop pondering immediately when you are running it from the command line. (But who cares...?)
Time Control
Post by H.G.Muller 13 May 2011, 20:15
Strictly speaking, time control is an intrinsic part of the engine, and not part of the protocol driver. However, not every engine that you want to convert to WinBoard protocol supports all WinBoard time-control modes. It is quite possible that the engine's thinking time can only be controlled by search depth, for instance. For this reason, I want to include a short discussion on how to implement the time controls defined in WinBoard protocol. A second reason is that the routines discussed here will also feature in a more advanced implementation of pondering.
We already discussed the least subtle way of enforcing time control: aborting the search when a certain time is reached. This is a very inefficient way to control the search time, though. A large fraction (50-70%) of the search time of an aborted search is usually completely wasted. It is much more efficient to let an engine decide itself what is a good time to stop, so it gets the opportunity to finish something it started, and the work spend on it is not wasted.
There are two natural points to stop: after finishing a complete iteration, and after finishing the search of a move in the root. The latter is already dubious; for instance, if you would have completed a 9-ply search, and then start the 10 ply iteration by searching the best move of the 10-ply iteration, stopping immediately after it wouldn't have brought you a lot. You still would have no choice but to play that move. To have any beneficial effect from the 10-ply search, you would have to search at least two moves at 10 ply, so that you can change move if the second move you searched happens to be better. An additional complication is that in a normal search, searching a move that is the best so far usually takes far more time than searching one that is no good.
For this reason, we already refrain from starting a new iteration when more than half the nominal time for an iteration has start. This limit is stored in the 'noNewIterationLimit' global variable. As a rough guideline, searching the first move of an iteration at N+1 ply, takes as much time as the entire N-ply iteration. (This because after having done that first move, it actually is an N-ply search!). Then searching the first two moves of the new iteration we start, will bring us around 1.5 times the nominal move time when we started it at 0.5 times nominal. If the second move we search is worse than the first, it is probably rejected much faster, so we could reject a great number of them in the same time, and acheive good confidence that the first move we tries is indeed the best, even if we did not have time to search all. So at the end of the loop over moves in RootSearch, we put a check that will break out of the loop when we have reached 1.5 times nominal search time (the 'noNewMoveLimit').
It is good to make an exception on this, though: if the first move we searched has a really large drop in score compared to the previous iteration, we are apparently dealing with a distant threat that the engine has not been able to recognize so far. There then is a far-above-average probability that one of the other moves could actually pre-empt that threat. So spending some extra time on the remaining moves now is time very well spent. Much better to try and find a solution now, than play a move you already know to be bad, and hope the time you save by that can be used to find a miraculous recovery later! For this reason, we accompany the test for exceeding the noNewMoveLimit with a test on the score drop. Only if we have a score-wise acceptable move when we exceed this time limit, we will play it immediately, and otherwise, we will continue searching remaining moves of this iteration, to make sure the bad move is the best we can do.
Occasionally this gets out of hand as well, but the neverExceedLimit protects us against that. It is set such that we can search up to 10 times the nominal time per move. Of course you cannot afford that if you are only a few moves away from the time control. For this reason we apply the factor 10/(movesToGo+9), which reduces to 1 if you have only one move to go, but allocates 10 times as much time to the next move when we are still far away from the time control, where we have complete freedom in distributing the time between the moves.
int rootScore;
MOVE rootMove;
// time-control variables
int startTime;
int noNewIterationLimit;
int noNewMoveLimit;
int neverExceedLimit;
#define MARGIN 25
int TimeUsed()
{
return ReadClock() - startTime;
}
void RootSearch()
{
startTime = ReadClock();
GenerateMoves();
for(depth=1; depth<=maxDepth && TimeUsed()<noNewIterationLimit; depth++) { // iterative deepening loop
bestScore = -INFINITY;
for(ALL_MOVES) {
MakeMove();
score = -Search(...);
UnMake();
if(abortFlag) return;
// handle score, etc.
...
if(TimeUsed() > noNewMoveLimit && bestScore > rootScore - MARGIN) break;
}
// end of iteration
...
rootMove = bestMove;
rootScore = bestScore;
}
}
#define GUESSEDLENGTH 40
void SetTimeLimits(int msecLeft, int st, int tc, int inc, int mps, int moveNr)
{
int movesToGo = mps - moveNr/2;
if(st > 0) movesToGo = 1; // in maximum-time-per-move mode, the time left is always for one move
else if(mps == 0) movesToGo = GUESSEDLENGTH; // in sudden-death, we have to guess how many moves we still must do
else while(movesToGo <= 0) movesToGo += mps; // calculate moves before next time control
msecLeft -= 16; // keep absolute safety margin of 16 msec
neverExceedLimit = 10*msecLeft / (movesToGo + 9);
noNewMoveLimit = 1.5*msecLeft / (movesToGo + 0.5);
noNewIterationLimit = 0.5*msecLeft / movesToGo;
}
Post by H.G.Muller 29 May 2013, 08:02
The implementation of pondering (and analyse mode, which is basically pondering the position in force mode) in the design discussed above suffers from the problem that each incoming command interrupts the ponder search. This is OK when the search efficiently picks up where it left off after restarting it. But not all engines have this nice property, and engines without hash table would not remember anything from the previous search at all.
It would thus be better to have a design that can check incoming commands while the search is in progress. If it then sees an input move, it can decide if this was a ponder hit or miss. In case of a miss it can abort the current ponder search, which was wasted effort anyway. But in case of a hit, it could simply let the search run on, but now as a normal search with time limits, rather than a ponder search.
Note that this approach requires two different ways to handle input moves, depending on whether they are ponder hits or misses. Pondering already speculatively performed the move in the root before you started pondering, so in case of a hit the input move can be ignored, and it is the taking back of the move after the seach completes that should be suppressed. In case of a miss the ponder move should be taken back, and the input move should be performed after that, both of which can only be done after the search is aborted. We will implement it by leaving the input move in the input buffer on a ponder miss, so that the main protocol driver's input loop will see it again.
The design of the main loop will have to be changed. Before, we used different calls to Search() for pondering and thinking. But is a ponder hit can change a ponder search into a normal search, these seaerches are logically the same, and using separate calls for them just leads to code duplication. So the new design will look like
while(1) {
if( ENGINE_ON_MOVE || PONDER_ON_MOVE ) {
if( PONDER_ON_MOVE ) MAKE_PONDER_MOVE;
THINK;
if( INPUT_LEFT ) UNMAKE_PONDER_MOVE; // ponder search was interrupted
else {
MAKE_MOVE;
continue;
}
} else
PONDER_OR_ANALYZE;
if( ! INPUT_LEFT ) READ_INPUT_LINE; // blocking input
HANDLE_INPUT_COMMAND;
}
This code has a 'unified' call to Search(), written as THINK, used both for thinking and pondering on a speculative move. There still is a second call to Search() for analyzing and pondering on a position, like in the old design. But now that PONDER_OR_ANALYZE is made conditional, in the 'else' clause of the if(ENGINE_ON_MOVE || PONDER_ON_MOVE), so that it would be never done if you pondered on a move or after thinking, and only for pondering a position, rather than a speculative move. In the old design all pondering was done here, so it needed to be called after thinking completed, to start pondering before waiting for input. Now this is acheived by looping back (with the aid of a 'continue' statement) to the ponder / think code every time the computer plays a move.
Post by H.G.Muller 29 May 2013, 09:22
If we look a bit more in detail how we have to decide whether we have a ponder hit or miss, it turns out that WB protocol is not very friendly in this respect. We obviously have to decide this on the basis of the usermove command that comes in, but this will always be preceded by the time and otim command to inform us of the clocks. And when we have a ponder hit, these commands will be relevant for turning the ponder search into a normal search by time limits.
So when we detect during pondering that there is input (with the aid of the already described InputWaiting() routine), we must be prepared to process the time and otim command, as well as usermove. In addition, WB protocol has the strange habit to poll engines for additional search info during analysis mode, with a '.' (period) command. It is also very undesirable that this command would abort the search, so we will process it too. For all other commands we can abort the search, leaving the command in the input buffer, so that after the search unwinds, and we get to the main loop of the protocol driver, the latter will encounter the command again, and execute it there.
So the routine TerminalCondition() needs to process 4 commands in ponder mode. Of these, only usermove should change the search mode, either to abort it (by setting abortFlag), or by changing the mode from pondering to thinking (so that future calls to TerminalCondition() will check the time rather than the input. The . command for periodic updates should simply output the requested message (for which it needs to access some information from the root node). The time and otim command were already treated special in the old code, because they would always be immediately followed by other commands, so that it would be pointless to resume pondering after them. Thi was implemented by jumping immediately back to reading a new input line (at the label noPonder). The new code behaves similarly, by not returning from TerminalCondition() (to resume the search), but staying in it for reading and processing the following command.
In the new design some information will have to be used both from TerminalCondition() as well as from the main loop of the protocol driver, and will thus have to be put in global, rather than local variables. This in particular applies to the time-control specifications. These are needed to determine the time limits for the search, both when thinking starts in the root, or when TerminalCondition() detects a ponder hit, and must convert the ongoing ponder search to a normal search. Also the input buffer must be accessible from both these places, to allow commands read in TerminalCondition() that could not be executed there to be left in it, so the main loop will later find them.
This gives the following code:
#define GUESSEDLENGTH 40
int mps, timeControl, inc, timePerMove; // time-control parameters
int neverExceedLimit, noNewMoveLimit, noNewIterationLimit; // used
by Search()
int timeLeft;
char inBuf[80], command[80], ponderMoveText[20];
char abortFlag, pondering;
void SetTimeLimits(int msecLeft)
{
int movesToGo = mps - moveNr/2;
if(st > 0) movesToGo = 1; // in maximum-time-per-move mode, the time left is always for one move
else if(mps == 0) movesToGo = GUESSEDLENGTH; // in sudden-death, we have to guess how many moves we still must do
else while(movesToGo <= 0) movesToGo += mps; // calculate moves before next time control
msecLeft -= 16; // keep absolute safety margin of 16 msec
neverExceedLimit = 10*msecLeft / (movesToGo + 9);
noNewMoveLimit = 1.5*msecLeft / (movesToGo + 0.5);
noNewIterationLimit = 0.5*msecLeft / movesToGo;
}
int PeekAtInput(int root)
{
while(1) {
ReadLine(inBuf);
sscanf(inBuf, "%s", command);
if(!strcmp(command, "otim")) { continue; } // do not resume pondering after receiving time commands, as move will follow immediately
if(!strcmp(command, "time")) { sscanf(inBuf, "time %d", &timeLeft); continue; }
if(!strcmp(command, ".")) { inBuf[0] = 0; return FALSE; }
// ignore for now
if(!root && !strcmp(command, "usermove")) {
if(!strcmp(inBuf+9, ponderMoveText)) { // ponder hit
inBuf[0] = 0; // eat away command, as we will process it here
pondering = 0; SetTimeLimits(10*timeLeft + TimeUsed()); // turn into time-based search
return FALSE; // do not abort
}
}
return TRUE; // other commands (or ponder miss) abort search
}
}
int TerminalCondition()
{
if(pondering) { // only new input can cause abort
if(InputWaiting()) return PeekAtInput(0); // but only abort if the input requires us
} else { // when thinking only time can cause abort
if(TimeUsed() > neverExceedLimit) return TRUE;
}
return FALSE;
}
Note that the SetTimeLimits() routine now only accepts a single parameter (the time left), as the time-control parameters are now accessible globally, so there is no need to pass them. The time left would also be accessible globally, but there is a subtlety here that in the case of calculating time limits for a 'flying start', we want to add the time already spent on pondering the move so far. e.g. if we have 20 sec left on the clock for 2 moves, and have already been pondering 10 sec on the first of those, it makes sense to allocate 5 more seconds on the current move (so they get 15 each, half of 10+20). When a search for thinking is started from scratch in the main loop, there would be no such addition.
Another subtlety is the 'root' parameter to PeekAtInput(): this was added to allow us to also call this routine from the main loop for reading the input line, as well as processing the time and otim commands, so that the code for processing these commands does not have to be duplicated (and the nasty 'goto noPonder' can disappear). In this situation you would not want it to process the usermove command, though, (as that needs different treatment), and the root parameter is used to tell it that.
Last edited by H.G.Muller on 29 May 2013, 13:52, edited 2 times in total.
Post by H.G.Muller 29 May 2013, 10:37
With this infrastructure in place, the main loop of the engine would look like this:
#define OPPONENT(x) WHITE + BLACK - (x)
main()
{
int stm=WHITE; // side to move
int engineSide=NONE; // side played by engine
int maxDepth; // used by search
MOVE move, ponderMove;
int i, score;
while(1) { // infinite loop
fflush(stdout); // make sure everything is printed before we do something that might take time
inBuf[0] = 0; // empty input buffer, so we can detect if something appears in it
pondering = (ponder && engineSide == OPPONENT(stm) && moveNr != 0); // calculate if we are expected to ponder
if(engineSide == stm || pondering && ponderMove != INVALID) {
MOVE newPonderMove; int oldStm = stm;
if(pondering) { // we are apparently pondering on a speculative move
sprintf(ponderMoveText, "%s\n", MoveToText(ponderMove)); // remember ponder move as text (for hit detection)
stm = MakeMove(stm, ponderMove);
SetTimeLimits(INFINITE); // make sure we will never terminate because of time
} else SetTimeLimits(10*timeLeft);
score = SearchBestMove(stm, &move, &newPonderMove);
if(pondering) { // pondering was aborted because of miss or other command
UnMake(ponderMove); stm = oldStm;
pondering = FALSE;
} else if(move == INVALID) { // game apparently ended
engineSide = NONE; // so stop playing
PrintResult(stm, score);
} else {
stm = MakeMove(stm, move); // assumes MakeMove returns new side to move
gameMove[moveNr++] = move; // remember game
printf("move %s\n", MoveToText(move));
ponderMove = newPonderMove;
continue; // start pondering (if needed)
}
} else if(engineSide == ANALYZE || pondering) { // this catches pondering when we have no move
MOVE dummy;
pondering = TRUE; // in case we must analyze
ponderMoveText[0] = 0; // make sure we will never detect a ponder hit
SetTimeLimits(INFINITE); // make sure we will never terminate because of time
SearchBestMove(stm, &dummy, &dummy);
pondering = FALSE;
}
fflush(stdout); // make sure everything is printed before we do something that might take time
// the previous calls to SeachBestMove() could have left a command that interrupted it in inBuf !
if(inBuf[0] == 0) PeekAtInput(1); // handles time, otim
// recognize the command,and execute it
if(!strcmp(command, "quit")) { break; } // breaks out of infinite loop
if(!strcmp(command, "force")) { engineSide = NONE; continue; }
if(!strcmp(command, "analyze")) { engineSide = ANALYZE; continue; }
if(!strcmp(command, "exit")) { engineSide = NONE; continue; }
... // processing of other commands that do not alter the position (or side to move)
ponderMove = INVALID;
... // processing of commands that do alter the position (new, setboard, usermove, undo, remove, white, black)
}
}
Note that we did away here with the routine PonderUntilInput(), for which we now also use SearchBestMove(). To make that possible the latter now longer sets its own time limits (and thus also does not get the time-control parameters passed), but relies on an extra call to SetTimeLimits() before it to do that. For pondering we use the kludge to set ridiculously large time limits. (This is mainly to prevent the tests on noNewMoveLimit and noNewIterationLimit in RootSearch(), as the neverExceedLimit will not be tested by TerminalCondition() when pondering. Perhaps a neater way to solve this would be to explicitly testing for 'pondering' in the tests of these other limits in RootSearch(), in which case all SetTimeLimits(INFINITE) calls could be left out, as setting pondering = TRUE then already has that effect.)
Last edited by H.G.Muller on 29 May 2013, 14:42, edited 3 times in total.
Post by H.G.Muller 29 May 2013, 12:58
This would be the complete code, tested to the point where it at least compiles without serious warnings:
/********************************************************/
/* Example of a WinBoard-protocol driver, by H.G.Muller */
/********************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// four different constants, with values for WHITE and BLACK that
suit your engine
#define WHITE 1
#define BLACK 2
#define NONE 0
#define ANALYZE 3
// some value that cannot occur as a valid move
#define INVALID 666
// some parameter of your engine
#define MAXMOVES 500 /* maximum game length */
#define MAXPLY 60 /* maximum search depth */
#define OFF 0
#define ON 1
#ifndef WIN32
# include <sys/ioctl.h>
# include <sys/time.h>
# define FALSE 0
# define TRUE 1
#endif
#define DEFAULT_FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w
KQkq - 0 1"
typedef int MOVE; // in this example moves are encoded as an int
int moveNr; // part of game state
MOVE gameMove[MAXMOVES]; // holds the game history
// Some routines your engine should have to do the various essential things
int MakeMove(int stm, MOVE move); // performs move, and
returns new side to move
void UnMake(MOVE move); // unmakes the move;
int Setup(char *fen); // sets up the position from the given FEN, and returns the new side to move
void SetMemorySize(int n); // if n is different from last time, resize all tables to make memory usage below n MB
char *MoveToText(MOVE move); // converts the move from your internal format to text like e2e2, e1g1, a7a8q.
MOVE ParseMove(char *moveText); // converts a long-algebraic text move to your internal move format
int SearchBestMove(int stm, MOVE *move, MOVE *ponderMove);
void PonderUntilInput(int stm); // Search current position for stm, deepening forever until there is input.
// Some global variables that control your engine's behavior
int ponder;
int randomize;
int postThinking;
int maxDepth;
int resign; // engine-defined option
int contemptFactor; // likewise
int mps, timeControl, inc, timePerMove; // time-control parameters
int neverExceedLimit, noNewMoveLimit, noNewIterationLimit; // used by Search()
int timeLeft, startTime;
char inBuf[80], command[80], ponderMoveText[20];
char abortFlag, pondering;
int ReadClock()
{ // returns wall-clock time in msec
#ifdef WIN32
return GetTickCount();
#else
struct timeval t;
gettimeofday(&t, NULL);
return t.tv_sec*1000 + t.tv_usec/1000;
#endif
}
int InputWaiting()
{
#ifdef WIN32
DWORD cnt;
static HANDLE hInp = NULL;
if(hInp == NULL) hInp = GetStdHandle(STD_INPUT_HANDLE);
return !PeekNamedPipe(hInp, NULL, 0, NULL, &cnt, NULL) || cnt > 0;
#else
static fd_set rset;
static struct timeval timeout = {0, 0};
FD_ZERO(&rset);
FD_SET(0, &rset);
if(select(1, &rset, NULL, NULL, &timeout) < 0) printf("error X\n");
if (FD_ISSET(0, &rset)) return 1;
#endif
return 0;
}
int TimeUsed()
{
return ReadClock() - startTime;
}
#define GUESSEDLENGTH 40
void SetTimeLimits(int msecLeft)
{
int movesToGo = mps - moveNr/2;
if(timePerMove > 0) movesToGo = 1; // in maximum-time-per-move mode, the time left is always for one move
else if(mps == 0) movesToGo = GUESSEDLENGTH; // in sudden-death, we have to guess how many moves we still must do
else while(movesToGo <= 0) movesToGo += mps; // calculate moves before next time control
msecLeft -= 20; // keep absolute safety margin of 20 msec
neverExceedLimit = 10*msecLeft / (movesToGo + 9);
noNewMoveLimit = 1.5*msecLeft / (movesToGo + 0.5);
noNewIterationLimit = 0.5*msecLeft / movesToGo;
}
void ReadLine()
{ // read one line of input
int i, c;
for(i = 0; (inBuf[i] = c = getchar()) != '\n'; i++) if(c == EOF || i>77) exit(0);
inBuf[i+1] = 0;
}
int PeekAtInput(int root)
{
while(1) {
ReadLine(inBuf);
sscanf(inBuf, "%s", command);
if(!strcmp(command, "otim")) { continue; } // do not resume pondering after receiving time commands, as move will follow immediately
if(!strcmp(command, "time")) { sscanf(inBuf, "time %d", &timeLeft); continue; }
if(!strcmp(command, ".")) { inBuf[0] = 0; return FALSE; }
// ignore for now
if(!root && !strcmp(command, "usermove")) {
if(!strcmp(inBuf+9, ponderMoveText)) { // ponder hit
inBuf[0] = 0; // eat away command, as we will process it here
pondering = 0; SetTimeLimits(10*timeLeft + TimeUsed()); // turn into time-based search
return FALSE; // do not abort
}
}
return TRUE; // other commands (or ponder miss) abort search
}
}
int TerminalCondition()
{
if(pondering) { // only new input can cause abort
if(InputWaiting()) return PeekAtInput(0); // but only abort if
the input requires us
} else { // when thinking only time can cause abort
if(TimeUsed() > neverExceedLimit) return TRUE;
}
return FALSE;
}
#ifdef EXAMPLE
// these are only examples for where and how you should test for time-control enforcement in your search
int rootScore;
MOVE rootMove;
int Search()
{
nodeCount++;
if((nodeCount & 0x3FF) == 0 && TerminalCondition()) abortFlag = TRUE; // test if we should abort (not too often)
...
for(ALL_MOVES) {
MakeMove();
score = -Search(...);
UnMake();
if(abortFlag) return 0; // here we put an abort to make the search unwind
...
}
}
}
#define MARGIN 25
void RootSearch()
{
int depth, score, bestScore; MOVE rootMove
startTime = ReadClock();
GenerateMoves();
for(depth=1; depth<=maxDepth && (pondering || TimeUsed()<noNewIterationLimit); depth++) { // iterative deepening loop
bestScore = -INFINITY;
for(ALL_MOVES) {
MakeMove();
score = -Search(...);
UnMake();
if(abortFlag) return;
// handle score, etc.
...
if(!pondering && TimeUsed() > noNewMoveLimit && bestScore > rootScore - MARGIN) break; // extra time for fail low
}
// end of iteration
...
rootMove = bestMove;
rootScore = bestScore;
}
}
#endif
int TakeBack(int n)
{ // reset the game and then replay it to the desired point
int last, stm;
stm = Setup(NULL); // assumed to remember argument it was last called with
last = moveNr - n; if(last < 0) last = 0;
for(moveNr=0; moveNr<last; moveNr++) stm = MakeMove(stm, gameMove[moveNr]);
return stm;
}
void PrintResult(int stm, int score)
{
if(score == 0) printf("1/2-1/2\n");
if(score > 0 && stm == WHITE || score < 0 && stm == BLACK)
printf("1-0\n");
else printf("0-1\n");
}
#define OPPONENT(x) WHITE + BLACK - (x)
int main()
{
int stm=WHITE; // side to move
int engineSide=NONE; // side played by engine
MOVE move, ponderMove;
int score;
while(1) { // infinite loop
fflush(stdout); // make sure everything is printed before we do something that might take time
inBuf[0] = 0; // empty input buffer, so we can detect if something appears in it
pondering = (ponder && engineSide == OPPONENT(stm) && moveNr != 0); // calculate if we are expected to ponder
if(engineSide == stm || pondering && ponderMove != INVALID) {
MOVE newPonderMove; int oldStm = stm;
if(pondering) { // we are apparently pondering on a speculative move
sprintf(ponderMoveText, "%s\n", MoveToText(ponderMove)); // remember ponder move as text (for hit detection)
stm = MakeMove(stm, ponderMove);
gameMove[moveNr++] = ponderMove; // remember game
} else SetTimeLimits(10*timeLeft);
score = SearchBestMove(stm, &move, &newPonderMove);
if(pondering) { // pondering was aborted because of miss or other command
UnMake(ponderMove); stm = oldStm; moveNr--;
pondering = FALSE;
} else if(move == INVALID) { // game apparently ended
engineSide = NONE; // so stop playing
PrintResult(stm, score);
} else {
stm = MakeMove(stm, move); // assumes MakeMove returns new side to move
gameMove[moveNr++] = move; // remember game
printf("move %s\n", MoveToText(move));
ponderMove = newPonderMove;
continue; // start pondering (if needed)
}
} else if(engineSide == ANALYZE || pondering) { // this catches pondering when we have no move
MOVE dummy;
pondering = TRUE; // in case we must analyze
ponderMoveText[0] = 0; // make sure we will never detect a ponder hit
SearchBestMove(stm, &dummy, &dummy);
pondering = FALSE;
}
fflush(stdout); // make sure everything is printed before we do something that might take time
// the previous calls to SeachBestMove() could have left a command that interrupted it in inBuf !
if(inBuf[0] == 0) PeekAtInput(1); // handles time, otim
// recognize the command, and execute it
if(!strcmp(command, "quit")) { break; } // breaks out of infinite loop
if(!strcmp(command, "force")) { engineSide = NONE; continue; }
if(!strcmp(command, "analyze")) { engineSide = ANALYZE; continue; }
if(!strcmp(command, "exit")) { engineSide = NONE; continue; }
if(!strcmp(command, "level")) {
int min, sec=0;
sscanf(inBuf, "level %d %d %d", &mps, &min, &inc) == 3 || // if this does not work, it must be min:sec format
sscanf(inBuf, "level %d %d:%d %d", &mps, &min, &sec, &inc);
timeControl = 60*min + sec; timePerMove = -1;
continue;
}
if(!strcmp(command, "protover")){
printf("feature ping=1 setboard=1 colors=0 usermove=1 memory=1 debug=1");
printf("feature option=\"Resign -check 0\""); // example of an engine-defined option
printf("feature option=\"Contempt -spin 0 -200 200\""); // and another one
printf("feature done=1");
continue;
}
if(!strcmp(command, "option")) { // setting of engine-define option; find out which
if(sscanf(inBuf+7, "Resign=%d", &resign) == 1) continue;
if(sscanf(inBuf+7, "Contempt=%d", &contemptFactor) == 1) continue;
continue;
}
if(!strcmp(command, "sd")) { sscanf(inBuf, "sd %d", &maxDepth); continue; }
if(!strcmp(command, "st")) { sscanf(inBuf, "st %d", &timePerMove); continue; }
if(!strcmp(command, "memory")) { SetMemorySize(atoi(inBuf+7)); continue; }
if(!strcmp(command, "ping")) { printf("pong%s", inBuf+4); continue; }
if(!strcmp(command, "easy")) { ponder = OFF; continue; }
if(!strcmp(command, "hard")) { ponder = ON; continue; }
if(!strcmp(command, "go")) { engineSide = stm; continue; }
if(!strcmp(command, "post")) { postThinking = ON; continue; }
if(!strcmp(command, "nopost")) { postThinking = OFF;continue; }
if(!strcmp(command, "random")) { randomize = ON; continue; }
if(!strcmp(command, "hint")) { if(ponderMove != INVALID) printf("Hint: %s\n", MoveToText(ponderMove)); continue; }
// if(!strcmp(command, "")) { sscanf(inBuf, " %d", &); continue; }
// ignored commands:
if(!strcmp(command, "book")) { continue; }
if(!strcmp(command, "xboard")) { continue; }
if(!strcmp(command, "computer")){ continue; }
if(!strcmp(command, "name")) { continue; }
if(!strcmp(command, "ics")) { continue; }
if(!strcmp(command, "accepted")){ continue; }
if(!strcmp(command, "rejected")){ continue; }
if(!strcmp(command, "variant")) { continue; }
if(!strcmp(command, "")) { continue; }
// now process commands that do alter the position, and thus invalidate the ponder move
ponderMove = INVALID;
if(!strcmp(command, "new")) { engineSide = BLACK; stm = Setup(DEFAULT_FEN); maxDepth = MAXPLY; randomize = OFF; continue; }
if(!strcmp(command, "setboard")){ engineSide = NONE; stm = Setup(inBuf+9); continue; }
if(!strcmp(command, "undo")) { stm = TakeBack(1); continue; }
if(!strcmp(command, "remove")) { stm = TakeBack(2); continue; }
if(!strcmp(command, "usermove")){
int move = ParseMove(inBuf+9);
if(move == INVALID) printf("Illegal move\n");
else {
stm = MakeMove(stm, move);
gameMove[moveNr++] = move; // remember game
}
continue;
}
printf("Error: unknown command\n");
}
return 0;
}