# Blended ROI/intercept team for CS470 Assignment 3.
from captureAgents import CaptureAgent
import heapq
import random
from game import Directions
from util import nearestPoint
def createTeam(firstIndex, secondIndex, isRed,
first='BlendedCourierAgent',
second='PortalInterceptAgent'):
return [globals()[first](firstIndex), globals()[second](secondIndex)]
class LayoutAgent(CaptureAgent):
DIRECTIONS = (
(Directions.NORTH, (0, 1)),
(Directions.SOUTH, (0, -1)),
(Directions.EAST, (1, 0)),
(Directions.WEST, (-1, 0)),
)
def registerInitialState(self, gameState):
self.start = gameState.getAgentPosition(self.index)
self.width = gameState.data.layout.width
self.height = gameState.data.layout.height
self.compactLayout = self.width <= 22 and self.height <= 8
CaptureAgent.registerInitialState(self, gameState)
self.homeEntries = self.computeHomeEntries(gameState)
self.patrolEntries = self.computePatrolEntries()
def getSuccessor(self, gameState, action):
successor = gameState.generateSuccessor(self.index, action)
pos = successor.getAgentState(self.index).getPosition()
if pos != nearestPoint(pos):
return successor.generateSuccessor(self.index, action)
return successor
def computeHomeEntries(self, gameState):
walls = gameState.getWalls()
x = self.width // 2 - 1 if self.red else self.width // 2
entries = []
for y in range(1, self.height - 1):
if not walls[x][y]:
entries.append((x, y))
return entries or [self.start]
def computePatrolEntries(self):
entries = sorted(self.homeEntries, key=lambda p: p[1])
if len(entries) <= 2:
return entries
lower = entries[max(0, len(entries) // 3)]
upper = entries[min(len(entries) - 1, (2 * len(entries)) // 3)]
if lower == upper:
return [entries[len(entries) // 2]]
return [lower, upper]
def chooseBestAction(self, gameState, scorer):
actions = gameState.getLegalActions(self.index)
values = [scorer(action) for action in actions]
bestValue = max(values)
bestActions = [a for a, v in zip(actions, values) if v == bestValue]
if Directions.STOP in bestActions and len(bestActions) > 1:
bestActions.remove(Directions.STOP)
return random.choice(bestActions)
def minDistance(self, pos, targets):
if pos is None or not targets:
return 0
return min(self.getMazeDistance(pos, target) for target in targets)
def nearestTarget(self, pos, targets):
if pos is None or not targets:
return None
return min(targets, key=lambda target: self.getMazeDistance(pos, target))
def activeGhostPositions(self, gameState):
positions = []
for opponent in self.getOpponents(gameState):
enemy = gameState.getAgentState(opponent)
pos = enemy.getPosition()
if pos is not None and not enemy.isPacman and enemy.scaredTimer <= 1:
positions.append(nearestPoint(pos))
return positions
def activeGhostDistances(self, gameState, pos):
if pos is None:
return []
return [self.getMazeDistance(pos, ghost) for ghost in self.activeGhostPositions(gameState)]
def visibleInvaders(self, gameState):
enemies = [gameState.getAgentState(i) for i in self.getOpponents(gameState)]
return [enemy for enemy in enemies if enemy.isPacman and enemy.getPosition() is not None]
def reversePenalty(self, gameState, action, amount=3):
reverse = Directions.REVERSE[gameState.getAgentState(self.index).configuration.direction]
return amount if action == reverse else 0
def isOpen(self, pos, walls):
x, y = pos
return 0 <= x < self.width and 0 <= y < self.height and not walls[x][y]
def neighborPositions(self, pos, walls):
x, y = pos
result = []
for action, (dx, dy) in self.DIRECTIONS:
nxt = (x + dx, y + dy)
if self.isOpen(nxt, walls):
result.append((action, nxt))
return result
def firstPlannedAction(self, gameState, target, avoidGhosts=True):
start = gameState.getAgentPosition(self.index)
if start is None or target is None:
return None
start = nearestPoint(start)
target = nearestPoint(target)
if start == target:
return None
walls = gameState.getWalls()
ghosts = self.activeGhostPositions(gameState) if avoidGhosts else []
frontier = []
bestCost = {start: 0}
counter = 0
heapq.heappush(frontier, (self.getMazeDistance(start, target), 0, counter, start, None))
limit = self.width * self.height * 4
while frontier and counter < limit:
priority, cost, _, pos, firstAction = heapq.heappop(frontier)
if cost != bestCost.get(pos):
continue
if pos == target:
return firstAction
for action, nxt in self.neighborPositions(pos, walls):
stepCost = 1 + self.plannerRisk(nxt, ghosts)
newCost = cost + stepCost
if newCost >= bestCost.get(nxt, 999999):
continue
counter += 1
bestCost[nxt] = newCost
first = action if firstAction is None else firstAction
heapq.heappush(frontier, (
newCost + self.getMazeDistance(nxt, target),
newCost,
counter,
nxt,
first
))
return None
def plannerRisk(self, pos, ghosts):
risk = 0
for ghost in ghosts:
distance = self.getMazeDistance(pos, ghost)
if distance <= 1:
risk += 90
elif distance <= 2:
risk += 35
elif distance <= 5:
risk += 6 * (6 - distance)
return risk
def likelyDied(self, gameState, successor):
oldState = gameState.getAgentState(self.index)
newState = successor.getAgentState(self.index)
oldPos = oldState.getPosition()
newPos = newState.getPosition()
if oldState.isPacman and newPos == self.start and oldPos != self.start:
return True
if oldState.numCarrying > 0 and newState.numCarrying == 0:
return self.getScore(successor) <= self.getScore(gameState)
return False
def compactRoleAction(self, gameState):
self.updateCompactLastEatenFood(gameState)
mode = self.compactTeamMode(gameState)
role = self.compactRole(gameState, mode)
targets = self.compactTargets(gameState, mode, role)
avoidDanger = role in ('offense', 'conservative')
action = self.firstActionToTargets(gameState, targets, avoidDanger)
if action is not None:
return action
if avoidDanger:
action = self.firstActionToTargets(gameState, targets, False)
if action is not None:
return action
return self.compactFallbackAction(gameState, targets, role)
def compactTeamMode(self, gameState):
invaders = self.visibleInvaders(gameState)
maxCarry = max([invader.numCarrying for invader in invaders] or [0])
score = self.getScore(gameState)
timeLeft = gameState.data.timeleft
if len(invaders) >= 2 or maxCarry >= 3:
return 'defense'
if score < -5 and not invaders:
return 'offense'
if score > 5 or timeLeft < 150:
return 'conservative'
return 'split'
def compactRole(self, gameState, mode):
if mode == 'split':
team = sorted(self.getTeam(gameState))
if self.index == team[0]:
return 'offense'
return 'defense'
return mode
def compactTargets(self, gameState, mode, role):
if role == 'defense':
return self.compactDefenseTargets(gameState)
if role == 'conservative':
return self.compactConservativeTargets(gameState)
return self.compactOffenseTargets(gameState, mode)
def compactOffenseTargets(self, gameState, mode):
myState = gameState.getAgentState(self.index)
myPos = gameState.getAgentPosition(self.index)
food = self.getFood(gameState).asList()
capsules = self.getCapsules(gameState)
homeDistance = self.minDistance(myPos, self.homeEntries)
ghosts = self.activeGhostDistances(gameState, myPos)
closestGhost = min(ghosts) if ghosts else None
returnThreshold = 4 if mode == 'offense' else 3
shouldReturn = (
myState.numCarrying >= returnThreshold or
len(food) <= 2 or
(myState.numCarrying > 0 and closestGhost is not None and closestGhost <= 5) or
gameState.data.timeleft < homeDistance + 24
)
if shouldReturn:
return self.sortedTargets(myPos, self.homeEntries)
if capsules and closestGhost is not None and closestGhost <= 5:
return self.sortedTargets(myPos, capsules)
if food:
return self.compactFoodTargets(myPos, food)
return self.sortedTargets(myPos, self.homeEntries)
def compactFoodTargets(self, myPos, food):
if myPos is None:
return list(food)[:4]
scored = []
for target in food:
distance = self.getMazeDistance(myPos, target)
homeDepth = self.minDistance(target, self.homeEntries)
cluster = 0
for other in food:
if other != target and abs(target[0] - other[0]) + abs(target[1] - other[1]) <= 3:
cluster += 1
scored.append((distance + 0.3 * homeDepth - 1.8 * cluster, distance, target))
scored.sort()
return [target for score, distance, target in scored[:4]]
def compactDefenseTargets(self, gameState):
myPos = gameState.getAgentPosition(self.index)
invaders = self.visibleInvaders(gameState)
if invaders:
invaders.sort(
key=lambda invader: (
-invader.numCarrying,
self.getMazeDistance(myPos, invader.getPosition())
)
)
return [invader.getPosition() for invader in invaders]
if getattr(self, 'lastEatenFood', None) is not None:
if myPos is None or self.getMazeDistance(myPos, self.lastEatenFood) > 1:
return [self.lastEatenFood]
self.lastEatenFood = None
return [self.compactPatrolTarget(gameState)]
def compactConservativeTargets(self, gameState):
myState = gameState.getAgentState(self.index)
if self.visibleInvaders(gameState):
return self.compactDefenseTargets(gameState)
if myState.numCarrying > 0 or myState.isPacman:
return self.sortedTargets(gameState.getAgentPosition(self.index), self.homeEntries)
return [self.compactPatrolTarget(gameState)]
def compactPatrolTarget(self, gameState):
myPos = gameState.getAgentPosition(self.index)
if getattr(self, 'lastEatenFood', None) is not None:
if myPos is None or self.getMazeDistance(myPos, self.lastEatenFood) > 1:
return self.lastEatenFood
self.lastEatenFood = None
team = sorted(self.getTeam(gameState))
rank = team.index(self.index) if self.index in team else 0
if self.patrolEntries:
return self.patrolEntries[rank % len(self.patrolEntries)]
targetY = self.height * (rank + 1) / float(len(team) + 1)
return min(self.homeEntries, key=lambda p: abs(p[1] - targetY))
def updateCompactLastEatenFood(self, gameState):
if not hasattr(self, 'lastEatenFood'):
self.lastEatenFood = None
previous = self.getPreviousObservation()
if previous is None:
return
previousFood = set(self.getFoodYouAreDefending(previous).asList())
currentFood = set(self.getFoodYouAreDefending(gameState).asList())
eaten = list(previousFood - currentFood)
if eaten:
myPos = gameState.getAgentPosition(self.index)
if myPos is None:
self.lastEatenFood = eaten[0]
else:
self.lastEatenFood = min(eaten, key=lambda p: self.getMazeDistance(myPos, p))
def sortedTargets(self, pos, targets):
if pos is None:
return list(targets)
return sorted(targets, key=lambda target: self.getMazeDistance(pos, target))
def firstActionToTargets(self, gameState, targets, avoidDanger):
if not targets:
return None
start = gameState.getAgentPosition(self.index)
if start is None:
return None
start = nearestPoint(start)
targetSet = set(nearestPoint(target) for target in targets if target is not None)
if not targetSet:
return None
legalActions = [a for a in gameState.getLegalActions(self.index) if a != Directions.STOP]
random.shuffle(legalActions)
walls = gameState.getWalls()
danger = self.activeGhostPositions(gameState)
queue = []
visited = set([start])
for action in legalActions:
nxt = self.nextPosition(start, action)
if not self.isOpen(nxt, walls):
continue
if avoidDanger and self.isDangerous(nxt, danger):
continue
if nxt in targetSet:
return action
queue.append((nxt, action))
visited.add(nxt)
head = 0
while head < len(queue):
pos, firstAction = queue[head]
head += 1
for action, (dx, dy) in self.DIRECTIONS:
nxt = (pos[0] + dx, pos[1] + dy)
if nxt in visited or not self.isOpen(nxt, walls):
continue
if avoidDanger and self.isDangerous(nxt, danger):
continue
if nxt in targetSet:
return firstAction
visited.add(nxt)
queue.append((nxt, firstAction))
return None
def nextPosition(self, pos, action):
for direction, (dx, dy) in self.DIRECTIONS:
if direction == action:
return (pos[0] + dx, pos[1] + dy)
return pos
def isDangerous(self, pos, dangerPositions):
for danger in dangerPositions:
if abs(pos[0] - danger[0]) + abs(pos[1] - danger[1]) <= 1:
return True
return False
def compactFallbackAction(self, gameState, targets, role):
def scorer(action):
successor = self.getSuccessor(gameState, action)
myState = successor.getAgentState(self.index)
pos = myState.getPosition()
value = 120 * self.getScore(successor)
if targets and pos is not None:
value -= self.minDistance(pos, targets)
if role in ('offense', 'conservative'):
ghosts = self.activeGhostDistances(successor, pos)
if ghosts:
closest = min(ghosts)
if myState.isPacman and closest <= 1:
value -= 1000
else:
value += min(closest, 5)
if myState.isPacman and role == 'defense':
value -= 500
if action == Directions.STOP:
value -= 100
value -= self.reversePenalty(gameState, action, 3)
return value
return self.chooseBestAction(gameState, scorer)
class BlendedCourierAgent(LayoutAgent):
def chooseAction(self, gameState):
if self.compactLayout:
return self.compactRoleAction(gameState)
target, returning = self.chooseTarget(gameState)
action = self.firstPlannedAction(gameState, target, True)
if action is not None and not self.badFirstStep(gameState, action):
return action
return self.chooseBestAction(gameState, lambda a: self.scoreAction(gameState, a, target, returning))
def chooseTarget(self, gameState):
myState = gameState.getAgentState(self.index)
myPos = myState.getPosition()
food = self.getFood(gameState).asList()
home = self.nearestTarget(myPos, self.homeEntries)
ghosts = self.activeGhostDistances(gameState, myPos)
closestGhost = min(ghosts) if ghosts else None
if myState.numCarrying > 0:
if myState.numCarrying >= self.carryThreshold(gameState):
return home, True
if myState.isPacman and closestGhost is not None and closestGhost <= 5:
return home, True
if gameState.data.timeleft < self.minDistance(myPos, self.homeEntries) + 24:
return home, True
if len(food) <= 2 or not food:
return home, True
capsules = self.getCapsules(gameState)
if capsules and closestGhost is not None and closestGhost <= 5 and myState.isPacman:
return self.nearestTarget(myPos, capsules), False
return self.bestFoodTarget(gameState, myPos, food), False
def carryThreshold(self, gameState):
if self.compactLayout:
return 1
if self.getScore(gameState) >= 3:
return 2
if self.width >= 30 and self.height >= 15:
return 4
return 3
def bestFoodTarget(self, gameState, myPos, food):
ghosts = self.activeGhostPositions(gameState)
scored = []
for target in food:
distance = self.getMazeDistance(myPos, target)
homeDistance = self.minDistance(target, self.homeEntries)
cluster = self.foodClusterBonus(target, food)
risk = self.foodRisk(target, distance, ghosts)
overlap = self.teammateOverlapPenalty(gameState, target, distance)
cost = distance + 0.55 * homeDistance + risk + overlap - cluster
scored.append((cost, distance, homeDistance, target))
scored.sort()
return scored[0][3]
def foodClusterBonus(self, target, food):
bonus = 0.0
for other in food:
if other == target:
continue
distance = abs(target[0] - other[0]) + abs(target[1] - other[1])
if distance <= 2:
bonus += 2.2
elif distance <= 4:
bonus += 1.0
elif distance <= 6:
bonus += 0.35
return min(7.5, bonus)
def foodRisk(self, target, myDistance, ghosts):
risk = 0.0
for ghost in ghosts:
ghostDistance = self.getMazeDistance(ghost, target)
margin = ghostDistance - myDistance
if margin <= 0:
risk += 18.0 + min(12.0, -margin * 2.0)
elif margin <= 2:
risk += 8.0 - 2.0 * margin
elif margin <= 4:
risk += 2.0
return min(38.0, risk)
def teammateOverlapPenalty(self, gameState, target, myDistance):
penalty = 0.0
for teammate in self.getTeam(gameState):
if teammate == self.index:
continue
pos = gameState.getAgentPosition(teammate)
if pos is None:
continue
teammateDistance = self.getMazeDistance(pos, target)
if teammateDistance + 1 < myDistance:
penalty += 8.0
elif teammateDistance <= myDistance + 1:
penalty += 3.0
return penalty
def badFirstStep(self, gameState, action):
if action == Directions.STOP:
return True
successor = self.getSuccessor(gameState, action)
if self.likelyDied(gameState, successor):
return True
myState = successor.getAgentState(self.index)
ghosts = self.activeGhostDistances(successor, myState.getPosition())
return myState.isPacman and ghosts and min(ghosts) <= 1
def scoreAction(self, gameState, action, target, returning):
successor = self.getSuccessor(gameState, action)
myState = successor.getAgentState(self.index)
myPos = myState.getPosition()
food = self.getFood(successor).asList()
ghosts = self.activeGhostDistances(successor, myPos)
closestGhost = min(ghosts) if ghosts else None
value = 250 * self.getScore(successor)
value -= 105 * len(food)
if target is not None:
value -= 4 * self.getMazeDistance(myPos, target)
homeDistance = self.minDistance(myPos, self.homeEntries)
if returning or myState.numCarrying > 0:
value -= (12 + 3 * myState.numCarrying) * homeDistance
if closestGhost is not None:
value += 2 * closestGhost
if myState.isPacman and closestGhost <= 2:
value -= 1200 * (3 - closestGhost)
elif myState.isPacman and closestGhost <= 5:
value -= 210
if action == Directions.STOP:
value -= 500
value -= self.reversePenalty(gameState, action, 5)
if self.likelyDied(gameState, successor):
value -= 9000
return value
class PortalInterceptAgent(LayoutAgent):
def registerInitialState(self, gameState):
LayoutAgent.registerInitialState(self, gameState)
self.lastEatenFood = None
self.currentTarget = self.choosePatrolTarget(gameState)
self.mode = 'patrol'
def chooseAction(self, gameState):
if self.compactLayout:
return self.compactRoleAction(gameState)
self.updateLastEatenFood(gameState)
self.currentTarget, self.mode = self.chooseTarget(gameState)
if self.mode == 'support':
action = self.firstPlannedAction(gameState, self.currentTarget, True)
if action is not None and not self.badSupportStep(gameState, action):
return action
return self.chooseBestAction(gameState, lambda a: self.scoreDefenseAction(gameState, a))
def chooseTarget(self, gameState):
invader = self.primaryInvader(gameState)
if invader is not None:
myPos = gameState.getAgentPosition(self.index)
invaderPos = invader.getPosition()
portal = self.nearestTarget(invaderPos, self.homeEntries)
distToInvader = self.getMazeDistance(myPos, invaderPos)
invaderToPortal = self.getMazeDistance(invaderPos, portal)
catchSoon = distToInvader <= 2 or distToInvader <= invaderToPortal
nearEscape = invaderToPortal <= max(4, self.width // 6)
atPortal = self.getMazeDistance(myPos, portal) <= 1
if catchSoon or (invader.numCarrying < 2 and atPortal and distToInvader <= invaderToPortal + 2):
return invaderPos, 'chase'
if invader.numCarrying >= 2 or nearEscape or invaderToPortal < distToInvader:
return portal, 'hold'
return invaderPos, 'chase'
if self.lastEatenFood is not None:
myPos = gameState.getAgentPosition(self.index)
if myPos is not None and self.getMazeDistance(myPos, self.lastEatenFood) <= 1:
self.lastEatenFood = None
else:
return self.lastEatenFood, 'inspect'
supportTarget = self.chooseSupportTarget(gameState)
if supportTarget is not None:
return supportTarget, 'support'
return self.choosePatrolTarget(gameState), 'patrol'
def chooseSupportTarget(self, gameState):
if self.compactLayout or gameState.data.timeleft <= 260:
return None
myState = gameState.getAgentState(self.index)
myPos = myState.getPosition()
if myPos is None:
return None
if myState.numCarrying > 0:
return self.nearestTarget(myPos, self.homeEntries)
if self.getScore(gameState) > 0 and gameState.data.timeleft > 500:
return None
ghosts = self.activeGhostDistances(gameState, myPos)
if myState.isPacman and ghosts and min(ghosts) <= 5:
return self.nearestTarget(myPos, self.homeEntries)
food = self.getFood(gameState).asList()
if not food:
return None
target = min(
food,
key=lambda p: (
self.getMazeDistance(myPos, p) + self.minDistance(p, self.homeEntries),
self.getMazeDistance(myPos, p)
)
)
roundTrip = self.getMazeDistance(myPos, target) + self.minDistance(target, self.homeEntries)
if roundTrip > self.width + 6:
return None
return target
def scoreDefenseAction(self, gameState, action):
successor = self.getSuccessor(gameState, action)
myState = successor.getAgentState(self.index)
myPos = myState.getPosition()
target = self.currentTarget or self.choosePatrolTarget(successor)
targetDistance = self.getMazeDistance(myPos, target)
value = 0
if self.mode == 'support':
value += 400 * self.getScore(successor)
value -= 18 * targetDistance
if myState.numCarrying > 0:
value -= 25 * self.minDistance(myPos, self.homeEntries)
ghosts = self.activeGhostDistances(successor, myPos)
if myState.isPacman and ghosts and min(ghosts) <= 5:
value -= 900 * (6 - min(ghosts))
else:
if myState.isPacman:
value -= 1200
value -= 12 * targetDistance
invaders = self.visibleInvaders(successor)
if invaders:
closest = min(self.getMazeDistance(myPos, inv.getPosition()) for inv in invaders)
if self.mode == 'chase':
value -= 10 * closest
if closest <= 1 and myState.scaredTimer == 0:
value += 500
if myState.scaredTimer > 0 and closest <= 2:
value -= 250
if action == Directions.STOP:
if self.mode == 'hold' and targetDistance == 0:
value -= 1
else:
value -= 100
value -= self.reversePenalty(gameState, action, 2)
return value
def badSupportStep(self, gameState, action):
successor = self.getSuccessor(gameState, action)
myState = successor.getAgentState(self.index)
ghosts = self.activeGhostDistances(successor, myState.getPosition())
return myState.isPacman and ghosts and min(ghosts) <= 1
def primaryInvader(self, gameState):
invaders = self.visibleInvaders(gameState)
if not invaders:
return None
myPos = gameState.getAgentPosition(self.index)
return max(
invaders,
key=lambda inv: (
inv.numCarrying,
-self.getMazeDistance(myPos, inv.getPosition())
)
)
def updateLastEatenFood(self, gameState):
previous = self.getPreviousObservation()
if previous is None:
return
previousFood = set(self.getFoodYouAreDefending(previous).asList())
currentFood = set(self.getFoodYouAreDefending(gameState).asList())
eaten = list(previousFood - currentFood)
if eaten:
myPos = gameState.getAgentPosition(self.index)
if myPos is None:
self.lastEatenFood = eaten[0]
else:
self.lastEatenFood = min(eaten, key=lambda p: self.getMazeDistance(myPos, p))
def choosePatrolTarget(self, gameState):
defendingFood = self.getFoodYouAreDefending(gameState).asList()
if not defendingFood:
return random.choice(self.homeEntries)
center = (
sum(x for x, y in defendingFood) / float(len(defendingFood)),
sum(y for x, y in defendingFood) / float(len(defendingFood))
)
base = min(self.homeEntries, key=lambda p: abs(p[0] - center[0]) + abs(p[1] - center[1]))
team = sorted(self.getTeam(gameState))
if self.patrolEntries and self.index in team and len(self.patrolEntries) > 1:
rank = team.index(self.index)
return self.patrolEntries[rank % len(self.patrolEntries)]
return base