Steve Brown’s Game: Round 1(2)

Continuing our game, here is the current position:

  • Move: gi → 5s
  • Move: hd → 8h

The next move sequence is a good illustration of Steve’s skill. The obvious option is “hf” since we are one good card away from claiming our first empty column. However, the downside of that move is polluting column 6. We would no longer able to perform the move “fa”. Assuming we connect the 8-7 of Hearts, this would also create a long-term problem of two Sevens in column 6 but no Sixes. This means if column 6 later becomes a junk pile, then we might have to start worrying about a shortage of Sevens. Therefore we might consider “fa,ha” instead. But this would be rather embarrassing if we turned a Nine.

Steve finds a good solution: noting that both Spade Nines are visible, he simply breaks the 9-8 of Spades in column 4 to form the “other” 9-8 of Spades in column 6. Now we get to have our anti-smoking song and sing it too since we will turn the last card in column 8 before committing ourselves to the move “fa”. Hence our best-so-far move is now “dh, df, hd”.

But Steve still isn’t done yet. He observes that he can shift some junk from column 4 to column 1. Since column 1 contains a King, we’re probably not turning over cards there any time soon. But there’s a chance we might get to shift the Q-Q-J-0 in column 4 if things go well. Admittedly this is a long shot, but no harm trying. In any case, Steve arrives at the following move sequence:

  • Move: dh, df, da, ha → Kh

In my opinion, Steve has done everything right here – except the final card in column 8 nullified all his efforts to obtain an empty column ☹ Steve observes that the King is not completely useless. At least there is an option of splitting the Queens in column 3.

Again, now is a good time to take stock. How would you assess our chances? More specifically, let’s pretend we are playing a mash-up of Spider Solitaire, Backgammon and Among Us and consider the following questions:

  • Would you rather be a crewmate or an impostor?
  • Should you double?
  • If you double then should your opponent(s) accept or refuse?

As usual, I have added a spoiler-blocker in case you wish to form your own conclusions before reading on.

This is the usual spoiler blocker for my blog.

Here is my analysis:

We have two turnovers, although one of them requires exposing an Ace and polluting column 10, our best chance of obtaining an empty column. We have fair chances of improving on our minimum guaranteed turnovers (I will leave computing the outs as an exercise for the reader).

It’s a pity we can’t quite perform the supermove “ah”. Despite Steve’s skilful play, there is a fundamental limit to how much awesomeness you can achieve when you don’t have an empty column! However, that is not a serious loss anyway. We are a long way from completing the Heart suit. We would almost certainly need an empty column before Hearts become a realistic possibility, but once we get an empty column there is a fair chance the K-Q-J-0 of Hearts will sort itself out anyway without us really trying or even noticing.

Although Steve has recovered somewhat after a poor start, I would rather be an Impostor than a Crewmate. But the difference is small and much will depend on the luck of the cards. I certainly wouldn’t be doubling the stakes any time soon (obviously I would expect an opponent to take a cube)

Yet Another Digression

When I first started this blog, I was under the impression that Spider Monkeys are intelligent creatures, able to recognise legal moves in a game of Spider Solitaire and play at lightning-fast speed – albeit with less than optimal strategy. But Wikipedia says I wasn’t even close. In fact, I wasn’t even aware that Spider Monkeys are a thing, and I only found out by complete accident when trying to lit-review a subject I know very little about, but my supervisor wants me to look at.

This cartoon is based on a well-known Russian chess joke.

Toward Agent-Based Models for Investment is the title of a paper by J. Doyne Farmer in the 2001 AIMR Conference proceedings. The important bit appears near the end of page 2. It says:

“The same principles apply in blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah spider monkeys. Blah blah blah monkeys blah blah blah blah blah”

At least I have learnt that spider monkeys are New World monkeys belonging to the genus Ateles, part of the subfamily Atelinae, family Atelidae. Reading the rest of the Wikipedia article and summarising the important bits in a paragraph or two is left as an exercise for the reader.

Anyways, that’s enough digressing for now. Back to the game …

