Progress on Rustic

[hgm]

Fairy-Max' fixed-time-per-move implementation had to be very conservative, because there is no way to abort a search. It only tests at the start of an iteration whether there is time for yet another one. So it must be very sure that there is such time, and the duration of an iteration can be quite unpredictable. And if it would ever to be optimisitic, it forfeits immediately. So although the average EBF is just 2-3, it must take into account that it sometimes takes 10 times longer. So it doesn't start a new iteration if it has already used more than ~5% of the maximum time.

I never bothered to improve that; the problem doesn't exist in classical or incremental TC. (In classical TC it just divides the time such that the last move before the next session gets as much time as 5 average moves.) And fixed-time TC is not recommended for engines anyway: it is a very inefficient way to use CPU time; the large fraction of the time spent on unfinished iterations is mostly wasted.

And yes, PV is very useful for identifying why the engine blunders, if it does. And it is quite trivial to implement; I think in Fairy-Max I only had to add 2 or 3 lines of code.

[mvanthoor]

Fairy-Max' fixed-time-per-move implementation had to be very conservative, because there is no way to abort a search. It only tests at the start of an iteration whether there is time for yet another one. So it must be very sure that there is such time, and the duration of an iteration can be quite unpredictable. And if it would ever to be optimisitic, it forfeits immediately. So although the average EBF is just 2-3, it must take into account that it sometimes takes 10 times longer. So it doesn't start a new iteration if it has already used more than ~5% of the maximum time.

I never bothered to improve that; the problem doesn't exist in classical or incremental TC. (In classical TC it just divides the time such that the last move before the next session gets as much time as 5 average moves.) And fixed-time TC is not recommended for engines anyway: it is a very inefficient way to use CPU time; the large fraction of the time spent on unfinished iterations is mostly wasted.

Yes, I'm still thinking about how to go about this. I have to implement some improvements when I implement game-time:

- I need to guess if I can finish another iteration (it seems to be a good guess that the next iteration costs up to 12x the amount of time of the previous). If the engine thinks it can't finish, it should abort before even starting.
- If the engine finds mate, it should abort after finishing the iteration and immediately return the move. Now it'll try to find a shorter mate, but to be honest, I don't really care about that.

And yes, PV is very useful for identifying why the engine blunders, if it does. And it is quite trivial to implement; I think in Fairy-Max I only had to add 2 or 3 lines of code.

Repetition detection, 50 move rule, and a PV are the next things on the list. I haven't seen the engine make outright blunders, but surprisingly, I've seen it make "intuitive guesses". One of them was to sacrifice a piece to be able to push a pawn to promotion, and only when it reached e3 the engine realized it wouldn't make it. After e3e2, white had a "zwischen-zug" to play his bishop around the board and then control E1.

On the other hand, I've seen my engine also pull some defensive stunts of which I thought "What the hell... I would NEVER have thought of that myself." One of those was where I thought it would lose a full rook, but then it just sacrificed it for two pawns ending in giving a check, and then proceeding to grab another two pawns for it. Pity I didn't think of saving those games separately.

[Ras]

Why taking the guess approach at all?

You can just allocate a maximum thinking time beforehand. That's either a fixed move time, or some logic based on remaining time, increment, game phase and other factors.

During search, you query the system time every so many nodes, something like 500 or so will do. If the time limit has been reached, quit the search.

If you start another depth iteration and aren't in "fixed time per move" mode, check whether you have already spent more then e.g. 50% of your allocated thinking time - if so, bail out.

[mvanthoor]

Why taking the guess approach at all?

You can just allocate a maximum thinking time beforehand. That's either a fixed move time, or some logic based on remaining time, increment, game phase and other factors.

During search, you query the system time every so many nodes, something like 500 or so will do. If the time limit has been reached, quit the search.

If you start another depth iteration and aren't in "fixed time per move" mode, check whether you have already spent more then e.g. 50% of your allocated thinking time - if so, bail out.

I already do all of this in the fixed move time mode, and the engine replies at exactly the set time. What I meant by guessing was that it's impossible to know if you're going to finish an iteration or not, and how much time you have for an interation.

In a game with base + increment (no repeating time control) or worse, time without repeat, you don't know how long the game is going to last. Then you'd have to guess, let's say... 5 minutes for the game (known), 60 moves for the game (guess) so you have 5 seconds per move. As soon as your last iteration uses any time at all, you'd better exit as to not exceed this time... but it could be that the game is over with you as the loser in 28 moves. You *could* in theory have spent more time, see a bit deeper, and not lose...

[Ras]

