Looking for a Random Mover

[Kirill Kryukov]

Random Mover - an engine that makes random legal moves. Does such a thing exist?

More specifically, I am looking for the one which:

• Supports UCI
• Open source
• Uses a good RNG (e.g. Mersenne Twister).
• Preferably collects some more entropy other than just system time for initializing the RNG.

Any info or hints will be appreciated.

[Stephan Vermeire]

Hi Kirill,

If you can't find any, let me know. It will be little work to transform Brutus into such an 'engine'. (You may choose a new name too).
Do you have additional requests concerning time management? Should it reply a move instantly or consume some time first?

Best wishes,
Stephan

[Kirill Kryukov]

Hi Stephan,

I never saw such engine yet. It will be very cool if you will make one! (In which case the name choice is totally up to you). I guess that instant moves should be OK. If you suspect it may cause any issues, perhaps a parameter can be provided to use time on each move. Of course all common time controls should be supported, and basically it should have bullet-proof stable and compliant protocol implementation. (It would not make much sense for it to freeze of lose on time). Yeah, protocol support means also sending a random ponder move.

Additional bonus features:

• RNG selectable by a parameter (MT and some LCG for start, more can be added later).
• ANSI C ("gcc -std=c89 -W -Wall" with no warnings).
• No dependencies on anything other than standard library (RNGs included in source).
• Built-in support for Winboard protocol (for completenes, and anti-offtopic on this forum).

The reason to look for this engine: I am curious to estimate its rating. Then I will propose to use that rating as 0, and shift the other ratings accordingly. This will give some physical meaning to the rating scale, which is now totally arbitrary. Absolute zero of engine rating. (Although negative ratings will still be possible, by carefully avoiding good moves).

Of course it will take some time and effort because there is no way to directly estimate Random Mover's rating by matching it with normal engines. I have some ideas how to approach that, more on that later.

I guess it may be also used for some other fun experiments. (True Monte Carlo).

[Guenther Simon]

Hi Stephan,

I never saw such engine yet. It will be very cool if you will make one! (In which case the name choice is totally up to you). I guess that instant moves should be OK. If you suspect it may cause any issues, perhaps a parameter can be provided to use time on each move. Of course all common time controls should be supported, and basically it should have bullet-proof stable and compliant protocol implementation. (It would not make much sense for it to freeze of lose on time). Yeah, protocol support means also sending a random ponder move.

Additional bonus features:

• RNG selectable by a parameter (MT and some LCG for start, more can be added later).
• ANSI C ("gcc -std=c89 -W -Wall" with no warnings).
• No dependencies on anything other than standard library (RNGs included in source).
• Built-in support for Winboard protocol (for completenes, and anti-offtopic on this forum).

The reason to look for this engine: I am curious to estimate its rating. Then I will propose to use that rating as 0, and shift the other ratings accordingly. This will give some physical meaning to the rating scale, which is now totally arbitrary. Absolute zero of engine rating. (Although negative ratings will still be possible, by carefully avoiding good moves).

Of course it will take some time and effort because there is no way to directly estimate Random Mover's rating by matching it with normal engines. I have some ideas how to approach that, more on that later.

I guess it may be also used for some other fun experiments. (True Monte Carlo).

I had some thoughts on this too some years ago, but I convinced myself that if the rating scale had any meaning it could not have
a rating of 0, because an engine(practically losers chess) always playing the ('best')worst move must still be a lot(not infinite because of unavoidable
draws due to 50 moves rules or similar) worse than the random mover.
(Except one would agree on that it does not play a game of chess, but I don't think the rules of chess demand a certain quality of moves or the intention
to go for a win or draw, thus it must be playing chess as it will still follow all formal rules of chess)
BTW that sentence below surely is not correct at least not generally:

Of course it will take some time and effort because there is no way to directly estimate Random Mover's rating by matching it with normal engines. I have some ideas how to approach that, more on that later.

E.g. I have programs at the end of my rating list which could be already only slightly better or worse than a random mover, but those are unknown
of course by CCRL or CEGT
Nevertheless a random mover is surely interesting for several experiments and I also want to encourage Stephan to give it a try.

Guenther

[Richard Allbert]

Random Mover - an engine that makes random legal moves. Does such a thing exist?

