60 million girls "missing"

The 2005 UNFPA report states that 60 MILLION girls are "missing" in Asia: How to Name It?

In Asia, at least 60 million girls are “missing” due to prenatal sex selection, infanticide or neglect.

[Also see this article :
'I have killed two daughters and will kill more']

Mumbai Free Map Demo

I've been in the mapping mood lately (more on that later) and came across this recently: Mumbai Free Map Demo. It seems to be an attempt to do a Google Maps kind of app for Mumbai.

More information about this is available here.

Also check out this post which outlines the differences with Google Maps.

Flock browser

Check out Flock. According to this BusinessWeek article, Flock has inbuilt support for blogging and putting bookmarks on del.icio.us and many more features. Sounds cool. Now we only have to see whether it really does all this or if it's just another startup trying to take advantage of the "Web 2.0" meme.

Mousepad Upgrade

I finally upgraded (if you can call it that) my mousepad. This weekend, I bought the func surface 1030 to replace the Everglide Gaming Mat that I'd been using for the last three years.

Visions of Science

Check out this list of 10 images from the Visions of Science Photographic Awards : In pictures | Visions of Science

3-5-7 (Part 2)

I wrote about the board game 3-5-7 in my previous post.

I wrote this program to as an experiment in AI. A simple board game seemed to be a good way to start. The program implements the minimax algorithm for determining the best move.

3-5-7 is a simple game, so the program can explore the entire problem search space. This means that if there is a winning move, the computer will find it.

3-5-7 also has a clear winner. Unlike tic-tac-toe, draws are not possible. Therefore, if there is no guaranteed winning move available, then the opponent has a guaranteed winning move irrespective of the move you make. In particuler, the player playing first has a winning move, so the first player cannot lose if the player plays a perfect game. Make a mistake however, and player 2 has a winning move.

When the computer has no winning move and is guaranteed to lose irrespective of the move it plays (provided the player plays perfectly), then how does it choose which move to make? Against an experienced player who knows how to play a perfect game, it does not make a difference which move is played. However, against a novice, some moves are more adept at inducing mistakes.

This is where the Strategy classes come into play. The program implements two strategy classes - RandomStrategy and FilterStrategy. RandomStrategy randomly chooses a move. FilterStrategy gets rid of moves that leave the board in obvious states, and chooses from the remaining moves. This has the effect of increasing the chance that the novice player will make a mistake and give the computer a winning move.

To implement other algorithms for choosing a losing strategy, we just need to implement another strategy class and set the strategyClass variable in the first line of the main program to point to this class.

The boardstate variable is initialised to [3, 5, 7] in the main program. We can change this to try playing with different number of coins. Change it to [21, 23, 25] and we can see how slow the AI is because it no longer becomes feasible to search the whole tree. An interesting evolution would be to limit the depth of the tree searched by the AI and see how it performs. Pruning the search and implementing heuristics are other possible improvements.

One interesting technique to learn the perfect moves is to play the computer against itself. Start two instances of the game. Play first in one, and play second in the other. Feed in the moves played by the computer in the first game as the player move in the second game, and vice verca (in effect playing the computer against itself). Soon, you will get a hang of the better moves.

This post is a part of the selected archive.

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.

How IBM Conned My Execs Out Of Millions

Interesting link: How IBM Conned My Execs Out Of Millions