3-5-7

3-5-7 is a simple two player board game. There are three rows of coins. The first row has three coins, the second has five and the last row has seven. A player can take any number of coins from one particular row. The player to take the last coin on the board loses.

This python program plays 3-5-7 with a human opponent. To run it, you need the python interpreter. My version is 2.4.1, but it should work with previous versions as well.

If you are copy-pasting this somewhere, then remember that whitespace in python programs are significant, so all those tabs and spaces should remain as they are!

[I would much rather upload this somewhere than put the source in a blog post. Any good uploading services available that allow you to upload small files? Preferably no intrusive ads, sign-ups etc]

###########################################################################################
#
#   Constants

GAME_NOT_OVER  = 0
PLAYER_1_WINNER = 1
COMPUTER_WINNER = 2

###########################################################################################
#
#   Error Class

class InputError(Exception):
 pass

###########################################################################################
#
#   Strategy Classes
#
# Strategy classes are the really interesting part of this program. They determine what
# the computer will do when the computer cannot play a guaranteed winning move. Some
# moves are more likely to induce mistakes than others. Each strategy class uses a
# different strategy to choose between two losing moves
#
# All classes implement getBestMove which returns the best move from a list of moves
# for the given boardstate
#


# Strategy to randomly select one of the moves
class RandomStrategy:
 def getBestMove(self, boardstate, moveList):
  # toss a coin ;)
  import random
  random.seed()
  selectedIndex = random.randint(0, len(moveList) - 1)
  return moveList[selectedIndex]

# Strategy which filters out moves which leave the board in simple states
class FilterStrategy:
 def hasOnlyOneRowLeft(self, boardstate):
  if (boardstate[0] == 0) and (boardstate[1] == 0):
   return True
  if (boardstate[1] == 0) and (boardstate[2] == 0):
   return True
  if (boardstate[2] == 0) and (boardstate[0] == 0):
   return True
  return False

 def hasTwoRowsLeft(self, boardstate):
  if (boardstate[0] == 0):
   return True
  if (boardstate[1] == 0):
   return True
  if (boardstate[2] == 0):
   return True
  return False

 def hasMirrorRows(self, boardstate):
  if (boardstate[0] == boardstate[1]):
   return True
  if (boardstate[1] == boardstate[2]):
   return True
  if (boardstate[2] == boardstate[0]):
   return True
  return False

 def getBestMove(self, boardstate, moveList):
  import random
  def move(board, move):
   newboard = board[:]
   row = move[0] - 1
   coins = move[1]
   newboard[row] = board[row] - coins
   return newboard

  filterList = [self.hasOnlyOneRowLeft, self.hasTwoRowsLeft, self.hasMirrorRows]
  boardstateList = [(x, move(boardstate, x)) for x in moveList]
  # filter out cases which leave board in simple states
  for filter in filterList:
   newlist = [x for x in boardstateList if not filter(x[1])]
   # if we are left with nothing, unfilter
   if len(newlist) == 0:
    newlist = boardstateList
   boardstateList = newlist
  # now take one of the remaining moves
  random.seed()
  selectedIndex = random.randint(0, len(boardstateList) - 1)
  return boardstateList[selectedIndex][0]



###########################################################################################
#
#   Output routines

def printWelcomeScreen():
 print "_" * 50
 print "WELCOME TO 7-5-3"
 print "_" * 50
 print "Rules: In this game there are three rows of coins."
 print "The first row has 3 coins, the second row has 5 "
 print "coins and the last row has 7 coins. In your turn,"
 print "you can pick up as many coins as you like from any"
 print "one row. You must enter your move in the format"
 print "row:number where row is the row you want to pick"
 print "up from and number is the number of coins you"
 print "would like to pick up."
 print
 print "For example enter your input as 2:5 if you want"
 print "to pick up five coins from row 2"
 print
 print "The player to pick up the last coin is the loser"
 print

def drawboard(boardstate):
 print "_" * 50
 print
 print "Row 1 : [" + str(boardstate[0]) + " coins]",
 print "    " + boardstate[0] * "O "
 print "Row 2 : [" + str(boardstate[1]) + " coins]",
 print "  " + boardstate[1] * "O "
 print "Row 3 : [" + str(boardstate[2]) + " coins]",
 print boardstate[2] * "O "
 print

def displayMove(player, move):
 print
 print "_" * 50
 print
 print " -> " + player + " moved " + str(move[1]) + " coins from row " + str(move[0])
 print

def displayWinner(winner):
 print
 print "_" * 50
 print
 if winner == COMPUTER_WINNER:
  print "The computer is the winner"
 else:
  print "You are the winner"
 print
 print "_" * 50
 print
 raw_input("Press Enter to quit...")

