The bottom link on this page is a bit incorrect: http://www.rybkachess.com/index.php?auswahl=Purchase+Rybka

Should be: http://www.chessbase.com/newsdetail.asp?newsid=4772

Randomizer matches and building trees after them are presented in Aquarium.

http://rybkachess.com/index.php?auswahl=Rybka+2.3+readme

As I understand that, the only "random" factor in Randomizer is set by the "randomize=" threshold in centipawns.

CB. writes: "Monte Carlo Analysis yields precise evaluations by playing

**thousands of ultra-fast games**in a few minutes in a given position."

I understand the similarity, but it is not clear to me that it's the same feature (which would mean that we had Monte Carlo analysis already in 2.x, with the randomizer?!).

**Looks**but

**is**it really? Vas has to clear this....

*a lot*, to call it Monte Carlo analysis. I'm not an expert of the concept but from what I have read about it, I think I can say that the randomizer feature is much

*too simple*, compared to a true Monte Carlo approach.

And IIRC, he never called randomizer as Monte-Carlo.

It seems like they started to call randomizer as Monte-Carlo for better marketing.

In a true Monte-Carlo implementation, the engine must use this method for move selection in addition to normal search.

**Monte Carlo**methods are and why i think its simply irrelevant to chess.

I want go into strict definitions because it really does not matter and because some very specific maths are required but the general idea can be seen in the following example

Imagine a Square with a side a=2 and a circle inscribed inside the square with radius r=1.

We know that the square has an area of Sarea = a*a and the circle area = Carea = pi*r*r and if we put a=2 and r=1 we have

Sarea = 4 and Carea = pi

*Now we start with a monte carlo like procedure.*

If we randomly select points inside the square then those points may or may not fall inside the circle too.

The basic question is

The basic question is

If N are the total number of points how many do we "expect" to be inside the circle?

The answer is "obvious". For a large number of points N(in circle) / N (total) = circle area / square area = Carea/Sarea = pi/4

So here we have a way to calculate pi.

1) Generate a number of points UNIFORMLY inside the square

2) Count how many are inside the circle

3) Calculate N(in circle)/ Ntotal

the result is pi

**The bigger the number of N the better the approximation.**

**So we have transformed an area calculation problem to a probability one.**

Now how can this be applied to chess? or even better can this be applied?

*My opinion is NO and i will state why.*

**The basic idea is the following.**

1) Define a starting position.

2) Play a large number of positions (Ntotal)

3) Check the evaluation after and win percentages of moves after X number of positions.

4) Transform the winning percentages to evaluations.

So if a position is won 99% of the time its evaluation is 10.00 (for example)

if its always drawn then the evaluation is always 0.00

Nice try but i think the story does not have a dragon.

Why i think this is a bad approach (and i think i can prove it after i get my hands on the code)

The only assumption i will use is:

**Assumption**: The evaluation is not correct. (if it is correct then we dont need any special algorithm)

So the engine does not know how to play either side.

I will also need the following definitions

a)

**Winning Space**= the number of all variations that lead to a win

b)

**Drawing Space**= the number of variations that lead to a draw

c)

**Variations Space**= all variations

*When it will work.*

It will work in drawn positions when the engine has a large score but will not win (e.g opposite square bishops)

but the problem with this example is that Drawing Space is equal to the Variations Space so there is nothing to miss

When it will not work.

When it will not work.

It will simply not work when

**there is a winning space and its a very small one**, that is very few variations lead to a win.

For example it is possible that if we tell the engine to do a monte carlo analysis of 2Nvp (for a winning position) it will tell as that the position is a draw.

Generally i think that if

a) the winning space is not zero and it is much smaller than the drawing space (difficult to win)

b) the drawing space is not zero but it is much smaller than the winning space (difficult to draw)

montel carlo will fail.

**In a position that is neither a win nor a draw**(middlegame position) then the monte carlo approach {comparing the winning space to the drawing space to the variations space}

**is correct**

So this is good for a general assessment .

But in a win draw situation this simply does not hold. Why? Because a single variation that wins (or draws ) is enough and finding it in the general variations space without a compass (a very good engine evaluation) is impossible (in probabilities terms)

>Imagine a Square with a side a=1 and a circle inscribed inside the square with radius r=1.

I guess you mean diameter=1 or else the following you have said have no meaning.

So if diameter=1 then radius=0.5 so by modifying your statements we have:

------------

We know that the square has an area of Sarea = a·a and the circle area = Carea = pi·r·r and if we put a=1 and r=0.5 we have

Sarea = 1 and Carea = pi/4

Now we start with a monte carlo like procedure.

If we randomly select points inside the square then those points may or may not fall inside the circle too.

The basic question is

