Merge branch 'develop'HEAD1.0.0main

4 files changed, 182 insertions, 26 deletions

diff --git a/.gitignore b/.gitignore
index 510c73d..326c50e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -112,3 +112,5 @@ dmypy.json
 
 # Pyre type checker
 .pyre/
+
+.vscode/settings.json
\ No newline at end of file
diff --git a/.vscode/launch.json b/.vscode/launch.json
index 2cd7062..a637bbe 100644
--- a/.vscode/launch.json
+++ b/.vscode/launch.json
@@ -12,9 +12,11 @@
             "cwd": "${workspaceFolder}/src",
             "args": [
                 "-q",
-                "q3",
-                "--no-graphics",
+                "q7",
                 "--student-code=bustersAgents.py,inference.py",
+                // "--no-graphics",
+                // "--test",
+                // "test_cases/q5/6-ParticleElapse",
             ],
         }
     ]
diff --git a/src/bustersAgents.py b/src/bustersAgents.py
index bfc3035..e7a78a3 100644
--- a/src/bustersAgents.py
+++ b/src/bustersAgents.py
@@ -163,15 +163,26 @@ class GreedyBustersAgent(BustersAgent):
             [beliefs for i, beliefs in enumerate(self.ghostBeliefs)
              if livingGhosts[i+1]]
         "*** YOUR CODE HERE ***"
-        actionValues = util.Counter()
-        
+
+        # initialize variables
+        maxAction = None
+        minDistance = float("inf")
+
+        # for every legal action
         for action in legal:
+            # get the successor
             successorPosition = Actions.getSuccessor(pacmanPosition, action)
+            # for every position distribution of each ghost
             for ghostPosDist in livingGhostPositionDistributions:
+                # take the largest position as our ghost position
                 ghostPos = ghostPosDist.argMax()
+                # get the distance between the ghost position and where pacman will be after his action
                 distance = self.distancer.getDistance(ghostPos, successorPosition)
                 
-                if distance != 0:
-                    actionValues[action] += 75/distance
+                # update the max action if the calculated distance will get him closer
+                if maxAction is None or distance <= minDistance:
+                    maxAction = action
+                    minDistance = distance
 
-        return actionValues.argMax()
+        # return the max action
+        return maxAction
diff --git a/src/inference.py b/src/inference.py
index 862dc79..ceabde3 100644
--- a/src/inference.py
+++ b/src/inference.py
@@ -149,23 +149,28 @@ class ExactInference(InferenceModule):
         pacmanPosition = gameState.getPacmanPosition()
 
         "*** YOUR CODE HERE ***"
-        # Replace this code with a correct observation update
-        # Be sure to handle the "jail" edge case where the ghost is eaten
-        # and noisyDistance is None
-        allPossible = util.Counter()
-        for oldPos in self.legalPositions:
+
+        # initialize
+        PossibleGhostLocations = util.Counter()
+
+        # for each legal position
+        for position in self.legalPositions:
+            # if there is no noisyDistance, then a ghost is in jail
             if noisyDistance == None:
+                # update the ghost location to be consistent
                 jailEdge = self.getJailPosition()
-                allPossible[jailEdge] = 1.0
+                PossibleGhostLocations[jailEdge] = 1.0
             else:
-                trueDistance = util.manhattanDistance(oldPos, pacmanPosition)
-                if emissionModel[trueDistance] > 0:
-                    allPossible[oldPos] = emissionModel[trueDistance] * self.beliefs[oldPos]
+                # get the distance between pacman and the posible ghost
+                distance = util.manhattanDistance(position, pacmanPosition)
+                if emissionModel[distance] > 0:
+                    # update the possible location using the emission model and beliefs
+                    PossibleGhostLocations[position] = emissionModel[distance] * self.beliefs[position]
 
         "*** END YOUR CODE HERE ***"
 