Steve Brown’s Game: Round 1(1)

Here is the start position, which also appears in my blog previous post.

Bart has kindly requested I redact the value of hidden cards to make it “more realistic” from the viewpoint of the player. Here is the game state after Steve reluctantly deals the first row of cards.

This is a dire state of affairs, much like our previous game involving a doubling cube and a similarly depressing round 1. I think an impostor Among-Us blob would be justified in sending a doubling cube over (assuming of course it is possible to double without revealing whose side you’re on!). We have only two guaranteed turnovers and most columns require more than one good card to get a turnover.

  • Move: gd,hd,ha → Jd

This is an interesting decision. The obvious option seems to be jg,jg which builds in-suit in Hearts and avoids exposing an Ace in Column 7. Moreover column 10 is one step closer to getting our first empty column. But Steve gives a valid reason for his play: column 8 is more difficult to turnover because we need a Jack and a King, whereas column 10 only requires a Jack because once we shift the Ten of Hearts, there is always the option of immediately shifting the Nine of Spades. Getting the more difficult task out of the way is a useful principle for expert play, and Steve shows good insight here.

However, if this were Among Us then I would vote “jg,jg” and let the whole world know that Steve is sus. Apart from the advantages listed, it also keeps some degree of flexibility. For instance, we keep the option of ca or da. At least Steve exposes a good card.

  • Move: da, hd → 7h
  • Move: ad, ja, jd → 8s
  • Move: jd → 2c

Although the next move is obvious, I wish to take stock and assess our chances. Our situation has improved quite a bit – we still have two turnovers and are getting closer to getting an empty column. We also have a small amount of flexibility (e.g. moves like fa,eh) and given our poor start we might need every advantage we can get. It’s a pity the 5-4-3 in Column 1 is buried under a rot13(xvat) but we can’t do much about that.

As an extra bonus, I get a chance to confirm that both IM Bug and IM Bart are both happy with the new format (gray question marks) before pushing forward.

NOTE: for inexperienced players, it is useful to observe how Steve is able to increase in-suit builds with “supermoves” despite the lack of an empty column.

I think it’s good practice to assess our game state regularly, even if the next move is obvious since it will improve your feel of how well or badly a game is going. If you’re willing to accept a Backgammon doubling cube centred at ‘2’ then your position isn’t that bad.

Well, that’s all folks and here’s looking forward to More Of The Same, coming soon to a place near u if you excuse the numerous terrible clichés!

Steve Brown’s Game: Round 0(1)

Here is the start position of Steve Brown’s game, which also appears in the previous post of this blog.

The observant reader has no doubt tried to assess the opening game state and concluded it’s worse than average. We have a run of length four (0987, mixed suits) and not much else. That’s three turnovers, which is less than average (just below 4). Given we also have two Aces showing, this definitely qualifies as a “bad three”.

With limited options available, the opening moves require little explanation:

Move: ea → Kc

Move: be → Ah

Move: af → 5s

Move: jf → 9s

The first interesting moment occurs after the fourth move. Steve explains he has a choice between “jf” (the actual play) and “da”. He chose jf because neither move was suited and the 7c is higher in rank than the 4d. Although Steve found the correct play, I don’t buy this explanation. The correct reason is that column 6 is already impure and there is no danger of losing a turnover if the next card is a Jack. Whereas “da” costs a turnover if the next card is a Six. Assuming no in-suit builds are possible, the higher-rank logic only applies when you have a full sequence like 9-8-7-6-5-4-3 rather than 9-8-K-K-K-4-3.

In general, when reading the entire book, I found that Steve sometimes struggles to articulate his thoughts properly and I’ve seen a number of strange typos such as “loses” instead of “losses”. Still, let us withhold judgment on Steve’s overall ability until the end of the game.

Move da → 3d

Move da → Qs

This completes a disappointing round 0. Steve mentions that on average he will expect to turnover 12 cards in round 0, which is exactly double the six turnovers he has in this hand. The sample size is small (306 games) but I can’t accuse Steve of not keeping careful records.

