Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / First ever Monte Carlo vs. Rybka 3 game
1 2 Previous Next  
Parent - By Banned for Life (Gold) Date 2008-07-27 21:45
OK, good point. Now we need to figure out the SNR. :-)

Regards,
Alan
Parent - - By Roland Rösler (****) [de] Date 2008-07-27 22:18
I thought, MC can be a tool for endgame analysis. Here you have not the problem with close evals of Rybka. Here you see sometimes (often?) the following eval from Rybka in mv mode: Three moves with eval +3.21, two with +1.23 and the next with lower than +0.1. You know that the first 5 moves only draws (and Rybka will see this in real! MC too!), but about the next you are not so sure. Okay, you can solve this problem with very much time in analysis. But I hoped MC can be a help for this issue. After all what I read here in the last days of the MC implementation of R3 I´m sure it doesn´t help.
Parent - - By lkaufman (*****) Date 2008-07-28 01:03
I think you are right in this case, the way things are implemented. But I also think there are many endgames where MC will be helpful.
Parent - By Roland Rösler (****) [de] Date 2008-07-28 02:05 Edited 2008-07-28 02:07
Thanks for clarifacation (I was only 99.9% sure). Now I hope for this cases on IDeA. Maybe here I can exclude the first 5 moves and Rybka is looking only to the rest (or a part of the rest) without losing speed. And then maybe MC on the very bests. :-)
Parent - By Mars (**) [de] Date 2008-07-26 13:33
One could test it in an 6 pieces endgame position without the corresponding table bases (i.e. just with 3-4-5). It would be just an example (not a proof) but better than nothing. Just a thought.
Parent - By Uly (Gold) [mx] Date 2008-07-26 06:40
This thread should be called "First ever MC vs. Rybka 3 game", that way people could think it's about Magnus Carlsen vs. Rybka :)
Parent - - By tralala (*) [de] Date 2008-07-27 18:34
Am I right, that Monte Carlo Search offers great scalability for hundreds or even thousands of cores? If I understand the concept behind the Monte Carlo search correctly I'd expect it would scale well on a supercomputer with thousands of CPUs since it plays out a lot of games independently. Am I right?
Parent - By Vempele (Silver) [fi] Date 2008-07-27 19:28
Yes. I believe Larry has already pointed this out, though.
Parent - - By zwegner (***) Date 2008-07-27 19:33
Not really. It will scale well in the sense that doubling the number of cores will just about double the number of simulations, but this type of scalability is meaningless. In fact pure Monte Carlo scales quite badly with strength / simulations. The only thing more simulations will give you is a decreased margin of error. But given infinite time, it will not converge on a perfect score. Take for instance a situation where after a certain move M, there is one forced response R that wins outright, but there are 9 other responses to the move lose instantly. Pure MC will say that move M wins, because it will show something like a 90% win rate. You do more and more simulations, and it only increases the statistical significance of this 90%. The actual percentage I suppose will be off, because of any bias in the move selection. I gather that Rybka uses this bias very heavily, only playing moves that are suggested by an N-ply search.

On the other hand, with a tree based MC method, move M will get expanded, and each of the responses will be played out. Then it will find that move M loses badly because of R. Of course, once you use this tree method, scaling becomes bad again, in the sense of speed. There is a lot of information that needs to be shared between the cores in order for a tree-based approach to work without duplicating information, and this comes at an overhead in large numbers of cores.

I suspect some people might say that if you increase the "depth" parameter of Rybka's MC, then it will play perfectly given enough time. But that's no longer MC...
Parent - - By lkaufman (*****) Date 2008-07-27 19:58
I would say that it scales perfectly in the sense that with twice as many cores we can add one ply to the MC search (assuming 1 ply = double time) whereas with normal search you get less than one ply for doubling of cores. That is the way I would use more cores, once I find the point where adding a ply is more useful than doubling the number of simulations.
Parent - - By sharpnova (***) [us] Date 2008-07-27 20:05
i'm confused. what does it mean to add a ply to the mC search. I thought MC played all the games out to conclusion
Parent - - By lkaufman (*****) Date 2008-07-27 20:14
It means adding a ply to the depth of search used by MC to play out each game. This is a key parameter of MC, which the user can select.
Parent - - By sharpnova (***) [us] Date 2008-07-27 20:15
so what you're saying is it does a regular search to a certain depth and then from there plays out games?

