Expected gain of a game of chance with differently-priced tokens
They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar.

The game is not really a game of strategy, since there are no choices involved, only chance. In order to compute the expected value that Foo gets, it is enough to compute the probability that Foo takes each particular item. Let $p_{a,b}$ be the probability that Foo takes an item which is the $a$th from the left, $b$th from the right ($a,b \geq 0$, total number of elements is $a+b+1$). Then
$$
\begin{align*}
p(0,0) &amp;= 1, \\
p(0,1) &amp;= 1/2, \\
p(1,0) &amp;= 1/2, \\
p(1,1) &amp;= 1/2, \\
p(0,b+2) &amp;= 1/2 + p(0,b)/4, \\
p(a+2,0) &amp;= 1/2 + p(a,0)/4, \\
p(1,b+2) &amp;= p(0,b+1)/2 + p(1,b)/4, \\
p(a+2,1) &amp;= p(a+1,0)/2 + p(a,1)/4, \\
p(a+2,b+2) &amp;= (p(a+2,b)+2p(a+1,b+1)+p(a,b+2))/4.
\end{align*}
$$
You could precompute the requisite values for $a+b+1 \leq 2000$ and then your program will be blazingly fast.

It turns out that for fixed $c$, $p(c,n-c)$ tends to a limit $p_c = 1/2(1 + (-1)^c/3^{c+1})$. To see why, note first that $p_0$ is the ability that if you and a friend alternate tossing fair coins, yours will come up HEAD first. There are many ways to see that $p_0 = 2/3$. Next, we have the formula $p_{c+1} = p_0 (1-p_c) + (1-p_0) p_c$ (exercise), from which the formula for $p_c$ follows by induction.