What I meant by guessing was that it's impossible to know if you're going to finish an iteration or not

That's right. But you can know when it will be unlikely, and that's e.g. if you have already used up 50% of the time that you had allocated for this move before starting the search. Then you can bail out (except in fixed time mode) and save the remaining time.

and how much time you have for an interation.

You decide that before starting the search, either as hard limit, or when not using fixed time, with the option of using additional time e.g. if you need to resolve a fail-low at root. If you're doing the latter, that will require additional logic because you can't do that if the current move is the last one before the time control.

In a game with base + increment (no repeating time control) or worse, time without repeat, you don't know how long the game is going to last. Then you'd have to guess

That's basically what I do. At each move, I guesstimate how many moves I think the game will last, based on the current move number. A more advanced approach could also consider the board position.

[mvanthoor]

Today Rustic gained the ability to display the principal variation. I implemented it using vectors, as described in this article:

http://vajoletchess.blogspot.com/2013/1 ... cipal.html

It basically does the same thing as a triangular PV array: create a child PV, and then stick it after the best move. The only difference is that it uses a vector passed into alpha-beta and a local variable. I could have implemented it using a triangular array (passed into alpha/beta within my "SearchInfo" struct), but as my MAX-DEPTH is set to 254, I didn't want to create a 254x254x8 byte array (over 500 kB) of which only half is used.

Also, this vector-implementation is very intuitive: "Just find the best move for this node, and put the series of best moves of the nodes below after it"; and it can be expressed literally as such in Rust:

Code: Select all

            // We found a better move for us.
            if eval_score > alpha {
                // Save our better evaluation score.
                alpha = eval_score;

                // We found a better move, so we have to replace our PV. We
                // do this by clearing the PV and then inserting our new
                // best move. Then append the child PV, created from the
                // nodes below this one.
                pv.clear();
                pv.push(current_move);
                pv.append(&mut child_pv);
            }

Very nice. The two things to be done before I can actually release this engine as Rustic Alpha 1 ("baseline") is to implement GameTime mode, XBoard to the point that it can do the same thing as the current UCI interface, and send "mate in X" to the GUI when the engine finds mate.

I've been testing this version using games that run at 5 seconds per move, against engines such as Shallow Blue. A (very) tentative guesstimate would put the engine at 1650 CCRL Blitz. It's about 150 points higher than I hoped for

Note that the engine doesn't have ANY search optimizations or evaluation yet, beyond MVV-LVA (which is absolutely essential), material count, and a PSQT. Shallow Blue is one of the engines that I find a strange beast: it has been in development for years, it has a laundry list of features. However, it is only 70 Elo above Rustic, which compared to Shallow Blue, can do ZILCH but search very fast and count pieces.

Rustic Alpha 2, 3, 4... and so on will implement the most common search / sorting optimizatoins (killers, heuristics, check extension), and a TT. I can measure Elo increase after adding each feature. At that point I'll probably call the engine Rustic 1.0, because it finally has all the basics.

And then on to the more advanced topics, such as null move, LMR, different sorts of pruning, tapered evaluation and evaluation terms... And I've got that book to write after version 1.0 is done.

Why didn't anyone tell me that writing a chess engine was so much work if you do it from scratch? Grumble.... but it's getting there.

[mvanthoor]

Grrr. Something is wrong somewhere. In some positions the engine now plays exceedingly weird moves. I've deleted the PV-collection and subsequent cleanup. I'll try again this weekend.

[hgm]

- If the engine finds mate, it should abort after finishing the iteration and immediately return the move. Now it'll try to find a shorter mate, but to be honest, I don't really care about that.

You should care about that. Engines that don't care often bungle won games in the face of checkmate, because they happen to see the mate in 3 before the mate in 2, and will then prefer it on every subsequent move, so that they will never get any closer to the checkmate. My engine Joker has been able to salvage a draw when defending a KQBK ending against Ktulu in the Leiden tournament, once.

As long as you have a fixed-depth search and no TT you will always see the fastest mate first. But with TT, or using extensions and reductions (e.g. check extension) there is no guarantee. I think this was the problem with Ktulu: it kept seeing a distant mate through many checks first, because of the check extension.

As to timing:

The following system is often used:

You allocate 3 times, in increasing order:
1) time after you are not going to start a new iteration, as there is no hope to finish it. (E.g. half the nominal time.)
2) a time after which you won't search any new move in the root, if you already have a satisfactory one (i.e. close in score to the previous iteration). E.g. 1.5 times nominal. This allows the engine to use extra time when it suddenly discovers its original plan was fatally flawed.
3) a 'cold-turkey dead-line', where you would lose anyway, even when you would find a good move (because you forfeit outright, or would be facing a huge time odds for the remainder of the game or a large number of moves).

