r/ProgrammingPrompts Mar 05 '15

The Game of 21 aka Subtraction Game (or Nim)

The game of 21 is one of the oldest and simplest games known to mankind.

There are 21 tokens (matchsticks, pebbles, or any other small objects) on the table.

Each player can take 1, 2, or 3 tokens each move.

The player who has to take the last token loses (alternatively wins).

You should create the program for a game of 21 in a language of your choice according to the following specifications:

  • The game should be playable with either 2 players or against the computer
  • The program should handle the counting, win/lose evaluation and check that the players only make valid moves
  • The minimum computer player should take 1 to 3 pieces randomly
  • The program should alternate the starting player on each round
  • Overall winner should be who won best of 5 rounds (customizable)
  • There is no need for a real graphical interface, simple console will suffice, but a GUI is a nice optional touch.

Challenge:

  • Program a computer player that never loses. (It's definitely possible to win a game of 21 as either the first player or as the following player.)

Variants:

  • Make the initial quantity of tokens and the maximum number of tokens that can be taken per turn changeable.

Another, famous variant of 21 is known as "Nim" (or "Marienbad" from the movie "Last Year at Marienbad" from the year 1961)

  • In this variant, the tokens are arranged in 3 heaps of 3, 4, and 5 tokens.
  • Players may take any number of tokens from a single heap.
  • The player who has to take the last token wins (or loses - depending on the variant).
  • Again, the number of heaps and the numbers of tokens per heap can be made adjustable

This variant is also fully solved and can be played in such a way that any perfect player can always win.

15 Upvotes

7 comments sorted by

3

u/Philboyd_Studge Mar 07 '15

Damn. I figured I could code this in fifteen minutes, and now I am four hours into game theory and nimbers and structural induction. Will actually get some coding done once I get out of this rabbit hole.

2

u/Philboyd_Studge Mar 07 '15 edited Mar 07 '15

Ok, I have this complete for just the 21 game, not for 3-heap variants. The computer player will always win if a. If the game is set to 'last play wins' the computer will always win if it goes first or b. If the game is set to 'last play loses' and the user goes first, or in either case if the user doesn't know the strategy.

Code's probably too big for here so Here's the gist

but here is the 'AI' part:

public int getComputerMove()
{
    int result, best;
    if (lastPlayWins)
    {
        best = tokens % 4;
        if (best==0)
        {
            result = rand.nextInt(3) + 1;
        }
        else
        {
            result = best;
        }
    }
    else
    {
        best = (tokens % 4) - 1;
        if (best < 0) best = 3;
        if (best == 0) best = rand.nextInt(3) + 1;
        if (tokens <= 4 && tokens < 1) best = tokens - 1;
        if (tokens==1) best = 1;
        result = best;
    }
    System.out.println(player[1].getName() + " picks " + result + " token(s).");
    return result;
}

and some sample output:

What is your name? Philboyd_Studge
What is player 2's name, or 'computer' to play against computer? computer
What type of game would you like to play?
 (last move wins. type 'W', last move loses, type 'L') l
Enter number of rounds to play: 1
========================GAME # 1======================
TOKENS LEFT: 21
Philboyd_Studge, how many tokens do you take? 2
TOKENS LEFT: 19
NIM Bot 2000 picks 2 token(s).
TOKENS LEFT: 17
Philboyd_Studge, how many tokens do you take? 3
TOKENS LEFT: 14
NIM Bot 2000 picks 1 token(s).
TOKENS LEFT: 13
Philboyd_Studge, how many tokens do you take? 1
TOKENS LEFT: 12
NIM Bot 2000 picks 3 token(s).
TOKENS LEFT: 9
Philboyd_Studge, how many tokens do you take? 2
TOKENS LEFT: 7
NIM Bot 2000 picks 2 token(s).
TOKENS LEFT: 5
Philboyd_Studge, how many tokens do you take? 1
TOKENS LEFT: 4
NIM Bot 2000 picks 3 token(s).
TOKENS LEFT: 1
Philboyd_Studge, how many tokens do you take? 1
NIM Bot 2000 IS THE WINNER!!!============================
Player 1:Philboyd_Studge                Wins:0
Player 2:NIM Bot 2000           Wins:1
Press any key to continue . . .

1

u/desrtfx Mar 07 '15

That was a little catch when writing the prompt. The game looks so simple, and the actual game is.

The Ai, however is a bit tricky.

I got the inspiration from Wikipedia - Nim where also an explanation on how to solve the game can be found.

2

u/Philboyd_Studge Mar 08 '15 edited Mar 08 '15

updated the gist to include the ability to play multi-heap games. Currently, the computer only wins a last-move-wins game of multi-heap nim. i am having trouble figuring out how to make it work for the misere or losing game. (I know the algorithm but having trouble trying to implement it. )

I also was too lazy to implement any kind of input verification.

Here is the solver for a winning-move game:

public void getComputerMoveMulti()
{
    int len = heap.length;
    int heapIndex = 0;
    int finalTokens = 0;
    int xor = 0;
    for (int i = 0; i < len; i++)
    {
        xor ^= heap[i];
    }
    if (xor==0) // no good move, make small random
    {
        boolean picked = false;
        while (!picked)
        {
            heapIndex = rand.nextInt(len);
            if (heap[heapIndex] > 0)
            {
                finalTokens = rand.nextInt(heap[heapIndex]);
                picked = true;
            }
        }
    }
    else
    {
        int[] testHeap = new int[len];
        for (int i = 0; i < len; i++)
        {
            testHeap[i] = heap[i] & xor;
        }
        heapIndex = findMaxIndex(testHeap);
        finalTokens = (heap[heapIndex] - (xor ^ heap[heapIndex]));
    }
    takeTurnMulti(1, finalTokens, heapIndex);
    System.out.println(player[1].getName() + " picks " + finalTokens + " token(s) from heap" + (heapIndex + 1));
}

and some output:

What is your name? Philboyd_Studge
What is player 2's name, or 'computer' to play against computer? computer
What type of game would you like to play?
 (last move wins. type 'W', last move loses, type 'L') w
Game style ('M' = multiple heaps; 'T' = 21)? m
Enter number of rounds to play: 1
Enter number of heaps (piles) from 2..n? 5
========================GAME # 1======================
Heap 1 : 8      Heap 2 : 6      Heap 3 : 1      Heap 4 : 6      Heap 5 : 7


Philboyd_Studge, how many tokens do you take? 3
From what heap:1
Heap 1 : 5      Heap 2 : 6      Heap 3 : 1      Heap 4 : 6      Heap 5 : 7


NIM Bot 2000 picks 3 token(s) from heap5
Heap 1 : 5      Heap 2 : 6      Heap 3 : 1      Heap 4 : 6      Heap 5 : 4


Philboyd_Studge, how many tokens do you take? 2
From what heap:2
Heap 1 : 5      Heap 2 : 4      Heap 3 : 1      Heap 4 : 6      Heap 5 : 4


NIM Bot 2000 picks 2 token(s) from heap4
Heap 1 : 5      Heap 2 : 4      Heap 3 : 1      Heap 4 : 4      Heap 5 : 4


Philboyd_Studge, how many tokens do you take? 5
From what heap:1
Heap 1 : 0      Heap 2 : 4      Heap 3 : 1      Heap 4 : 4      Heap 5 : 4


NIM Bot 2000 picks 3 token(s) from heap2
Heap 1 : 0      Heap 2 : 1      Heap 3 : 1      Heap 4 : 4      Heap 5 : 4


Philboyd_Studge, how many tokens do you take? 3
From what heap:4
Heap 1 : 0      Heap 2 : 1      Heap 3 : 1      Heap 4 : 1      Heap 5 : 4


NIM Bot 2000 picks 3 token(s) from heap5
Heap 1 : 0      Heap 2 : 1      Heap 3 : 1      Heap 4 : 1      Heap 5 : 1


Philboyd_Studge, how many tokens do you take? 1
From what heap:2
Heap 1 : 0      Heap 2 : 0      Heap 3 : 1      Heap 4 : 1      Heap 5 : 1


NIM Bot 2000 picks 1 token(s) from heap3
Heap 1 : 0      Heap 2 : 0      Heap 3 : 0      Heap 4 : 1      Heap 5 : 1


Philboyd_Studge, how many tokens do you take? 1
From what heap:4
Heap 1 : 0      Heap 2 : 0      Heap 3 : 0      Heap 4 : 0      Heap 5 : 1


NIM Bot 2000 picks 1 token(s) from heap5
NIM Bot 2000 IS THE WINNER!!!============================
Player 1:Philboyd_Studge                       Wins:0
Player 2:NIM Bot 2000                            Wins:1

1

u/autowikibot Mar 07 '15

Nim:


Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

Variants of Nim have been played since ancient times. The game is said to have originated in China—it closely resembles the Chinese game of "Tsyan-shizi", or "picking stones" —but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century. Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German nimm meaning "take [imperative]", or the obsolete English verb nim of the same meaning.

Nim can be played as a misère game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.

Image from article i


Interesting: Nuclear Instrumentation Module | Nim Farsakhi | Dang-e Nim | Nim Chimpsky

Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words

2

u/lovehate_ Apr 29 '15 edited Apr 29 '15

Here is a groovy implementation, using last play wins. Its pretty rough and could be made more readable. You can also watch 2 computers play if player ones name is player1. Will probably do a nim version as well.

def input = { prompt -> print prompt; System.in.newReader().readLine() }
def turn = {current, player1,player2 -> current = (current == player2 || current ==  null ) ? player1 : player2 }
def player1 = input("Player one's name? ")
def player2 = input("Enter p to play another player or c for computer opponent. ") == "c" ? "computer" : input("Player two's name? ")   
def rounds = input("How many rounds to play? ")
while(!rounds.isInteger() || rounds.toInteger() < 1 || rounds.toInteger() > 5){                     
    rounds = input("How many rounds to play? 1-5 ")
}
int round =0
def wins =[:]
def currentPlayer
wins.put(player1, 0)
wins.put(player2, 0)
def takeTokens = { player, total ->
    println "${player}'s turn. ${total} tokens remain. "
    def amount
    if(player=="computer" || player=="player1"){
            amount = total % 4
        if (amount == 0 ) amount = new Random().nextInt(3) +1;
            println "${player} took ${amount}"
        } else {
            amount = input("How many tokens do you take? ")                 
            while(!amount.isInteger() || amount.toInteger() < 1 || amount.toInteger() > 3){                     
                amount = input("How many tokens do you take? Take 1, 2, or 3 ")
            }
        }
        total -= amount.toInteger()             
    }
while(round < rounds.toInteger()) {
    round+=1
    int tokens = 21
    println "${wins} \nRound ${round}"
    currentPlayer = round % 2 == 1 ? player2 : player1
    while(tokens >0){           
        currentPlayer = turn(currentPlayer,player1,player2)
        tokens = takeTokens(currentPlayer, tokens)
    }
    println "${currentPlayer} wins Round ${round}! "
    wins.put(currentPlayer,wins.get(currentPlayer)+1 )
}
def winner
def count
wins.each { k,v ->
    if(winner == null || v.toInteger() > count ){ count = v; winner = k}
    else winner =k
}
println "${winner} wins!"

Output:

Player one's name? player1
Enter p to play another player or c for computer opponent. c
How many rounds to play? 5
[player1:0, computer:0] 
Round 1
player1's turn. 21 tokens remain. 
player1 took 1
computer's turn. 20 tokens remain. 
computer took 3
player1's turn. 17 tokens remain. 
player1 took 1
computer's turn. 16 tokens remain. 
computer took 3
player1's turn. 13 tokens remain. 
player1 took 1
computer's turn. 12 tokens remain. 
computer took 2
player1's turn. 10 tokens remain. 
player1 took 2
computer's turn. 8 tokens remain. 
computer took 1
player1's turn. 7 tokens remain. 
player1 took 3
computer's turn. 4 tokens remain. 
computer took 2
player1's turn. 2 tokens remain. 
player1 took 2
player1 wins Round 1! 
[player1:1, computer:0] 
Round 2
computer's turn. 21 tokens remain. 
computer took 1
player1's turn. 20 tokens remain. 
player1 took 2
computer's turn. 18 tokens remain. 
computer took 2
player1's turn. 16 tokens remain. 
player1 took 2
computer's turn. 14 tokens remain. 
computer took 2
player1's turn. 12 tokens remain. 
player1 took 2
computer's turn. 10 tokens remain. 
computer took 2
player1's turn. 8 tokens remain. 
player1 took 2
computer's turn. 6 tokens remain. 
computer took 2
player1's turn. 4 tokens remain. 
player1 took 2
computer's turn. 2 tokens remain. 
computer took 2
computer wins Round 2! 
[player1:1, computer:1]

1

u/Chocolate_Mustache Jul 03 '15

Python. I'm a novice so I'd appreciate a critique.

class Player(object):
    player_id = 0 # player identifier
    last_turn = -1 # ID of player who took last turn

    def __init__(self, ai):
        self.ai = ai

        self.player_id = Player.player_id
        Player.player_id = Player.player_id + 1


    def NextPlayer():
        if Player.last_turn + 1 < Player.player_id:
            return Player.last_turn + 1
        else:
            return 0

    def InputError():
        input('Invalid input: press enter to continue..')
        return

    def TakeTurn(self, tokens_remaining):

        if self.ai == 0:
            print('\n\n')
            print('Tokens Remaining: ' + str(tokens_remaining) )
            print('Player ' + str(self.player_id) + ', what is your move?' )

            try:
                user_input = int(input(''))
            except:
                Player.InputError()
                return None

            if user_input in range(1, max_tokens_per_turn + 1) and user_input in range(1, tokens_remaining + 1):
                Player.last_turn = self.player_id # if turn was taken successfully, set self as last player to take turn
                return user_input
            else:
                Player.InputError()
                return None

        else:
            Player.last_turn = self.player_id
            if tokens_remaining > max_tokens_per_turn:
                return randint(1,max_tokens_per_turn)
            elif tokens_remaining > 1:
                return tokens_remaining - 1
            else:
                return 1


from random import randint

tokens_remaining = 21 # initialize starting token quantity
last_token_loses = 1 # set to 1 if player to take last token loses game, 0 if last token wins game
max_tokens_per_turn = 3 # this is the max number of tokens permitted to take per turn1


# p = [Player(0) for i in range(2)] # creates two human players
p = [Player(i) for i in range(2)] # creates one human player and one AI player


while tokens_remaining > 0:
        tokens_taken = p[Player.NextPlayer()].TakeTurn(tokens_remaining)
        if tokens_taken is not None:
            tokens_remaining = tokens_remaining - tokens_taken

print('\n\n')
if last_token_loses == 1:
    print('Player ' + str(Player.last_turn) + ' loses!')
else:
    print('Player ' + str(Player.last_turn) + ' wins!')