If N are the total number of points how many do we "expect" to be inside the circle?

The answer is "obvious". For a large number of points N(in circle) / N (total) = circle area / square area = Carea/Sarea = Pi/4

------------

We can still find Pi of course that way (Pi = 4·N(in circle)·N(total) ).

About the Chess related i don't have time to see them for now. I will look at them later....

It can be helpful to draw general conclusions. You might say that i can help overcome horizon effect but it can also help to evaluate as draw a winning position.

Anyway , its more useful in opening and middle game positions and almost bad in endgames

> Monte Carlo is a great tool if you know which positions to use it in

Exactly.

Generally monte carlo methods (in math) need a deterministic evaluator to apply probabilistic methods. So the results are as good as the evaluator function (in chess i mean).

A bad evaluator => bad results

Yes, Monte Carlo isn't excellent.

But, is current method of search excellent?

This is the point :)

*It will simply not work when there is a winning space and its a very small one, that is very few variations lead to a win.*

This might be valid if there is no "hash" or memory of the lines in the ultrafast games, but why do you assume this. Its clear that it is much more efficient to utilise the Monte Carlo method if each micro-game to some (mild) extend takes the results of previous games into account. (for example by applying the Monto Carlo method in different leaves in the

variation tree). In the case where the micro games help build up a tree (which is my understanding) and if one side has a "small winning space" any random walk will eventually hit this and thus the Monte Carlo method will eventually give the "correct" result.

I do not see what the method of finding the area of a circle has to do with chess. Probabilistic methods can be applied cleverly or stupid. Your circle example illustrate the idea behind the Monto Carlo method very well , but it is an incredible stupid application of the Monto Carlo method since there is absolutely no reason to randomize the selection of points and convergence is very slow. Primality testing is an example where the probabilistic methods currently beat the best deterministic methods. No fast deterministic evaluators are known to work in this case.

I think that your underlying premise is wrong. You compare Monte Carlo to traditional evaluation by engines, but as long as there just are some positions (e.g. positions where one party can build a fortress) that Monte Carlo pick up, the method is justified as an analytic tool. Nobody was suggesting that the Monto Carlo method should be used uncritically.

>I do not see what the method of finding the area of a circle has to do with chess

hehe. Its is exactly the same thing. If you where a mathematician you could see the analogy at once.

>and if one side has a "small winning space" any random walk will eventually hit this and thus the Monte Carlo method will eventually give the "correct" result.

Plain wrong.

If there is 1 winning line in millions of lines then even if it finds it cannot mark it as "winning" Why?.

Simple. Let to 1000 (rating) players play the ending KNB v K. The games will probably end in a draw or sometimes a win. Those are pure random walks but the "win" is not a winning line but a line that player B blundered and player A won.

The same is valid for chess engines. Let them play a rook ending. Winning losing drawing is irrelevant. There might be a study win and engine A may win engine B in a different way than the correct winning line because engine B played badly.

The key always is the evaluator. Its like trying to find maxima in a manifold. Without the gradient you can not do so.

The gradient in chess is the evaluator that acts like a compass.

Trust me i am 100% correct here.

*>I do not see what the method of finding the area of a circle has to do with chess*

hehe. Its is exactly the same thing. If you where a mathematician you could see the analogy at once.

hehe. Its is exactly the same thing. If you where a mathematician you could see the analogy at once.

I have a PhD in Pure mathematics from University of Oxford so I see the analogue.

*>and if one side has a "small winning space" any random walk will eventually hit this and thus the Monte Carlo method will eventually give the "correct" result.*

Plain wrong.

If there is 1 winning line in millions of lines then even if it finds it cannot mark it as "winning" Why?.

Simple. Let to 1000 (rating) players play the ending KNB v K. The games will probably end in a draw or sometimes a win. Those are pure random walks but the "win" is not a winning line but a line that player B blundered and player A won.

Plain wrong.

If there is 1 winning line in millions of lines then even if it finds it cannot mark it as "winning" Why?.

Simple. Let to 1000 (rating) players play the ending KNB v K. The games will probably end in a draw or sometimes a win. Those are pure random walks but the "win" is not a winning line but a line that player B blundered and player A won.

You are inventing a straw man here. Nobody claims that Monto Carlo is a method that leads to perfect play perfect chess or would in general suggest the strongest move.

When you talked about a small winning space I did not realise you referred you had end games like KNB v K in mind.

Your example with KNB v K is correct in theory but useless in practice (like the answer in the math joke). From a practical perspective an engine might evaluate KNB v K as +5.00 but if the hyper bullet games (at a level of a rating of 1000) leads to many draw, the engine would be alerted that the value of +5.00 could be wrong. In practice Monto Carlo would help alert many other type of end games might be drawn. Nobody is claiming that the method always produce the correct result and always manage to pick up potential problems.

