pallanguli.py

   1 # the classic Indian pallanguli game AI
   2 # http://library.thinkquest.org/26408/data/texts/34079638.shtml
   3
   4 import sys
   5
   6 __author__ = 'Sridhar Ratnakumar <http://nearfar.org/>'
   7
   8 BOARD_SIZE = 7
   9 SEEDS_PER_CUP = 5
  10
  11 MAXSEEDS = BOARD_SIZE * SEEDS_PER_CUP
  12 MAXDEPTH = 4
  13
  14
  15 class Player(object):
  16
  17     def __init__(self, store):
  18         self.store = store # number of seeds on player's store
  19
  20     def clone(self):
  21         return Player(self.store)
  22
  23     def distribute(self):
  24         "Distribute the seeds from my pristine store to the cups in the board."
  25         seeds = self.store
  26
  27         if seeds > MAXSEEDS:
  28             seeds = MAXSEEDS
  29
  30         for index in range(seeds/SEEDS_PER_CUP):
  31             self.store -= SEEDS_PER_CUP
  32             yield index
  33
  34     def give(self, seeds):
  35         self.store += len(list(seeds))
  36
  37     def __str__(self):
  38         return '<Player: %d seeds>' % self.store
  39
  40
  41 class Board(list):
  42
  43     @staticmethod
  44     def create(player1, player2):
  45         ll = [None] * (BOARD_SIZE*2)
  46
  47         for player, offset in [(player1, 0),
  48                                (player2, BOARD_SIZE)]:
  49             for index in player.distribute():
  50                 ll[offset + index] = SEEDS_PER_CUP
  51
  52         return Board(ll)
  53
  54     def clone(self):
  55         return Board(self)
  56
  57     def pick(self, cup):
  58         "Pick all the seeds from `cup` and yield them one by one"
  59         seeds = self[cup]
  60         if seeds == 0:
  61             raise EmptyCup
  62
  63         self[cup] = 0
  64         for index in range(seeds):
  65             yield index
  66
  67     def next(self, index):
  68         index += 1
  69         while self[index] == None:
  70             index += 1
  71         return index
  72
  73     def count(self):
  74         "Return the count of seeds on both sides of the board"
  75         return (sum([n for n in self[:BOARD_SIZE] if n is not None]),
  76                 sum([n for n in self[BOARD_SIZE:] if n is not None]))
  77
  78     def __getitem__(self, index):
  79         if type(index) is not slice: # __getslice__ too calls this function
  80             index = index % len(self)
  81         return super(Board, self).__getitem__(index)
  82
  83     def __setitem__(self, index, value):
  84         index = index % len(self)
  85         super(Board, self).__setitem__(index, value)
  86
  87     def __str__(self):
  88         "Draw the board"
  89         def fill(stars):
  90             # return ('*' * stars) + ('_' * (SEEDS_PER_CUP-stars))
  91             if stars is None:
  92                 return ' X'
  93             else:
  94                 return '%2d' % stars
  95
  96         return 'B: %s\n   %s\nA: %s\n' % (
  97             ' | '.join([fill(n) for n in self[:BOARD_SIZE-1:-1]]),
  98             '-' * 32,
  99             ' | '.join([fill(n) for n in self[:BOARD_SIZE]]))
 100
 101
 102 class EmptyCup(Exception): pass
 103
 104 class NoPossibleTurn(Exception): pass
 105
 106 def minimax(game, player, depth):
 107     if game.endGame(player) or depth == 0:
 108         return game.evaluate(player)
 109
 110     if player is True:
 111         beta = - sys.maxint
 112         for cgame in game.allMoves(player):
 113             beta = max(beta, minimax(cgame, not player, depth-1))
 114         return beta
 115     else:
 116         alpha = sys.maxint
 117         for cgame in game.allMoves(player):
 118             alpha = min(alpha, minimax(cgame, not player, depth-1))
 119         return alpha
 120
 121
 122 class Game(object):
 123     """
 124     The Pallanguli Game object.
 125
 126     Player A is the good player represented by `True`
 127     Player B is the bad player represented by `False`
 128     """
 129
 130     def __init__(self, pA, pB, board, parentIndex):
 131         self.pA, self.pB = pA, pB
 132         self.parentIndex = parentIndex
 133         self.players = {True: pA, False: pB}
 134         self.board = board or Board.create(pA, pB)
 135
 136     def clone(self, index):
 137         return Game(self.pA.clone(),
 138                     self.pB.clone(),
 139                     self.board.clone(),
 140                     parentIndex = index)
 141
 142     def cupOwner(self, index):
 143         if (index % len(self.board)) < BOARD_SIZE:
 144             return self.players[True]
 145         else:
 146             return self.players[False]
 147
 148     def allMoves(self, playerIndex):
 149         index = -1
 150         if playerIndex is False:
 151             index += BOARD_SIZE
 152
 153         player = self.players[playerIndex]
 154         moves = []
 155
 156         while True:
 157             index = self.board.next(index)
 158             if self.cupOwner(index) is not player:
 159                 break # we invaded the other player's cups
 160
 161             if self.board[index] == 0:
 162                 continue # no seeds to pick; skip
 163
 164             # for each valid cup of mine,
 165             cgame = self.clone(index)
 166             cgame.doTurn(index, cgame.players[playerIndex])
 167             yield cgame
 168
 169     def endGame(self, playerIndex):
 170         if playerIndex:
 171             rack = self.board[:BOARD_SIZE]
 172         else:
 173             rack = self.board[BOARD_SIZE:]
 174
 175         return len([n for n in rack if n is not None and n > 0]) == 0
 176
 177     def evaluate(self, playerIndex):
 178         return self.players[True].store - self.players[False].store
 179
 180     def dopABestTurn(self):
 181         alpha = - sys.maxint
 182         bestIndex = None
 183         for cgame in self.allMoves(True):
 184             value = minimax(cgame, False, MAXDEPTH)
 185             if bestIndex is None or value > alpha:
 186                 bestIndex, alpha = cgame.parentIndex, value
 187         self.doTurn(bestIndex, self.players[True])
 188         return bestIndex
 189
 190     def dopBTurn(self, indexOfpB):
 191         self.doTurn(BOARD_SIZE + indexOfpB, self.players[False])
 192
 193     def doTurn(self, cup, player):
 194         "Do turn for player `player` from cup `cup`"
 195         b = self.board
 196
 197         assert self.cupOwner(cup) is player, \
 198             'Player [%s] must move seed from his side only, not #%d' % \
 199             (player, cup)
 200
 201         # Turn
 202         index = cup
 203         while True:
 204             # pick seeds from cup `index` and distribute it
 205             for offset in b.pick(index):
 206                 index = b.next(index)
 207
 208                 if b[index] != None: # valid cup?
 209                     b[index] += 1
 210
 211                     if b[index] == 4:
 212                         self.cupOwner(index).give(b.pick(index))
 213
 214             index = b.next(index)
 215
 216             if b[index] == 0:
 217                 index = b.next(index)
 218                 if b[index] > 0:
 219                     # if the next cup is empty, pick all seeds from
 220                     # the next-next cup
 221                     player.give(b.pick(index))
 222                     b.next(index)
 223                 # stop playing
 224                 break
 225             else:
 226                 # ..else, continue playing
 227                 continue
 228
 229     def __str__(self):
 230         return '%sA,B: %s, %s\n' % (self.board,
 231                                     self.players[True],
 232                                     self.players[False])
 233
 234
 235 def getFromUser(prompt, default):
 236     q = "%s (%s) " % (prompt, default)
 237     return raw_input(q).strip() or default
 238
 239 def toBool(userInput):
 240     if userInput.lower() in ['y', 'yes', 'yep']:
 241         return True
 242     if userInput.lower() in ['n', 'no', 'nope']:
 243         return False
 244     assert "Invalid userInput for toBool: %s" % userInput
 245
 246 def playPallanguli():
 247     aSeeds = int(getFromUser("Player A's seeds", MAXSEEDS))
 248     bSeeds = int(getFromUser("Player B's seeds", MAXSEEDS))
 249     assert aSeeds + bSeeds == 2*MAXSEEDS
 250
 251     g = Game(Player(aSeeds),
 252              Player(bSeeds),
 253              None,
 254              None)
 255     print g
 256     print 'GAME STARTS'
 257
 258     def askAdversary():
 259         index = int(getFromUser('Adversary chose:', 1))
 260         g.dopBTurn(index-1)
 261         print '--> ADVERSARY picked cup #%d' % index
 262         print g
 263
 264     pBStarts = toBool(getFromUser('Adversary starts?', 'n'))
 265     if pBStarts:
 266         askAdversary()
 267
 268     while True:
 269         index = g.dopABestTurn()
 270         print '--> YOU picked cup #%d' % (index+1)
 271         print g
 272
 273         askAdversary()
 274
 275
 276 if __name__ == '__main__':
 277     playPallanguli()