Got a Strategy for Last Biscuit?
Description
Last Biscuit is a game that challenges you to use a systematic
approach to deduce a winning strategy. Can you find a strategy that
will beat the computer?
Solution:
You can beat your opponent if you leave the following number of
biscuits: 1, 2 3, 5 4, 7 6, 10 8, 13 9, 15 11, 18 12, 20 14, 23 16,
26 17, 28 19, 31 21, 34 22, 36 24, 39 25, 41 27, 44 29, 47 30, 49
32, 52 33, 54 35, 57 37, 60 38, 62 40, 65 42, 68 43, 70 45, 73 46,
75 48, 78 50, 81
I'm now convinced there's some interesting maths in this. It looked
like w1(i) and w2(i) [the biscuits lefts in the ith winning
position] were approximately linearly related to i, so I charted
them in Excel and read off the regression line: Using a few 10s of
results this gave: w1(i) is approximately 2.618i - 0.5026 w2(i) is
approximately 1.618i - 0.5026 Interesting, since 1.618 is very
close to the golden ratio phi, and 2.618 is (phi+1) or phi^2. That
-0.5026 looks like it's caused by rounding down to an integer
value. So, with phi = (\sqrt(5)+1)/2, I tried for 0 < = i < =
10000: w1(i) = floor(phi*i) w2(i) = floor((phi+1)*i) Perfect match
on all pairs! If phi is involved there must be some Fibonacci
sequences around. In fact there are lots of them. The winning pairs
are the even pairs of consecutive numbers in a union of Fibonacci
sequences. If F(1,2) is the Fibonacci sequence that starts
1,2,3,5,8... and F(1,3) starts 1,3,4,7,11,.... you can use F(1,3)
to fill in the gaps left by F(1,2). F(2,4) fills in the gaps left
by the previous 2, and so on. This all makes a certain amount of
sense since the ratio of successive Fibonacci numbers is phi - and
that was the gradient of the regression line. It's still all just
conjecture though - I haven't been able to prove any of it so far.
Assuming it's all true, it's possible to write a slick algorithm
that works for very large numbers of biscuits - essentially by
using the inverse linear relationship to find the nearest winning
pairs that can be reached from any position. Unfortunately, the
calculation is still a bit much to do in one's head - but it avoids
the need to tabulate all pairs up to the one that works. I tried
that and so far as I can tell it works fine. An Excel spreadsheet
so you can see what I mean is saved in common > site content.
See
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrab.html#PhiPlot
This page is all relevant to the winning pairs in Last Biscuit.
It's talking about the same function I needed to calculate them -
floor(i*phi) - defining this as the spectrum of phi. There's an
interesting section on how the spectra of 2 numbers A and B can
partition the integers into 2 sets iff 1/A + 1/B = 1. The smaller
and larger numbers of the winning pairs form such a partition with
A = phi and B = phi^2. 1/phi + 1/phi^2 = 1 since phi + 1 = phi^2.
http://home.att.net/~numericana/answer/games.htm goes into some
detail linking this version other nim like games and the grundy
numbers. After that background, the following paper might be more
understandable
http://www.math.temple.edu/~xysun/wythoff/wythoff_2.pdf I think it
contains a proof that last biscuit winning pairs are a wythoff
sequence - but it ain't easy!
You can beat your opponent if you leave the following number of
biscuits:
1, 2
3, 5
4, 7
6, 10
8, 13
9, 15
11, 18
12, 20
14, 23
16, 26
17, 28
19, 31
21, 34
22, 36
24, 39
25, 41
27, 44
29, 47
30, 49
32, 52
33, 54
35, 57
37, 60
38, 62
40, 65
42, 68
43, 70
45, 73
46, 75
48, 78
50, 81
A strategy to find winning moves is to note that $(0,0)$ is a
winning pair and then find the complete set of winning pairs by
induction. If $(A_n,B_n),A_n \leq B_n$ is the last move discovered,
then $A_{n+1}$ is the minimum positive integer that does not appear
in a winning pair yet, and $B_{n+1} = A_{n+1} + 1 + (B_n - A_n)$.
$(A_{n+1},B_{n+1})$ must be a new winning move because it is
impossible to generate a lower winning move from it in one turn.
Neither $A_{n+1}$ nor $B_{n+1}$ appear in a lower pair,so taking
from a single stack fails. Also, no lower winning pair has a
difference of $A_{n+1}-B_{n+1}$,so taking from both stacks will
fail.
Plotting $A_{n}$ against $n$ and $B_{n}$ against $n$ reveals near
linear relationships, which turn out to be represented exactly by
the equations:- \begin{eqnarray} A_n&=&
\mbox{floor}(n\phi)\\ B_n &=& \mbox{floor}(n\phi^2)
\end{eqnarray} where the floor function rounds values to the
next lowest integer, and $\phi$ is the golden section. A good way
to discover these relationships is to plot them in Excel and infer
them from the regression line equations. For a proof, see ref [10]
in this paper by Xinyu Sun
Even when you know the winning pairs, it is not trivial to
calculate the next best move from a given starting position, since
the above formulae must be inverted (the floor function complicates
matters) and applied with some care.
The winning move from a (500,1000) start will take you to (500,
309).