There's a whole family of shedding type or beating games where the players take turns playing to a pile with the goal of getting rid of their cards. There are various constraints on the cards played, requiring you to somehow beat or match the previous card. If you can't play (or don't want to), you have to pick up cards, either from the pile or from a talon. Games of this type include Crazy Eights, Uno, Cheat, Bluffstopp (those last two are different games by the way), Vändtia (Turning Tens), Silltunna (Herring Barrel) and many more.
If you have my type of curiosity, you'll wonder how simple such a game can be and still be nontrivial.
So let's remove the special cards, forget about the different suits, and just have two people play with a deck of cards numbered from 1 to some number N. When it's your turn, you either play a higher card than the previous one, or pick up the whole pile. That's basically it. There is no talon and therefore perfect information. Your opponent has precisely the cards that are not in your hand or in the pile.
In traditional shedding games you normally win as soon as you get rid of your last card, but let's change that slightly in order to continue the game to its logical conclusion: Let's say you win only when your opponent picks up everything so that they have all the cards on their hand. That sort of makes it a misère game, since you win when it's your turn and you can't play.
We'll introduce another twist to the game in a moment, but let's start from just these rules and assume that the cards are somehow dealt randomly. Since this is the simplest shedding game I can think of, it seems fitting to call it Shed. Actually what we're discussing now is what I will eventually call Shed Endgames, the part coming before the endgame having to do with that twist.
But first things first. Here's an example showing that you sometimes want to pick up the pile even if you have a card that's high enough to play.
Suppose N = 5 and you deal the cards 1, 3, 4 to your opponent and 2, 5 to yourself. Your opponent starts with the 3. By the way, a note to the mathematicians out there who may otherwise be confused: You cannot pick up the pile if it's empty. In that case you have to play a card, but you can play any card you like (and if your own hand is empty too, that means you already won!).
Anyway, now it's your turn, and you can play the 5 or pick up the 3. It's not hard to see that you lose if you play, but win if you pick up. If you play the 5, your opponent picks up the 3 and the 5, and you play your last card, the 2. Then your opponent plays the 3, you pick up the 2 and the 3, and your opponent plays the following cards in the order 1, 4, 5 no matter what you do.
If on the other hand you pick up the 3 in the first place, play might go (with a notation I just invented, X meaning pick up):
3 - X, 1 - 2, 4 - 5, X - 3, 4 - X, 1 - 3, 5 - X, 2 - 3, X - 1, 2 - 4, X - 5, and you win.
If you try this game a few times with a small number of cards (say up to 13, one suit of a standard pack), you'll notice that most of the time the game is an easy win for the player who happens to have the better cards. If you have good enough cards, they will almost automatically get better. You will enter a good spiral where your opponent can only choose between picking up your bad cards or giving you their good ones. There are relatively few card distributions that are "balanced" enough for the game to be interesting.
We'll return to this issue in a moment, but before we continue, let's formulate some mathematical questions about this game:
Q1. Are there card distributions where the game is drawn under optimal play? In other words, are there hands where none of the players can force a win? The answer, as revealed by a small computer hack, is yes, but the smallest N for which this is possible is 10. It will happen for instance if you deal 1, 2, 6, 7, 8 to your opponent and 3, 4, 5, 9, 10 to yourself (following the convention that the person who didn't deal plays first).
An example of optimal play from these hands is 1 - 3, 6 - 9, X - 4, 6 - X, 1 - 4, 7 - X, 2 - 4, 8 - X, 3 - 4, 9 - 10, X - 5, X, and we are back to the original position but with the roles of the players reversed: You now have the hand 1, 2, 6, 7, 8, and it's your turn.
Q2. What are the asymptotical probabilities of dealer winning, draw, and first hand winning respectively? I'm assuming here that the cards are distributed with equal probabilities on all the 2 to the power of N different possibilities (By the way, how can you achieve this in practice with an Uno deck? Answer: you riffle-shuffle and then distribute the cards based on their orientation, which you can see even for the symmetric digits by looking at the "shadow"). One hypothesis is that the drawn positions are rare, of asymptotic probability zero. Another is that the advantage of playing first is getting smaller as the number of cards increases, and that asymptotically 50% of the times the dealer wins, and 50% of the times the first hand wins. But I have no idea how to try to prove any of this.
One thing I can prove though is that a player holding the four highest cards (that we may call the ace, king, queen and jack) can force a win. To demonstrate this, it suffices to show that a player holding only the fifth highest card (the ten) and playing first will lose. This can be checked for some reasonable values of N like 10 and 11, and one will see that the method is the same and works for arbitrary N. If you have the four highest cards and any other combination, you can pick up everything until your opponent has only one card left, and in the worst case that's the 10.
This means that the probability of a certain player winning a random deal is at least 1/16. So in any case the probability of a drawn position is at most 7/8, and in particular does not tend to 100%.
On the other hand I cannot even construct an infinite family of drawn positions. There are draws when N = 10 and when N = 12, but for all I know, drawn positions might not exist for any larger N.
Q3. How many moves can it take, at most, to force a win in the N-card game (as a function of N)? What do the hardest hands look like? And is there a simple mathematical solution to the game after all? Again I have no idea.
The twist: an open talon
As I mentioned earlier, there is a tendency for moderately good hands to almost automatically get better, quickly reaching a point where they "play themselves". The game will not be very exciting if nine times out of ten you can tell from a glance at your cards who is winning. Therefore we'd like to modify the game by introducing some other mechanism like a talon (maybe you can draw a card from the talon instead of playing) or some protocol of the type I-split-you-choose.
An idea that comes to mind is to start the game with all cards face up in an open talon. When it's your turn, you can play a card of your choice either from your hand or from the talon. The winning condition is still that your opponent should have all the cards on their own hand. You don't want to play the strong cards from the talon too early, because your opponent will get an advantage by simply picking them up. So it seems the game should now have a natural tendency to lead to the balanced and interesting positions. At the same time it removes the random element, since there is now a natural starting position.
From now on, this is the game that we call Shed, and the final phase when (if) the talon is exhausted is the endgame.
Perhaps surprisingly, Shed seems to be quite sharp and complicated. One might a-priori expect there to be a simple strategy that draws or that wins for a particular player (first or second), or perhaps that the outcome would depend on the parity of the number of cards. But there seems to be no such simple pattern. Shed with an N-card deck is a first-player win for N = 1, 4, 7, 10, 11, 13, 14 and 15, and a second-player win for N = 2, 3, 5, 6, 8, 9 and 12. The number of moves that it takes (counting the moves of the winning player) to force a win for N = 1,...,15 is 1, 2, 6, 8, 14, 16, 20, 30, 36, 45, 49, 58, 74, 68 and 91.
By the way, with a talon there are drawn positions already for N = 6 (though the starting position is not one of them). The second player wins under optimal play, but if the game starts 1 - 4 (correct), X - 2?, we reach a drawn position (the second player should have played the 3 instead in the second move). With optimal play from this point on, the game continues 5 - X, 1 - 6, X - 2, 4 - X, 1 - 4, X - 2, 4 - X, and so on. All those moves are unique, anything else loses, and the 3 stays in the talon forever.
There are some patterns in the data: It seems at first that when N is divisible by 3, the game is a second-player win. Moreover it appears that the second player should pick up the first card if the first player starts with a card in the top two thirds, but play something higher if the first card is in the lower third. This is true for N = 3, 6, 9 and 12. But the pattern is broken for N = 15, when the first player wins by starting with the 5 and then picking up even if the second player just plays the 6.
When N = 3k+1, the game seems to be a first-player win with the unique winning first move of playing the card k+1 from the talon (so that there remain exactly twice as many higher cards as lower cards). But it's hard to see a clear pattern in the following strategy, so maybe this too is just a red herring.
An intriguing observation is that there always seems to be a well-defined threshold at around N/3 with at most one card that wins as a first move for the first player, and all cards above the threshold losing because the second player picks them up. It seems clear that if the second player wins by picking up a certain card in the first move, they would also have won by picking up any higher card. It also seems very reasonable that the first player should never start with a card on the upper half, say, because the second player immediately gets an advantage by picking it up. But I don't see a reason why the first player could never win by playing a small card like the 1.
Some more questions: Are there infinitely many N for which Shed is a first-player win, and infinitely many for which it's a second-player win? Is there some N for which it's a draw? Is there a simple pattern to this, say periodic, after all? And is there some constant c between 0 and 1 such that the "threshold" for picking up in the first move is asymptotically at c times N? Is c = 1/3?
Multi-suit Shed, strict and relaxed
Can we play Shed with an ordinary deck with several different suits? Let's say that, just as in traditional card games, a card only counts as higher than another if it's higher in rank and in the same suit. So if you play first to the pile you can play any card you like, but all the following cards in that pile will have to be in the same suit as the first one.
Again the game seems to be complicated, and sometimes a first-player win, sometimes a second-player win, sometimes drawn. It seems to become drawish if there are many suits and few cards in each suit, and otherwise most often a first-player win. For instance 4-3-3-2 seems easy to draw, but 5-3-2-2 is a first-player win in 99 moves.
The game also seems to make sense with a joker or excuse which is lower than all other cards and may only be played first in a pile. For instance, 5-3-3 with a low joker is a tricky second-player win, but would be drawn without the joker. If on the other hand the joker is regarded as higher than the other cards (a wild-card that can be played anytime forcing the opponent to pick up the pile), the game seems to become completely drawish.
We can even play under the rule that one of the suits, say spades, is lower than all the others, so that a spade can be beaten by a higher spade or by a card of any other suit, while cards other than spades can only be beaten by higher cards in their own suit. For instance, the game 5-3-1-(3), where the ordinary suits have 5, 3, and 1 card respectively and the spade suit has 3 cards, is drawn under optimal play. You can draw by starting with the spade 1 or spade 3 (or with the smallest card in the suit of length 5), but if you start with the spade 2, your opponent has a forced win in 106 moves.
In principle, Shed can be played with an arbitrary partial order imposed on the cards. The rule that each card must beat the previous one might be called the Strict rule. But there is also another natural generalization of Shed to partially ordered decks: The rule can just as well be that a card can be played to the pile as long as it's not lower than any card already in the pile. This might be called the Relaxed rule. In Relaxed Shed, if you play the 9 of hearts, I can still play the 4 of clubs. You can then play any spade or diamond, and any heart higher than the 9 or club higher than the 4. Under the relaxed rule it seems that we must have a high wild-card or a trump-suit for the game to make sense, because unless there's a card that's higher than all others, the game is normally an easy draw.
Relaxed Shed might be played with cards from a tarot deck. In a tarot deck there is a designated trump suit of cards numbered from 1 to 21 (that's what I used in the second picture above) as well as the ordinary four suits.
Yet an example: In Relaxed Shed with suits of 4-3-2 and a trump suit of 3, first-hand has a forced win in 66 moves. The unique winning first move is to play the 3 of the suit of 4, and in the line I looked at, the first 13 moves, and 45 out of the first 50, where "unique" in the sense that any other move would have lost. Amazing stuff.
Why should we care?
I guess for now, Shed will have to be just another artificial card game that you probably won't play unless you just want to see how weirdly difficult a game can be with just ten or so cards face up. But I might explain in some later blog post that it has certain features that makes it interesting to experiment with. In particular it seems to be a complex and razor sharp game that has "board-feel" and scales easily. There are difficult positions, but also easy ones. The level of difficulty might be varied in a rather controlled way. Maybe someone can see where this is going.
No comments:
Post a Comment