Timing Moves
There are three ways in which Rival can be instructed to make its moves.
- Fixed Search Depth
- Fixed Time
- Given number of moves in a given time
- Base plus Increment per Move
If the program is instructed to make a move within a fixed time limit, a full-width search is performed to a depth of two followed by progressively deeper searches, each time extending the maximum search depth by one. This continues until the time limit expires. At first this appears like a waste of valuable search time but with the use of a transposition/refutation table, killer heuristics and the knowledge of the best move sequence from previous iterations, iterative deepening can often complete searches faster than a fixed depth search. The technique is also used if the program is instructed to search to a specified depth. This is primarily so that a move is always available in case the user instructs the program to make a move before the search is complete.
The third move selection method is the method used in chess tournaments and is the method that produces the best results from the program. When playing this way, the program will calculate the average amount of time available to make each of its remaining moves. The program will then aim to make its next move within ¾ of this time, effectively saving time for situations later in the game where the time may be more useful. An example from one of the games played by the program will help to demonstrate the advantages of this timing method.
The position shown in figure 4 was reached. Rival was playing the white pieces. It is move number 34 with white to move. The white clock was at 6 minutes, 47 seconds and the time control was 60 moves in 15 minutes, leaving the program with an average time of a little over 18 seconds to make each move. Therefore, the program would aim to make its next move after 14 seconds.
Figure 4 Chess position reached in a game played by the program. White to play.
The program had completed a search to depth four after about three seconds considering that the move sequence 1. H3*H6..G8*G2 2. D2*G2..G6*G2 would leave it a pawn up in material. A search to depth five was started and the program realised very quickly that the move H3*H6 was bad, leading to the loss of the queen with a series of checks 1. H3*H6..G8*G2+ 2. G1-H1..G2-E2+ 3. D4-D5..E2*E1+. The depth five search continued but when the 14 seconds was up, the best move was 1. E1-G3 with a move sequence that resulted in the loss of the queen and a pawn for the gain of a rook. At this point, more time was allowed to search for a reasonable move. The eventual move was 1. G1-H1 which the program again believed left it a pawn up in material. In many cases, this may have prevented a heavy defeat but in this example the program's position was hopeless and black won the match comfortably.
If, after the allotted amount of time, the current best move does not score within 75 points (roughly ¾ of a pawn) of the best move from the previous iteration, the search will continue until an acceptable move is found or a the search time exceeds an upper limit.
Base plus Increment method
This method was added when Rival was made compatible with Tim Mann's Winboard to allow Rival to play as an automated player on an Internet Chess Server and to allow it to play automated against other chess engines. At the beginning of the search, Rival sets two variables, NormalMoveTime and ExtendMaxMoveTime. The normal move time is the time within which Rival will attempt to make a move unless the program believes it will benefit from having more time (as described above), in which case it will make the move within the extend max move time.The following code outlines (roughly) how these variables are set:
ExtendMaxMoveTime = 0;
if (Increment>0) {
NormalMoveTime = Increment;
if (TimeLeft>30000) {
ExtendMaxMoveTime = min(Increment*4, (int)(TimeLeft/2.0));
NormalMoveTime = min(Increment*2, (int)(TimeLeft/2.0));
}
} else {
// Guess number of moves left
TotalMoves = (TotalMovesMade < 60 ? 80 : (TotalMovesMade < 100 : 120));
MovesLeft = TotalMoves - TotalMovesMade;
if (MovesLeft>0 && ClockLeft>10000) {
ClockLeft -= BaseMinutes*5;
TimePerMove = ((float)ClockLeft/(float)MovesLeft);
NormalMoveTime = (int)TimePerMove;
} else {
// Minimal Thinking Time
NormalMoveTime = 0;
}
}
Introduction