"Beggar Your Neighbor" has Infinite Loops - Maybe
Chris Long
In _The Mathematics of Games_ John Beasley describes the following
card game:
Each player has a stack of cards, and plays in rotation to trick.
Play passes normally as long as the cards played are face cards (two
to ten inclusive), but the rule changes the moment a court card is
played; the next player must now play repeatedly until either he has
laid down a certain number of plain cards (one is the court card was
a jack, two if a queen, three if a king, four if an ace) or he plays
a court card himself. In the former case, the player who played the
court card picks up the trick, puts it on the bottom of his stack, and
leads to the next trick; in the latter, the next player in turn must
play to the new court card in the same way. A player whose stack is
exhausted drops out, and the winner is the last to be left in play.
Beasley doesn't mention the orientation of the three stacks, but
standard play is that the player stacks are face down, and that the
trick stack is face up.
The largest number of tricks Beasley found was 239; however, I've
discovered that the following hand
First Second
F F
F A
J F
F Q
F F
F A
F F
F F
A F
F F
F F
F F
Q F
J F
F K
K F
F J
F F
A F
F Q
Q F
F F
F K
K F
F F
J F
either cycles or has a truly enourmous number of tricks. I don't have
the time to check if it indeed cycles; can anyone either prove this
or refute it?
--
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ 08901 (908) 846-5569
"It has no normal subgroups" was Tom's simple observation.
Christopher Tate
cl...@remus.rutgers.edu (Chris Long) says:
>
>In _The Mathematics of Games_ John Beasley describes the following
>card game:
>
> Each player has a stack of cards, and plays in rotation to trick.
> Play passes normally as long as the cards played are face cards (two
> to ten inclusive), but the rule changes the moment a court card is
> played; the next player must now play repeatedly until either he has
> laid down a certain number of plain cards (one is the court card was
> a jack, two if a queen, three if a king, four if an ace) or he plays
> a court card himself. In the former case, the player who played the
> court card picks up the trick, puts it on the bottom of his stack, and
> leads to the next trick; in the latter, the next player in turn must
> play to the new court card in the same way. A player whose stack is
> exhausted drops out, and the winner is the last to be left in play.
>
>discovered that the following hand
>
>
>either cycles or has a truly enourmous number of tricks. I don't have
>the time to check if it indeed cycles; can anyone either prove this
>or refute it?
When I learned this game some years ago, there was an additional rule
which would seem to negate any cyclic behavior in the game:
If two of the same card are played in sequence, the first person to
slap the trick may pick it up. Play then continues normally.
In the hand you give above, there are occasional opportunities for this
rule to take effect. Perhaps this alternate rule exists because someone
noticed that the game would never end with certain distributions of cards?
-------
Christopher Tate | Cryptogram #2:
cxt...@psuvm.psu.edu |
CXT...@PSUVM.BITNET | UWOOK; CX'U EHBUUCICPR. C EWZHR
---------------------------------| XPHH KWZ, GZX XMPL C'R MBTP XW
Send me the answer; I love mail! | SCHH KWZ.
Matt Ender
>
>In _The Mathematics of Games_ John Beasley describes the following
>card game:
>
> Each player has a stack of cards, and plays in rotation to trick.
> Play passes normally as long as the cards played are face cards (two
> to ten inclusive), but the rule changes the moment a court card is
> played; the next player must now play repeatedly until either he has
> laid down a certain number of plain cards (one is the court card was
> a jack, two if a queen, three if a king, four if an ace) or he plays
> a court card himself. In the former case, the player who played the
> court card picks up the trick, puts it on the bottom of his stack, and
> leads to the next trick; in the latter, the next player in turn must
> play to the new court card in the same way. A player whose stack is
> exhausted drops out, and the winner is the last to be left in play.
>
The non-deterministic Beggar Your Neighbor variant 'Egyptian Ratscrew'
is mor fun to play, though impossible to analyze. There is one added
rule: If, at any time, two cards of the same denomination are played
one after the other onto the trick stack, the first person to slap
hir hand on the stack wins the trick (5,6,A,2,Q,4,4, SLAP! for
example). Try it sometime with friends who wear no rings or brass
knuckles.
-- Matt
Matt Ender
>When I learned this game some years ago, there was an additional rule
>which would seem to negate any cyclic behavior in the game:
>
>If two of the same card are played in sequence, the first person to
>slap the trick may pick it up. Play then continues normally.
>
>In the hand you give above, there are occasional opportunities for this
>rule to take effect. Perhaps this alternate rule exists because someone
>noticed that the game would never end with certain distributions of cards?
>
Sorry for wasting bandwidth by not reading the newsgroup before
'F'ollowing up. Yet a new note: an eliminated player could 'slap
back in' by slapping an appropraite trick. To prevent continuous
slapping, 3 false slaps took an eliminated player out permanently. A
false slap (slapping a non-pair) by an active player caused the loss
of a single card. In some house versions, it was allowed to exploit
this loss to sacrifice up to a known pair in your hand, and then slap
that, winning the trick. If you counted wrong, you're toast...
-- Matt
Chris Long
As many people have pointed out, the hand I posted terminated after
9 tricks. Thanks; there was a small problem in how my program
handled the trick stack.
Since my hand was a bust, I've decided to run a "beggar your neighbor"
contest. The person who finds a hand that involves the most tricks
before ending wins! Beasley's best was a 239, my current best is a
538 after searching through ~50,000,000 random hands (although I'm
not eligible). First prize is a year's subscription to either _Games
Magazine_, _The Journal of Recreational Mathematics_, or the _Fibonacci
Quarterly_. You have approximately six weeks before the close of the
contest.
I might be convinced to run contests like this periodically if enough
interest is expressed. In addition, if anything interesting is
generated as a result I'll submit a short article to _The Journal of
Recreational Mathematics_, giving full credit to the parties involved.
The rules of the game follow:
In _The Mathematics of Games_ John Beasley describes the following
card game:
Each player has a stack of cards, and plays in rotation to trick.
Play passes normally as long as the cards played are face cards (two
to ten inclusive), but the rule changes the moment a court card is
played; the next player must now play repeatedly until either he has
laid down a certain number of plain cards (one is the court card was
a jack, two if a queen, three if a king, four if an ace) or he plays
a court card himself. In the former case, the player who played the
court card picks up the trick, puts it on the bottom of his stack, and
leads to the next trick; in the latter, the next player in turn must
play to the new court card in the same way. A player whose stack is
exhausted drops out, and the winner is the last to be left in play.
Beasley doesn't mention the orientation of the three stacks, but
standard play is that the player stacks are face down, and that the
trick stack is face up.
--
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ 08901 (908) 846-5569
"The simplest way, with a per-move limit, is for the Codemaker to start
yelling at the Codebreaker to move, which usually brings compliance
but might result in a fight."
Leslie H. Ault, _The Official Master Mind Handbook_
Mike Challis
>
>In _The Mathematics of Games_ John Beasley describes the following
>card game:
>
> Each player has a stack of cards, and plays in rotation to trick.
> Play passes normally as long as the cards played are face cards (two
> to ten inclusive), but the rule changes the moment a court card is
> played; the next player must now play repeatedly until either he has
> laid down a certain number of plain cards (one is the court card was
> a jack, two if a queen, three if a king, four if an ace) or he plays
> a court card himself. In the former case, the player who played the
> court card picks up the trick, puts it on the bottom of his stack, and
> leads to the next trick; in the latter, the next player in turn must
> play to the new court card in the same way. A player whose stack is
> exhausted drops out, and the winner is the last to be left in play.
>
>Beasley doesn't mention the orientation of the three stacks, but
>standard play is that the player stacks are face down, and that the
>trick stack is face up.
>
>The largest number of tricks Beasley found was 239; however, I've
>discovered that the following hand
>
> [hand deleted]
>
>either cycles or has a truly enourmous number of tricks. I don't have
>the time to check if it indeed cycles; can anyone either prove this
>or refute it?
My program says your hand completes pretty soon:
BMN - Version V0.1
Starting hands are:
A: 00100000400021030040200301
B: 04020400000000301002003000
C: EMPTY
A wins after 73 moves and 23 tricks
A's cards are:
04000000000020310040302000000320100000014310
Discard pile is:
00020400
The program was written some years ago, but if I remember correctly it
simulates exactly the game you describe; in particular:
- A goes first
- When a trick is won, the winner picks up the discard pile (which is face
up), turns it over, and adds it to the bottom of his hand (which is face
down).
In this case we have:
A plays 0: 0
B plays 0: 00
A plays 1: 100
B plays 4: 4100
A plays 0: 04100
A plays 0: 004100
A plays 0: 0004100
A plays 0: 00004100
B has won the trick, and so adds 00140000 to the end of his hand.
Just in case, I also tried out the hands in reverse order; this lasted a
little longer:
BMN - Version V0.1
Starting hands are:
A: 10300204003012000400000100
B: 00030020010300000000402040
C: EMPTY
B wins after 439 moves and 136 tricks
B's cards are:
0100040400300300000230010000400110000022040030200
Discard pile is:
000
For interest, the longest game I found was as follows - almost 1000 tricks:
BMN - Version V0.1
Starting hands are:
A: 00420004000034002000030010
B: 01002004003000020300010010
C: EMPTY
B wins after 3171 moves and 992 tricks
B's cards are:
420220000004000001004002000430000000000000010
Discard pile is:
3130130
I'd be interested to hear of longer games - either in moves or tricks!
Chris Long
Jim Propp has informed me that John Conway has offered $100 to anyone
who can exhibit an initial BYN hand that has an infinite cycle. For
the duration of the Great Usenet BYN contest I hereby offer an
additional $400 (for a total of $500) for the first person
finding such a hand.
To get everyone started, here's a hand which involves 538 tricks
before terminating. If you don't get this, your program is buggy
or you're confused about the rules of the game!
0 = face card, 1 = Jack, 2 = Queen, 3 = King, 4 = Ace, First person
plays first
First person
3
4
0
0
0
0
4
0
0
0
1
0
0
Second person
0
4
3
0
0
3
0
1
0
0
0
0
0
0
0
2
2
3
4
1
0
0
0
0
0
0
0
0
2
1
0
0
0
2
0
0
0
0
0
Joseph William DeVincentis
>
> Jim Propp has informed me that John Conway has offered $100 to anyone
> who can exhibit an initial BYN hand that has an infinite cycle. For
> the duration of the Great Usenet BYN contest I hereby offer an
> additional $400 (for a total of $500) for the first person
> finding such a hand.
>
> To get everyone started, here's a hand which involves 538 tricks
> before terminating. If you don't get this, your program is buggy
> or you're confused about the rules of the game!
>
[hand deleted]
Are you sure? It looks like player 1 never wins a trick!
Here's the debugging output from my program. Players' hands are listed
from the top down, the stack on the table is from the bottom up.
If I'm confused about the rules, please tell me what I'm doing wrong.
Player 1:400004000100
Player 2:043003010000000223410000000021000200000
stack:3
Player 1:400004000100
Player 2:3003010000000223410000000021000200000
stack:304
Player 1:00004000100
Player 2:3003010000000223410000000021000200000
stack:3044
Player 1:00004000100
Player 2:003010000000223410000000021000200000
stack:30443
Player 1:04000100
Player 2:00301000000022341000000002100020000030443000
stack:
Player 1:04000100
Player 2:0301000000022341000000002100020000030443000
stack:0
Player 1:4000100
Player 2:0301000000022341000000002100020000030443000
stack:00
Player 1:4000100
Player 2:301000000022341000000002100020000030443000
stack:000
Player 1:000100
Player 2:301000000022341000000002100020000030443000
stack:0004
Player 1:000100
Player 2:01000000022341000000002100020000030443000
stack:00043
Player 1:100
Player 2:0100000002234100000000210002000003044300000043000
stack:
Player 1:100
Player 2:100000002234100000000210002000003044300000043000
stack:0
Player 1:00
Player 2:100000002234100000000210002000003044300000043000
stack:01
Player 1:00
Player 2:00000002234100000000210002000003044300000043000
stack:011
Player 1:0
Player 2:000000022341000000002100020000030443000000430000110
stack:
Player 1:0
Player 2:00000022341000000002100020000030443000000430000110
stack:0
Player 1:
Player 2:00000022341000000002100020000030443000000430000110
stack:00
(Player 2 wins)
--
\ Joseph De Vincentis jw...@owlnet.rice.edu /
\ /
\ "Hey! Where's that music comin' from?" /
`-------------------------------------- -Bo -----------------'
Joseph William DeVincentis II
> In article <Nov.8.10.00....@remus.rutgers.edu>, cl...@remus.rutgers.edu (Chris Long) writes:
> >
> > Jim Propp has informed me that John Conway has offered $100 to anyone
> > who can exhibit an initial BYN hand that has an infinite cycle. For
> > the duration of the Great Usenet BYN contest I hereby offer an
> > additional $400 (for a total of $500) for the first person
> > finding such a hand.
> >
> > To get everyone started, here's a hand which involves 538 tricks
> > before terminating. If you don't get this, your program is buggy
> > or you're confused about the rules of the game!
> >
>
> [hand deleted]
>
> Are you sure? It looks like player 1 never wins a trick!
> Here's the debugging output from my program. Players' hands are listed
> from the top down, the stack on the table is from the bottom up.
> If I'm confused about the rules, please tell me what I'm doing wrong.
>
Chris just sent me mail telling me that the problem was that the hand was
written incorrectly. The first 13 cards of player 2's hand actually
belong to player 1's hand. Both hands should start with 26 cards:
Player 1: 34000040001000430030100000
Player 2: 00223410000000021000200000
My program now gives 537 tricks for this hand. I guess I was right before:
my program misses either the first or the last trick every time. I guess I'll
just have to add 1 to all my totals.
Thank god my program really does work! I've run almost 2 million random hands
so far. My best is the following hand which involves 439 tricks:
The game is over. (Game number 379322)
Player 1 has won.
There were 438 tricks played. ** Plus the one it forgot to count! **
The starting hands were:
Player 1: 01040004003000302030200002
Player 2: 00400010004030000001100200
The winner's final cards were
030000301000002401000100002013000
Unfinished trick: 0000000000243042400
My program currently only processes about 100-150 hands per second.
I'm trying to rewrite it so it's not so wasteful, but the optimized
version currently doesn't work!
Chris Long
The first 13 cards in the second player's hand should be the last 13
cards in the first player's hand; each should have 26.
Incidentally, I'm not sure if this was made clear or not, but each
player must have 26 cards in order for the intial hands to be
considered valid, and there must be exactly 4 each of Jacks, Queens,
Kings, and Aces.
--
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ 08901 (908) 846-5569
"It has no normal subgroups" was Tom's simple observation.
Chris Long
The first 13 cards in the second player's hand should be the last 13
cards in the first player's hand; each should have 26.
Matthew Merzbacher
>Chris just sent me mail telling me that the problem was that the hand was
>written incorrectly. The first 13 cards of player 2's hand actually
>belong to player 1's hand. Both hands should start with 26 cards:
>Player 1: 34000040001000430030100000
>Player 2: 00223410000000021000200000
>My program now gives 537 tricks for this hand. I guess I was right before...
Scott Turner and I have been working on the problem. So far, our best result:
Hands = 7378594.
New best is 548.
#0 Original: : 00100034020000402003000103
#1 Original: : 01040000202000400001000030
#0 Final: :
#1 Final: : 00004000023040000003000012002130002040100043010
Final Stack: : 00000
It might be 549, I guess, depending on the counting of the last trick.
Some interesting notes:
If you were stupid enough to want to consider ALL possible hands, then
you'd have: C(52,4)*C(48*4)*C(44*4)*C(40*4), which is:
653,534,134,886,878,245,000 (653 Quintillions!)
Where does this come from? Well, you have to place the sixteen "honor"
cards amongst the fifty-two cards dealt. There are four of each honor.
Anyhow, I note with interest that our best effort thusfar has an
unbalanced initial distribution of honors.
Finally, I have a question for the math whizzes out there (this means
*YOU*, C.L.).
If we take the number of tricks for each hand, and plot it, we get some
probability distribution, possibly looking like:
P(n)
^ xxxx
| xx xxx
| x xxxxx
| x xxxx
| xx xxxxx
| x xxxxxxxx
|x xxxxxxxxxx
+-------------------------------------------------> no. tricks (n)
My question:
After running N cases (where N is small compared with the total number
of sample points, say 1,000,000), and finding a best solution (B),
what is the AVERAGE amount of time we have to wait for a solution better
than B.
Intuitively, the wait should take until time 2*N (on average), since there's
a fifty-fifty chance that the best of the first 2*N cases is in the second
half. Experimentally, I find this to be true (for the few samples I checked).
Followup comment:
My hypothesis may be true if each N returned a different value. Given
that many cases return the same value, it may affect the results.
Matthew Merzbacher ARPA: mat...@CS.UCLA.EDU
Moo - Moo Moo UUCP: ...!{uunet|rutgers|ucbvax}!cs.ucla.edu!matthew
This time, *with* the oys
Joseph William DeVincentis
> Scott Turner and I have been working on the problem. So far, our best result:
>
> Hands = 7378594.
> New best is 548.
> #0 Original: : 00100034020000402003000103
> #1 Original: : 01040000202000400001000030
> #0 Final: :
> #1 Final: : 00004000023040000003000012002130002040100043010
> Final Stack: : 00000
>
> It might be 549, I guess, depending on the counting of the last trick.
>
Lucky! I've run 20 million hands and only come up with 508 tricks.
I had a game with 507 tricks before that.
Here are my games:
Player 1 has won.
There were 507 tricks played.
The starting hands were:
Player 1: 00130040000411300020000020
Player 2: 40030000000000000302014020
The winner's final cards were
3000000400000031020000100110002000000034423000
Unfinished trick: 020400
Player 2 has won.
There were 508 tricks played.
The starting hands were:
Player 1: 03000020400033300001020210
Player 2: 00040410000100020000400000
The winner's final cards were
300000021100300204010000402000243003000
Unfinished trick: 0000000000140