How hard would it be to modify Stockfish to implement a Mont

[Isaac]

How hard would it be to modify Stockfish and implement a Monte-Carlo method this way:

MonteCarloMethod(numGames, numDepth, numMaxMoves):
For each legal move, SF plays vs itself up to depth numDepth for each move (say depth 1). It plays numGames number of games for each legal move. If a game lasts more than numMaxMoves either abort the game or return a winner if the score is mate in 1 or score is greater than a threshold. Else return draw.
Keep track of the number of wins and draw for each legal move.

Outputs the ranking of the legal moves according to their win ratio. (I.e. number of won games / numGames).

It would be possible to make it "smarter" in the way that it would not play many games if the winning % is very low, and play more games where the winning % is close to 50% or greater.

I'm curious how such an engine would play and what its strength would be.
I don't have the coding knowledge to perform the experiment, but I am willing to invest some time if it isn't too hard to do, with your help.

So, how hard would such an implementation be?

[yurikvelo]

It is easier to implement it as a wrapper over UCI wrapper like CLI-Cutechess
https://chessprogramming.wikispaces.com/Cutechess-cli

If you are going to modify engine code itself, you need to do a lot of work - different platform compiles, track changes of basecode to keep version up to date, implement user interaction (Stockfish understand only UCI protocol and your input/output is not in UCI)

Easiest way is to write script worker, as Fishtest framework does.

