CS188 Discussion

elapsed_time.py

def elapseTime(self, gameState):
    """Sample in place, passed the test."""
    pacPos = gameState.getPacmanPosition()
    newParticles = []

    for oldParticle in self.particles:
        newParticle = list(oldParticle)  # A list of ghost positions
        # now loop through and update each entry in newParticle...

        for i in range(self.numGhosts):
            beliefs = self.getPositionDistribution(
                gameState, oldParticle, i, self.ghostAgents[i])

            # Update given pacman position
            jailPos = self.getJailPosition(i)
            beliefs[jailPos] += beliefs[pacPos]
            beliefs[pacPos] = 0.0

            # NOTE: directly sample the most likely ghost position
            # This passed the test!
            newParticle[i] = beliefs.sample()

        newParticles.append(tuple(newParticle))
    self.particles = newParticles


def _elapseTime(self, gameState):
    """
    This method calculates next tuples of ghost positions, and union all the probability.
    It then samples on top of the unioned probability.

    In graphic UI, it converges to the position, but it doesn't pass the test.
    """
    prior = self.getBeliefDistribution()
    # Distribution for each ghost's position
    accumulated_beliefs = DiscreteDistribution()
    pacPos = gameState.getPacmanPosition()

    for particle in self.particles:
        assert len(particle) == self.numGhosts
        prior_p = prior[particle]
        # { pos => p}
        ghosts_p = []
        for i in range(self.numGhosts):
            # NOTE: given the current ghosts, what's the next position distribution
            beliefs = DiscreteDistribution({pos: p * prior_p for pos, p in
                                            self.getPositionDistribution(
                                                gameState, particle, i, self.ghostAgents[i]).items()
                                            })

            # Update given pacman position
            jailPos = self.getJailPosition(i)
            beliefs[jailPos] += beliefs[pacPos]
            beliefs[pacPos] = 0.0
            ghosts_p.append(beliefs)

        for next_positions in list(
                itertools.product(*[set(dist.keys()) for dist in ghosts_p])):
            # P(tuple[gh1 = pos1, gh2 = pos2, gh3 = pos3])
            # equals
            # P(gh1 = pos1) * P(gh2 = pos2) * P(gh2 = pos2)
            p = 1.0
            for i in range(self.numGhosts):
                p *= ghosts_p[i][next_positions[i]]
            accumulated_beliefs[next_positions] = p

    accumulated_beliefs.normalize()

    # Resampling according to global distribution of possible actions
    self.particles = []
    for _ in range(self.numParticles):
        self.particles.append(accumulated_beliefs.sample())

random_choice.py

"""Test to confirm random.shuffle effect."""

from collections import defaultdict
import itertools
import random


def make_samples(l, N=10_000):
    samples = []
    for _ in range(N):
        samples.append(random.choice(l))
    return samples


def to_dist(samples):
    dist = defaultdict(int)
    for s in samples:
        dist[s] += 1
    total = sum(dist.values())
    for k in dist.keys():
        dist[k] /= total
    return dist


def compare_dist(d1, d2):
    diff = {}
    keys = set(d1.keys()).union(set(d1.keys()))
    for k in keys:
        if d1[k] - d2[k] > 1e-3:
            diff[k] = abs(d1[k] - d2[k])

    return diff, sum(diff.values())


if __name__ == "__main__":
    legal_positions = []
    for i in range(10):
        for j in range(10):
            legal_positions.append((i, j))

    possible_positions = list(
        itertools.product(legal_positions, repeat=3))
    shuffled_possible_positions = list(
        itertools.product(legal_positions, repeat=3))
    random.shuffle(shuffled_possible_positions)

    dist_without_shuffle = to_dist(make_samples(possible_positions, 500))
    dist_with_shuffle = to_dist(make_samples(
        shuffled_possible_positions, 500))

    print(compare_dist(dist_with_shuffle, dist_without_shuffle))

sample.py

# Quesiton 5a
def sample(self):
    """
    Draw a random sample from the distribution and return the key, weighted
    by the values associated with each key.

    >>> dist = DiscreteDistribution()
    >>> dist['a'] = 1
    >>> dist['b'] = 2
    >>> dist['c'] = 2
    >>> dist['d'] = 0
    >>> N = 100000.0
    >>> samples = [dist.sample() for _ in range(int(N))]
    >>> round(samples.count('a') * 1.0/N, 1)  # proportion of 'a'
    0.2
    >>> round(samples.count('b') * 1.0/N, 1)
    0.4
    >>> round(samples.count('c') * 1.0/N, 1)
    0.4
    >>> round(samples.count('d') * 1.0/N, 1)
    0.0
    """
    # Built-in failed? Why?
    # return random.choices(list(self.keys()), weights=list(self.values()))
    prob = 0.0
    acc_probs = {}
    for k, v in self.items():
        prob += v
        acc_probs[k] = prob

    p = random.random() * prob
    for k, prob in acc_probs.items():
        if prob > p:
            return k