More specifically, I am looking for the one which:

• Supports UCI
• Open source
• Uses a good RNG (e.g. Mersenne Twister).
• Preferably collects some more entropy other than just system time for initializing the RNG.

Any info or hints will be appreciated.

If Stefan has any problems (can't imagine) then I could also do one for you... Jabba virtually makes random moves anyway. Although c++ isn't what you want?

It should be easy to implement - allow the engine to search as normal, and when time is up pick a random move from the list of legal moves rather than the search best move. Finito. You could mod any OS engine out there in a few minutes like this.

Regards

Richard

[Stephan Vermeire]

It should be easy to implement - allow the engine to search as normal, and when time is up pick a random move from the list of legal moves rather than the search best move. Finito. You could mod any OS engine out there in a few minutes like this.
Richard

Yep, that is exactely what I am going to do! I think I will make a UCI-option to enable this feature. Is anyone else interested? In that case, I will release it publically.


Stephan

[H.G.Muller]

I always use POS for this purpose. With the command line

pos.exe --io-mode xboard --brain-mode random

it runs as a random mover. (Not that this makes much difference from its normal mode of opertion... )

[Stephan Vermeire]

Hi Kirill,

Try this version: http://www.xs4all.nl/~vermeire/BrutusRND.rar

It is a BrutusRND-version with a UCI-option 'moveRandomly'. It is switched on permanently in this version, now you have your random move generator. You can use all other options that the original chess program had already. SMP, openingbook (don't forget to switch off the book in case you won't want a random opening), pondering (yes, that is random also), all time controls, UCI/WB. Let me know if this is OK for you.

I will probably include the moveRandom UCI-option in my next release as a bonus feature. Then the source will be available too.

Playing against this engine is really fun! I won my first game against a program since years! (OK I admit, I got mated once by the openingbook also...)
Perhaps I can get my son interested in playing chess now. He hates losing.

Best wishes,
Stephan

[Kirill Kryukov]

I had some thoughts on this too some years ago, but I convinced myself that if the rating scale had any meaning it could not have
a rating of 0, because an engine(practically losers chess) always playing the ('best')worst move must still be a lot(not infinite because of unavoidable
draws due to 50 moves rules or similar) worse than the random mover.

Yes I realize that, so as I said negative ratings will still be possible. Random Mover would solve the arbitrariness of the rating scale. It's the simplest imaginable chess player with 0 chess knowledge other than what the legal moves are. So using it as 0 makes some sense to me.

(Except one would agree on that it does not play a game of chess, but I don't think the rules of chess demand a certain quality of moves or the intention
to go for a win or draw, thus it must be playing chess as it will still follow all formal rules of chess)
BTW that sentence below surely is not correct at least not generally:

Of course it will take some time and effort because there is no way to directly estimate Random Mover's rating by matching it with normal engines. I have some ideas how to approach that, more on that later.

E.g. I have programs at the end of my rating list which could be already only slightly better or worse than a random mover, but those are unknown
of course by CCRL or CEGT

I imagine that even the simplest and buggiest engine will score close to 100% against a random mover, but I may be wrong. The weakest engine I tested so far is Elf 1.3.0 (rated 1770 in my tourney), which is of course too strong in this context.

Nevertheless a random mover is surely interesting for several experiments and I also want to encourage Stephan to give it a try.

Guenther

[Kirill Kryukov]

If Stefan has any problems (can't imagine) then I could also do one for you... Jabba virtually makes random moves anyway. Although c++ isn't what you want?

Thanks for the offer! C is just my aesthetic preference.

It should be easy to implement - allow the engine to search as normal, and when time is up pick a random move from the list of legal moves rather than the search best move. Finito. You could mod any OS engine out there in a few minutes like this.

Regards

Richard

I was thinking to do it myself, but figured to ask here first. (Providing others with this opportunity to create a "Golden Rating Standard of 0 Elo points". )

[Kirill Kryukov]

I always use POS for this purpose. With the command line

pos.exe --io-mode xboard --brain-mode random

it runs as a random mover. (Not that this makes much difference from its normal mode of opertion... )

Thanks for the hint. It's not open source, right? I'd appreciate being able to see that RNG is used properly, and to be able to replace or add more RNGs.

[Kirill Kryukov]

Hi Kirill,

Try this version: http://www.xs4all.nl/~vermeire/BrutusRND.rar

It is a BrutusRND-version with a UCI-option 'moveRandomly'. It is switched on permanently in this version, now you have your random move generator. You can use all other options that the original chess program had already. SMP, openingbook (don't forget to switch off the book in case you won't want a random opening), pondering (yes, that is random also), all time controls, UCI/WB. Let me know if this is OK for you.

I will probably include the moveRandom UCI-option in my next release as a bonus feature. Then the source will be available too.

Playing against this engine is really fun! I won my first game against a program since years! (OK I admit, I got mated once by the openingbook also...)
Perhaps I can get my son interested in playing chess now. He hates losing.

Best wishes,
Stephan

Thanks a lot Stephan! I'll try it!

[Miguel A. Ballicora]

Hi Stephan,

I never saw such engine yet. It will be very cool if you will make one! (In which case the name choice is totally up to you). I guess that instant moves should be OK. If you suspect it may cause any issues, perhaps a parameter can be provided to use time on each move. Of course all common time controls should be supported, and basically it should have bullet-proof stable and compliant protocol implementation. (It would not make much sense for it to freeze of lose on time). Yeah, protocol support means also sending a random ponder move.

Additional bonus features:

• RNG selectable by a parameter (MT and some LCG for start, more can be added later).
• ANSI C ("gcc -std=c89 -W -Wall" with no warnings).
• No dependencies on anything other than standard library (RNGs included in source).
• Built-in support for Winboard protocol (for completenes, and anti-offtopic on this forum).

The reason to look for this engine: I am curious to estimate its rating. Then I will propose to use that rating as 0, and shift the other ratings accordingly. This will give some physical meaning to the rating scale, which is now totally arbitrary. Absolute zero of engine rating. (Although negative ratings will still be possible, by carefully avoiding good moves).

Of course it will take some time and effort because there is no way to directly estimate Random Mover's rating by matching it with normal engines. I have some ideas how to approach that, more on that later.

I guess it may be also used for some other fun experiments. (True Monte Carlo).

Great!
I always wonder that myself.

Random move (RM) would be very weak, but its rating could be estimated indirectly. Another engine could play in a different random way: Simple alpha-beta, but at ply 1 the "eval" score is determined randomly (let's call it RM1). Note that RM would be the equivalent of RM1, but the random process is determined at the root, so RM could be called RM0. So, you can designed engines, RM2, RM3, RM4 etc. all of them weak, but as you increase the plies, they will get stronger (amazing, but this has been proven). So, you can determine a relative rating between RM0... RM6 etc. At this point, you can use RM6 to measure the rating of a weak stable engine, and now you may be on the range to grade the rest.

The only bad or good effect (depends how you look at it) is that the rating scale will be dependent on the time controls. RM strength will be always zero despite it gets relatively weaker at longer time controls. But that is ok, longer time controls give you more "absolute" strength for a normal engine.

Miguel

[H.G.Muller]

This is a very interesting project, and I once made a similar attempt to extend the rating scale downwards, by analysing the results from the ChessWar promo division. One problem is that the weakest engines are often very unstable. And then they do not behave accordingly to the Elo curve, and analyzing their results as if they do, would extract wrong ratings. (E.g. there is an engine that prints "resign" in stead of "checkmate", so the weaker the opponent, the lower its average score against it.)

I tried to delete as many of obviously disturbing factors (e.g. games where a stronger engine crashed against a weaker one), but it is hard to catch everything. My conclusion (or rather, the result of the analysis) was that the rating of an engine like Pos 1.17 (in its non-random mode!) is slightly below zero, around -50 or so. And Pos 1.17 scores about 75% against a random mover.

The N-ply + random eval is sure to result in a nice set of stable engines that are asymptotically weak. It will take a chain of many of them before you will be able to connect to any decent rating. And connecting the random mover with the poule of decent engines by only one chain will be extremely unreliable. Connecting it through aother chain of engines might lead to a completely different rating. Nevertheless, the ratings of such N-ply random evaluators is of great fundamental interest.

I understood that Bob once did experiments like this. I am not sure about his implementation details. One question is how to evaluate a position where you are checkmated. Is that a normal evaluation, that you assign a random? Or do you assign it minus infinity. (It could be argued that that is cheating of some sort. Especially if you recognize stalemate seperately.) And would you play strictly by legal moves, or by King capture?

My engine NEG is very stable, and very weak, as it has no search. I especially made it to provide a stable engine in that Elo range. It just captures the piece with the best SEE, or if there is nothing to capture, tries a checking move. It does not know about checkmate. Nevertheless, it has won several games by checkmate in ChessWar. KQQQK is usually enough for it to accidentally win. But it has also won through a kind of fool's mate.

[Guenther Simon]

I imagine that even the simplest and buggiest engine will score close to 100% against a random mover, but I may be wrong. The weakest engine I tested so far is Elf 1.3.0 (rated 1770 in my tourney), which is of course too strong in this context.

Well, the mentioned POS(HG) in my rating list currently is below 400 when Gerbil e.g. has a rating of 2000 at RWBC
and Elf around 1630(with not much games).

Guenther

[H.G.Muller]

Pos 1.17 scores about 75% against a random mover. I think NEG scores about 80-90% against Pos.

The problem with buggy engines is that they never score 100%, no matter how weak the opponent. They lose many games because they crash, do illegal moves, false claims, spontaneously resign... This tend to strongly distorts the tail of the rating list in the upward direction. Even one such game would make BayesElo think: "oh, this guy scored 1 point against B, so it cannot possibly be 1000 Elo weaker than B, because then that would have only a chance of 1:10,000". And then it rates it 500. While the point was a gift that a non-crashing program could impossibly dodge, because his opponent got stuck after 2 moves or so.

It is really very hard to guard against any games where a badly losing program gets the game thrown into its lap without having done anything at all on merit. I am pretty sure that a random mover in the ChessWar promo would earn 2-3 points. Even NEG has 3 points now, and will probably end on 3.5, because it is paired in the last round with an opponent that is known to play Ra1-a2, Ra2-a1, Ra1-a2 for the entire game from move 2 on... (after 1. Na3).

[Kirill Kryukov]

Random move (RM) would be very weak, but its rating could be estimated indirectly. Another engine could play in a different random way: Simple alpha-beta, but at ply 1 the "eval" score is determined randomly (let's call it RM1). Note that RM would be the equivalent of RM1, but the random process is determined at the root, so RM could be called RM0. So, you can designed engines, RM2, RM3, RM4 etc. all of them weak, but as you increase the plies, they will get stronger (amazing, but this has been proven).

Interesting. Has it been proven by experiment (running test matches)? If so do you have any more information, like time control, number of games, and rating differences? Or has it been proven analytically, like a theorem? Looks interesting, but I can't imagine how many ELO points RM<N> may be stronger than RM?

Also, does any engine implement the RM<N> idea?

So, you can determine a relative rating between RM0... RM6 etc. At this point, you can use RM6 to measure the rating of a weak stable engine, and now you may be on the range to grade the rest.

The only bad or good effect (depends how you look at it) is that the rating scale will be dependent on the time controls. RM strength will be always zero despite it gets relatively weaker at longer time controls. But that is ok, longer time controls give you more "absolute" strength for a normal engine.

Miguel

[Kirill Kryukov]

This is a very interesting project, and I once made a similar attempt to extend the rating scale downwards, by analysing the results from the ChessWar promo division. One problem is that the weakest engines are often very unstable. And then they do not behave accordingly to the Elo curve, and analyzing their results as if they do, would extract wrong ratings. (E.g. there is an engine that prints "resign" in stead of "checkmate", so the weaker the opponent, the lower its average score against it.)

I tried to delete as many of obviously disturbing factors (e.g. games where a stronger engine crashed against a weaker one), but it is hard to catch everything. My conclusion (or rather, the result of the analysis) was that the rating of an engine like Pos 1.17 (in its non-random mode!) is slightly below zero, around -50 or so. And Pos 1.17 scores about 75% against a random mover.

The N-ply + random eval is sure to result in a nice set of stable engines that are asymptotically weak. It will take a chain of many of them before you will be able to connect to any decent rating. And connecting the random mover with the poule of decent engines by only one chain will be extremely unreliable. Connecting it through aother chain of engines might lead to a completely different rating. Nevertheless, the ratings of such N-ply random evaluators is of great fundamental interest.

I understood that Bob once did experiments like this. I am not sure about his implementation details. One question is how to evaluate a position where you are checkmated. Is that a normal evaluation, that you assign a random? Or do you assign it minus infinity. (It could be argued that that is cheating of some sort. Especially if you recognize stalemate seperately.) And would you play strictly by legal moves, or by King capture?

My engine NEG is very stable, and very weak, as it has no search. I especially made it to provide a stable engine in that Elo range. It just captures the piece with the best SEE, or if there is nothing to capture, tries a checking move. It does not know about checkmate. Nevertheless, it has won several games by checkmate in ChessWar. KQQQK is usually enough for it to accidentally win. But it has also won through a kind of fool's mate.

Well it's great that some real engine exist that are comparable to a random mover. This will make the task easier. You are right that connecting a random mover to the field with a single chain of engines is very inaccurate. I hope to eventually establish a 32-engines wide diagonal connection down to Random Mover, like I maintain in my tournament. This will obsiously take a long time.

Unstable or buggy engines are a big headache, and I many of them distort the ratings. (By the way I try to evaluate how much each particular engine disagrees with the Elo curve by measuring the performance slope for every engine in my tournament). The wide diagonal helps greatly to combat this problem. A single-engine connection (or a few engines wide connection) would easily suffer from great distortions.

[Kirill Kryukov]

Pos 1.17 scores about 75% against a random mover. I think NEG scores about 80-90% against Pos.

The problem with buggy engines is that they never score 100%, no matter how weak the opponent. They lose many games because they crash, do illegal moves, false claims, spontaneously resign... This tend to strongly distorts the tail of the rating list in the upward direction. Even one such game would make BayesElo think: "oh, this guy scored 1 point against B, so it cannot possibly be 1000 Elo weaker than B, because then that would have only a chance of 1:10,000". And then it rates it 500. While the point was a gift that a non-crashing program could impossibly dodge, because his opponent got stuck after 2 moves or so.

Yes this is a problem. In my testing I am trying to reduce it be several measures:

1. No resignation or draw offers are allowed in my testing. All games must end by the rule (Checkmate, stalemate, repetition, 50 moves), except insufficient material which is a shortcut to 50 moves rule. (Engine's evaluations can't be trusted, so you can't reliably adjudicate based on them). With the exception when the engine on the losing side crashed or dropped flag before receiving checkmate.

2. I remove crashed games and lost on time games, where the lost side that was not already losing.

3. I only run matches where two engines are not more than 500 points away from each other. Eventually I hope to lower this limit to 400 or less. (All games with larger rating difference that I had were removed when I introduced the limit).

These methods don't eliminate the problem completely, but at least help to reduce it somewhat.

It is really very hard to guard against any games where a badly losing program gets the game thrown into its lap without having done anything at all on merit. I am pretty sure that a random mover in the ChessWar promo would earn 2-3 points. Even NEG has 3 points now, and will probably end on 3.5, because it is paired in the last round with an opponent that is known to play Ra1-a2, Ra2-a1, Ra1-a2 for the entire game from move 2 on... (after 1. Na3).

Again, performance slope is an excellent tool to detect unusual rating behavior. Unfortunately it requires many games to have any significance. The games I run (about 1000-1500 per engine) only allow to detect the most extreme deviations. (Although probably there is a lot of space for improvement there).

[Kirill Kryukov]

Well, the idea I had to fill the gap between the Random Mover and normal engines: To introduce the "Engine Mixing Console". It would work like an UCI->UCI adapter. On the GUI side it will present a usual UCI interface. On the engine side, it will load two (or more) engines simultaneously, and on every move it will randomly select one of them to play. (The idea is inspired by Alessandro's multi-hamster engine ).

Thus, you'll be able to create a 50/50 mix between a random mover and POS (for example), or a 20/80 mix, or anything. Even 1% Random Mover / 99% Rybka. This would allow to fill any gap and have infinite posibilities by mixing existing engines in any proportion.

Of course for this idea to work someone will have to implement the Mixing Console.