From my experience, the real game starts in round 1, not round 0. With 50 cards remaining in the stock, it’s almost impossible for a half-decent player to make a fonumental muck-up and Steve is well aware there is plenty of opportunity for a reversal of fortunes (in either direction). This hand is no exception if you pardon the terrible cliché. In Backgammon/Among Us terms, round 0 is equivalent to memorising the correct plays for opening rolls and replies and it’s extremely rare for the luck-o-meter(TM) to surpass the “refuse-doubling-cube” threshold from the viewpoint of a Crewmate or Impostor.

One thing I should mention: the stock is read from left-to-right. That means the next 10 cards will contain two more Queens (as if we don’t already have enough problems in this stupid world).

Spider GM is back!

It’s been a while since I’ve posted in my Spider blog. I wrote that something has turned up at work a while ago. But it’s been fixed. More importantly, I didn’t have to “put in a special effort” to get rot13(fuvg) done (e.g. threaten to embarrass somebody if nothing improved).

The something I was referring to was the Gawler Line. Essentially the trains are running again and I can travel to work without worrying about less-than-stellar traffic or risk of car-pooling accidents etc.

Going back to the Spider Solitaire, the next exercise I wish to discuss is a walkthrough of a game by Steve N Brown – the author of Spider Solitaire Winning Strategies. This book has fourteen chapters with the final chapter being a play-through of a sample hand. Presumably Steve chose this hand as an example of overcoming a difficult start. He could also have chosen an example of safeguarding a strong start – also a useful skill for the expert – but that would be less appealing to the general audience. In any case, the reader will have a “spoiler” in the sense that he already knows that Steve won this particular hand.

In the next few posts, I intend to critique the way he played from beginning to end. This should give some insight as to how an expert player (other than Yours Truly) goes about playing four-suits sans rot13(haqb).

With decent luck I should be able to manage one post per two or three days. For further good news, I also have an opportunity to show off my mad coding skills: the image above shows how one can input a position to Ninja Monkey’s improved algorithm with a GUI that looks half decent.

Something has turned up at work

Uh oh.

Something has turned up at work, and I might not be able to update this blog as much as I would like to.

Of course if IM Bart or IM Bug can convince other strong players to participate in another game then I might reconsider 🙂

Thank you for your patience and understanding if you pardon the terrible cliche …

Mathematics of Doubling in Match-Play

In this post I wish to discuss the mathematics of doubling in some detail.

Let us assume Hero and Villain are playing a “match-to-three”. That is, first player to win three VP is the overall match winner. Each individual game is worth 1 VP. The actual game being played is irrelevant: it could be Chess, Agricola, Snakes and Ladders, the royal game (with Hero moving the cards and Villain trash-talking at every sub-optimal play), or a well-known poker variant where both players start with three items of clothing. To make things interesting, assume the winning probability of an individual game is slightly less than 50%. To be specific, I will set the win rate to 40%. What are the chances of Hero winning the overall match?

This kind of question is most easily solved with dynamic programming. The boundary condition says that if someone already has three wins then the overall winning chances is either 0% or 100%. Next, we can compute the winning chances when the score is 2-2. We can then work our way backwards, eventually arriving at 31.7% winning chances for the Hero at 0-0.

You will notice that if the match score is X-X then the Villain prefers smaller numbers of X. Intuitively, smaller values of X means that it is less likely that Hero will find enough “random noise” to overcome Villain’s advantage in the long run. The following diagram summarises the probability of Hero winning the match at every possible match-score:

I should mention that Bart has already done his homework, and he knows how to compute the probabilities corresponding to each match score. If the winning chances of an individual game are 0.25 then he correctly computes the following:

  • 0.049 chance of winning 5-point match, no doubling
  • 0.104 chance of winning 3-point match (equivalent to 5-point match with 2VP per game)

I will leave this as an exercise for the reader.

Now let us give Hero the following handicap: Before each game, Hero can demand the game be played for 1 VP or 2 VP. Moreover, there is no bonus for winning the match with 4 VP instead of 3 VP.

This means, for instance, if Villain has 2 points then Hero will always play for 2 VP. Again, we can use dynamic programming to compute the winning chances. If you use Excel to perform the dynamic programming then you will need the function max(FOO,BAR) somewhere in your calculations. You will notice several things:

  • The boundary conditions now include either player having 3 or 4 VP.
  • The table only shows winning percentages, but not whether Hero should play for 1 VP or 2 VP.
  • The numbers look weird: The winning chances on the main digonal is no longer strictly increasing and the winning chances for 1-2 is the same as 1-1.

The latter is easily explained. Since Hero can choose to play for 2 VP, Villain gets no advantage from being 1-2 instead of 2-2. Slightly more interesting is a match-score of 1-1. If Hero plays for 2 VP, then the next game decides the match. If Hero plays for 1 VP then the worst case scenario is the match score becomes 1-2, in which case Hero can play for 2 VP and the next game decides the match. Therefore, it must be correct to play for 1 VP. It turns out Hero is close to breaking even thanks to his handicap.

It is not hard to get an Excel spreadsheet to crunch the numbers for different parameter values. We can, for instance, figure out what happens in a match to 13 points with Hero’s winning chances down to 30% for an individual game.

When we talk about longer matches, it is generally more convenient to think in terms of number of VP remaining instead of number of VP already scored. For instance, 19-18 in a 21-point match is equivalent to 5-4 in a 7-point match and it makes sense to describe both of them as “2-away 3-away”.

Redoubles

Now what happens if either side has the right to double the stakes, but there are no redoubles? This is a trivial case: it makes no sense to refuse a double. If one side declines to double, he can’t prevent the opponent from doing the same. Therefore, it must be correct for either side to double.

But what if redoubles were allowed? This means e.g. if Hero proposes to play for 2 VP then Villain can propose to play for 4 VP before the game starts. Then things may get weird. I will leave the analysis as an exercise for the reader.

Doubling During the Middle of a Game

Hitherto, we have assumed that doubling could only occur before the start of every game. In this case, each individual game can be thought of as a black box – the only relevant parameter is the winning chances of a single game. Moreover, it never makes sense to pass a double since the loser gets the same “pre-starting position” and the winner gets a free point.

But if doubling were allowed during a game then the “structure” of the game tree becomes important. For instance, two different games could have the same winning chances of 25% but a different structure. If Hero doubles judiciously then he can leverage the structure to improve his overall chances of winning the match (of course he can’t leverage the structure to improve his chances of winning a particular game – if Villain were hell-bent on winning the next game at all costs, then he would never pass a double).

To illustrate the concept of structure, assume we are interested in maximising the expected number of VP for a single game instead of a “match-to-N-points”. Consider the following “random-walk-game”: A happy star randomly moves to one of the twelve coloured leaf nodes, with each node occurring with probability 1/12. If the colour is Green (Red) then Hero wins (loses) one VP. If no doubling cube is used then basic math says the expected gain per game is 1/3 = 0.333 VP for both structures depicted in the left and right halves of the diagram below.

Now suppose that Hero has the right to double before the game and Villain can double when the happy star reaches one of the three “intermediate” nodes. On the left diagram, assume that Hero doubles (since there are more greens than reds). Villain should accept and then Hero can expect to win 0.667 VP. But on the right diagram Hero is only winning 0.5 VP if Villain uses correct doubling strategy. This is left as an exercise for the reader.

Therefore, structure is important: without the cube Hero wins the same expected VP in both games, but with the cube Hero prefers the first game. Another lesson is that ownership of the cube (i.e. exclusive right to make the next double) is worth some equity. As a general rule, if all other things are equal then whoever owns the cube prefers game states that require many moves before one side has a decisive advantage.

Hopefully this example should make it clear why a simple mathematical analysis breaks down when we consider real games with doubling decisions occurring during the game. Similar considerations obviously apply when computing optimal match strategy rather than expected VP in a single game.

Summary

