A game of 11 marbles wherein each player can either pick one or two marbles from the total. Starting from Player A & then Player B alternatively. This continues till all the marbles are picked. The winner is the one having odd number of marbles.

What is the strategy to be followed for Player A & B to win?. What happens for higher total number of marbles (13, 15 etc )?

The first three columns below represent the number of available marbles remaining, the number of marbles currently held by the player whose turn it is, and the number of marbles held by the opponent.  The fourth column is how many marbles to take.

After the gap, the next three columns represent what situation this leaves the opponent in: available marbles, marbles in his own hand, marbles in the original player's hand.  The next two sets of three are the possibilities for what the other player might give back to the original.

  1  4  6  1       0  6  5
  1  6  4  1       0  4  7
  2  3  6  2       0  6  5
  2  4  5  1       1  5  5       0  5  6
  2  5  4  2       0  4  7
  2  6  3  1       1  3  7       0  7  4
  3  3  5  2       1  5  5       0  5  6
  3  5  3  2       1  3  7       0  7  4
  4  3  4  1       3  4  4       2  4  5       1  4  6
  5  2  4  1       4  4  3       3  3  5       2  3  6
  5  2  4  2       3  4  4       2  4  5       1  4  6
  5  4  2  1       4  2  5       3  5  3       2  5  4
  5  4  2  2       3  2  6       2  6  3       1  6  4
  6  1  4  2       4  4  3       3  3  5       2  3  6
  6  2  3  1       5  3  3       4  3  4       3  3  5
  6  3  2  2       4  2  5       3  5  3       2  5  4
  7  1  3  2       5  3  3       4  3  4       3  3  5
  8  1  2  1       7  2  2       6  2  3       5  2  4
  9  0  2  1       8  2  1       7  1  3       6  1  4
  9  0  2  2       7  2  2       6  2  3       5  2  4
 10  0  1  1       9  1  1       8  1  2       7  1  3

The second player has the win, as he's initially presented with situation 10,0,1 or 9,0,2 depending on whether the first player took 1 or 2 marbles.  If the first took 1 marble, the second must take 1 marble, leaving the first player with the state 9,1,1, from which there is no winning strategy, as he must leave it to the second player as 8,1,2 or 7,1,3, both of which have winning strategies posted above.

If the first player took 2 marbles, the second could take either 1 or 2 and still be assured of victory: follow the path as above.

DECLARE FUNCTION makePlay! (n!)
CLEAR , , 29999

DIM SHARED pl, avail, hand(2), h$, ct

CLS
OPEN "mkplay1.txt" FOR OUTPUT AS #2
OPEN "mkplay2.txt" FOR OUTPUT AS #3
avail = 11
pl = 1
h$ = ""
  res = makePlay(1)
  res = makePlay(2)
PRINT ct

FUNCTION makePlay (n)
 h$ = h$ + LTRIM$(STR$(n))
 avail = avail - n
 hand(pl) = hand(pl) + n
 IF avail = 0 THEN
   IF hand(pl) MOD 2 THEN
    winner = pl
    PRINT #2, h$
    GOSUB report2
    ct = ct + 1
   ELSE
    winner = 3 - pl
   END IF
 ELSE
   pl = 3 - pl
   winner1 = makePlay(1)
   pl = 3 - pl
   IF avail > 1 THEN
    pl = 3 - pl
    winner2 = makePlay(2)
    pl = 3 - pl
   ELSE
    winner2 = 0
   END IF
   IF winner1 = pl AND (winner2 = pl OR winner2 = 0) THEN
     winner = pl
     PRINT #2, h$
     GOSUB report2
     ct = ct + 1
   ELSE
     winner = 3 - pl
   END IF
 END IF
 makePlay = winner
 h$ = LEFT$(h$, LEN(h$) - 1)
 avail = avail + n
 hand(pl) = hand(pl) - n
EXIT FUNCTION

report2:
    PRINT #3, USING "###"; avail + n; hand(pl) - n; hand(3 - pl); n;
    PRINT #3, "     ";
    PRINT #3, USING "###"; avail; hand(3 - pl); hand(pl);
    IF avail > 0 THEN
      PRINT #3, "     ";
      PRINT #3, USING "###"; avail - 1; hand(pl); hand(3 - pl) + 1;
      IF avail > 1 THEN
        PRINT #3, "     ";
        PRINT #3, USING "###"; avail - 2; hand(pl); hand(3 - pl) + 2;
      END IF
    END IF
    PRINT #3,
RETURN

END FUNCTION

The table shown is file #3, mkplay2.txt, sorted with duplicate lines removed.

Edited on October 4, 2006, 9:37 am

Posted by Charlie on 2006-10-04 09:20:20