1

As part of a project, I am trying to implement A* within the context of a pacman game (see UC Berkley pacman ai project). There are no ghosts or capsules, only a maze and the 'fruit'. I am having trouble, however, understanding the relationship between my heuristic function and my cost function.

As per the project, when defining the search problem, we need to specify a step cost that derives from: score = -Nb Steps + 10*NbOfEatenDots + 200*NbOfEatenGhosts + (-500*isLoss) + (500*isWin) This cost is supposed to be always positive and so, for simplicity, I have decided to take: 1.5 - (0.5*AteAFoodDot). I have ignored ghosts and capsules since they do not exist and I have given a preferential score for moves tht end up eating a dot. I have also ignored steps that result in a loss (since they do not exist) and steps that result in a win state.

Now as far as the A* algorithm itself is concerned, we have to implement a cost function and a heuristic function of our own:

As a cost function I have chosen: Cost = sum(step costs to current state) and as a heuristic: h = Manhattan distance between pacman and the dot closest to him + manhattan distance of this dot and another dot that is furthest away from it, as long as it exists, which is an admissible heuristic. I have also implemented this heuristic using real maze distances instead of manhattan distances, but this seemed too time consuming for mazes with many food dots.

Now if I have understood correctly if g(n) is my cost function and h(n) my heuristic, I must always have: g(n to goal) >= h(n) so that A* always returns an optimal path and the closest the values of g and h for a node n, the less nodes will be expanded.

In this respect, is it not in my interest to ignore how the score is computed, ignore the fact that a step results in eating a food dot or not and simply take step_cost = 1 for all steps?

This is how I obtain the best results with respect to computation time and nodes expanded, but ignoring the cost function of the game seems wrong.

Could someone clarify this for me? Is it a matter of rpeference/choice or is there an objective correct answer/best approach?

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.