or actually what ur saying is that for the games it plays out.. each move is calculated to a certain depth. (different from what i said in the previous line)
Parent - By lkaufman (*****) Date 2008-07-27 20:18
the second line is correct.
Parent - By zwegner (***) Date 2008-07-27 20:15
Yes it does, but it looks like what Rybka does is for each move in each game, it searches to N ply with a random element added to the eval.
Parent - - By zwegner (***) Date 2008-07-27 20:30
I suppose that is true, but once it scales all the way to the end, i.e. infinite depth, then it is not really MC, as there will be no random element. Of course tree-based methods do the same, once the tree is expanded to the end of the game. I guess when I think of scalability, I'm thinking along the lines of adding more simulations, not making the simulations smarter. I'm not sure the latter will scale perfectly in all types of positions. One of the key aspects of MC is its robustness. It has bias towards likely moves, but not too much. If the key move is a queen sacrifice, it will only get played by Rybka-style MC when its search depth shows some compensation within its random margins, whereas with "regular" MC, the queen sacrifice will be played, although with possibly a low priority. For fortress-type positions, it will never really see the compensation except with very large depth. This doesn't really apply at the root of course, as every move is tried there. I would like to see some Rybka MC analysis on a position like this (don't know how to post diagrams here, sorry):

8/6p1/7k/7B/6PK/2p2P2/8/8 w

There's another similar position here: http://membres.lycos.fr/albillo/ajedre8a.htm

In go programs, most people find that there is a hard balance between the intelligence of the playouts and playing strength. If you make the playouts too smart, they lose robustness, and it will play weaker overall.
Parent - - By lkaufman (*****) Date 2008-07-28 00:57
I've heard this before about GO programs. It's a bit hard for me to understand this, at least in the context of chess. If your life depended on winning a certain chess game, and for each move you had the choice of asking 1000 players rated 2000 to play it out or 2000 players rated 2500 to play it out (with the best scoring move to be your choice), is there anyone who would choose the amateurs rather than the grandmasters? Can you make sense of this paradox?
Parent - - By Permanent Brain (*****) Date 2008-07-28 01:19 Edited 2008-07-28 01:26
With this approach, maybe it will be best to ask 2 players with 2700. :-)

What I was hoping for is, that MC. would help in positions where Rybka fails due to "principle" problems, like in my position with the pawn chain above. If I get it right, the problem is that Rybka-MC would never try the white king moves because there isn't enough randomness in this implementation. But only the king moves draw. My idea of MC. is that it does try these king moves (in addition to bxa5??), in the first move but also in the following moves. I thought MC. is capable to get it that if white never plays bxa5 (or gxh6, eventually), he will draw while after the captures, sooner or later someting bad happens.

Here is the position again:

2b1k2r/8/2p3p1/rpPp1pPp/pP1PpP1P/P3P3/8/3K4 w k - 0 1


(try Shredder on it :-) )

And what about the Behting study? Does Rybka 3's MC. analysis clearly point to Kc6?
Parent - - By Margus (*) [us] Date 2008-08-01 06:26

>With this approach, maybe it will be best to ask 2 players with 2700. :-)


I think there was one a match - Kasparov VS The World
Wasn't there?

I think he won!
Parent - By Uri Blass (*****) [il] Date 2008-08-01 07:17
The match of kasparov against the world is not relevant for this discussion because kasparov used computers to help him and the world also used computers.