Use Python, Perl, PHP or any your favourite interpreteur, *.ini files as input and *.log/*.pgn files as output.

[yurikvelo]

I'm curious how such an engine would play and what its strength would be.

Engine strength is measured on a given Hardware and given Time Control.

Your monte-carlo approach is the same as very agressive forward pruning: you early cut (based on very shallow search) all PV-s but one and dig it extremely deep (up to win/draw/loss resolve), but very shallow.


Imagine in current FEN position you have 30 legal moves.
You wanna decide which of these 30 is best and run 30-sets of games.

Imagine that next move (first opponent reply) has two kind of moves:
- wrong move which is best at shallow search, but pruned on D+1
- correct move which is not best at low D, but is discovered at D+1

If you run thousand games and win them all - you might think this is good move.

But if you play this move vs traditional engine, it will not play that bad opponent move (which you are expecting him to play) and you not win, even if your Monte-Carlo show 100% win ratio


I expect score of your pseudo-engine to be a small fraction of strength of engine used to run Monte-Carlo.

500-600 ELO weaker my estimate

[Isaac]

It is easier to implement it as a wrapper over UCI wrapper like CLI-Cutechess
https://chessprogramming.wikispaces.com/Cutechess-cli

If you are going to modify engine code itself, you need to do a lot of work - different platform compiles, track changes of basecode to keep version up to date, implement user interaction (Stockfish understand only UCI protocol and your input/output is not in UCI)

Easiest way is to write script worker, as Fishtest framework does.

Use Python, Perl, PHP or any your favourite interpreteur, *.ini files as input and *.log/*.pgn files as output.

Why would I ever need to do multi platform compiles?! As long as it runs on my computer it's ok... Why would I track changes of codebase to keep the version "up to date"? This is not my goal!
And how is writing a script easier than modifying Stockfish? I don't see how a script would help me to achieve my goal. Am I missing something?

Your monte-carlo approach is the same as very agressive forward pruning: you early cut (based on very shallow search) all PV-s but one and dig it extremely deep (up to win/draw/loss resolve), but very shallow.

I think that this is not true at all, especially the word "same".

I expect score of your pseudo-engine to be a small fraction of strength of engine used to run Monte-Carlo.

500-600 ELO weaker my estimate

It would be fine for me if this was the case, but I really want to check it out.

[yurikvelo]

Why would I ever need to do multi platform compiles?! As long as it runs on my computer it's ok...

If you are going to do it as a private closed project of your own - you might not ever get it working, because of limited resources: your time, skill etc

Why would I track changes of codebase to keep the version "up to date"? This is not my goal!

Because newer Stockfish will become stronger than version you have frozen. Everybody loves free ELO boost.

And how is writing a script easier than modifying Stockfish? I don't see how a script would help me to achieve my goal. Am I missing something?

Stockfish cannot play games. Even without modification - you have to use some UCI-protocol interface to actually run games.
Either graphical (like Arena, Fritz) or command line (like cutechess-cli).

To implement gameplay inside Stockfish C++ code you have to rewrite basically all CLI-cutechess code into Stockfish code.
That is pretty big piece of work.

Cutechess-CLI alone is 10 000+ lines of C++ code you have to port inside Stockfish (or write your own equivalent, which will take years).

If you use Cutechess-CLI "as is" (readily available binary) you will need just couple hundred lines of Python/Perl/PHP code (actually any framework/language, you can compile EXE from C++ if you like it more than scripting). Without need to rewrite, debug, test, compile cutechess and SF code.

Code to start a game from any given position and get final outcome will be just couple of lines.

You will be able to run any existing or future engines.

[abulmo]

To implement gameplay inside Stockfish C++ code you have to rewrite basically all CLI-cutechess code into Stockfish code.
That is pretty big piece of work.

Why do you want to rewrite all the feature of cutechess for Stockfish to selfplay games in a monte-carlo approach ? Adding selfplay to a chess engine is trivial, and can be done in a few dozen lines.

If you use Cutechess-CLI "as is" (readily available binary) you will need just couple hundred lines of Python/Perl/PHP code (actually any framework/language, you can compile EXE from C++ if you like it more than scripting). Without need to rewrite, debug, test, compile cutechess and SF code.

I am not sure using a scripting language is much simpler than modifying stockfish. What is sure is that it will be too slow for doing an efficient monte-carlo search. Using IO to communicate between a script & stockfich brings a performance bottleneck.

[jeffreyan11]

I don't think it is quite that hard...

All you would need to do is create your own tree structure to store the Monte Carlo tree. Stockfish has nearly everything else you need. To do the playout phase, just call their depth 1 search repeatedly on alternating colors and update a single Board with the moves as they come. Checkmates, draws, etc. are easy to detect since Stockfish should already have functions to do each of these things. They may not be 100% accurate (i.e. two-fold instead of three-fold repetition), but the playout doesn't need to be 100% accurate.

There is no need to keep it synced with Stockfish master. My guess is that most of the elo gaining patches for Stockfish wouldn't benefit a Monte Carlo engine whatsoever. Things that make an evaluation strong for alpha-beta do not necessarily make a better playout policy, especially with regards to king safety.

On the other hand, the resulting engine would be extremely weak (-1000 or more elo? Has anyone tried it before?). To make it stronger you would need to do extensive tuning of selection policy and add other heuristics - making it "smarter". This is the difficult part.

[velmarin]

One tool based in Stockfish DD it can be found here :
"Chess analysis tool using the Monte Carlo method"
http://chessengine.blogspot.com.es/

At some time the codes were offered, now links are dead, I guess for lack of interest.

Perhaps contacting the author, it would be possible...

[Isaac]

I don't think it is quite that hard...

All you would need to do is create your own tree structure to store the Monte Carlo tree. Stockfish has nearly everything else you need. To do the playout phase, just call their depth 1 search repeatedly on alternating colors and update a single Board with the moves as they come. Checkmates, draws, etc. are easy to detect since Stockfish should already have functions to do each of these things. They may not be 100% accurate (i.e. two-fold instead of three-fold repetition), but the playout doesn't need to be 100% accurate.

There is no need to keep it synced with Stockfish master. My guess is that most of the elo gaining patches for Stockfish wouldn't benefit a Monte Carlo engine whatsoever. Things that make an evaluation strong for alpha-beta do not necessarily make a better playout policy, especially with regards to king safety.

On the other hand, the resulting engine would be extremely weak (-1000 or more elo? Has anyone tried it before?). To make it stronger you would need to do extensive tuning of selection policy and add other heuristics - making it "smarter". This is the difficult part.

Thanks a lot, that's exactly the kind of information I was looking for.
Of course I know such an enigne would be much weaker than the original, the goal is not to maximize elo (Yuri got it all wrong I think on this point).