all five players tie for first in a monthly cup

einstein.mc.2011.nov.1.13

I did a quick back-of-the-envelope calculation of the probability of a 5-way tie if all games are a fair coin-flip (and let's face it, Ewn is pretty close to that:).

Anyone care to do their own calculation, and see if we come up with the same number?

I verified my number empirically on a few million tourneys. (and boy, are my thumbs tired... :)

If you don't want to post a spoiler, send me your answer in a message, and in a couple of days i'll post a list of people who got it.

Has anyone ever seen this before on LG -- in a round with 5 or more players? I think it's pretty cool!

> empirically on a few million tourneys

Since there are only 2**10 tourney outcomes, I would think checking 1024 carefully selected tourneys would be enough.

Carroll: I take it that a "tournament", as used on that page, is a graph with one node for each player and a directed edge for each played game, but I didn't find definitions for "regular tournament" or "labeled regular tournament". What are those?

That happens sometimes, the same results came up one month before:

• einstein.mc.2011.oct.1.8

My first calculation was effectively an enumeration over the 1024 cases. I checked it using a simple coin-flipping simulation (this is very good practice for probability questions that are more complicated than this one). The simplicity of the program makes it a nearly bullet-proof sanity check; and a million tourneys gives three-digit accuracy in only a few seconds.

So far, Tasmanian Devil, MarleysGhost, and OneStone_c (i.e. Richard Lorentz) have provided correct answers. Tasmanian Devil used a different method than mine, which is quite slick.

@YHW: Again with me in the mix. I guess mine was a dumb question!

I guess, you're playing so many games that you're not able to control all results ;)

"ewn is close to a fair coin flip" Was that supposed to be a joke?

It is close to a coin flip if the number of played games against each other is low. It can be that a significant worse player would be in front against a strong player (by luck) even after 50 finished single matches. So, the coin flip assumption should not produce a high error applied to a single 3-point-match tournament.

If both players are not weak (e.g. beginner level), then yes, the outcome of any one game should be close to a coin flip. A 55-45 advantage would indicate a significant skill difference, and even the random initial positions can be more skewed than that, let alone lucky rolls.

As i mentioned in another thread, it would probably take more than a thousand games to confidently differentiate between any two of the the strong bots, for example (and possibly much more than that). Lots of thinking may go into a game, but nevertheless, the final result is mostly due to chance.

Take any player as A. S/he must go 2-2. The chance of that is 3/8. Of the two players who lost to A, one will win when they play each other. Call that player B and the other one C. Of the two who lost to A, one will lose when they play each other. Call that one E and the other D.

B, having already beaten A and C, must lose to D and E. Now we're at 4/32. Similarly, E must beat C (and as we've already accounted for, B) so now we're at 3/64. That accounts for 9 of the 10 games. The last game must go a particular way, so we end up at 3/128.

Dvd, that is almost identical to the solution I sent to darse. ;-)

These were best of 5 games. I wouldn't call that "pretty close to a coin flip" but of course, it depends on your definition of "pretty close".

> 4/32

or 3/32.

@Thnik: I'll go out on a limb and suggest that the fraction of monthly cup matches that end in 5-way ties is significantly less than the calculated fraction. If so, the hypothesis that Ewn results are equivalent to a coin flip is disproved.

Dvd's argument isn't quite correct because at one point B is among the players who lost to A and at one point B has beaten A.

@Carroll

What is the number of such paths for the 5 players regular tournament?

I got 15.

> A beats B who beats C who beats D who beats E

And if we append "..who beats A", we get a Hamiltonian cycle.

Assuming a "regular" tournament is a round robin in which each player has the same number of victories, I found 1 Hamiltonian cycle for 3 players, 2 for 5 players, and 17 Hamiltonian cycles for 7 players.

And 3 Hamiltonian paths for 3 players, 15 for 5, and 175 for 7.

These 5 player regular tournaments are isomorphic, but is that generally true?

Wow, it is gratifying to pose such a question to an audience who is absolutely all over it. :)