Uri
Parent - - By zwegner (***) Date 2008-07-28 01:46
It is counterintuitive. It's the same with search vs. evaluation. You can add tons and tons of knowledge, but sometimes the knowledge will be counterproductive, either because it slows the engine down, or because it's not correct in all positions. The same thing can happen with go playouts, but for a different reason. Playouts need to have the property that they are robust enough so that whenever there is a winning line available, it has a possibility of playing it, but smart enough so that the playouts approximate real games. I don't completely grasp all of the reasons behind it (and I doubt anyone does), but it seems to me that a lot of the "knowledge" that you add will be correct in most positions, but not in all. Playouts that are less smart will likely perform equally well in all types of positions. And search trees are pretty good at finding those types of positions...
Parent - - By lkaufman (*****) Date 2008-07-28 02:15
I can't even imagine what would be the optimum level for MC in chess if this is true, 1200 or 3200 or anywhere in between??? Is there anything in the experience with GO that would shed any light on the ideal level?
Parent - - By Mark (****) [us] Date 2008-07-28 10:50
Maybe a variable level could be best?  Deeper search near the root and gradually tapering off?
Parent - By Permanent Brain (*****) Date 2008-07-28 12:59
I am not sure, but I think MC. approaches include simpler, much faster evaluation functions (I didn't read much about it and I don't remember much). Also, after this discussions here I think that the preselection of moves by an eval margin, while the other moves are omitted, is against the MC. concept. Even more if this decision is based on shallow searches.

Nevertheless it's a first step, and the introduction of the term "Monte Carlo Analysis" into major chess software. Think positively! :-D
Parent - By lkaufman (*****) Date 2008-07-29 00:33
Actually just doing fixed depth searches has that effect, because as pieces get traded the same depth search gets faster and faster.
Parent - - By Permanent Brain (*****) Date 2008-07-28 01:12
8/6p1/7k/7B/6PK/2p2P2/8/8 w - - 0 1


(your FEN was incomplete; diagrams appear automatically for complete FEN)
Parent - - By zwegner (***) Date 2008-07-29 00:50
Ahh, thanks.

So could somebody run Rybka 3 MC on this position? g5 is the best move, score should be drawish.

As a point of reference my engine ZCT sees the line to make the fortress, but evaluates it as about -4.5.
Parent - - By Dadi Jonsson (Silver) [is] Date 2008-07-30 23:07 Edited 2008-07-31 07:40
A ran a quick Randomizer match of 300 games in this position (depth=9; eval window 10 centipawns). It should be equivalent to MC and gave 8% success for 1.g5. It always played 1.g5, except in two games where it played 1.f4.

Here we seem to have an ideal MC position: It is an endgame, it is drawn(?), the engine gives a high score and White can save himself by setting up a fortress. To improve the situation even further the engine sees and plays the correct first move in almost all the games. However the statistics in the root position don't indicate that the position is drawn.

Edit: And maybe it isn't drawn as Permanent Brain suggested.
Parent - By zwegner (***) Date 2008-07-30 23:23
Thank you Dadi. ;)

That is an interesting result, if somewhat expected. MC will need a lot of work, including being paired with a tree search, for it to become really useful.

Perhaps one of the lucky few with R3 can check if the result is any different?

Also, it might be instructive to run the position after the fortress has been created, after 1. g5+ Kh7; 2. Bf7 c2; 3. Kh5 c1=Q; 4. g6+ Kh8
Parent - - By Permanent Brain (*****) Date 2008-07-30 23:36 Edited 2008-07-30 23:44
Is it absolutly sure that White can hold the draw here?

For example, in this position (but without the pawn f3), White loses, as the tablebases confirm:

7k/5Bp1/6P1/7K/8/8/8/2q5 w - - 0 5


I hope I got the intended fortress formation correctly? - Appearantly, Black's queen can force a zugzwang, forcing the bishop to leave f7 etc. I didn't study it intensively.

From the position above, after the moves 1.g5+ Kh7 2.Bf7 c2 {forced} 3.Kh5 c1=Q 4.g6+ Kh8, this position would arise:

7k/5Bp1/6P1/7K/8/5P2/8/2q5 w - - 0 5


I am not strong enough to be sure, that the presence of the extra pawn guarantees White the draw.

Edit: I did run 2 so called "shootout" (engine against herself) for this position. At first, Rybka 2.2 at depth 8 produced a draw. Then, Rybka 2.3.2a at depth 9 won for black. But this was with 3+4-piece tbs., only:

[Event "Shootout (Rybka232a32-bit, 9ply) "]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "New game"]
[Black "?"]
[Result "0-1"]
[SetUp "1"]
[FEN "8/6p1/7k/7B/6PK/2p2P2/8/8 w - - 0 1"]
[PlyCount "120"]

