Life In 19x19

Let P (even) be the number of players in a single round-robin and R = P-1 be the number of rounds.

Let there be either a) no jigos or b) jigos. Advanced consideration: Assume a particular frequency for jigos.

Each player's NumberOfWinsScore is the sum of his number of wins plus half his number of jigos.

Let us ignore specific players but consider result tables in general regardless of player names.

Let there be only one result criterion: the NumberOfWinsScore. Places with equal scores are tied.

Depending on P, how many different result distributions (tables) do exist?

Depending on P, how many of the result distributions have a tie on place 1? How many on place 2? Etc. How many on place P?

Do you want to assume players of even strength?

Harleqin wrote:Do you want to assume players of even strength?

The questions posed by OP can be answered without knowing anything about the strength.

Example:

- two players: one possible distribution, no ties (unless jigo is possible)
- four players: four possible distributions (again with no jigos), one of which contains three player tie for the first place, one of which contains a two player tie for the first place and another two player tie for the third place, one of which contains a three player tie for the second place and one of which contains no ties
etc.

e: there probably is an easy way to calculate these, but I'm not sure if I can figure it out. I may write a small program for this, unless someone does the calculations before me.

Harleqin, the question is independent of player strengths.

tj86430, maybe there is already some theory but it might be hard to find. Programmed calculations would be great! In practice, such questions are interesting up to P=16, e.g, for various components of EC systems.

On http://en.wikipedia.org/wiki/Tournament_graph
there is a bit of theory in what they call "score sets" but that does not answer my questions directly, except that "Let s(n) be the number of different score sequences of size n. The sequence s(n) (sequence A000571 in OEIS) starts as:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ..."

might for the even numbers extract answer my first question, if I interpret the cited text correctly. Then

http://www.research.att.com/~njas/sequences/A000571

gives yet more numbers for
Number of different scores that are possible in an n-team round-robin tournament:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 915695102, 3251073303, 11605141649, 41631194766, 150021775417, 542875459724, 1972050156181

So the even case numbers are:

2 4 6 8 10 12 14 16
1, 4, 22, 167, 1486, 14805, 158808, 1799659, ...

The numbers grow rapidly! So more theory is needed. (Manual calculation is already too tedious.)

Not only different numbers but also frequencies of same score distributions will be relevant.

I get the following

n | Number of distinct tournaments | Number of ties for first place
2 | 1 | 0
4 | 4 | 2
6 | 22 | 9
8 | 167 | 67
10 | 1486 | 561
12 | 14805 | 5419
14 | 158808 | 56461
16 | 1799659 | 625699

Does anyone know how to get tables to look pretty?

pwaldron wrote:n | Number of distinct tournaments | Number of ties for first place
6 | 22 | 9

I got
6 20 7, but I have probably overlooked something:

543210
543111
542220
542211
533310
533220
533211
532221
522222
444210
444111
444300
443310
443220
443211
442221
433320
433311
433221
432222

pwaldron wrote:Does anyone know how to get tables to look pretty?

use code tags

pwaldron wrote:

Code: Select all

n   | Number of distinct tournaments | Number of ties for first place
2   |              1                 |      0
4   |              4                 |      2
6   |             22                 |      9
8   |            167                 |     67
10  |           1486                 |    561
12  |          14805                 |   5419
14  |         158808                 |  56461
16  |        1799659                 | 625699

tj86430 wrote:6 20 7, but I have probably overlooked something:

You're missing the set where the winner only wins three games.
Also, [4 4 4 3 0 0] isn't valid. It's a round robin so you can't have two players without wins.

RobertJasiek wrote:Let P (even) be the number of players in a single round-robin and R = P-1 be the number of rounds.

Let there be either a) no jigos or b) jigos. Advanced consideration: Assume a particular frequency for jigos.

Each player's NumberOfWinsScore is the sum of his number of wins plus half his number of jigos.

Let us ignore specific players but consider result tables in general regardless of player names.

Let there be only one result criterion: the NumberOfWinsScore. Places with equal scores are tied.

Depending on P, how many different result distributions (tables) do exist?

Depending on P, how many of the result distributions have a tie on place 1? How many on place 2? Etc. How many on place P?

What do you mean?

Did some thinking for a round robin of 4 players

A Round robin of 4 players means 6 games
and excluding jigo's it means that there are 64 (2 power6) possible combinations of game results.

of these 64

24 (4 faculty) are clear results (every player has a definite place without ties)

the rest of them (40 or 62.5% has one of more ties)

I need to do some more testing but my hunch is that for more players the percentage of ties will grow.

4 person round robin

Players A, B, C, D

> means beats.

Round 1

Without loss of generality (Wolog)

A > B
C > D

Round 2

Wolog

A > C
B > D

Round 3

A ? D
B ? C

The winner of B vs. C will have 2 wins. If A wins she will be the sole winner, if D wins there will be a tie.

Assuming that the probability that A wins is 1/2, the probability of a sole winner is 1/2, and the probability of a tie is 1/2.

Just as pwaldron's numbers indicate.


Edit: I see that this is wrong:

Round 2

Wolog

A > C
B > D

willemien wrote:I need to do some more testing but my hunch is that for more players the percentage of ties will grow.

I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows.

pwaldron wrote:I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows.

Oh no, I just saw an infinite crowd of go players checking into Hilbert's hotel to play a single round robin. Someone should tell them...

Bill Spight wrote:4 person round robin




Edit: I see that this is wrong:

Round 2

Wolog

A > C
B > D

You did got me wondering where i was wrong. (the results did differ)

Guess that next time it will be me again that was wrong (As usual)

but i do think that A>C was Wolog (but agree that B>D was not)

pwaldron wrote:

willemien wrote:I need to do some more testing but my hunch is that for more players the percentage of ties will grow.

I think you're right. Your calculation keeps the labels on the players, but if we do that then there are 2^((n^2-n)/2) possible tournaments and only n! ways of having no ties. The limit goes to zero as n grows.

no that is not true n! is the amount of games without ANY ties. (for any place)

While the question was of ties in the first 3 places. a quite more limited amound.

and unfortunedly it will cost a lot odtf time to calculate t (even for an 6 persons round)

willemien wrote:

Bill Spight wrote:4 person round robin




Edit: I see that this is wrong:

Round 2

Wolog

A > C
B > D

You did got me wondering where i was wrong. (the results did differ)

Guess that next time it will be me again that was wrong (As usual)

but i do think that A>C was Wolog (but agree that B>D was not)

I think you're right.