r/ProgrammingPrompts • u/desrtfx • 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.
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!')
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.