Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #1  
Old 09-20-2005, 01:23 PM
LetYouDown LetYouDown is offline
Senior Member
 
Join Date: Mar 2005
Location: Sharing a smoke w/negativity
Posts: 524
Default Game Theory (possibly redundant)

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.
Reply With Quote
  #2  
Old 09-20-2005, 01:46 PM
Guest
 
Posts: n/a
Default Re: Game Theory (possibly redundant)

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.
Reply With Quote
  #3  
Old 09-20-2005, 01:59 PM
LetYouDown LetYouDown is offline
Senior Member
 
Join Date: Mar 2005
Location: Sharing a smoke w/negativity
Posts: 524
Default Re: Game Theory (possibly redundant)

[ 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.
Reply With Quote
  #4  
Old 09-20-2005, 02:17 PM
LetYouDown LetYouDown is offline
Senior Member
 
Join Date: Mar 2005
Location: Sharing a smoke w/negativity
Posts: 524
Default Re: Game Theory (possibly redundant)

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.
Reply With Quote
  #5  
Old 09-21-2005, 05:38 PM
Johnnyj580 Johnnyj580 is offline
Member
 
Join Date: Jun 2005
Posts: 48
Default Re: Game Theory (possibly redundant)

This thread sucks!
Reply With Quote
  #6  
Old 09-21-2005, 06:13 PM
AaronBrown AaronBrown is offline
Senior Member
 
Join Date: May 2005
Location: New York
Posts: 505
Default Re: Game Theory (possibly redundant)

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.
Reply With Quote
  #7  
Old 09-21-2005, 07:32 PM
UATrewqaz UATrewqaz is offline
Senior Member
 
Join Date: Feb 2005
Location: Atlanta
Posts: 276
Default Re: Game Theory (possibly redundant)

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.
Reply With Quote
  #8  
Old 09-23-2005, 01:56 AM
yellowjack yellowjack is offline
Senior Member
 
Join Date: Nov 2004
Location: Vancouver, Canada
Posts: 263
Default Re: Game Theory (possibly redundant)

My coding class today just covered mods. I was thinking about poker but wrote it everything down anyways. Are they difficult to understand?
Reply With Quote
  #9  
Old 09-23-2005, 02:42 AM
Moozh Moozh is offline
Member
 
Join Date: Jan 2004
Posts: 40
Default Re: Game Theory (possibly redundant)

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)
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 11:07 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.