In general it is bad to allow a large difference in remaining time for the players to develop. If your opponent moves faster than what you decided is optimal for you, and is developing a large time advantage that way, you'd better speed up a little bit as well. And if he thinks on average very long, better think a bit longer too, to make sure you will still be alive to exploit the time advantage you are building.

Also note that even in fixed-time-per move just using up all your time even though you are pretty sure it would be wasted can actually hurt you: the opponent might be pondering, and there is no guarantee the extra time you allow him to do that will not benefit him.

[mvanthoor]

- If the engine finds mate, it should abort after finishing the iteration and immediately return the move. Now it'll try to find a shorter mate, but to be honest, I don't really care about that.

You should care about that. Engines that don't care often bungle won games in the face of checkmate, because they happen to see the mate in 3 before the mate in 2, and will then prefer it on every subsequent move, so that they will never get any closer to the checkmate. My engine Joker has been able to salvage a draw when defending a KQBK ending against Ktulu in the Leiden tournament, once.

As long as you have a fixed-depth search and no TT you will always see the fastest mate first. But with TT, or using extensions and reductions (e.g. check extension) there is no guarantee. I think this was the problem with Ktulu: it kept seeing a distant mate through many checks first, because of the check extension.

Thanks for the warning. So I'll leave that as it is. Yesterday Rustic drew two games against Pulse (who should have won), probably because of this issue. Rustic can see deeper. It could see that it was being mated (I could see the mate myself), but Pulse couldn't. So it went: "check. is it mate already? no? damn... check. And now? Arghh... check..." until Rustic lured it into a threefold repetition. Pulse drew two games it should clearly have won. (It possibly has no check for three-fold rep, or the check is buggy. I haven't looked into the code.)

As to timing:

The following system is often used:

You allocate 3 times, in increasing order:
1) time after you are not going to start a new iteration, as there is no hope to finish it. (E.g. half the nominal time.)
2) a time after which you won't search any new move in the root, if you already have a satisfactory one (i.e. close in score to the previous iteration). E.g. 1.5 times nominal. This allows the engine to use extra time when it suddenly discovers its original plan was fatally flawed.
3) a 'cold-turkey dead-line', where you would lose anyway, even when you would find a good move (because you forfeit outright, or would be facing a huge time odds for the remainder of the game or a large number of moves).

In general it is bad to allow a large difference in remaining time for the players to develop. If your opponent moves faster than what you decided is optimal for you, and is developing a large time advantage that way, you'd better speed up a little bit as well. And if he thinks on average very long, better think a bit longer too, to make sure you will still be alive to exploit the time advantage you are building.

Also note that even in fixed-time-per move just using up all your time even though you are pretty sure it would be wasted can actually hurt you: the opponent might be pondering, and there is no guarantee the extra time you allow him to do that will not benefit him.

Thanks for the pointers I was thinking along those lines as well, except for "don't search a new move". With "don't search a new move in the root", what do you exactly mean? Thanks for explaining.

In matches, I turn pondering off; I assume engines respect this setting; but you're right. Often the first ply's whizz by in 2-3 seconds, and then the engine will need 20-30 seconds for the next one.

[hgm]

Each iteration in the root will run through all moves, starting with the best move of the previous iteration. If you started an iteration in the expectation you would be able to finish it in reasonable time, but it turns out it takes much longer than you thought, breaking out of this loop would be a relatively benign way to abort the search: you are sure all nodes in the tree have been fully searched, and only the root is partly searched. But you are not interested in the root score anymore; any later return to it will be a repetition. You have already searched the move that is likely the best, and spending enormous amounts of time on the off-chance one of the still unconsidered moves is better, is just not worth it. Better save that time for when there really is something at stake.

That is different when the score of the PV move has significantly dropped. Then you are apparently dealing with a position that has some deep tactics, and time spent on thinking how to avoid the trap you were nealy running into is time very well spent. Note that time spent on an iteration that didn't change the move was basically wasted time (in hindsight). So whether you want to spend more time or less should be dependent on your estimate for the likelihood that the move will change. If the best move from the previous iteration has dropped much in score, it greatly enhances the probability that one of the other moves is better. As it has been proven (in the previous iteration) only that they were below the old score, and might have been above the dropped score already at that time, and could have kept their score at the now larger depth. If the score of the PV move is similar or better than in the previous iteration, you would need a significant score increase for some other move compared to the previous iteration to get a significantly better move, and this is a lot less likely.