In this post I show that optimal use of the doubling cube is a lot more complex than “always double (take) if our winning chances are at least 80% (20%)”. There are three caveats:

  • The elephant in the room is nobody knows how to reliable estimate the winning chances of a specific game state. Not even Spider GM can do this, unless there are very few cards unseen
  • 80% and 20% turn out to be optimal parameters – only if we assume the winning chances change continuously rather than suddenly change (think Brownian motion instead of quantum leaps!).
  • The parameters 80% and 20% also assume we are playing for money (e.g. $1 = 1 VP, aim to maximise expected winnings). It doesn’t work in match-to-N-points, especially when we reach the pointy end with both sides close to victory.

If we can solve the elephant in the room, then this doubling strategy should be a good starting point – coupled with a few “common-sense tweaks” near the end of the match. For instance, you never double when you are 1 point away from winning the match etc. But one could argue it is precisely the elephant in the room that makes Spider Solitaire such a great game 😊

Fun Fact

If Hero has the exclusive right to make the next double then it is possible to construct a pathological game tree where one can change some green nodes to red while also changing Hero’s correct doubling decision from No-Double to Double. A well-known Backgammon example is the Jacoby Paradox.

April Fool’s Joke Explained

IM Bart has reminded me via email I haven’t yet explained the joke on 1st of April.

It turns out if you click the last link with words “please click this link” you do not get the video of Never Gonna Give You Up. Instead you reach my Spider Solitaire paper in the UNSW high school Parabola (which doesn’t involve any Rick-Roll at all).

Oh of course

Villain’s Double in Round 1

In this post I will discuss why Villain doubled after dealing the cards in round 1.

The position in round 1 is this:

There is only one way to get two turnovers. The best play is “fg,bf,bc,jc,jb” giving the following position (I used MS Paintbrush instead of explicitly undoing moves in the Spider Solitaire program).

Now let us compute the chances of improving our minimum guaranteed turnovers after turning the card in Column 10. For simplicity assume each of the 13 ranks are equally likely. Let us assume each rank is worth one happy star if it yields a turnover, 0.5 happy stars if you need the correct suit to get the extra turnover and 0 happy stars if no turnovers regardless of suit. Multiple turnovers are possible. For instance, 1.5 happy stars means you always get one extra turnover, with a chance of a second turnover if you were allowed to call the suit, etc.

Note that if the next card in Column 10 were an Ace or Four then we don’t get an extra turnover since we counterfeited the turnover in column 9. It turns out the only good ranks are Three, Nine, Jack and Queen. That’s only 4 happy stars out of a possible 13. Actually, we can increase that to 4 and a half, since a Jack of Spades gives us a double turnover in columns 8 and 10 to go with our turnover in column 9. Given that we only start with two turnovers, it’s about an even chance we get bad cards in both column 9 and column 10.

The other piece of bad news is there are no “atomic columns”. Note that we were forced to pollute column 6 to guarantee our two turnovers in the first place. If we assign the capital letters A and B to columns 9 and 10 respectively, then it’s hard to find decent plans corresponding to the rest of the alphabet. This also means that we need to turnover every card in column 9 or 10, not just the first to get a fighting chance.

In a nutshell, we have difficult short-term problems and long-term problems to deal with. This is why Villain doubled. If I were in Hero’s shoes, I would have passed the double.

Match Summary (Alternative Version)

Once upon a time, there lived a Beaver in the Animal Kingdom.

The Beaver had just beat the highest difficulty level of Spider Solitaire – four suits sans undo. He felt he had played well after a difficult start, but it was hard to judge his overall ability at the game. After all, one wins and zero losses does not a large sample size make. And the fact none of his friends displayed any aptitude for the Royal Game certainly didn’t help. So, the Beaver decided to have a chat with his best friend, the Raccoon, who was known for his extensive knowledge of all things mathematics.

“It’s hard to judge your playing strength after one game,” said the Raccoon. “You need to play a large number of games to prove your victory wasn’t just beginner’s luck.”

“Suppose I played 129 games in a row,” replied the Beaver, plucking a three-digit number at random. “Then we can tally up my wins and losses and then we have a much better understanding of where I’m at.”