###########################################################################################
#
#   Input routines

def parseInput(input):
 tokens = input.split(":")
 if len(tokens) != 2:
  raise ValueError
 row = int(tokens[0])
 numberOfCoins = int(tokens[1])
 return (row, numberOfCoins)

def getInput():
 try:
  input = raw_input("Enter your move: ")
  move = parseInput(input)
  return move
 except ValueError:
  raise InputError("Input should be of the form row:num. For example 2:3 means take 3 coins from row 2")

###########################################################################################
#
#   Game routines

def makeMove(boardstate, move):
 row = move[0] - 1
 numberOfCoins = move[1]
 if (row < 0) or (row > 2):
  raise InputError("You must enter a row number between 1 and 3")
 if numberOfCoins <= 0:
  raise InputError("You must pick up at least one coin")
 if boardstate[row] < numberOfCoins:
  raise InputError("That row has only " + str(boardstate[row]) + " coins, so you cannot pick up " + str(numberOfCoins) + " coins.")
 boardstate[row] = boardstate[row] - numberOfCoins
 return boardstate

def doPlayerMove(boardstate):
 validInput = False
 while not validInput:
  try:
   move = getInput()
   boardstate = makeMove(boardstate, move)
   validInput = True
  except InputError, args:
   print "Invalid input. " + str(args)
 displayMove("You", move)

def isGameOver(boardstate):
 if (boardstate[0] == 0) and (boardstate[1] == 0) and (boardstate[2] == 0):
  return True
 return False

###########################################################################################
#
#   Computer AI code

def simulatePlayerMove(boardstate, depth):
 global strategyClass
 bestMoveList = None
 bestPoints = None
 for row in [1, 2, 3]:
  for coins in range(boardstate[row-1], 0, -1):
   currentMove = (row, coins)
   newboard = boardstate[:]
   makeMove(newboard, currentMove)
   if isGameOver(newboard):
    if (None == bestMoveList):
     bestMoveList = [currentMove]
     bestPoints = 100
    continue
   (move, points) = getBestComputerMove(newboard, depth+1)
   if points == 0:
    return (currentMove, 100-points)
   if (None == bestMoveList) or (points < bestPoints):
    bestMoveList = [currentMove]
    bestPoints = points
   elif points == bestPoints:
    bestMoveList.append(currentMove)

 bestMove = strategyClass.getBestMove(boardstate, bestMoveList)
 return (bestMove, 100-bestPoints)

def getBestComputerMove(boardstate, depth):
 global strategyClass
 bestMoveList = None
 bestPoints = None
 for row in [1, 2, 3]:
  for coins in range(boardstate[row-1], 0, -1):
   currentMove = (row, coins)
   newboard = boardstate[:]
   makeMove(newboard, currentMove)
   if isGameOver(newboard):
    if (None == bestMoveList):
     bestMoveList = [currentMove]
     bestPoints = 100
    continue
   (move, points) = simulatePlayerMove(newboard, depth+1)
   if points == 0:
    return (currentMove, 100)
   if (None == bestMoveList) or (points < bestPoints):
    bestMoveList = [currentMove]
    bestPoints = points
   elif points == bestPoints:
    bestMoveList.append(currentMove)

 bestMove = strategyClass.getBestMove(boardstate, bestMoveList)
 return (bestMove, 100-bestPoints)

def doComputerMove(boardstate):
 (bestMove, status) = getBestComputerMove(boardstate, 0)
 boardstate = makeMove(boardstate, bestMove)
 displayMove("Computer", bestMove)

###########################################################################################
#
#   Main Program

# Change this to the strategy you want the computer to use
strategyClass = FilterStrategy()

boardstate = [3, 5, 7]
printWelcomeScreen()
playfirst = raw_input("Do you want to play first? (Y/N) : ")
if len(playfirst) == 0:
 playfirst = "Y"
if playfirst[0].upper() == "Y":
 firstMove = doPlayerMove
 firstWinner = PLAYER_1_WINNER
 secondMove = doComputerMove
 secondWinner = COMPUTER_WINNER
else:
 firstMove = doComputerMove
 firstWinner = COMPUTER_WINNER
 secondMove = doPlayerMove
 secondWinner = PLAYER_1_WINNER

winner = GAME_NOT_OVER
while True:
 drawboard(boardstate)
 firstMove(boardstate)
 if isGameOver(boardstate):
  winner = secondWinner
  break
 drawboard(boardstate)
 secondMove(boardstate)
 if isGameOver(boardstate):
  winner = firstWinner
  break

displayWinner(winner)