1. g5+ Kh7 2. Bf7 c2 3. Kh5 c1=Q 4. g6+ Kh8 5. Kg4 {-5.78/9 0} Qe3 {
(Qg1+) -5.78/9 1} 6. f4 {(Bd5) -5.78/9 0} Qd3 {(Qe4) -5.89/9 1} 7. Kg5 {
-5.94/9 1} Qh3 {-6.58/9 1} 8. f5 {-6.67/9 1} Qf3 {-6.75/9 1} 9. Bc4 {-6.89/9 1}
Qe3+ {-6.87/9 2} 10. Kh5 {-6.87/9 1} Qh3+ {-6.89/9 1} 11. Kg5 {-6.87/9 0} Qg3+
{-6.89/9 1} 12. Kh5 {-6.87/9 0} Qh2+ {-6.89/9 1} 13. Kg4 {-6.89/9 0} Qg1+ {
-6.86/9 1} 14. Kf3 {-6.86/9 1} Qh1+ {-6.92/9 2} 15. Ke3 {-6.92/9 1} Qh3+ {
(Qc1+) -7.05/9 2} 16. Kd4 {-7.05/9 1} Qg4+ {-6.89/9 1} 17. Kc3 {-6.89/9 0} Qxf5
{-6.94/9 1} 18. Bf7 {-6.94/9 1} Qe4 {-6.83/9 2} 19. Kb3 {-7.11/9 1} Qd4 {
-7.17/9 1} 20. Ka3 {-7.25/9 1} Qb6 {(Qd6+) -7.25/9 1} 21. Ka4 {-7.33/9 0} Qb1 {
(Qc5) -7.31/9 0} 22. Ka3 {(Ka5) -7.27/9 0} Qb5 {-7.26/9 0} 23. Ka2 {-7.31/9 0}
Qb4 {-7.40/9 1} 24. Ka1 {-7.39/9 0} Qd2 {-7.39/9 1} 25. Kb1 {-7.41/9 0} Qh2 {
(Qf2) -7.31/9 1} 26. Kc1 {-7.41/9 0} Qe2 {-7.38/9 0} 27. Kb1 {-7.47/9 0} Qd2 {
-7.48/9 0} 28. Bb3 {-7.53/9 1} Qe1+ {(Qb4) -7.58/9 1} 29. Kb2 {-7.58/9 1} Qb4 {
(Qe5+) -7.53/9 1} 30. Ka2 {-7.68/9 1} Qa5+ {-7.91/9 2} 31. Kb2 {(Kb1) -7.91/9 1
} Qb6 {-8.09/9 2} 32. Kc3 {-8.22/9 4} Qxg6 {-8.41/9 6} 33. Bd5 {-8.54/9 13}
Qg3+ {-8.76/9 4} 34. Kc4 {-8.76/9 4} Qe3 {(g5) -9.16/9 2} 35. Kb5 {-10.72/9 1}
Qd3+ {(g5) -#26/9 1} 36. Kc5 {-#26/7 1} Qxd5+ {-#24/3 0} 37. Kxd5 {-#25/1 0}
Kh7 {-#24/1 0} 38. Ke4 {-#23/1 0} Kg6 {-#23/1 0} 39. Kf4 {-#22/1 0} Kh5 {
-#22/1 0} 40. Kg3 {-#22/1 0} Kg5 {-#21/1 0} 41. Kf2 {-#20/1 0} Kf4 {-#20/1 0}
42. Kg2 {-#20/1 0} Kg4 {-#19/1 0} 43. Kh2 {-#19/1 0} Kf3 {-#18/1 0} 44. Kh1 {
-#18/1 0} g5 {-#17/1 0} 45. Kg1 {-#17/1 0} Kg3 {-#16/1 0} 46. Kh1 {-#16/1 0} g4
{-#15/1 0} 47. Kg1 {-#15/1 0} Kh3 {-#14/1 0} 48. Kf2 {-#14/1 0} g3+ {-#13/1 0}
49. Kf1 {-#13/1 0} Kh2 {-#12/1 0} 50. Ke2 {-#12/1 0} g2 {-#11/1 0} 51. Kd3 {
-#11/1 0} g1=Q {-#10/1 0} 52. Kc4 {-#10/1 0} Kg3 {-#9/1 0} 53. Kd5 {-#8/1 0}
Kf4 {-#8/1 0} 54. Kd6 {-#8/1 0} Qd1+ {-#7/1 0} 55. Kc5 {-#6/1 0} Ke5 {-#6/1 0}
56. Kb4 {-#5/1 0} Kd5 {-#5/1 0} 57. Kc3 {-#5/1 0} Kc5 {-#4/1 0} 58. Kb2 {
-#4/1 0} Kb4 {-#3/1 0} 59. Ka2 {-#3/1 0} Kc3 {-#2/1 0} 60. Ka3 {-#2/1 0} Qb3# {
-#1/1 0} 0-1
Parent - By Dadi Jonsson (Silver) [is] Date 2008-07-31 00:03 Edited 2008-07-31 00:25
That's a good point. I just took it for granted that it was a draw, but I think you might be right and Black can force the win of White's f-pawn.

White would probably need to push the pawn to f5 and then he could shuffle the bishop safely between f7 and e6. The question is if the pawn can be pushed to f5. No, I think this is just lost.
Parent - - By zwegner (***) Date 2008-07-31 00:13

> Is it absolutly sure that White can hold the draw here?
>
> For example, in this position (but without the pawn f3), White loses, as the tablebases confirm:


Perhaps you're right. I'm pretty weak myself, but I can tell in your first position it is easy to force a zugzwang: Kg4 Qf1 Kg3 Qf5 Kg2 Qf4 Kg1 Qf3 Kh2 Qg4 Kh1 Qg3.

But from the other position, I think the white king can stick next to the pawn. Having the pawn as a shield from checks makes it able to avoid being forced into a corner.
Parent - - By George Tsavdaris (****) Date 2008-07-31 10:03 Edited 2008-07-31 10:06
8/6p1/7k/7B/6PK/2p2P2/8/8 w - - 0 1


>But from the other position, I think the white king can stick next to the pawn. Having the pawn as a shield from checks makes it able to avoid >being forced into a corner.


After 1.g5+ Kh7 2.Bf7 c2 3.Kh5 c1Q 4.g6+ Kh8 5.Kg4(forced) we have that:

After 5...Qc3 Shredder 10 with some backtracking analysis with its powerful 3,4,5 Shredderbases and having loaded the Nalimov's KQPKBP gives:

7k/5Bp1/6P1/8/6K1/2q2P2/8/8 w - - 0 1

Analysis by Shredder 10 UCI:

1. -+  (-279.72): 6.Bf7-e6 Qc3-d4+ 7.Kg4-h3 Qd4-f6 8.Be6-g4 Qf6xg6 9.Kh3-g2 Kh8-h7 10.Kg2-f2 Qg6-d3 11.Bg4-h3 Qd3-d4+
2. -+  (-279.72): 6.Kg4-f5 Qc3-e3 7.Kf5-g4
3. -+  (-279.72): 6.Kg4-f4 Qc3-d4+ 7.Kf4-f5 Qd4-e3 8.Kf5-g4
4. -+  (-279.72): 6.Kg4-g3 Qc3-d4
5. -+  (-279.76): 6.Bf7-d5 Qc3-c8+ 7.Kg4-f4 Qc8-c7+ 8.Kf4-f5 Qc7-c5 9.Kf5-e5
6. -+  (-279.79): 6.Bf7-a2 Qc3-d4+

So black wins! As all moves before Qc3 for white were forced for white.
Parent - By zwegner (***) Date 2008-08-01 03:03
Huh... so is the other position on the page:
8/8/8/5Bp1/7k/8/4pPKP/8 w - - 0 1

...also won for black? This one seems a little trickier to win the pawn. It looks like the white king can just walk around the pawn, mostly f1-g1-g2, and the queen can't pry him away. I'm not sure though--I just played against ZCT for a while and it wasn't able to make progress, but maybe that's not so surprising... ;)
Parent - By BB (****) [au] Date 2008-09-23 06:33
7k/5Bp1/6P1/7K/8/5P2/8/2q5 w - - 0 5


>Is it absolutly sure that White can hold the draw here?


Chapter 13 of Queen v. Rook/Minor Piece Endings by Avebakh, Chekhover, and Henkin (position 314) notes that Cheron showed in 1952 that Black should win (the Zakhodyakin study is from 1929).
Parent - By Vempele (Silver) [fi] Date 2008-07-31 07:26 Edited 2008-07-31 07:33

> As a point of reference my engine ZCT sees the line to make the fortress, but evaluates it as about -4.5.


Which is about correct. Toga needed 38 iterations after Kh8 to see that black really wins a pawn. :)

38/76+  23:01  1.503.551.060  1.088.265  +7,41  Qc3 Kf4 Qd4+ Kg5 Qf6+ Kg4 Qe5 f4 Qe2+ Kf5 Qe3 Kg5 Qe4 Kg4 Qd3 Kh4 Qf3 Kg5 Qh3 Bd5 Qh6+ Kf5 Qh5+ Ke4 Qxg6+ Ke3 Qg3+ Ke4 Kh7 f5 Qe1+ Kd4 Qf2+ Ke5 Kh6 Be6 Kg5 Kd5 Kf6 Bd7 Ke7 Be6 g6 Ke5 Qe3+ Kd5 Kf6 Kc4 gxf5 Bd5

The capture is on ply 25 after a zugzwang on ply 19.
Parent - - By Permanent Brain (*****) Date 2008-07-27 19:58
Do you think it was a good decision to call Rybka's randomizer function Monte Carlo analysis?
Parent - - By zwegner (***) Date 2008-07-27 20:14
It depends. The old Rybka Randomizer, AFAIK, just adds a random value to the evaluation. That I would not call Monte Carlo analysis.

The new version, from what I gather, does use MC playouts, but heavily biased ones. So technically it is MC, but I'd say it's pushing it. The main strength it has is from Rybka's search and eval.
Parent - - By Vempele (Silver) [fi] Date 2008-07-27 20:27

> The old Rybka Randomizer, AFAIK, just adds a random value to the evaluation.


No. It plays the moves that are worth at least best_score - margin. There's nothing random about it, really.

More.
Parent - - By zwegner (***) Date 2008-07-27 20:36
That's pretty strange. If there isn't a random element, but it just plays the best move within the margin that it hasn't played before, then that's definitely not MC. If the new Rybka MC is the same way, then I will reverse my last statement and say that it is _not_ MC. MC needs randomness!
Parent - - By Roland Rösler (****) [de] Date 2008-07-27 20:48
MC needs randomness!

Very true!
Parent - - By Jim Walker (***) [us] Date 2008-07-27 22:51
From what I've been reading here the randomness comes from the many games that will be played from the starting moves.  They will not all be the same game and eventually statistics will tell you which of the moves you are considering is best.  Am I wrong?
Jim
Parent - - By Roland Rösler (****) [de] Date 2008-07-27 23:30
Am I wrong?

I´m not sure. But in the starting position R3 will only have a look to the best moves in her eval. She will never look to a move which is more than -3 in eval to the other best moves in starting position. This seems to be good for most of the posters here. But MC is gambling and therfore you need randomness. And be sure, in endgames R3 needs gambling (flipping a coin!) sometimes.
Parent - By kblaine (**) Date 2008-10-16 21:26
What is the purpose of displaying what looks like 1st, 2nd, and 3rd standard deviation confidence limits while running Monte Carlo? What are the numbers in brackets? Should we be using this information in some way? Should I get out my old probability distribution tables from Statistics 101?

Sorry to post this here but have had no luck finding answer in the forum or at Chessbase. My guess is that it is not really important but my curiosity is aroused.
Parent - By lkaufman (*****) Date 2008-07-27 20:17
There is little difference in principle between Rybka 2.32a randomizer and Rybka 3 Monte Carlo, but the new one is vastly more efficient and easier to use. Either name is valid, maybe the new name was chosen to emphasize how much better the implementation is this time. It may not be the best way to do Monte Carlo analysis, but I think it does qualify as such.
Up Topic Rybka Support & Discussion / Rybka Discussion / First ever Monte Carlo vs. Rybka 3 game
1 2 Previous Next  

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill