A game theoretical question...

[KnifeMissile]

I haven't seen a good math discussion in here for a while so I thought I'd try entertaining you all with this little tid bit.

My question involves a card game. There are nine cards, face up, valued 1 through 9. There are two players and they alternate picking cards from this list. Their goal is to have exactly three cards (out of the cards that they have chosen, of which there may be more than three) that sum to 15. The first one to do so, wins.

So, it is a finite, perfect knowledge game.

The question is this. Does there exist a winning strategy for this game? In other words (in case you're unfamiliar with game theoretical terms), can either player guarantee that they will win, regardless of what the other player does?
What do you think? Why?

[asaris]

If you are going first, I think this will work:

You take 9. So your friend has to take 6 (since otherwise you can get 15 next turn). Then take 8, your friend takes 7. Then take 2. You can then get 15 on your next turn by taking either 4 or 5, so your friend can't stop you from doing it.

[hrdwareguy]

Originally posted by asaris
If you are going first, I think this will work:

You take 9. So your friend has to take 6 (since otherwise you can get 15 next turn). Then take 8, your friend takes 7. Then take 2. You can then get 15 on your next turn by taking either 4 or 5, so your friend can't stop you from doing it.

The flaw exists because you can't make 15 on your second turn.

You must have 3 cards that add to 15. Therefore, on the opponents first turn, you are not forcing them to take any particular card.

[KnifeMissile]

Thank you, hrdwareguy! I was about to post a clarification of the game but, apparently, I did mention that aspect of it.

Well, I'm glad to see that people are actually thinking about this problem! Would anyone like a hint?

[synic213]

It seems to me that the game is a bit like tic-tac-toe. If it is played correctly by both sides, no one will ever win.

The only winning combo I;ve discovered in which the opponent could not prevent a win went something like this:

Turn 1) Player 1 picks "1"
Turn 2) Player 2 picks "2"
Turn 3) Player 1 picks "3"
Turn 4) Player 2 picks "4"
Turn 5) Player 1 picks "5"
Turn 6) Player 2 picks "7" (first forced move to counter player 1)
Turn 7) Player 1 picks "9" (and wins with "9" "5" "1" combo)

This sequence will be a win for player 1 everytime as long as the first 5 picks are the same (order does not matter). This seems highly unlikely, especially against a real person. The counter to this strategy seems simple enough -> Player 2 picks a "high value" card on turn 2.

I'm curious to see if there actually is a winning strategy.

[yatzr]

okay. so i messed around with it for awhile. The first three cards should be the only ones "picked"...the rest should be forced. I found that if you pick 6 as the first card, unless your opponent picks 5, you can gaurantee a win. Even if they pick 5 you can still win sometimes but at least draw. 6 was the only one that had this much success that I found.

Here's my rounds

me ...... them
6 ...... 1
5 ...... 4
7 ...... 3 or 2
win!

6 ...... 2
4 ...... 5
8 ...... 3 or 1
win!

6 ...... 3
2 ...... 7
5 ...... 8 or 4
win!

6 ...... 4
2 ...... 7
8 ...... 1 or 5
win!

6 ...... 5 (the only next card that you can MAYBE gaurantee a win is 9, but this lets your oppenent "choose" their next card since they won't have to block you)
9 ...... 1
2 ...... 4 or 7
win!

6 ...... 5
9 ...... 2 (cannot gaurantee win here)

6 ...... 5
9 ...... 3 (cannot gaurantee win here)

6 ...... 5
9 ...... 4 (cannot gaurantee win here and can easily lose)

6 ...... 5
9 ...... 7
3 (you're just plain screwed on this one)

6 ...... 5
9 ...... 8
2 ...... 4 or 7
win!

(so unless your opponent chooses 1 or 8 after your 9, you can't garauntee victory.....but if you could have 4 cards add to 15 you could do it anyway
6 ...... 5
1 ...... 8
2 ...... 7
3 ...... 4 or 9
win!)

6 ...... 7
5 ...... 4
1 ...... 8 or 9
win!

6 ...... 8
4 ...... 5
2 ...... 7 or 9
win!

6 ...... 9
2 ...... 7
5 ...... 4 or 8
win!

Pretty sure I doubled checked all of those to make sure they're legit. Please correct me if any are wrong though.

Some winning strategies I found: make sure not to get numbers that screw you over (6 and 3, 7 and 4, 7 and 1, 3 and 9) because the one number you need is a number you already have. If your oppenent picks one of these numbers as their first, try to force them to pick the other one and you won't have to block him.

Never expect to use your first two numbers in your 3 number combo since your opponent will block it right away. You want a two way street between your 1st and 3rd and 2nd and 3rd to gaurantee the win. Also, alternate between high and low, if you pick too many highs, you force your opponent low which then forces you high and vice versa.

So yeah, it is like tic tac toe where you can garauntee victory except for that ONE tiny defensive move. If 4 cards counted though, you could always garauntee victory since there is only that one instance where your opponent could even get a 4th card.

noted: I checked for a few other numbers as first picks but didn't get the success I got with 6, but if anybody wants to try it, go ahead (I think i tried 1,2,3,4, and 5 and maybe 7 I don't remember I did it all yesterday).

[rsl12]

1. make a magic square:

2 7 6
9 5 1
4 3 8

2. play tic-tac-toe.

[KnifeMissile]

Of course, my card game is isomorphic to tic tac toe. Thus, the question of whether my card game has a winning strategy is equivalent to asking whether tic tac toe has a winning strategy...

[kutulu]

using the magic square, the most strategic number to choose is 5 because it is a part of the highest amount of winning combinations (4). After that, the corners: 2, 4, 6, 8 (3). 1, 3, 7, and 9 are only parts of 2 winning combinations each.

It is exactly the same as tic tac toe.

[kutulu]

KM:

Wargames showed us that there is no effective stategy to ttt.

[TIO]

So it's a game theoretic stalemate.

kutulu, there is no 'best' choice of opener. If your opponent plays perfectly, you can't win.

But does one of you want to prove the isomorphism to ttt?

[KnifeMissile]

When there is a "game theoretic stalemate," we say that there exists no winning strategy.

Now, about a proof of an isomorphism, didn't rsl12's "magic square" convince you? It has the same rules as tic-tac-toe but satisfies all the properties of my card game. Therefore, there exists an isomorphism between the two.
QED.

[rsl12]

also, to prove isomorphism, you need to convince yourself that all possible ways of making 15 with 3 numbers are represented in the magic square. Can't think of an elegant way to do that, but if you examine it, you'll see that nothing's been left out.

[rsl12]

btw, that was an interesting puzzle knifemissile. thanks for posting it.

[KnifeMissile]

Well, I'm glad you appreciated it, rsl12! Thanks for bringing it up.

I don't know, if there are only 8 ways of winning then exhaustively listing them all is elegant enough for me...

[frozenstellar]

just a question.. this looks very similar to game theory that i did in intro. microeconomics last semester.

is it mathematical based? how would i go about doing math like this?

[Yakk]

also, to prove isomorphism, you need to convince yourself that all possible ways of making 15 with 3 numbers are represented in the magic square. Can't think of an elegant way to do that, but if you examine it, you'll see that nothing's been left out.

Try examining the "order" of each card. Define "order" to be "the number of winning combinations that use this card".

5 has order 4.
2, 6, 4 and 8 have order 3
9, 3, 1 and 7 have order 2

this lines up with the orders of the tic-tac-toe squares. This isn't much different than listing all of the solutions and comparing them in the end, but I think it looks prettier.