Flickr Badge

Sunday, October 02, 2005

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)


This post is a part of the selected archive.

1 comment:

Anonymous said...

hi i'm looking for the solution of how to always wqin this game. does anyone know the answer?