So many repeats

[Jellby]

Just to confirm it, can you run the same with the algorithm KuWizard described (13 distinct cards out of 110 are chosen randomly, a single random index between 1 and 5 is chosen randomly, the word with that index from each of the 13 cards is selected)?

[Mathew5000]

Just to confirm it, can you run the same with the algorithm KuWizard described (13 distinct cards out of 110 are chosen randomly, a single random index between 1 and 5 is chosen randomly, the word with that index from each of the 13 cards is selected)?

Algorithm 3 (13 distinct cards out of 110 are chosen randomly and the same randomly-chosen index, from 1 to 5, is used for each of the 13 cards): Results from simulating a set of three games, one million times:
56.4% no repeats
16.9% exactly one word repeated once (with no word repeated twice)
14.4% exactly two words each repeated once (with no word repeated twice)
7.2% exactly three words each repeated once (with no word repeated twice)
2.6% exactly four words each repeated once (with no word repeated twice)
1.0% exactly five words each repeated once (with no word repeated twice)
0.7% six or more words each repeated once (with no word repeated twice)
0.7% at least one word repeated twice (i.e. there's a word that's in all three games)

So if you're playing three games, and want to avoid repeats, this is a much better algorithm than the other two.

Playing 3 games, algorithm 3 would give only a 44% chance of any repeat, whereas algorithm 1 or 2 gives a 61% chance of any repeat.

But ... suppose you play more than 3 games, let's say 5 games. My hunch is that algorithm 3 would then be worse. Or actually, what I think might happen is, when you play five games, all three algorithms would give quite a high probability of any repeat, but algorithm 3 would have a higher probability of, 3 or more repeats within the 5 games, whereas for the other two algorithms, usually there would only be 1 or 2 repeats. I'm just speculating about that. I'll run a simulation of all three algorithms, for 5 games, today or tomorrow. Stay tuned.

[Mathew5000]

Since I last posted in this thread, my crappy little laptop has played 15 million games of Just One. That's a million sets of five games each, for each of three algorithms. (To be honest, my laptop did not really "play" the game; it merely simulated a setup of 13 distinct words for each game.)

In the results below, when I say "4 repeats" (for example), it means that within a set of five games, there were exactly 4 instances of a word occurring that had previously occurred in the set. So the category of "4 repeats" includes the following situations, among others:
- exactly 57 words occur once and exactly 4 words occur twice
- exactly 58 words occur once, exactly 2 words occur twice, and exactly 1 word occurs three times
- exactly 59 words occur once and exactly 2 words occur three times
- exactly 59 words occur once, exactly 1 word occurs twice, and exactly 1 word occurs four times
- exactly 60 words occur once and exactly 1 word occurs 5 times

Also, and I think this is clear already but I want to state it explicitly, if I refer to "probability" (or "chance") it is not a probability calculated analytically, but rather the frequency that the category occurred in my simulation of a million sets of five games (for the algorithm in question). It should be very close to the true probability.

Here are my results:

Algorithm 1 (13 distinct cards out of 110 are chosen randomly and for each chosen card 1 word out of 5 is chosen randomly):

Code: Select all

0 repeats:  4.0 %
1 repeat:  13.8 %
2 repeats: 22.9 %
3 repeats: 24.1 %
4 repeats: 18.0 %
5 repeats: 10.3 %
6 repeats:  4.6 %
7 repeats:  1.7 %
8 or more repeats: 0.7 %

Algorithm 2 (13 distinct words out of 550 are chosen randomly):

Code: Select all

0 repeats:  3.9 %
1 repeat:  13.8 %
2 repeats: 23.0 %
3 repeats: 24.0 %
4 repeats: 18.0 %
5 repeats: 10.2 %
6 repeats:  4.6 %
7 repeats:  1.7 %
8 or more repeats: 0.7%

Algorithm 3 (13 distinct cards out of 110 are chosen randomly and the same randomly-chosen index, from 1 to 5, is used for every card):

Code: Select all

0 repeats: 11.5 %
1 repeat:  17.6 %
2 repeats: 19.7 %
3 repeats: 16.3 %
4 repeats: 12.4 %
5 repeats:  8.8 %
6 repeats:  5.7 %
7 repeats:  3.4 %
8 or more repeats: 4.7 %

It's fair to say that for each of these three algorithms, if you play five games you are very likely to see at least one repeat. For algorithms 1 and 2, you'd have about a 59% chance of seeing 3 or more repeats in 5 games, while for algorithm 3 you'd have about a 51% chance of seeing 3 or more repeats in 5 games. So on that basis, I'd say that algorithm 3 is preferable to either of the other algorithms.

Still, even under algorithm 3, after you play a few games then you will usually see, in each subsequent game, 1 or 2 words that you've already seen recently. I can sympathize with people who think, to quote the OP, "it should be way more rare to see repeats than what I've seen". It's the Birthday Paradox, as Jellby pointed out.

[Mathew5000]

Here's my proposal, which may sound a bit crazy: the server should look at the last several games of each player, and choose 13 words that none of these players have seen in a while.

For example, if there are 5 players, look at their most recent 6 games. This gives you a set of at most 390 words. There are 160 words remaining, from which to choose the 13 to be used in this game.

Now, what if there are say, 7 players, and when you look at all of their most recent 6 games, it totals up to 546 words leaving only 4 remaining? Well, you can use those 4 words plus 9 others that most of the players have not seen in a while. But this situation won't happen very often, because the way this game is played on this site, people frequently use the "propose a rematch" button so typically in a game of 7 players, at least 5 of them will have played together in their most recent game or two. I believe that almost always, if the software can examine each player's most recent games, it could pick a set of 13 words that none of the players have seen recently.

@KuWizard is something like this feasible?

[Jellby]

Apart from repeat probability, another issue is predictability. Assuming you know how the words are distributed among the cards.

With algorithm 1 (closest to the physical game), once you see the first word, you can be sure 4 other words won't appear in the rest of the game.

With algorithm 2, you can't exclude any other word.

With algorithm 3, you can exclude 440 words, it's sure that the next words are only chosen among 109.

In my opinion, if you're not going to use the actual rules of the physical game (let the players choose the word in the card), there's no reason to actually limit yourself to how the words are distributed in the cards, and you could either use algorithm 2 or create "fake" cards with a number of words different from 5 (would 3 or 10 words per card cause fewer repeats, if that's your only concern?).

[Jellby]

Note also that algorithm 3, while it increases the chance of "no repeats", it also increases the chance of 1 repeat (17.6% vs 13.8%), and 6 or more (13.8% vs. 7.0%).

[bagofnails]

More words would seem to obviously be the answer. In the real life game this would problematic, but on a website such as this, the problems would be much easier to overcome.

[robinzig]

Here's my proposal, which may sound a bit crazy: the server should look at the last several games of each player, and choose 13 words that none of these players have seen in a while.

While I don't know how Just One is currently implemented, I have enough experience of developing for BGA to be able to tell you that this, while a nice idea, isn't possible to do in the BGA framework. You can't query any database other than those that exist for that specific table.

Maybe some BGA in-house developer knows a way to get around this, because in theory it should be possible - but there's nothing documented and I can well understand not wanting to let game developers do anything outside the scope of a single table.

[pjt33]

While I don't know how Just One is currently implemented, I have enough experience of developing for BGA to be able to tell you that this, while a nice idea, isn't possible to do in the BGA framework.

I think it is possible by abusing the mechanism for persisting player preferences, and I'm 99% sure that at least one game already does something very similar. (Possibly The Crew, to avoid repeating missions, although I couldn't swear to it).

[KuWizard]

Here's my proposal, which may sound a bit crazy: the server should look at the last several games of each player, and choose 13 words that none of these players have seen in a while.

For example, if there are 5 players, look at their most recent 6 games. This gives you a set of at most 390 words. There are 160 words remaining, from which to choose the 13 to be used in this game.

@KuWizard is something like this feasible?

I was pretty sure it's impossible however there might be a possibility to do that. Unfortunately I don't really have time to experiment and implement that so if there's any developer who would like to invest their time - I'm ready to share the code and lead to the correct direction