Probability to have repeated games

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Milos
Posts: 3384
Joined: Wed Nov 25, 2009 12:47 am

Re: Probability to have repeated games

Post by Milos » Mon Dec 21, 2009 1:34 pm

kingliveson wrote: The constraint will probably be a book made with a single game--so there is only one predefined position for the 1000 games. Now the question is up to how many moves before exiting the book. It would seem the higher the number of book moves the more likely there is a chance of getting repeat games--because you could end up with singular move positions.
How I see it, simplified it's something like:
The probability that the engine will play the same move in game at ply=n (where n is the number of book plys) is p. The probability at ply=n+1 becomes p^2, at n-2 becomes p^3, etc.
Let's say we have 10 moves from the book. The probability that the game will diverge up to move 30 is:
(1-p)+(1-p^2)+...+(1-p^40). Now let's say p=99.9%. This gives us probability of 81% that the game will diverge up to move 30 starting from the book move of 10.
All this is just hypothetical but it give you some feeling about how the number of book moves could effect it.
Also, the shorter time control is, the smaller p is and vice-versa.

User avatar
slobo
Posts: 2331
Joined: Mon Apr 09, 2007 3:36 pm

Re: Probability to have repeated games

Post by slobo » Mon Dec 21, 2009 3:36 pm

playjunior wrote:You can test it.
Put the same opening position and run games, see what is the probability of getting the same game. Do this for different opening positions.

Then sample books and see how often you get the same position. Multiply this with the probability of getting the same game from the step above. This will be a good approximation of probability of getting repeated games.
Very good idea:
When we have not any theoretical truth, we should start an experiment and find out a practical one.

Many thanks to all of you who answered my question.

SL
"Well, I´m just a soul whose intentions are good,
Oh Lord, please don´t let me be misunderstood."

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Mon Dec 21, 2009 4:00 pm

Milos wrote:
kingliveson wrote: The constraint will probably be a book made with a single game--so there is only one predefined position for the 1000 games. Now the question is up to how many moves before exiting the book. It would seem the higher the number of book moves the more likely there is a chance of getting repeat games--because you could end up with singular move positions.
How I see it, simplified it's something like:
The probability that the engine will play the same move in game at ply=n (where n is the number of book plys) is p. The probability at ply=n+1 becomes p^2, at n-2 becomes p^3, etc.
Let's say we have 10 moves from the book. The probability that the game will diverge up to move 30 is:
(1-p)+(1-p^2)+...+(1-p^40). Now let's say p=99.9%. This gives us probability of 81% that the game will diverge up to move 30 starting from the book move of 10.
All this is just hypothetical but it give you some feeling about how the number of book moves could effect it.
Also, the shorter time control is, the smaller p is and vice-versa.
Interesting...though am not sure that this probability can be described mathematically with summation of a single static variable. I understand n-p-p^2-...-p^n series is all hypothetical, but there are just too many dynamic variables that comes to play. Only thing left is to run some tests. I welcome suggestions on max book ply.

Franklin

bob
Posts: 20411
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Probability to have repeated games

Post by bob » Mon Dec 21, 2009 5:56 pm

Bill Rogers wrote:If the program can randomly choose between equal moves then duplicate games are very likely.
How do you figure? we already know that if you play two games using the same program/opponent for both games, and for each game you vary the nodes searched by only _one_ node, you get different games 99% of the time. So how is randomly choosing between equal moves going to make duplicate games "very likely"? Or did you mean "unlikely" and mistype???

playjunior
Posts: 338
Joined: Thu Jun 21, 2007 10:53 pm

Re: Probability to have repeated games

Post by playjunior » Tue Dec 22, 2009 10:44 am

slobo wrote:
playjunior wrote:You can test it.
Put the same opening position and run games, see what is the probability of getting the same game. Do this for different opening positions.

Then sample books and see how often you get the same position. Multiply this with the probability of getting the same game from the step above. This will be a good approximation of probability of getting repeated games.
Very good idea:
When we have not any theoretical truth, we should start an experiment and find out a practical one.

Many thanks to all of you who answered my question.

SL
The problem is you cannot calculate this theoretically. There are some variables which you need to measure in the end of the day. Like-the probability of having a repeated game from the same position. It depends on the engine, compiler used to compile it, time control, hardware, OS, and maybe outside temperature.

Same with the book - book moves have different probabilities. Some leaf positions are more likely to occur because they are main lines. No way to compute that theoretically either.

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Tue Dec 22, 2009 6:07 pm

I have some results which I will post/upload later. I think it will add some perspective to the discussion.

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Probability to have repeated games

Post by Bill Rogers » Tue Dec 22, 2009 9:06 pm

Robert
I tried to correct my posting right after I had posted it on the site. I don't know why it did not take my corrections. You are correct my reply should have read very unlikely.
I did not read where a person could very some of the variables before each game as you stated ie. number of nodes, etc.
Bill

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Tue Dec 22, 2009 10:37 pm

1000 Games Tested:
Condition:

The test is conducted using Fritz 11 GUI on Windows 7 64-bit. The hardware is an AMD Phenom II 940 overclocked to 3.6 GHz. The test runs continuously--none stop until it reaches 1000 games.

The engines are 4 CPU 64 bit versions with hash size set to 128 MB and pondering/permanent brain is disabled. Time control is 1 minute with no increment.

Both engines use the same book renamed to 1000E01.ctg (Naum 4) and 1000E02.ctg (Zappa Mexico II). The book has only one predefined position with 20 half moves or 10 plies. The final position after exiting the book is:

r2qkb1r/1p1n1pp1/p2p1n2/3Pp2p/8/1N2BP2/PPP3PP/R2QKB1R w KQkq - 0 11
Results:

White Wins : 299 (29.9 %)
Black Wins : 393 (39.3 %)
Draws : 308 (30.8 %)

Final Outcome: No game is repeated.

Milos
Posts: 3384
Joined: Wed Nov 25, 2009 12:47 am

Re: Probability to have repeated games

Post by Milos » Wed Dec 23, 2009 12:20 am

kingliveson wrote: Results:

White Wins : 299 (29.9 %)
Black Wins : 393 (39.3 %)
Draws : 308 (30.8 %)

Final Outcome: No game is repeated.
Thanks for the result. It is kind of expected :).
One more firm conclusion can be made. This position is more beneficial for black. ;)

I usually test engines with 80 opening positions, no matter how many games per tournament is played. Sometimes I have a few thousand games per tournament. And I've never ever seen a repeated game.

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Wed Dec 23, 2009 12:52 am

Milos wrote:
kingliveson wrote: Results:

White Wins : 299 (29.9 %)
Black Wins : 393 (39.3 %)
Draws : 308 (30.8 %)

Final Outcome: No game is repeated.
Thanks for the result. It is kind of expected :).
One more firm conclusion can be made. This position is more beneficial for black. ;)

I usually test engines with 80 opening positions, no matter how many games per tournament is played. Sometimes I have a few thousand games per tournament. And I've never ever seen a repeated game.
I think the result may be skewed due to zappa mexico not playing blitz well. So now am running another 1000 game test with the same position, but this time with a single engine--Naum vs Naum. This should be interesting. Here is the result so far:

Games : 212 (finished)

White Wins : 57 (26.9 %)
Black Wins : 55 (25.9 %)
Draws : 100 (47.2 %)

No repeated game so far. I will post the final result later and upload the games.

Post Reply