-        allPossible.normalize()
-        self.beliefs = allPossible
+        PossibleGhostLocations.normalize()
+        self.beliefs = PossibleGhostLocations
 
     def elapseTime(self, gameState):
         """
@@ -222,16 +227,23 @@ class ExactInference(InferenceModule):
         """
         "*** YOUR CODE HERE ***"
         pacmanPos = gameState.getPacmanPosition()
-        allPossible = util.Counter()
+        PossibleGhostLocations = util.Counter()
         
+        # iterate through every possible position 
         for oldPos in self.legalPositions:
             # newPostDist[p] = Pr( ghost is at position p at time t + 1 | ghost is at position oldPos at time t )
+            # get the distribution of possible positions from the current position 
             newPosDist = self.getPositionDistribution(self.setGhostPosition(gameState, oldPos))
+            
+            # add the new position and probability of each position to the beliefs
             for newPos, prob in newPosDist.items():
-                allPossible[newPos] = allPossible[newPos] + prob * self.beliefs[oldPos]
+                PossibleGhostLocations[newPos] = PossibleGhostLocations[newPos] + prob * self.beliefs[oldPos]
+
+        # normalize the new beliefs
+        PossibleGhostLocations.normalize()
 
-        allPossible.normalize()
-        self.beliefs = allPossible
+        # set the current beliefs to the new beliefs
+        self.beliefs = PossibleGhostLocations
 
     def getBeliefDistribution(self):
         return self.beliefs
@@ -266,6 +278,14 @@ class ParticleFilter(InferenceModule):
         weight with each position) is incorrect and may produce errors.
         """
         "*** YOUR CODE HERE ***"
+        # Create a new list
+        self.particles = []
+        
+        # Loop numParticle times
+        for i in range(self.numParticles):
+            # Create a new particle by getting a position looping through the legal positions 
+            self.particles.append(self.legalPositions[i % len(self.legalPositions) - 1])
+        
 
     def observe(self, observation, gameState):
         """
@@ -298,7 +318,40 @@ class ParticleFilter(InferenceModule):
         emissionModel = busters.getObservationDistribution(noisyDistance)
         pacmanPosition = gameState.getPacmanPosition()
         "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        
+        # initialize
+        PossibleGhostLocations = util.Counter()
+        
+        # if there is no noisyDistance, then a ghost is in jail
+        if noisyDistance == None:
+            # update particles with jail position
+            for i in range(self.numParticles):
+                self.particles[i] = self.getJailPosition()
+        else:
+            # get the beliefs distribution
+            beliefs = self.getBeliefDistribution()
+            # for each legal position
+            for pos in self.legalPositions:
+                # get the distance between pacman and the posible ghost
+                distance = util.manhattanDistance(pos, pacmanPosition)
+                if emissionModel[distance] > 0:
+                    # update the possible location using the emission model and beliefs
+                    PossibleGhostLocations[pos] = emissionModel[distance] * beliefs[pos]
+
+            # if all particles drop to 0, then need to reinitialize
+            if PossibleGhostLocations.totalCount() == 0:
+                self.initializeUniformly(gameState)
+            # otherwise, update particles with PossibleGhostLocations
+            else:
+                # update the ghost location to be consistent
+                self.particles = util.nSample(PossibleGhostLocations.values(), PossibleGhostLocations.keys(), self.numParticles)
+
+        
+
+
+
+
+
 
     def elapseTime(self, gameState):
         """
@@ -315,7 +368,19 @@ class ParticleFilter(InferenceModule):
         a belief distribution.
         """
         "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        particles = list()
+        
+        # iterate through each particles 
+        for oldPos in self.particles:
+            # get the distribution of possible positions from the current position 
+            newPosDist = self.getPositionDistribution(self.setGhostPosition(gameState, oldPos))
+            
+            # create a new particle by taking a sample of the distribution 
+            particles.append(util.nSample(newPosDist.values(), newPosDist.keys(), 1)[0])
+
+        # set the current particles to the new particles
+        self.particles = particles
+
 
     def getBeliefDistribution(self):
         """
@@ -325,7 +390,18 @@ class ParticleFilter(InferenceModule):
         Counter object)
         """
         "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        