Here is how i counted it. There might be more elegant ways (like Taz's), but this was

the first thing i thought of.

<br/> 10 games gives 2^10 = 1024 possible outcomes
<br/><br/>  1:  1 2 3 4 5
<br/>    +-----------+
<br/>  1 | x 2 2 0 0 | (4 choose 2) = 6 ways of winning 2/4
<br/>  2 | 0 x . . . |  - all equivalent up to relabelling
<br/>  3 | 0 . x . . |
<br/>  4 | 2 . . x . |
<br/>  5 | 2 . . . x |
<br/>    +-----------+
<br/><br/> 2a:  1 2 3 4 5            2a:  1 2 3 4 5
<br/>    +-----------+             +-----------+
<br/>  1 | x 2 2 0 0 |           1 | x 2 2 0 0 |
<br/>  2 | 0 x 2 2 0 | 2 ways    2 | 0 x 2 2 0 |
<br/>  3 | 0 0 x . . |       ==> 3 | 0 0 x 2 2 | 1 way
<br/>  4 | 2 0 . x . |           4 | 2 0 0 x 2 |
<br/>  5 | 2 2 . . x |           5 | 2 2 0 0 x |
<br/>    +-----------+             +-----------+
<br/><br/> 2b:  a b c d e           2b2:  a b c d e
<br/>    +-----------+             +-----------+
<br/>  1 | x 2 2 0 0 |           1 | x 2 2 0 0 |
<br/>  2 | 0 x 0 2 2 | 1 way     2 | 0 x 0 2 2 |
<br/>  3 | 0 2 x . . |       ==> 3 | 0 2 x 2 0 | 2 ways
<br/>  4 | 2 0 . x . |           4 | 2 0 0 x 2 |
<br/>  5 | 2 0 . . x |           5 | 2 0 2 0 x |
<br/>    +-----------+             +-----------+
<br/><br/> 5-way tie = 6 * 2 * 2 = 24 ways,   24/1024 = 0.0234375  (2.34%)
<br/>

Here is Taz's solution:

It is also possible to find the answer without enumerating all possibilities.

Call one of the players A. The probability that he wins two and loses two is C(4, 2) / 2^4 = 3/8. We can assume that the two players he beat are B and C, and furthermore that B beat C.

Now C needs to beat the remaining players D and E, and the probability for this is 1/4.

We can assume that D beats E. Now D has two victories and E has two losses (recall that they both beat A), so we need that B beats D and that E beats B, and the probability for this is 1/4.

This gives 3/8 * 1/4 * 1/4 = 3/128.

With the existence of non-isomorphic tournaments, I thought there might be several different values for the number of paths for a given number of players, but I could be wrong.

@Carroll: I wrote code which, at each size, found a "regular" tournament, then tried all permutations (brute force) of the players, counting the number of permuations which were Hamiltonian paths and the number which were cycles. The only manual arithmetic was dividing the reported count of cycles by the number of players (because the code counted each cycle separately for each distinct starting player).

For the first, 249 cycles, 3357 paths. For the second, 228 cycles, 3279 paths, so they are different. This is rather off the cuff, so I would suggest checking these numbers before publishing a new Integer Sequence. :)

BTW, i forgot to mention that i re-ran the coin-flipping simulation with two good players and three worse players, with a fairly large 60-40 edge for the better players versus the worse ones (applies in 6 of the 10 games).

The number of 5-way ties drops, of course, but only to 2.07% (20702 tournaments out of a million). So the result is fairly robust (at around 2%), even if there is a moderate amount of skill variation in the players.

If a lot fewer 5-way ties have been seen in practice, there are a number of possible explanations, including smallish sample size, defaulted games, and the fact that humans aren't random. :)

The first has 24 cycles, 189 paths.

The second has 15 cycles, 171 paths.

It's the third that has 17 cycles, 175 paths.

Are there only 2 for 9-player tied tournaments, 1 fewer than than for 7-player tournaments?

