# 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
class BlendedCourierAgent(LayoutAgent):
def chooseAction(self, 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) > 1 else 2
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):
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