fork(3) download
copy 
  1. # multiAgents.py
  2. # --------------
  3. # Licensing Information: Please do not distribute or publish solutions to this
  4. # project. You are free to use and extend these projects for educational
  5. # purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
  6. # John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
  7. # For more info, see http://i...content-available-to-author-only...y.edu/~cs188/sp09/pacman.html
  8.  
  9. from util import manhattanDistance
  10. from game import Directions
  11. import random, util
  12.  
  13. from game import Agent
  14.  
  15. class ReflexAgent(Agent):
  16.   """
  17.     A reflex agent chooses an action at each choice point by examining
  18. 	its alternatives via a state evaluation function.
  19.  
  20. 	The code below is provided as a guide.  You are welcome to change
  21. 	it in any way you see fit, so long as you don't touch our method
  22. 	headers.
  23.   """
  24.  
  25.  
  26.  
  27.  
  28.   def evaluationFunction(self, currentGameState, action):
  29. 	"""
  30. 	Design a better evaluation function here.
  31.  
  32. 	The evaluation function takes in the current and proposed successor
  33. 	GameStates (pacman.py) and returns a number, where higher numbers are better.
  34.  
  35. 	The code below extracts some useful information from the state, like the
  36. 	remaining food (newFood) and Pacman position after moving (newPos).
  37. 	newScaredTimes holds the number of moves that each ghost will remain
  38. 	scared because of Pacman having eaten a power pellet.
  39.  
  40. 	Print out these variables to see what you're getting, then combine them
  41. 	to create a masterful evaluation function.
  42. 	"""
  43. 	# Useful information you can extract from a GameState (pacman.py)
  44. 	successorGameState = currentGameState.generatePacmanSuccessor(action)
  45. 	newPos = successorGameState.getPacmanPosition()
  46. 	newFood = successorGameState.getFood()
  47. 	newGhostStates = successorGameState.getGhostStates()
  48. 	newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates]
  49.  
  50. 	foodDist = float('inf')
  51. 	for food in newFood.asList():
  52. 		dist = manhattanDistance(food, newPos)
  53. 		if(dist < foodDist):
  54. 			foodDist = dist
  55.  
  56. 	ghostScore = 0
  57. 	for state in newGhostStates:
  58. 		dist = manhattanDistance(newPos, state.getPosition())
  59. 		if dist == 0 and state.scaredTimer > 0:
  60. 			ghostScore += 100000000000
  61. 		elif state.scaredTimer > 0 and dist < state.scaredTimer:
  62. 			ghostScore += (1 / (1 + dist))
  63. 		elif dist < 3:
  64. 			ghostScore -= dist / 100;
  65.  
  66. 	score = 3.0 / (1 + len(newFood.asList())) + ghostScore + 1.0 / (100 + foodDist)
  67.  
  68. 	return score;
  69.  
  70. def scoreEvaluationFunction(currentGameState):
  71.   """
  72. 	This default evaluation function just returns the score of the state.
  73. 	The score is the same one displayed in the Pacman GUI.
  74.  
  75. 	This evaluation function is meant for use with adversarial search agents
  76. 	(not reflex agents).
  77.   """
  78.   return currentGameState.getScore()
  79.  
  80. class MultiAgentSearchAgent(Agent):
  81.   """
  82. 	This class provides some common elements to all of your
  83. 	multi-agent searchers.  Any methods defined here will be available
  84. 	to the MinimaxPacmanAgent, AlphaBetaPacmanAgent & ExpectimaxPacmanAgent.
  85.  
  86. 	You *do not* need to make any changes here, but you can if you want to
  87. 	add functionality to all your adversarial search agents.  Please do not
  88. 	remove anything, however.
  89.  
  90. 	Note: this is an abstract class: one that should not be instantiated.  It's
  91. 	only partially specified, and designed to be extended.  Agent (game.py)
  92. 	is another abstract class.
  93.   """
  94.  
  95.   def __init__(self, evalFn = 'scoreEvaluationFunction', depth = '2'):
  96. 	self.index = 0 # Pacman is always agent index 0
  97. 	self.evaluationFunction = util.lookup(evalFn, globals())
  98. 	self.depth = int(depth)
  99. 	self.moves = 0
  100. 	self.tf = False
  101.  
  102. class MinimaxAgent(MultiAgentSearchAgent):
  103.   """
  104. 	Your minimax agent (question 2)
  105.   """
  106.  
  107.   def getAction(self, gameState):
  108. 	"""
  109. 	  Returns the minimax action from the current gameState using self.depth
  110. 	  and self.evaluationFunction.
  111.  
  112. 	  Here are some method calls that might be useful when implementing minimax.
  113.  
  114. 	  gameState.getLegalActions(agentIndex):
  115. 		Returns a list of legal actions for an agent
  116. 		agentIndex=0 means Pacman, ghosts are >= 1
  117.  
  118. 	  Directions.STOP:
  119. 		The stop direction, which is always legal
  120.  
  121. 	  gameState.generateSuccessor(agentIndex, action):
  122. 		Returns the successor game state after an agent takes an action
  123.  
  124. 	  gameState.getNumAgents():
  125. 		Returns the total number of agents in the game
  126. 	"""
  127. 	"*** YOUR CODE HERE ***"
  128. 	v = float('-inf')
  129. 	nextAction = Directions.STOP
  130. 	for action in gameState.getLegalActions(0):
  131. 		temp = self.minValue(0, 1, gameState.generateSuccessor(0, action))
  132. 		if temp > v and action != Directions.STOP:
  133. 			v = temp
  134. 			nextAction = action
  135.  
  136. 	return nextAction
  137.  
  138.  
  139.   def maxValue(self, depth, agent, state):
  140. 		if depth == self.depth:
  141. 			return self.evaluationFunction(state)
  142. 		else:
  143. 			actions = state.getLegalActions(agent)
  144. 			if len(actions) > 0:
  145. 				v = float('-inf')
  146. 			else:
  147. 				v = self.evaluationFunction(state)
  148. 			for action in actions:
  149. 				s = self.minValue(depth, agent+1, state.generateSuccessor(agent, action))
  150. 				if s > v:
  151. 					v = s
  152. 			return v
  153.  
  154.   def minValue(self, depth, agent, state):
  155. 		if depth == self.depth:
  156. 			return self.evaluationFunction(state)
  157. 		else:
  158. 			actions = state.getLegalActions(agent)
  159. 			if len(actions) > 0:
  160. 				v = float('inf')
  161. 			else:
  162. 				v = self.evaluationFunction(state)
  163.  
  164. 			for action in actions:
  165. 				if agent == state.getNumAgents() - 1:
  166. 					s = self.maxValue(depth+1, 0, state.generateSuccessor(agent, action))
  167. 					if s < v:
  168. 						v = s
  169. 				else:
  170. 					s = self.minValue(depth, agent+1, state.generateSuccessor(agent, action))
  171. 					if s < v:
  172. 						v = s
  173. 			return v
  174.  
  175.  
  176. class AlphaBetaAgent(MultiAgentSearchAgent):
  177.   """
  178. 	Your minimax agent with alpha-beta pruning (question 3)
  179.   """
  180.  
  181.   def getAction(self, gameState):
  182. 	"""
  183. 	  Returns the minimax action using self.depth and self.evaluationFunction
  184. 	"""
  185. 	"*** YOUR CODE HERE ***"
  186. 	v = float('-inf')
  187. 	nextAction = Directions.STOP
  188. 	for action in gameState.getLegalActions(0):
  189. 		temp = self.minValue(0, 1, gameState.generateSuccessor(0, action), float('-inf'), float('inf'))
  190. 		if temp > v and action != Directions.STOP:
  191. 			v = temp
  192. 			nextAction = action
  193.  
  194. 	return nextAction
  195.  
  196.  
  197.   def maxValue(self, depth, agent, state, alpha, beta):
  198. 		if depth == self.depth:
  199. 			return self.evaluationFunction(state)
  200. 		else:
  201. 			actions = state.getLegalActions(agent)
  202. 			if len(actions) > 0:
  203. 				v = float('-inf')
  204. 			else:
  205. 				v = self.evaluationFunction(state)
  206.  
  207. 			for action in actions:
  208. 				v = max(v, self.minValue(depth, agent+1, state.generateSuccessor(agent, action), alpha, beta))
  209. 				if v >= beta:
  210. 					return v
  211. 				alpha = max(v, alpha)
  212. 			return v
  213.  
  214.   def minValue(self, depth, agent, state, alpha, beta):
  215. 		if depth == self.depth:
  216. 			return self.evaluationFunction(state)
  217. 		else:
  218. 			actions = state.getLegalActions(agent)
  219. 			if len(actions) > 0:
  220. 				v = float('inf')
  221. 			else:
  222. 				v = self.evaluationFunction(state)
  223.  
  224. 			for action in actions:
  225. 				if agent == state.getNumAgents() - 1:
  226. 					v = min(v, self.maxValue(depth+1, 0, state.generateSuccessor(agent, action), alpha, beta))
  227. 					if v <= alpha:
  228. 						return v
  229. 					beta = min(v, beta)
  230. 				else:
  231. 					v = min(v, self.minValue(depth, agent+1, state.generateSuccessor(agent, action), alpha, beta))
  232. 					if v <= alpha:
  233. 						return v
  234. 					beta = min(v, beta)
  235. 			return v
  236.  
  237. class ExpectimaxAgent(MultiAgentSearchAgent):
  238.   """
  239. 	Your expectimax agent (question 4)
  240.   """
  241.  
  242.   def getAction(self, gameState):
  243. 	"""
  244. 	  Returns the expectimax action using self.depth and self.evaluationFunction
  245.  
  246. 	  All ghosts should be modeled as choosing uniformly at random from their
  247. 	  legal moves.
  248. 	"""
  249. 	"*** YOUR CODE HERE ***"
  250. 	v = float('-inf')
  251. 	nextAction = Directions.STOP
  252. 	for action in gameState.getLegalActions(0):
  253. 		temp = self.expValue(0, 1, gameState.generateSuccessor(0, action))
  254. 		if temp > v and action != Directions.STOP:
  255. 			v = temp
  256. 			nextAction = action
  257.  
  258. 	return nextAction
  259.  
  260.  
  261.   def maxValue(self, depth, agent, state):
  262. 		if depth == self.depth:
  263. 			return self.evaluationFunction(state)
  264. 		else:
  265. 			actions = state.getLegalActions(agent)
  266. 			if len(actions) > 0:
  267. 				v = float('-inf')
  268. 			else:
  269. 				v = self.evaluationFunction(state)
  270. 			for action in state.getLegalActions(agent):
  271. 				v = max(v, self.expValue(depth, agent+1, state.generateSuccessor(agent, action)))
  272.  
  273. 			return v
  274.  
  275.   def expValue(self, depth, agent, state):
  276. 		if depth == self.depth:
  277. 			return self.evaluationFunction(state)
  278. 		else:
  279. 			v = 0;
  280. 			actions = state.getLegalActions(agent)
  281. 			for action in actions:
  282. 				if agent == state.getNumAgents() - 1:
  283. 					v += self.maxValue(depth+1, 0, state.generateSuccessor(agent, action))
  284. 				else:
  285. 					v += self.expValue(depth, agent+1, state.generateSuccessor(agent, action))
  286. 			if len(actions) != 0:
  287. 				return v / len(actions)
  288. 			else:
  289. 				return self.evaluationFunction(state)
  290.  
  291. def betterEvaluationFunction(currentGameState):
  292.  	"""
  293. 	Your extreme ghost-hunting, pellet-nabbing, food-gobbling, unstoppable
  294. 	evaluation function (question 5).
  295.  
  296. 	DESCRIPTION: <write something here so we know what you did>
  297.   	"""
  298.   	"*** YOUR CODE HERE ***"
  299. 	newPos = currentGameState.getPacmanPosition()
  300. 	newFood = currentGameState.getFood()
  301. 	newGhostStates = currentGameState.getGhostStates()
  302. 	newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates]
  303.  
  304. 	foodDist = 0
  305. 	for food in newFood.asList():
  306. 		dist = manhattanDistance(food, newPos)
  307. 		#print ('dist', dist)
  308. 		foodDist += dist
  309.  
  310. 	score = 0
  311. 	if len(newFood.asList()) == 0:
  312. 		score = 1000000000
  313.  
  314. 	ghostScore = 0
  315. 	if newScaredTimes[0] > 0:
  316. 			 ghostScore += 100.0
  317. 	for state in newGhostStates:
  318. 		dist = manhattanDistance(newPos, state.getPosition())
  319. 		if state.scaredTimer == 0 and dist < 3:
  320. 			ghostScore -= 1.0 / (3.0 - dist);
  321. 		elif state.scaredTimer < dist:
  322. 			ghostScore += 1.0 / (dist)
  323.  
  324. 	score += 1.0 / (1 + len(newFood.asList())) + 1.0 / (1 + foodDist) + ghostScore + currentGameState.getScore()
  325.  
  326. 	return score;
  327.  
  328.  
Runtime error #stdin #stdout 0.15s 10264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/phBYOc
language:
Python 3 (python  3.12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!