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.
User avatar
slobo
Posts: 2331
Joined: Mon Apr 09, 2007 3:36 pm

Probability to have repeated games

Post by slobo » Mon Dec 21, 2009 12:34 am

Could anyone answer, please, what is the probability to have repeated games in a sample of 1000 games, with a time control 1 minute/game?
How many games could be repeated in one thousand of games played?
"Well, I´m just a soul whose intentions are good,
Oh Lord, please don´t let me be misunderstood."

User avatar
Graham Banks
Posts: 32889
Joined: Sun Feb 26, 2006 9:52 am
Location: Auckland, NZ

Re: Probability to have repeated games

Post by Graham Banks » Mon Dec 21, 2009 12:58 am

slobo wrote:Could anyone answer, please, what is the probability to have repeated games in a sample of 1000 games, with a time control 1 minute/game?
How many games could be repeated in one thousand of games played?
It would depend largely on the variety and depth limitation in the opening book that you use.
My email addresses:
gbanksnz at gmail.com
gbanksnz at yahoo.co.nz

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Mon Dec 21, 2009 1:51 am

slobo wrote:Could anyone answer, please, what is the probability to have repeated games in a sample of 1000 games, with a time control 1 minute/game?
How many games could be repeated in one thousand of games played?

I think this is not an easy statistically problem to tackle because there are too many unknown contributing factors. In this 1000 game sample, is this between the same engine, 2 different engines, or multiple engines? Is an opening book allowed, and if so, what is the move limit? Are we talking about a single or a set of predefined positions?

For example, there is 1/13 chances of picking a King in shuffled deck of cards. This is easy to calculate because we know how many Kings are there in deck of cards. So we when look at your question, we are dealing with a probability sequence problem. So what is the probability that in a shuffled deck of 52 cards the first card I pick is a King, and the second, a Queen? (4/52)x(4/51) = .006

Franklin

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

Re: Probability to have repeated games

Post by bob » Mon Dec 21, 2009 2:20 am

slobo wrote:Could anyone answer, please, what is the probability to have repeated games in a sample of 1000 games, with a time control 1 minute/game?
How many games could be repeated in one thousand of games played?
What are the constraints? Normal opening book? Very unlikely. Starting from a single position? Duplicates are likely, but not very many. No way to statistically answer this however, as there are too many questions unanswered abut a specific program.

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 » Mon Dec 21, 2009 5:54 am

If the program can randomly choose between equal moves then duplicate games are very likely.

Jouni
Posts: 1958
Joined: Wed Mar 08, 2006 7:15 pm

Re: Probability to have repeated games

Post by Jouni » Mon Dec 21, 2009 8:56 am

I have many times repeated 20 games Nunn matches. Even with ponder
off, longer time control and single CPU it's quite difficult to get exactly same game again. Many times 1-0 is in repeat 0-1!

Jouni

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 10:00 am

kingliveson wrote:
slobo wrote:Could anyone answer, please, what is the probability to have repeated games in a sample of 1000 games, with a time control 1 minute/game?
How many games could be repeated in one thousand of games played?

I think this is not an easy statistically problem to tackle because there are too many unknown contributing factors. In this 1000 game sample, is this between the same engine, 2 different engines, or multiple engines? Is an opening book allowed, and if so, what is the move limit? Are we talking about a single or a set of predefined positions?

For example, there is 1/13 chances of picking a King in shuffled deck of cards. This is easy to calculate because we know how many Kings are there in deck of cards. So we when look at your question, we are dealing with a probability sequence problem. So what is the probability that in a shuffled deck of 52 cards the first card I pick is a King, and the second, a Queen? (4/52)x(4/51) = .006

Franklin
Yes Franklin, the match is between the same two engines. And let´s imagine we have two oppening books: one with 100 positions and other with 200.

My impression is that 1 min/game time control contributes for getting repeated games, which would be much less probable for 1´+ 1" time control.
"Well, I´m just a soul whose intentions are good,
Oh Lord, please don´t let me be misunderstood."

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

Re: Probability to have repeated games

Post by playjunior » Mon Dec 21, 2009 10:06 am

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.

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

Re: Probability to have repeated games

Post by Milos » Mon Dec 21, 2009 11:06 am

slobo wrote:My impression is that 1 min/game time control contributes for getting repeated games, which would be much less probable for 1´+ 1" time control.
Actually the shorter time control is, there is less chance to get a repeated game. Simply in every move OS scheduling makes few milliseconds of difference, which after certain number of moves diverges the game that's started from the very same position as previous ones.
The uncertainty that is introduced by the OS is larger in relative units when time controls are shorter.

kingliveson

Re: Probability to have repeated games

Post by kingliveson » Mon Dec 21, 2009 1:06 pm

slobo wrote:
Yes Franklin, the match is between the same two engines. And let´s imagine we have two oppening books: one with 100 positions and other with 200.

My impression is that 1 min/game time control contributes for getting repeated games, which would be much less probable for 1´+ 1" time control.
I am thinking the more positions you introduce the lesser a chance there will be for a repeat game. This is all theory so the best course of action now is to define a test and carry it out. This is exactly what I plan to do and I should have some results by the weekend.

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.

Franklin

Post Reply