# k a l a h , p y # from copy import copy class Kalah : nextTag = 1 def __init__ (self, board, player, depth=0) : # Board is python list of 14 ints self.board = copy(board) self.stones = sum(self.board) self.half = self.stones/2.0 # over half wins self.player = player self.depth = depth self.alpha = -9999 ## New for extension self.beta = 9999 self.ivalue = 0 # Initial calculated value self.value = 0 # Propogated back from successors self.next = None # Set by func chooseMove self.bestMove = None # Set by func chooseMove self.legalMoves() self.eval() self.tag = Kalah.nextTag Kalah.nextTag += 1 def getBoard(self,loc) : return self.board[loc] def setBoard(self,loc,val) : assert loc >=0 and loc < 14, "setBoard %s" % loc self.board[loc] = val def move(self, loc) : # Clear all locations but put finalVal into last one if self.player=='A' : parms=(0,7) else : parms=(7,0) myKalah,theirKalah=parms board = self.board pebbles = board[loc] board[loc] = 0 inMyPots = True while pebbles : loc += 1 if loc > 13 : loc = 0 if loc == theirKalah : inMyPots=True; loc+=1 if loc == myKalah : inMyPots=False board[loc] += 1 pebbles -= 1 self.legalMoves() if not self.moves : # capture rest to my kalah board[myKalah] += sum(board[myKalah+1:myKalah+7]) board[myKalah+1:myKalah+7] = [0]*6 elif loc == myKalah : pass # get to go again else : # if last pebble hit my empty - it and the opposite # are captured and placed into my kalah opp = 7 + (7-loc) # just opposite if inMyPots : if board[loc] == 1 and board[opp] > 0 : board[myKalah] += board[loc]+board[opp] board[loc] = board[opp] = 0 self.player = self.other() self.legalMoves() self.eval() def other(self) : if self.player == 'A' : return 'B' else : return 'A' def over(self) : b = self.board win1 = (b[0] > self.half or b[7] > self.half) # maj in a kalah win2 = (b[0] + b[7] == self.stones) # all in kalahs return win1 or win2 def eval(self) : # if A ahead - positive values, if B negative if self.board[0] > self.half : val = 100 # Kalah A elif self.board[7] > self.half : val = -100 # Kalah B else : val = self.board[0] - self.board[7] # how far A ahead self.ivalue = self.value = val def legalMoves(self) : moves = [] self.moves = moves firstPot = (1,8)[self.player=='A'] for i in range(6) : if self.board[firstPot+i] > 0 : moves.append(firstPot+i) self.moves = tuple(moves) def maximizing(self) : # Want to maximize value if A, else minimize return (self.player == 'A') def printMe(self, mesg="") : b = list(self.board) # make massagable pots = self.board Apots = (pots[1:7]); Bpots = pots[8:14] Bpots.reverse() print "==============\n%s\n==============" % mesg print "Node=%s Stones=%s Depth=%s" %(self.tag,self.stones,self.depth) print "%s to play. ival=%s value=%s depth=%s moves=%s"% (self.player, self.ivalue,self.value,self.depth,self.moves) print " A %3d%3d%3d%3d%3d%3d" % (tuple(Bpots)) print "%5d %3d" % (pots[0],pots[7]) print " B %3d%3d%3d%3d%3d%3d" % (tuple(Apots)) print nxt = self.next if nxt : nxt.printMe("Next move is %s giving us..." % self.bestMove) def makeGame(perPot=3) : board = [0]+[perPot]*6+[0]+[perPot]*6 print board gNode = Kalah(board, 'A') return gNode def test() : import timeSearch, sys args = sys.argv board = eval(args[1]); player=args[2]; AB=True; maxDepth=int(args[3]) timeSearch.timeSearch(Kalah, board, player, AB, maxDepth) if __name__ == "__main__" : test()