“Agreed,” replied the Raccoon. “Right now, the only thing we can agree on is you can play a hell of a lot better than I can.”

The Beaver chuckles, and he soon notices Captain Obvious is eager to join in the conversation.

“The only problem is it will take a long time to churn through 129 games,” says Captain Obvious. “Spider GM probably doesn’t wanna hear this but we all have better things to do in our lives than playing the Royal Game all day.”

“True,” says Raccoon. “Very True.”

Hang on, thinks the Raccoon. 129 happens to be a power of two plus one. This has me thinking – what if we can involve powers of two somehow? Let us say some games can be worth more than others. Suppose that each individual game was worth N victory points, where N was a power of two. A series of 129 games is equivalent to “First to 65 wins”. This should speed things up considerably. But Captain Obvious will gleefully point out Spider Solitaire is a game for one player, not two. Hang on (***thinks for a while***) I think I might have something.

“Okay I have an idea,” says Raccoon.

“What is it?” asks the Beaver and Captain Obvious simultaneously.

“Let us pretend Beaver is the protagonist,” says Raccoon. “Only Beaver can move any cards. I am the Antagonist and I am willing Beaver to lose.”

Using a stick, the Raccoon sketches a hypothetical cube with all powers of 2 between 1 and 32.

“Initially, each game is worth 1 Victory Point. If Beaver thinks he has a good position, then he can double the stakes. I must concede 1 VP or agree to play on for 2 VP. Similarly, if I think Beaver has a poor position then I can double the stakes and Beaver has the same choice of refusing or accepting.”

“Sounds interesting,” says Beaver. “But if my game state were really bad, can’t you just double the stakes after every move? That wouldn’t be very interesting”

“That is correct,” replies the Raccoon. “Therefore, I propose another rule: if either side doubles the stakes and the opponent accepts then the opponent has the exclusive right to make the next double.”

“So that means, if I get a poor position, you double, I accept, then I turn the game around, then I can redouble and play for four VP?”

“Quite correct,” replies the Raccoon.

“Wait a minute,” says Captain Obvious. “If first to 65 wins then is it possible to get more than 65 if the doubling cube is more than 1?”

“Yes,” replies the Raccoon. “It doesn’t matter if you’re above 65 or exactly equal to 65. And before you ask, it’s perfectly legit for someone to double near the end of the match regardless of the game state because the math says he has nothing to lose.”

“Just to touch base,” says the rot13(fzneg nff) as he gleefully pokes the rot13(nff) of Captain Obvious, “does that mean only Beaver can moves cards, but both Beaver and Raccoon participate in cube-decisions.”

“That’s correct,” says Raccoon. “Even though I don’t move any cards, I can still participate in evaluating the winning chances of a given game-state. Win-win for everybody since I get a chance to improve my game as well.

This idea proved quite successful, and soon Raccoon was discussing the implications of the doubling cube with his friends, many of whom were also avid mathematicians. They had independently discovered some interesting theory and concepts such as market losers, the Crawford Rule, Jacoby Paradox, Woolsey’s Law for Doubling and so on. Not surprisingly, much of this theory is well-known to expert Backgammon players today.

For the record, the Beaver managed to win 66-42, although that may have been a function of Raccoon’s limited understanding of the Royal Game (and hence sub-optimal decisions with the cube). At least it was a lot better than the 8-65 drubbing that Raccoon received when they reversed the roles of Protagonist/Antagonist. Initially the Raccoon thought the best equaliser for a mediocre player is to play each game at high stakes and hope to get lucky, even if the game state rot13(fhpxrq) since a long match would allow the antagonist to “grind” his way to victory. But the Beaver thought it was better to be aggressive with even marginal advantages – for instance if an intermediate player starts with six guaranteed turnovers or a “good five” then he should immediately double. Then at least he is fighting from a position of strength. If the protagonist thought his chances without a doubling cube were 50-50 then he is probably better off grinding and should hope to win on skill, not luck.

And the less said about Ninja Monkey’s first Match-to-65 and his infamous random move algorithm the better 😊

The End