The same is valid for chess engines. Let them play a rook ending. Winning losing drawing is irrelevant. There might be a study win and engine A may win engine B in a different way than the correct winning line because engine B played badly.

The key always is the evaluator. Its like trying to find maxima in a manifold. Without the gradient you can not do so.

The gradient in chess is the evaluator that acts like a compass.

Trust me i am 100% correct here.

The same is valid for chess engines. Let them play a rook ending. Winning losing drawing is irrelevant. There might be a study win and engine A may win engine B in a different way than the correct winning line because engine B played badly.

The key always is the evaluator. Its like trying to find maxima in a manifold. Without the gradient you can not do so.

The gradient in chess is the evaluator that acts like a compass.

Trust me i am 100% correct here.

But the point is that the engine is so strong (even at hyper bullet level) that there (to use your terminology) often is a gradient. I am convinced that the Monto Carlo method implemented in Rybka 3, occasionally can help the engine reassess the value of a move or raise certain the alarm that a certain moved might be problematic.

Trust me I am 100% correct here.

>> I have a PhD in Pure mathematics from University of Oxford so I see the analogue.

if that is so, and you know about monte carlo (which is not obligatory since mathematics is such a big field) then you should not ask me about the analogy because its evident.

> Your example with KNB v K is correct in theory but useless in practice

My example shows simply that the results are as good as the evaluator. This holds for every monte carlo like method (mostly integration and economics...)

All those require a deterministic evaluator (usually a function of many variables)

> But the point is that the engine is so strong ...

When the engine is strong (at the position) the results are good.

When the engine is bad the results (e.g in endgames) are bad.

So in bottom line , you cannot bring the engine to a new level.

So if two low level players (of equal strength) play position A and player A wins player B by 70-30 then they reach to a conclusion that position A is +/-

The truth might be that the position is -+ :)

I am not saying its useless but it not important.

It would be great after creating the variations space to create an algorithm that can construct an evaluator (gradient) which will require

first to identify the number of the space of variations (super hard). That would be really interesting and i think has been discussed in the forum here by Vas.

> Trust me I am 100% correct here.

LOL

*So in bottom line , you cannot bring the engine to a new level.*

So if two low level players (of equal strength) play position A and player A wins player B by 70-30 then they reach to a conclusion that position A is +/-

The truth might be that the position is -+ :-)

So if two low level players (of equal strength) play position A and player A wins player B by 70-30 then they reach to a conclusion that position A is +/-

The truth might be that the position is -+ :-)

Who is concluding the position is +/- because player A wins has a score of 70/30 against player B? Given two alternatives that roughly get the same evaluation, but where the hyper bullet games strongly favor one of the options, it is probably wise to choose that option. I am sure Vas has some idea about whether this will bring the play to a different level. I do not believe its possible say anything non-trivial and definite about this without concrete experiments. But unlike you I am pretty confident that the Monto Carlo method is a new powerful tool that eventually (if not already) will take engine play to a higher level.

> Who is concluding the position is +/- because player A wins has a score of 70/30 against player B

Do i need to answer that? Its very obvious.

If we play a position (and we are of equal strength) and we win me 100-0 on that position then (if we are of equal strength) the position is a totally winning one.

A position is defined as +/- if..... (you can look at sample percentages at alburts book) Generally the limits are not strict and are just for the sake of definition.

> but unlike you I am very confident that the Monto Carlo methods is a new powerful tool that eventually (if not already) will take engine play to a higher level.

I am expecting to see a position in the middle game that boost the level of the engine and then i will counter show you hundreds of misleading :)

As a computer scientist I've used Monte Carlo Methods on problems ranging from image restoration to voice recognition to discovery of coding regions in DNA.

I'm certain that you could devise a Monte Carlo Method that would provably converge to the optimal move in a chess game, but it would of course need infinite time and/or space to do so. In any case, the theoretically optimal method would almost certainly not be the best one in practice.

Computer scientists are usually pragmatists, and I'm certain that Vas will use this virtue when applying such methods.

As for the number of processors that would outpreform normal chess programs, you must also take into account storage space.

If we move to infinity then the variation space converges to tablebases.

So in 5 years time it might be possible for ordinary people (as well as chess champions) to "rent" computational power that makes the Monto Carlo method even more powerful.

If each hyper bullet game in the future can be played at slower pace but highly parallelized maybe each game can be played at GM level and maybe with different settings (so the games are played with different settings representing different approaches to the position).

Larry, I have a few questions:

a) What is the current "rating" of each hyper bullet game

b) Are the games independent of each other or are the games results added into some variation tree (like shootouts in the IDeA in the aquarium)

