Scoring Misère: Two Heaps Perfect Strategy

Misère games are played by the same rules as the normal ones with one notable exception: while in the normal game the player unable to move loses, in the misère games, the player unable to move wins.

In the Scoring misère, like in Scoring, the players are presented with one or more piles (or heaps) of objects (chips, counters, pebbles.) A move consists in removing a number of objects from a single pile. In Scoring (normal or misère), a player, on a single move, is allowed to remove one or more objects up to a prescribed maximum. In the misère game, the player who was forced to remove the last item loses.

Unlike the normal games, the misère does not in general have a perfect strategy. However, in case of just two heaps a perfect strategy does exists.

The MAA Math Horizons magazine (v 17, n 4, April 2010, pp. 31-33) posted a solution to the problem by Dan Kalman and Michael Keynes of American University which the called Double Take:

Starting with two non-empty stacks of chips, one of size m and the other of size n, the two players alternate turns and take 1, 2, or 3 chips from a single stack on each turn. The loser is the player who removes the last chip out of the initial m + n chips. Find the values of m and n that guarantee that the second player wins with best play.

In the problem, the players are allowed to remove maximum of 3 chips. In the applet this restriction is removed and you can specify the maximum move of any size - in principle, of course. For technical reasons the applet allows to remove at most 10 chips. The chips are represented by small squares lined in a row (a heap). The squares are counted left to right. To remove a desired (but legal) number of squares click on the first one to be removed.


 

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

The strategy

References

  1. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 2, A K Peters, 2003
  2. J. H. Conway, On Numbers And Games, A K Peters, 2001
  3. R. Guy, fair game, Comap's Explorations in Mathematics, 1989

|Contact| |Front page| |Contents| |Games| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

The three correct submissions to the Math Horizons magazine proved that the second player wins just when one of the following is true (see modular arithmetic):

  (a) m ≡ 0 (mod 4) and n ≡ 1 (mod 4), or vice versa,
(b) m ≡ n ≡ 2 (mod 4),
(c) m ≡n ≡ 3 (mod 4).

More generally, if the largest allowed move is M ≥ 2 then, besides (a), the felicitous for the second starting positions are described as

  (a') m ≡ 0 (mod M+1) and n ≡ 1 (mod M+1), or vice versa,
(b') m ≡ n ≡ k (mod M+1), 2 < k ≤ M.

The extension is quite straightforward and implicit in the submitted solutions which were based on the folowing observations:

 
  1. In order for the second player to win, after an even number of turns the initial game must eventually reach a position when one of the stacks is empty and the other stack has one chip, since this is the only position that forces the first player to remove the final chip.

  2. When one player removes 1, 2, or 3 chips from a single stack that has at least 4 chips in it, the other player has the option of responding by removing 3, 2, or 1 chips respectively from the same stack, so that a total of 4 chips is removed during the two consecutive turns. Thus, a winning secondplayer strategy when the stacks have sizes m and n implies a winning second-player strategy when the stacks have sizes m' ≥ m and n' ≥ n, so long as m' ≡ m (mod 4) and n' ≡ n (mod 4).

  3. When the pair (m,n) is congruent modulo 4 to one of the pairs (0, 0), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3), (3, 0), (3, 1), and (3, 2), the first player can remove some number of chips from a single stack to arrive at an (m, n) pair congruent modulo 4 to either (0, 1) or (1, 0).

The extension is obvious.

Related material
Read more...

  • What Is a Combinatorial Game?
  • A Game of Candy Squares
  • A Sticky Problem
  • Another Sticky Problem
  • Date Game
  • Dawson's Chess: an Interactive Gizmo
  • Dawson's Kayles: an Interactive Gizmo
  • Grundy's Game
  • Hex 7
  • Kayles
  • Nimble: an Interactive Gizmo
  • Northcott's game (An Interactive Gizmo)
  • Odd Scoring
  • One Pile: an Interactive Gizmo
  • Plainim (An Interactive Gizmo)
  • Plainim Misere (An Interactive Gizmo)
  • Scoring: the simplest of the impartial games
  • Scoring Misere: an Interactive Gizmo
  • The Fraction Game
  • The Silver Dollar Game
  • Silver Dollar Game With No Silver Dollar
  • Subtraction Game
  • TacTix: an Interactive Gizmo
  • Turning Turtles
  • Take-Away Games
  • Wythoff's Nim, Literal Implementation
  • Wythoff's Nim (An Interactive Gizmo)
  • |Contact| |Front page| |Contents| |Games| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     61215479

    Search by google: