Teaser 3167: Binary primes
From The Sunday Times, 4th June 2023 [link] [link]
Grace and Helen play a turn-based card game. Each player is given two cards with a 0 printed on them, and unlimited cards with a 1 printed on them. Before the game starts a 1 is placed on the table. Sitting on the same side of the table, a turn then involves placing a card to the left of the table cards, such that the value shown in binary remains prime or one (allowing leading zeros). The winner is the player who is last able to play a card, earning points equal to the value on the table at that time.
Being expert logicians, they play the best possible cards to maximise their points or minimise their opponent’s points. Grace goes first.
Who wins and with what cards on the table from left to right?
[teaser3167]
Frits, and 
Mark Valentine are discussing. 
S2T2 
Jim Randell 4:35 pm on 2 June 2023 Permalink |
This Python program plays the game with each player aiming to maximise their winnings (or minimise their losses) at each stage. So it performs a depth first traversal of the game tree.
It runs in 56ms. (Internal runtime is 138µs).
Run: [ @replit ]
from enigma import (Accumulator, is_prime, int2base, compare, printf) # explore the outcome of this move def explore(n, k, a0, b0, rs): (rn, rk) = play(n, k, a0, b0) # play the move rs.accumulate_data(-rn, rk) # swap the result # play the game with current value <n> from <k> cards # player A to move, with <a0> zero cards # player B has <b0> zero cards # return (<pts>, <k>) [+ve for win, -ve for loss] def play(n, k, a0, b0): # choose the best move (maximum points) rs = Accumulator(fn=max) # play 0 if a0 > 0: explore(n, k + 1, b0, a0 - 1, rs) # play 1 n_ = n + (1 << k) if is_prime(n_): explore(n_, k + 1, b0, a0, rs) # make the best available move if rs.count: return (rs.value, rs.data) # if there are no moves, current points go to opponent return (-n, k) # play starting with value 1, on 1 card, and 2 zero cards for each player (n, k) = play(1, 1, 2, 2) # determine points won and the sequence of cards pts = abs(n) ss = int2base(pts, base=2, width=k) # output solution printf("{w} wins, {pts} pts, cards = {ss}", w=compare(n, 0, 'B?A'))Solution: Helen wins. The cards on the table are: (0 1 0 0 1 1 1 0 1).
The game proceeds:
The the final moves (0, 1, 0, out) are forced.
There are 61 positions in the game tree, 17 of them are terminal positions, and only 2 of these are wins for the player who goes first.
LikeLike
Mark Valentine 11:11 pm on 5 June 2023 Permalink |
What does run time vs zeros per person look like? How many zeroes can you reasonably solve for?
LikeLike
Jim Randell 10:43 am on 6 June 2023 Permalink |
Hi, Mark. Thanks for the puzzle!
I ran my program for games with up to 28 zero cards per player. The number of positions grows at a reasonable rate, but things start to get a bit slow above z = 20.
But we can switch to using the Miller-Rabin primality test [[
is_prime_mr()]] for larger primes, which allows us to check up to z = 55 in under 1s (or [[gmpy2.is_prime()]] which is even faster).z = 40 ends with a win for B with 302231454903657293676551 points.
It doesn’t seem like going first is an advantage. In the z = 2 case only 2 of the 17 terminal positions are wins for A.
LikeLike
Mark Valentine 3:37 pm on 6 June 2023 Permalink |
Impressive, it doesn’t blow up as much as I would have thought. I guess the primes becoming increasingly scarce helps.
LikeLike
Frits 3:39 pm on 9 June 2023 Permalink |
@Jim, if you start with a list of prime numbers is there an upper limit for a prime number that you beforehand can determine?
LikeLike
Jim Randell 5:41 pm on 9 June 2023 Permalink |
@Frits: Do you mean can we determine what the largest possible value on the table can be without playing the game?
Each position in the game must be a left-truncatable prime in binary (treating 1 as prime), and as there are a limited number of zeros, it is reasonable to suppose there are only a limited number of such primes. (See: Enigma 1075 for more on truncatable primes).
With up to 4 zeros there are 28 left-truncatable binary primes, and the largest is:
(Although determining this is pretty much the same as playing the game anyway).
And 829 does indeed show up as the largest possible score for player B in the game tree.
LikeLike
Frits 10:09 am on 11 June 2023 Permalink |
@Jim, thanks.
On PuzzlingInPython (see below) I published a program where I start with a list of all prime numbers up to a certain limit where you keep pruning this list until you have all 17 games.
I hoped to find by logic a limit on the number of consecutive 1’s but in some cases none of the new primes end on a 5 anymore (fi if the last used power of 2 ends on an 8 and your last prime ends on a 1 then your next primes will end on (7, 9, 3, 1, 7, 9, 3, 1, 7, ….) ).
It was relative easy to generate the 17 games by recursion but picking the winner from this list I found difficult to program.
Do you also plan to add some kind of binary tree implementation to enigma.py? I guess not that many puzzles you have published can be solved from a binary tree.
[ https://brg.me.uk/?p=8290#comment-3820 ]
LikeLike
Jim Randell 3:33 pm on 12 June 2023 Permalink |
@Frits: In these game puzzles I usually find it is easiest to write a recursive function to do a depth first traversal of the game tree. From the current position you can examine all possible moves, and then choose the “best” one for the player, and this means we can determine what the outcome of a game is from the result of the initial position (presuming the players are aiming to maximise their metric at each position). (And in some games we don’t even need to explore the entire tree).
I’ve done a couple of recent Tantalizer puzzles using this approach (see: Tantalizer 4, Tantalizer 7a), but there are other puzzles where the same approach works.
This particular puzzle is relatively simple, in that there are at most two plays from any position (playing “0” or “1”), but in other games there may be many more plays available, so the game tree is not always binary.
I didn’t really think about constructing the graph by starting from the all potential endpoints and then removing those that are not reachable. It seems that this might not be tractable on more complex games as the number of potential positions could be very large, and only a sparse subset of them would be reachable. I think it would be more efficient to build the tree going forward from the starting position.
LikeLike