Gröbner Nim

Instructions

You can play Gröbner Nim as a solitaire game or as a two-player game.

Scoring

• As a solitaire game, the goal is to complete the puzzle in the smallest number of turns.
• As a two-player game, the goal is to earn the most points before completing the puzzle. Players earn three points for adding a new stick.

Game pieces

• A grid that extends indefinitely to the north and east.
• Sticks, initially two, placed randomly.
  • Each stick has a head and tail, which can rest only on the grid’s corners. The head is visibly larger.
  • The head is always either the point farthest from the southwest corner, as determined by walking along the grid. In the case where both are equally north and east, the head is the point further right.
    • If a stick has one point that is 5 units east and 2 units north, and the other point is 3 units east and 3 units north, then the first point is the head.
    • If a stick has one point that that is 5 units east and 2 units north, and the other point is 7 units east and 0 units north, then the second point is the head.

Gameplay

Gameplay is relatively easy.

• A player selects a previously unselected pair.
  In this implementation, whenever you select a stick, the computer will highlight sticks that will form a new pair with it.
• A selected pair “mates” as follows:
  • A copy of one stick is moved east, and a copy of the other is moved north, until their heads meet. There is only one way to do this.
  • The heads annihilate.
  • If the tails meet, they also annihilate.
  • Otherwise, the tails form a new stick. As long as an older stick’s head is southwest of either new point:
    • A copy of the older stick is moved north and/or east until it meets a newer point.
    • The points that meet annihilate, and any remaining points form a new stick.
    In this implementation, the computer takes care of that for you, but if you want to work it out on paper while playing (advisable), Zoltán Kovács’ Gröbner Solitaire app illustrates it ably; click here to review it.
• The player’s turn ends.

Gameplay ends when no new sticks can be added. The computer tells you when this happens.

Variants

Other ways to play:

• Start with more than two sticks. (Not yet implemented.)
  If you play enough, you will see that even with two sticks the game sometimes grows complicated.
• Players may choose from the outset to reward a player who creates a new stick with another turn.
  This is comparaible to scoring a point in volleyball, or playing a “Draw” card in some variants of two-player Uno.

Credits

This web app was programmed by John Perry in Kotlin / JS. It is based on the game described in the article Androids Armed with Poisoned Chocolate Squares: Ideal Nim and Its Relatives by Haley Dozier and John Perry.

The game is based on the theory of how to compute a Gröbner basis of a binomial ideal over the boolean field.

Future plans

• The game currently uses Buchberger’s algorithm to determine when the game is over. Future editions may use more recent algorithms.
• The rule for determining a stick’s head will be allowed to vary.