p.s. I am sorry that I use the CB terminology "shoot out", but I am not sure what the terminology is in aquarium.

*a major new feature of computer chess*is being announced, members of the developement team have to guess(?!) what it actually is and how it works. This is not professional. If Monte Carlo, a major new idea in board game software, is being announced for a major chess software release, I expect that ALL members of a developement team have perfect, complete information what this is about.

It's like saying, yes we are flying to the moon, but I don't know which vehicle we use, who the astronauts are, etc. I guess during the Apollo missons every single member (from thousands!) knew the basic facts about these missions. It is a JOKE that in a

*small*team, one member doesn't know what the other makes, basically. You need to improve your communication.

> I expect that ALL members of a developement team have perfect, complete information what this is about.

This was caused by the fact of wanting everything to be kept secret ;)

Because in a given position, the number of possible continuations is extremely high for todays computers.

And , as Monte Carlo uses random moves (points), the possibility of finding the right pv is very very close to zero.

If the circle in the square has nothing to do with chess, this means that Monte Carlo method has nothing to do with chess. And this is wrong (until it is tested).

By the way, it is nice to be in a forum where everybody is 100% correct :)

> By the way, it is nice to be in a forum where everybody is 100% correct

LOL

> By the way, it is nice to be in a forum where everybody is 100% correct :-)

It's also nice that everybody trusts everybody else 100%. :)

> By the way, it is nice to be in a forum where everybody is 100% correct :-)

Yeah, and has performed a Monte Carlo experiment to prove it :)

For example, if in a position there are 2 candidate moves A and B, and both give a 50% score. But variation A has further 2 lines A1 and A2, with A1 scoring 100%, and A2 scoring 0. If we could explore the space near A1, perhaps we could get a better evaluation?

> Moves are as far as I understand not selected randomly

a) in a position the engine has accurate evaluation we dont need any other type of algorithm

b) in a position the engine has bad evaluation then moves are close to random (i have in mind rook endings for example or KNNvKp without tablebases)

The only cases the procedure will work are horizon effects and fortresses (although i am pretty sure we can construct fortresses that the engine will not find basically because it will not know how to defend the fortress. If the engine evaluates a fortress position +5 then its possible that every move in the stack is almost +5 and will not know how to defend the fortress , except for obvious ones)

if so, we don't need any other method than alpha-beta.

*playing at GM level in ultra-blitz?*

if so, we don't need any other method than alpha-beta.

if so, we don't need any other method than alpha-beta.

???

I wrote: "with sufficiently fast hardware" and did not claim such hardware exist. In a few years it might be possible to play (in parallel) a bunch 100 games every minute and use these games (together with specific traditional analysis) to build up a high quality variation tree.

My point of suggesting ultra fast games at GM-level was to provide a "counter example" to an "mathematical" argument by buffos who argue that the Monto Carlo method (in all circumstances i.e. including hyper fast shoot-outs at GM level) would never have any great value.

*Two men are in a hot-air balloon. Soon, they find themselves lost somewhere. The spot a guy on a hilltop below.*

One of the men leans over the basket and asks, "Where are we?"

The guy on the hilltop thinks for a while and then answers. "You are 10 meters above the ground in a balloon"

They continue the travel in th balloon. One of the men says, "That must have been a mathematician."

(1) he took a long time to answer,

(2) he was absolutely correct, and

(3) his answer was absolutely useless."

One of the men leans over the basket and asks, "Where are we?"

The guy on the hilltop thinks for a while and then answers. "You are 10 meters above the ground in a balloon"

They continue the travel in th balloon. One of the men says, "That must have been a mathematician."

(1) he took a long time to answer,

(2) he was absolutely correct, and

(3) his answer was absolutely useless."

> (3) his answer was absolutely useless.

Too funny. Andrew Wiles (alma mater at Oxbridge both) proved Fermat's last theorem and the Taniyama Shimura conjecture. Surely this proof must have had

*some*practical use??

by the way , one of the best proofs i have ever seen is the Godel's completeness theorem. Simply a masterpiece.

> one of the best proofs i have ever seen is the Godel's completeness theorem. Simply a masterpiece.

Please supply the practical application of it - so what was the benefit to the real world of it etc. I know it probably exists, but I don't know what it is.

But mathematics don't exactly work that way. Their use, the use for example of a theorem may have a practical application many many years after the theorem's appearance.....

> But mathematics don't exactly work that way. Their use, the use for example of a theorem may have a practical application many many years after the theorem's appearance.....

I think that his incompleteness theorems came out in 1931.

**If**what you say is correct then I wonder if there is a theorem (or formula) that says when any theorem will be practically useful? Alternatively this could be like the Emperor's New Clothes, or alternatively a tax wheeze? ;)

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill