Friday, January 29, 2010

Sometimes, a pendant vertex is just a pendant vertex.

I had a dream last night, in which I saw the proof of a mathematical theorem. It involved copies of K5, with pendant vertices arranged in such a way that all of the graphs linked perfectly together into a larger complete graph. It was a simple, beautiful proof, and I can still see the end of it now, hours later. A few of the details are fuzzy, but I'm sure I could work them out. There's only one problem.

I have absolutely no idea what it was I was proving.

Saturday, January 16, 2010

You Know What I Mean

The Naboo half of Phantom Menace, stretched out to two and a half hours.
Total Recall, but without the cool perception-vs.-reality philosophy.
An evening of watching someone else play Halo and they won't let you play and they watch all the cut scenes.
An Inconvenient (and Ham-Handed) Truth.
Like Star Trek IV, but when they get back to the present, Kirk helps the whale-aliens blow up Starfleet Headquarters.
Courtesy of the w: A live-action remake of Ferngully: The Last Rainforest.
A late addition: Pocahontas in space.

Probabilistic Filler

Some important probabilities related to Scat:

As I mentioned last time, your chance of getting scat (no 1's) on your first roll is 3125/7776, or (5/6)5, which is just over 40% of the time. The probability, then, of having scat as your final hand is (5/6)15, or 6.5%, which works out to about twice every 31 turns.

The probability of rolling five 1's within three rolls is, in theory, about 1.3% (the exact probability simplifies to (91/216)5, which I think is kind of neat—not because that ratio has any significance, but because the otherwise-complicated calculation ends up simplifying so neatly), or about once every 75 turns. In practice, though, this probability is smaller, because of situations which dictate abandoning the all-1's strategy.

If there are k people still left to roll, then, the chance that at least one person gets scat is 1 - (1 - (5/6)15)k; and the maximum probability that at least one person rolls all 1's is 1 - (1 - (91/216)5)k. If, for example, four players were still to roll after you, there would be a 23.5% chance that at least one would roll scat (thus saving you from elimination, if you had a fairly low roll), and as much as a 5% chance that someone would end the game prematurely by rolling five 1's.

The main factor we must consider when deciding which dice to re-roll is the expectation of each decision; this expectation is specifically based on the probability of winning or losing the game after this decision. The probabilities above are part of calculating the expectation - you can make riskier moves (i.e., keeping only your 1's) when there are more players still to roll, because there is a higher chance that someone after you will get a bad hand, and because there is a higher chance that if you don't win right now, someone else will do so before you get another roll. I'll get more into the decision-making process next time.

Tuesday, January 12, 2010

Roll the dice, don't think twice

I'm a little behind on everything these days, and Scat strategy is one of them. Go back a month to review the rules.

When it is your turn, you have two strategies available:

  1. Attempt to roll five 1's, thus winning the game.
  2. Obtain a hand which is not likely to be the low hand for the round, thus avoiding elimination.

After your first roll, you have two opportunities to decide which dice to keep, and which dice to re-roll. This decision is a choice among three options:

  1. Keep only the 1's, and re-roll all of the other dice.
  2. Keep the 1's and your highest-ranking die or dice.
  3. Keep the best hand you can make with the current dice.

For example, if your roll is 1-3-3-4-6, you can keep only the 1 (option 1), the 1 and the 6 (option 2), or the 1 and both 3's (option 3). There is no reason, ever, to keep the 4, or to not keep the 1.

In many cases, the decision is not even as complicated as the previous example; if the roll had been 1-3-4-6-6, or 1-3-4-5-6, options 2 and 3 would be the same. In fact, a little over 40% of the time (3126/7776, to be exact), there is only no decision to make - either you roll no 1's (3125 times), and must re-roll all five dice, or you roll five 1's (1 time), and win the game.

For those times when there is a decision to make, several additional factors should be considered:

  • The current low hand. The low hand in each round is eliminated, so you will often (not always) choose the option with the best chance to beat the current low. More importantly, you will want to avoid options that have a very low probability of beating the low hand (keeping three 2's when the current low hand is four 4's, for example, is usually a bad plan).
  • The number of players still to roll. Remember, you only need to beat one player each round, so if there are several players still to roll, you can choose a riskier option, based on the chance that not all of those players will beat you.
  • The number of players still in the game. Without taking strategy into account, if there are n players at the beginning of the next round, your chance of winning by avoiding elimination this round is roughly 1/n.

I'll start getting into the probabilities of the game next time (and I hope that next time comes more quickly than this time did). However, I expect we'll find that, early in the game, the expectation gained by winning the game immediately will outweigh the risks of being eliminated early. In other words, rolling five 1's is the primary strategy (in my limited experience, most players make avoiding the low hand primary, and rarely go for the outright win unless they have already beaten the current low). This means that option 1 will frequently be the correct decision, because the other two options necessarily abandon the primary strategy. This will be particularly true after the first roll, because committing to any die other than a 1 restricts the ways for a hand to improve. I also expect that avoiding the low hand will become the primary strategy later in the game, when simply staying alive represents a greater increase in the probability of winning—my guess is that this happens when there are three players remaining, but we'll see.

Finally, and perhaps unfortunately, I expect we'll find that, while skillful play does increase one's expectation of winning, the overall effect won't be that great against people who do not play as well. In other words, you'll be able to win an n-player game against "normal" players more often than once every n games, but you'll likely need to play a few hundred games to see that result. Also, since each player's hand is independent of the other hands, we may find that there is a single pure strategy that maximizes one's probability of winning. In this case, the result of all players adopting that strategy makes the probability of winning an n-player game exactly 1/n. This is all conjecture for another time, though. Stay tuned.