Game Theory (possibly redundant)

[LetYouDown]

Tried to search...but no avail. I'm sure someone has this completely solved somewhere as it's not overly difficult. Someone posed this question to me:

"My buddy brought up this math puzzle where you have 20 items on the table, i.e. sugar packets. Now you can pick up 1 or 2 on your turn and each person picks until someone gets the last 1 or 2 on the table. I was wondering if you could figure out mathimatical relationship needed to calculate your next move when picking?"

My initial suspicion is that going first is a disadvantage and that you never wanted your opponent to have a turn when there are 4 or 5 items left. So you'd never want a turn when there are 6 items left. So you'd never want him to have a turn when there are 7 or 8 items left, etc. etc.

This is called a 'take away' game (like nim).

In this simple case, I'm assumeing that the person to take the last packet wins.

Then you want to leave your opponent with a multiple of 3 packets. If he takes one, you take two, if he takes two you take one. Clearly, you'll take the last packet. Ergo, go first, and take two pakets.

If you want your opponent to take the last packet, the strategy is similar, but you always want to leave your opponent with a number that is equivalent to 1 mod 3 (that is, a number that has a remainder of 1 when divided by 3). By chopping off 3's you will leave him with the last packet, so Go first, and take one packet, and then match his moves as above.

[LetYouDown]

[ QUOTE ]
Then you want to leave your opponent with a multiple of 3 packets. If he takes one, you take two, if he takes two you take one. Clearly, you'll take the last packet. Ergo, go first, and take two pakets.

[/ QUOTE ]
Right, that's what I was getting at...although you posed it more eloquently. Makes sense.

[LetYouDown]

So, if there are 20 and the person who takes the last packet wins, all you have to do is take 2 and then take the opposite the entire way down. So going first turns out to be advantageous unless the number of items is a multiple of 3.

[Johnnyj580]

This thread sucks!

[AaronBrown]

By the way, although this is a game, and a theoretical solution, the solution does not require game theory. Generally you need asymmetric information for game theory to come into play.

[UATrewqaz]

This is a simple deterministic game, a classic AI game tree problem.

Given perfect play in a game like this the player who goes first is destined to win or the player who goes second is destined to win or it's destined to be a tie. The parameters of the game determine who this is.

The most famous of these games is tic-tac-toe. If both players play pefect it will be a tie every game, but not everyone plays perfect (ie retards). You can build a tree showing every possible move/result though.

I will give a simple example.

I say a number 1-3, you say a number 1-3, we keep a running sum and whoever makes the total 5 or more wins.

In this scenario you can build a tree

Player ONE has 3 intial moves: resulting in

1, 2, 3

Player TWO has of couse 3 responses to each of these

2,3,4 3,4,5 4,5,6

As you can see if player ONE selects 1 or 2 as his first choice then player TWO can choose a move leading to a win, thus assuming player TWO plays perfect it's clear player ONE should not choose 2 or 3 initially.

that leaves 2,3,4 going back to player ONE after player TWO's choice.

No matter what of these 3 numbers happen, player ONE may choose a number leading to a win.

This tree is relatively small but it can be clearly seen player 1 is determined to always win if he plays perfectly.

The problem can be inverted such that player 1 always loose

Say if hte total has to be 4 or greater...


We as humans can do these small ones easily, however computers can build these trees in nano-seconds.

So if I said, same number game.....

We go back and forth selecting numbers between 1-62 and first one to make the running sum either divisibile by 100 or totalling greater than or equal to 500 wins.

Now can you play perfect? A computer program can easily build this entire tree in less than a second.

[yellowjack]

My coding class today just covered mods. I was thinking about poker but wrote it everything down anyways. Are they difficult to understand?

[Moozh]

In case anyone cares (I'm bored). For the general case where:

You lose if you pick the last packet
You go first
Each player must pick between x and y packets (x<y)
There are n packets
If there are x or fewer packets left, the player must take them.

Realize that after the first pick, you can choose such that every subsequent pair of picks totals x+y

Your first step is to find the remainder of (n-1)/(x+y), or (n-1)%(x+y). That number will be your first pick. If that remainder is less than x, the 2nd player has the advantage.

After that, whatever your opponent picks, you pick a number such that his and yours add up to x+y.

You win (unless that remainder was less than x)