+        # initialize a new counter
+        BeliefDis = util.Counter()
+
+        # loop through each particle
+        for particle in self.particles:
+            # initialize the weight of each particle to 1
+            BeliefDis[particle] += 1.0
+
+        # normalize the weights
+        BeliefDis.normalize()
+        return BeliefDis
 
 class MarginalInference(InferenceModule):
     """
@@ -398,6 +474,17 @@ class JointParticleFilter:
         weight with each position) is incorrect and may produce errors.
         """
         "*** YOUR CODE HERE ***"
+        
+        # initialize
+        self.particles = []
+
+        # using the itertools helper function, create a cross product between each legal position and ghost
+        product = list(itertools.product(self.legalPositions, repeat=self.numGhosts))
+        # the product needs to be randomly shuffled
+        random.shuffle(product)
+        for i in range(self.numParticles):
+            # append the cross product as a new particle to the list of particles
+            self.particles.append(product[i % len(product) - 1])
 
     def addGhostAgent(self, agent):
         """
@@ -445,6 +532,40 @@ class JointParticleFilter:
         emissionModels = [busters.getObservationDistribution(dist) for dist in noisyDistances]
 
         "*** YOUR CODE HERE ***"
+        # initialize a counter of ghost locations
+        PossibleGhostLocations = util.Counter()
+
+        # loop through the particles
+        for particle in self.particles:
+            # initialize the particle's weight to 1
+            belief = 1.0
+
+            # loop through each ghost 
+            for i in range(self.numGhosts):
+                
+                # if there is no noisyDistance, then a ghost is in jail
+                if noisyDistances[i] == None:
+                    # update particles with jail position
+                    particle = self.getParticleWithGhostInJail(particle, i)
+                else:
+                    # get the distance between pacman and the current ghost's particle
+                    trueDistance = util.manhattanDistance(particle[i], pacmanPosition)
+                    # update ghost's the possible location using the emission model and beliefs
+                    belief *= emissionModels[i][trueDistance]
+            
+            # sum the belief of each ghost being at the particle
+            PossibleGhostLocations[particle] += belief 
+
+        # if all particles drop to 0, then need to reinitialize
+        if PossibleGhostLocations.totalCount() == 0:
+            self.initializeParticles()
+
+        else:
+            
+            # otherwise, normalize and update particles with PossibleGhostLocations
+            PossibleGhostLocations.normalize()
+            for i in range(self.numParticles):
+                self.particles[i] = util.sample(PossibleGhostLocations)
 
     def getParticleWithGhostInJail(self, particle, ghostIndex):
         """
@@ -506,13 +627,33 @@ class JointParticleFilter:
 
             "*** YOUR CODE HERE ***"
 
+            # iterate through each ghost 
+            for i in range(self.numGhosts):
+                # get the distribution of possible positions for the current ghost from the current position 
+                newPosDist = getPositionDistributionForGhost(
+                    setGhostPositions(gameState, newParticle), i, self.ghostAgents[i]
+                )
+                # set the ghost's position in the new particle by taking a sample of the distribution 
+                newParticle[i] = util.nSample(newPosDist.values(), newPosDist.keys(), 1)[0]
+
             "*** END YOUR CODE HERE ***"
             newParticles.append(tuple(newParticle))
         self.particles = newParticles
 
     def getBeliefDistribution(self):
         "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        
+        # initialize a new counter
+        BeliefDis = util.Counter()
+
+        # loop through each particle
+        for particle in self.particles:
+            # initialize the weight of each particle to 1
+            BeliefDis[particle] += 1.0
+
+        # normalize the weights
+        BeliefDis.normalize()
+        return BeliefDis
 
 # One JointInference module is shared globally across instances of MarginalInference
 jointInference = JointParticleFilter()