Using the data in that rt9 link, I get

111100001110001110011101111111000000: 3267 paths, 222 cycles

111100001010101110110010111011001000: 3275 paths, 224 cycles

111100001010110110101010111011001000: 3299 paths, 231 cycles

111100001111000100111101110111000101: 3159 paths, 207 cycles

111100001110100101011101110111000101: 3249 paths, 221 cycles

111100001010110110101100111111000101: 3303 paths, 231 cycles

111100001010110110011101011111000101: 3243 paths, 222 cycles

111100001010101110011010111110001000: 3281 paths, 225 cycles

111100001010011110101011101011001000: 3357 paths, 249 cycles

111100001010011110011011011110100010: 3279 paths, 228 cycles

111100001110010011101010110111100101: 3255 paths, 224 cycles

111100001111000101011101110111100101: 3255 paths, 225 cycles

111100001110010101101110110111100101: 3297 paths, 230 cycles

111100001011010110101001111011100101: 3333 paths, 243 cycles

111100001110001101011101110111000000: 3255 paths, 224 cycles

There's also an rt11 file with 1223 entries. Watching the data scroll by, it looked like 92 or 93 thousand paths, 4 or 5 thousand cycles each, but it's too much data to post.

Discussions like this one is the reason why I love Little Golem.

I didn't want to say anything at the time, but when this thread started i was already hoping for a 5-way tie in einstein.mc.2012.feb.1.2, which will now probably happen.

As usual, all of the matches finished within a few days, except for Diamante's games, which always drag on for weeks or months. (*) I started with 2 losses and a win, so the only way to keep my streak alive was for a 5-way tie on 4 points. That meant the sloth had to go 2-2, winning against both 2-1 players and losing to both 1-2 players. If he eventually plays the winning move that he rolled against naive_child almost 3 days ago, everyone will tie at 2-2.

(*) [Diamante takes the absolute maximum amount of time allowed for every single move, even if it is a winning move, and even if there is only one legal move. I occasionally tricked him into making several moves during the same session, but then he simply waited for the full 10 days to elapse before resuming the schedule of one move every three days. I stopped playing Ewn tournaments to avoid him (he plays in practically all of them), and i will be quitting LG due in large part to the reduced fun factor.]

you all tied but still you lost (placed bottom in the table)

btw darse, no reason to quit if a player is slow. Just enjoy the games that get played on time and ignore the others. Don't worry so much about tournaments, after all, EWN is a coin flip anyway ;)

So here you have your tie in that tournament, it is finished what means that Diamante is also in the next round...
I also try to avoid tournaments for which Diamante is already registered because it takes almost 2 months until the games are finished.
The thing is, Diamante has 300 active EWN matches. If he would do only one move per game every day/evening it would be as if he would play every day one and a half 7-point matches per session. That's too much. Such a high number of active matches is only practicable for a bot (24 hours on). I have no idea why he always sign up for new tournaments.

Does he often time out?

I'm guessing he is no match for the might Gerald with regards to signing up for tournaments and not playing.

You could make it so that you could only sign up for new tournaments if you had no games where you were on turn :O

@Thnikkman - that was discussed before and I was one of the players against it

To be fair, Diamante almost never quits, nor times out.

He actually plays very quickly, making decisions in a few seconds, and makes moves in dozens of games when he logs in (that's how i was able to get a few consecutive moves in, by responding very quickly). It's just that he only makes moves in the games that are near the time-out limit, not in any games that can wait another day or two.

A solution would be to have different time controls, according to different tastes. My guess is that that isn't gonna happen on LG anytime soon.

I have enjoyed playing casual games with good players like YHW, kpato, and the bots. I might continue to play occasional friendly matches, but for Ewn, 3 days per move (no less) is just too painful, so i'm done with tournaments.

5-way tie embedded in the middle of a table .

darse it makes no sense, why not play in tournament? How is a slow game worse than no game at all? Just don't worry about the state of the tournament and you will be fine.

And a double 3-way tie