# Quantum Go Fish. 10/21/2011 # # The idea of Quantum Go Fish was introduced to Dave Penneys by Scott Morrison and Noah Snyder at # the subfactor ski retreat in 2009 or 2010. The rules given at # # http://stacky.net/wiki/index.php?title=Quantum_Go_Fish # # were distilled by Anton Geraschenko and Dave Penneys from many games among Berkeley math grads. # # The following implementation was written by Dave Penneys with special guest Mark Fuge. ################################################################################################ # A Hand has two type of cards: knownCards and uncertainCards. # uncertainCards are lists of possible values. # known cards are integers in a list. import copy import random def testRandom(n): count = 0 for i in range(0,n): if random.random() > .5: count += 1 return float(count)/float(n) class Hand(object): def __init__(self, numberOfPlayers, cardsPerHand, manual = None): self.manual = manual if self.manual == None: self.knownCards = [] self.uncertainCards = [] for i in range(0,cardsPerHand): self.uncertainCards.append(range(0,numberOfPlayers)) else: self.knownCards = manual[0] self.uncertainCards = manual[1] def hasCard(self, value): return (value in self.knownCards) def canHaveCard(self, value): canHaveCard = False if self.hasCard(value): canHaveCard = True else: for card in self.uncertainCards: if value in card: canHaveCard = True return canHaveCard def collapseCard(self, value): if len(self.uncertainCards) > 0: self.uncertainCards = self.uncertainCards[:-1] self.knownCards.append(value) self.knownCards.sort() def giveCard(self, value): assert self.canHaveCard(value) if self.hasCard(value): self.knownCards.remove(value) else: self.uncertainCards.remove(self.uncertainCards[0]) def takeCard(self,value): assert self.hasCard(value) self.knownCards.append(value) self.knownCards.sort() def getUncertainCards(self): return self.uncertainCards def getUncertainty(self): return len(self.getUncertainCards()) def hasUncertainCards(self): return self.getUncertainty()>0 def removeSuit(self,value): for card in self.uncertainCards: try: card.remove(value) except: pass def setIDNumber(self,idNumber): self.idNumber = idNumber def getIDNumber(self): try: return self.idNumber except: print "ID number has not been set." def __str__(self): return "known cards: %s, uncertain cards %s" % (self.knownCards,self.uncertainCards) def getHandFeatures(self,numberOfPlayers,cardsPerHand): #TODO use cardsPerSuit AND cardsPerHand. Don't necessarily have to be equal. #TODO add more features! self.uncertainty = self.getUncertainty() if (self.uncertainty): self.possibleSuits = self.getUncertainCards()[0] self.numberOfPossibleSuits = len(self.possibleSuits) self.possibleSuitsHeld = len(set(self.possibleSuits).intersection(set(self.knownCards))) else: self.possibleSuits = None self.numberOfPossibleSuits = 0 self.possibleSuitsHeld = 0 self.possibleSuitsDifference = self.numberOfPossibleSuits - self.possibleSuitsHeld differences = [cardsPerHand-self.knownCards.count(i) for i in range(0,numberOfPlayers)] self.withinTwoBooleanList = [int(element == 2) for element in differences] self.withinOneBooleanList = [int(element == 1) for element in differences] self.allOfAKindBooleanList = [int(element == 0) for element in differences] result = [self.uncertainty,self.numberOfPossibleSuits,self.possibleSuitsDifference] result += self.withinTwoBooleanList result += self.withinOneBooleanList result += self.allOfAKindBooleanList # result has length 3+3(numberOfPlayers) return result ################################################################################################ class State(object): def __init__(self,cardsPerHand,hands,turn,turnsWithoutCollapse): self.cardsPerHand = cardsPerHand self.hands = hands self.turn = turn self.turnsWithoutCollapse = turnsWithoutCollapse self.numberOfPlayers = len(self.hands) self.knownSuits = [False for index in range(0,self.numberOfPlayers)] self.removeSuit() self.calculateCards() self.findUnintentionalCollapses() # self.oldTotalUncertainty def __str__(self): string = "" for hand in self.hands: string += "Player "+str(hand.getIDNumber())+"'s hand: "+str(hand)+"\n" string += "It is currently Player "+str(self.turn)+"'s turn.\n" return string ### first, clean up the state. def removeSuit(self): self.calculateCards() finished = True for value in range(0,self.numberOfPlayers): if not self.knownSuits[value]: if self.totalKnownCards[value]==self.cardsPerHand: finished = False # self.turnsWithoutCollapse = 0 self.knownSuits[value] = True for hand in self.hands: hand.removeSuit(value) return finished def calculateCards(self): self.totalKnownCards = [0 for index in range(0,self.numberOfPlayers)] self.uncertainty = 0 self.totalUncertainCards = [0 for index in range(0,self.numberOfPlayers)] for hand in self.hands: for value in range(0,self.numberOfPlayers): self.totalKnownCards[value] += hand.knownCards.count(value) if hand.hasUncertainCards(): if value in hand.getUncertainCards()[0]: self.totalUncertainCards[value] += len(hand.getUncertainCards()) self.uncertainty += len(hand.getUncertainCards()) self.remainingCards = [0 for index in range(0,self.numberOfPlayers)] for value in range(0,self.numberOfPlayers): self.remainingCards[value] = self.cardsPerHand - self.totalKnownCards[value] def findUnintentionalCollapses(self): # iterate tests until no updates. finished = False while not finished: finished = \ self.removeSuit() and \ self.checkForKnownCards() and \ self.collapseTest1() and \ self.collapseTest2() #and \ #self.collapseTest3() self.calculateCards() def checkForKnownCards(self): self.calculateCards() finished = True for hand in self.hands: uncertainCards = [] for card in hand.uncertainCards: if len(card)==1: finished = False hand.knownCards.append(card[0]) hand.knownCards.sort() else: uncertainCards.append(card) hand.uncertainCards = uncertainCards return finished def collapseTest1(self): # pick a player p with an uncertain card c, and pick a value v that c could be. # let k be how many known cards p has of value v # sum how many v's can be in player q's hand for p\neq q. call this n. # if k+n < 4, then c = v. # iterate over v # iterate over p self.calculateCards() finished = True for hand in self.hands: if hand.hasUncertainCards(): suits = hand.getUncertainCards()[0] for value in suits: # these uncertain cards should not include the player's uncertain cards! if (self.totalKnownCards[value]+self.totalUncertainCards[value]-hand.getUncertainty()) < self.cardsPerHand: finished = False hand.collapseCard(value) return finished def collapseTest2(self): # pick a player p with uncertain cards c_1,\dots, c_n. let v_1,\dots,v_m be the possible values of c_i. # for each i=1,\dots,m, let k_i be the # of known cards p has of value v_i. # let N_i = k_i + sum_{q\neq p} Number of known v_i in q's hand. # let R_i = (cardsPerSuit=cardsPerHand=4)-N_i. # now iterate through j=1,\dots,m: # let T_j = sum_{i\neq j} R_i. if n>T_j, then n-T_j of the c_i must be v_j. # iterate over p. self.calculateCards() finished = True for hand in self.hands: if hand.hasUncertainCards(): numberUncertain = len(hand.getUncertainCards()) suits = hand.getUncertainCards()[0] for value in suits: totalNotLikeValue = 0 for otherValue in suits: if otherValue != value: totalNotLikeValue += self.remainingCards[otherValue] for iterations in range(0,numberUncertain - totalNotLikeValue): finished = False hand.collapseCard(value) return finished def collapseTest3(self): # suppose there are n players. # checks whether k players have all the cards of k suits, # then removes the k suits from the other n-k players. # does case k=2. # this test collapses the following case: #Player 0's hand: known cards: [0], uncertain cards [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] #Player 1's hand: known cards: [1], uncertain cards [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] #Player 2's hand: known cards: [2, 2], uncertain cards [[2, 3], [2, 3]] #Player 3's hand: known cards: [3, 3], uncertain cards [[2, 3], [2, 3]] # #For some reason, adding this collapse test makes everything really slow! self.calculateCards() finished = True for hand0 in self.hands: if hand0.hasUncertainCards(): if len(hand0.getUncertainCards()[0]) == 2: uncertainCards0 = hand0.getUncertainCards() uncertainSuits = uncertainCards0[0] numberKnownOfUncertainSuits = self.totalKnownCards[uncertainSuits[0]]+self.totalKnownCards[uncertainSuits[1]] for hand1 in self.hands: if (hand1.getUncertainCards() == uncertainCards0) and (hand1 is not hand0): uncertainCards1 = hand1.getUncertainCards() numberUncertainForBoth = (len(uncertainCards0)+len(uncertainCards1)) if (numberKnownOfUncertainSuits+numberUncertainForBoth) == 2*self.cardsPerHand: finished = False for hand2 in self.hands: if hand2 not in [hand0,hand1]: hand2.removeSuit(uncertainCards0[0][0]) hand2.removeSuit(uncertainCards0[0][1]) return finished return finished ### Next, calculate all legal actions. def getAllowedResponses(self,askedPlayer,value): #askedPlayer is a number # this is hard-wired into game.confrontation if self.hands[askedPlayer].hasCard(value): return ["yes"] elif self.hands[askedPlayer].canHaveCard(value): return ["yes","no"] else: return ["no"] def findBestResponse(self,askedPlayerNumber,value): #askedPlayer is a number #finds best response for asked player. allowedResponses = self.getAllowedResponses(askedPlayerNumber,value) if allowedResponses == ["yes","no"]: ## if random.random() > .5: ## return "yes" ## else: ## return "no" possibleStates = [self.getNextStates(askedPlayerNumber,value,response) for response in allowedResponses] possibleStateValues = [state.getValueOfState(askedPlayerNumber,self.weights) for state in possibleStates] if possibleStateValues[0] > possibleStateValues[1]: return "yes" else: return "no" else: return allowedResponses[0] def getAllowedActions(self): #todo enumerates all actions it can take #returns pairs [player,suit] hand = self.hands[self.turn] actions = [] valuesToAskFor = [] for value in range(0,self.numberOfPlayers): if hand.canHaveCard(value): valuesToAskFor.append(value) for otherHand in self.hands: if otherHand is not hand: for value in valuesToAskFor: if otherHand.canHaveCard(value): actions.append([otherHand.idNumber,value]) return actions def findBestAction(self): player = self.turn allowedActions = self.getAllowedActions() possibleStates = [] for action in allowedActions: askedPlayer = action[0] value = action[1] response = self.findBestResponse(askedPlayer,value) possibleStates.append(self.getNextStates(askedPlayer,value,response)) possibleStateValues = [state.getValueOfState(player,self.weights) for state in possibleStates] actionPairs = zip(possibleStateValues,allowedActions) actionPairs.sort() return actionPairs.pop()[1] def getValueOfState(self,player,weights): #player is a number #any player should be able to calculate the value of a state to them. features = self.permuteFeatures(player) total = 0 for w,f in zip(weights,features): total += w*f return total ###################### #Copying states def copyState(self): return copy.deepcopy(self) def getNextStates(self,askedPlayerNumber,value,response): newState = self.copyState() newState.transformState(askedPlayerNumber,value,response) return newState def transformState(self,askedPlayerNumber,value,response):# = None): #askedPlayer is now a number #response is in [None,"yes","no"] hand = self.hands[self.turn] askedHand = self.hands[askedPlayerNumber] if not hand.hasCard(value): hand.collapseCard(value) self.findUnintentionalCollapses() if askedHand.canHaveCard(value): if askedHand.hasCard(value): askedHand.giveCard(value) hand.takeCard(value) else: ## if response == None: ## response = self.players[askedPlayer].decideResponse(value,self.state) if response is "no": askedHand.removeSuit(value) else: #response is "yes" askedHand.giveCard(value) hand.takeCard(value) ## else: ## if response == None: ## print "Player "+str(hand.idNumber)+" has collapsed the last "+str(value)+\ ## ". Hence Player "+str(askedHand.idNumber)+" cannot have a "+str(value)+"." self.findUnintentionalCollapses() ###################### #Features! def setWeights(self,weights): self.weights = weights def getWhoHasWhatSuit(self): self.whoHasWhatSuit = [[] for value in range(0,self.numberOfPlayers)] for value in range(0,self.numberOfPlayers): for hand in self.hands: if hand.canHaveCard(value): self.whoHasWhatSuit[value].append(hand.idNumber) return self.whoHasWhatSuit def getPairFeatures(self): existsSuitForOnlyTwo = [[0 for value1 in range(0,self.numberOfPlayers)] \ for value2 in range(0,self.numberOfPlayers)] whoHasWhatSuit = self.getWhoHasWhatSuit() for value in range(0,self.numberOfPlayers): if len(whoHasWhatSuit[value]) is 2: player0 = whoHasWhatSuit[value][0] player1 = whoHasWhatSuit[value][1] existsSuitForOnlyTwo[player0][player1] = 1 existsSuitForOnlyTwo[player1][player0] = 1 return existsSuitForOnlyTwo def calculateFeatures(self): #self.whoseTurn = game.state[0] self.playersFeatures = [hand.getHandFeatures(self.numberOfPlayers,self.cardsPerHand) \ for hand in self.hands] # self.playersFeatures has length (3+3(numberOfPlayers))numberOfPlayers self.pairFeatures = self.getPairFeatures() # self.pairFeatures has length (numberOfPlayers)^2 #TODO add more features, like: #did game collapse when it's your turn? #did game collapse on someone else's turn? #do you have 4 of a kind on your turn? #do you have no cards left? #does someone else have uncertainty i can collapse? #can a person be removed from game? pass def permuteFeatures(self,playerNumber): # playerNumber is a player.idNumber # returns a long vector... self.calculateFeatures() playersFeatures = self.playersFeatures[playerNumber:]+self.playersFeatures[:playerNumber] #print ("playersFeatures",playersFeatures) pairFeatures = [[] for value in range(0,self.numberOfPlayers)] for index in range(0,self.numberOfPlayers): pairFeatures[index] = self.pairFeatures[index][playerNumber:]+self.pairFeatures[index][:playerNumber] pairFeatures = self.pairFeatures[playerNumber:]+self.pairFeatures[:playerNumber] #print ("pairFeatures",pairFeatures) result = [] for entry in playersFeatures: result += entry for entry in pairFeatures: result += entry # adding total uncertainty at the end twice. # [1,0] if it's collapsed on your turn, # [0,1] if it's collapsed on not your turn. if (self.uncertainty == 0): if (self.turn == playerNumber): result += [1,0] else: result += [0,1] else: result += [0,0] # length of result is (3+2(numberOfPlayers))numberOfPlayers + (numberOfPlayers)^2 # = 3(numberOfPlayers)^2+3(numberOfPlayers) # when numberOfPlayers == 4, we get 3(4)^2+3(4) = 3*16+12=60 return result ################################################################################################ # a player has an ID number and a hand. # it has 2 methods decideResponse and decideAction class Player(object): def __init__(self, idNumber, hand): self.hand = hand self.idNumber = idNumber hand.setIDNumber(idNumber) self.computerPlayer = False def __str__(self): return "Player %d" % self.getIDNumber() def isComputerPlayerQ(self): return self.computerPlayer def getIDNumber(self): return self.idNumber def getHand(self): return self.hand def decideResponse(self, value, state): while True: decision = raw_input(str(self)+', do you have a '+str(value)+'? ') if decision in ['yes','Yes','YES','y','Y']: return 'yes' elif decision in ['no','No','NO','n','N']: return 'no' else: print str(self)+", please answer 'yes' or 'no'." def decideAction(self,state): askedPlayer = int(raw_input(str(self)+', from which player will you ask for a card? ')) value = int(raw_input('which card do you want to ask for? ')) return [askedPlayer,value] ################################################################################################ # TODO: make computer player better with reinforcement learning class ComputerPlayer(Player): def __init__(self,idNumber,hand): super(ComputerPlayer, self).__init__(idNumber,hand) self.computerPlayer = True def decideResponse(self, value, state): response = state.findBestResponse(self.idNumber,value) print (str(self)+" replied "+response) return response def decideAction(self,state): action = state.findBestAction() print (str(self)+" asked Player "+str(action[0])+" for a "+str(action[1])+'.') return action ################################################################################################ class Game(object): def __init__(self, cardsPerHand = 4): self.cardsPerHand = cardsPerHand def loadState(self,state = None): if state is not None: self.state = state self.numberOfPlayers = len(state.hands) else: self.numberOfPlayers,numberOfComputerPlayers = self.howManyPlayersQ() numberOfHumanPlayers = self.numberOfPlayers - numberOfComputerPlayers self.state = State(self.cardsPerHand, [Hand(self.numberOfPlayers,self.cardsPerHand) for i in range(0,self.numberOfPlayers)],0,0) self.players = [Player(i,self.state.hands[i]) for i in range(0,numberOfHumanPlayers)]+\ [ComputerPlayer(i,self.state.hands[i]) for i in range(numberOfHumanPlayers,self.numberOfPlayers)] def loadWeights(self): #run loadState first weightLength = 3*(self.numberOfPlayers)**2+3*self.numberOfPlayers try: weightFile = open('QGFWeights'+str(self.numberOfPlayers),'r') self.weights = pickle.load(weightFile) weightFile.close() except: self.weights = [] for index in range (0,3+2*self.numberOfPlayers): self.weights.append(1) for index in range (0,self.numberOfPlayers): self.weights.append(100) for playerIndex in range(0,self.numberOfPlayers-1): for index in range (0,(3+2*self.numberOfPlayers)): self.weights.append(-1) for index in range (0,self.numberOfPlayers): self.weights.append(-100) for index in range (0,self.numberOfPlayers): self.weights.append(-1) for index in range (0,self.numberOfPlayers*(self.numberOfPlayers-1)): self.weights.append(-1) #add weights for collapsing uncertainty self.weights += [300,-300] self.state.setWeights(self.weights) #TODO: update weights with reinforcement learning def __str__(self): for player in self.players: print str(player)+"'s hand: "+str(player.hand) print "It is Player "+str(self.turn)+"'s turn." def howManyPlayersQ(self): while True: numberOfPlayers = int(raw_input('How many players? Must be 2-6. ')) numberOfComputerPlayers = int(raw_input('How many are computer players? Must be 0-'+str(numberOfPlayers)+'. ')) if (numberOfPlayers in range(2,7)) and (numberOfComputerPlayers in range(0,numberOfPlayers+1)): return [numberOfPlayers,numberOfComputerPlayers] def getState(self): return self.state # ways you can win------------------------------------------------------------ # if after your turn all is collapsed, then you win. # if not, if some player can prove they have 4 of a kind, they win. # the strong win is if the player can prove they have 4 of a kind, but they cannot prove which suit it is. def gameCollapsed(self): return (self.state.uncertainty == 0) def strongWinQ(self,player): if player.hand.hasUncertainCards(): uncertainSuits = player.hand.getUncertainCards()[0] strongWinTotal = 0 for suit in uncertainSuits: strongWinTotal += player.hand.knownCards.count(suit) if (strongWinTotal + player.hand.getUncertainty()) >= (len(uncertainSuits)*(self.cardsPerHand-1)+1): return True return False def allOfAKindQ(self,player): for value in range(0,self.state.numberOfPlayers): if player.hand.knownCards.count(value) == self.cardsPerHand: return True return False def turnsWithoutCollapseQ(self): if self.state.turnsWithoutCollapse >= (self.numberOfPlayers)*3: return True return False # the actual game-------------------------------------------------------- def nextAction(self, player): while True: print str(player)+"'s allowed actions: [player,card]" allowedActions = self.state.getAllowedActions() print allowedActions [askedPlayer,value] = player.decideAction(self.state) if [askedPlayer,value] in allowedActions: return [askedPlayer,value] else: print str(player)+", please choose an allowed action." def confrontation(self, player, askedPlayer, value): #TODO: clean up this code and that of State.transformState() playerHand = self.state.hands[player] askedPlayerHand = self.state.hands[askedPlayer] if not playerHand.hasCard(value): playerHand.collapseCard(value) self.state.findUnintentionalCollapses() if askedPlayerHand.canHaveCard(value): if askedPlayerHand.hasCard(value): askedPlayerHand.giveCard(value) playerHand.takeCard(value) else: #pass state to askedPlayer to calculate features response = self.players[askedPlayer].decideResponse(value,self.state) if response is 'no': askedPlayerHand.removeSuit(value) elif response is 'yes': askedPlayerHand.giveCard(value) playerHand.takeCard(value) # this case can only happen if when player asks for value, it collapses the last of the value cards. else: print str(player)+' has collapsed the last '+str(value)+\ '. Hence '+str(askedPlayer)+' cannot have a '+str(value)+'.' def playGame(self): #turn = 0 while True: print "---------------------------------------------------------" print self.state player = self.players[self.state.turn] if self.state.getAllowedActions() == []: print str(player)+" has no allowed actions, and must forfeit turn." self.state.turn += 1 self.state.turn %= self.numberOfPlayers continue [askedPlayer,value]=self.nextAction(player) self.confrontation(player.getIDNumber(),askedPlayer,value) self.state.findUnintentionalCollapses() if self.turnsWithoutCollapseQ(): print "---------------------------------------------------------" print self.state print "DRAW. 3 rounds without collapsing any uncertainty." return [] if self.gameCollapsed(): print "---------------------------------------------------------" print self.state print "All uncertainty collapsed. "+str(player)+" wins!" return [player.idNumber] else: strongWinners = [] winners = [] for candidate in self.players: if self.strongWinQ(candidate): strongWinners.append(str(candidate)) elif self.allOfAKindQ(candidate): winners.append(str(candidate)) if len(strongWinners)>0: print "---------------------------------------------------------" print self.state print "STRONG WIN. Set of strong winners: "+str(strongWinners)+"." return strongWinners elif len(winners)>0: print '---------------------------------------------------------' print self.state print "ALL OF A KIND. Set of winners: "+str(winners)+"." return winners else: self.state.turn += 1 self.state.turn %= self.state.numberOfPlayers ################################################################################################ if __name__ == '__main__': game = Game() game.loadState() game.loadWeights() game.playGame()