Implementing an AI controller for Pacman

Question

I'm currently implementing an AI controller class that is being used to determine the moves that ms.pacman should make to collect pills and avoid ghosts. In order to determine which is the best move to make in each state (configuration) of the game, I'm using Breadth-First Search to search the decision tree at each state. I've gotten the controller to work (at least somewhat) for Depth-First Search so I was trying to apply the same logic here.

The idea for DFS was to start with a "root" or driver function which would iterate through the possible moves ms. pacman could make at each state in the decision tree and then make a call to a recursive function that searches the tree to find the terminal state (point at which all pills have been eaten) with the highest value (e.g. highest score). This value is returned from the recursive function and stored in a variable in the root function. The root function the returns the move (out of possible moves) that had the highest value in the tree.

Since BFS is not recursive, I was thinking that it wouldn't be necessary to have a driver function like this, so I decided to put it all in one function. Based on DFS, I'm implementing BFS using a queue which stores all of the neighboring states of the current state and visits each state in FIFO order. Once a state is reached in which all pills have been eaten, the current Move should be returned. I'm not sure if this is the best approach, but its what I could come up with. The problem is that the code for the function takes too long to run and ms.Pacman immediately just goes left and runs into a wall. I'm assuming this is because the terminal state is never being found. Here is the function (in Java):

  public MOVE bfs(Game state){
        EnumMap<GHOST,MOVE> ghostMove = new EnumMap<>(GHOST.class);
        MOVE bestMove = MOVE.NEUTRAL;
        Queue<Game> q = new LinkedList<>();
        q.add(state.copy());
        while(!q.isEmpty()){
            Game current = q.peek();
            q.remove();
            for (MOVE move : current.getPossibleMoves (current.getPacmanCurrentNodeIndex())) {
                Game neighbor = state.copy();
                neighbor.advanceGame(move, ghostMove);
                q.add(neighbor);
                if ((current.getNumberOfActivePills() == 0) && (current.getNumberOfActivePowerPills() == 0)) {
                    return move;
                }

            }
        }
        return bestMove;
    }

Is there anything wrong with the design of the algorithm that could be causing this problem?

Answer 1

You are using brutal force to find the solution, so you can't expect that to run fast.

I'll list some improvements for you:

• Implement a fitness function which evaluates how good is a node.
• Sort the node list with the next formula: V = p*f + (1-p)*d. p is a constant between 0 and 1. f is the fitness function and d is the actual node depth(not the tree depth, the node depth).
• Be carefull about the fitness function, if you want it to find a solution, it should never evaluate better a worse node, and it should return 0 for a solution node. You can start for example with 1 for all the nodes and 0 for the solution ones, and then start thinking about some penalties to make a decision worse than another in every case by adding some values. For example, if a decision is a move which will kill the character, you can set that value to infinite. Another example, a move which take a ball is better than a move that doesn't take it. It is just a example, think about it and you will find more examples.
• You should also take in account that you will have invalid moves. For example if you are in front of a wall, you cant move forward.

It is just A* algorithm, it will solve your problem easily.

Pseudo-code:

Node A_Star_Algorithm(Node initial)
{
    List open-nodes;
    List close-nodes;
    open-nodes.add(initial);
    Node actual;
    while(open-nodes is not empty)
    {   
        actual = open-nodes[0];
        open-nodes.erase(0);
        close-nodes.add(actual);
        if(actual is solution)
        {
            return actual-node;
        }
        else
        {
            List new-nodes = getChilds(actual, open-nodes, close-nodes);
            open-nodes.addAll(new-nodes);
            sort(open-nodes, A_STAR_ECUATION); // we sort the open list placing first the smaller values
                                                // this will make that in our next iteration we will analize
                                                // first the best values

        }
    }
    return NULL;
}


const float p = 0.5f // Value between 0 and 1

bool A_STAR_ECUATION(Node A, Node B)
{
    float H_A = p*FITNESS_FUNCTION(Node A) + (1-p)*A.GetCost();
    float H_B = p*FITNESS_FUNCTION(Node B) + (1-p)*B.GetCost();
    return H_A < H_B;
}

List getChilds(Node actual, List open-nodes, List close-nodes)
{
    List childs = getPosibilities(actual);
    for(int i = 0;i<childs.size();i++)
    {
        for(int k = 0;k<open-nodes.size();k++)
        {
            if(open-nodes[k] == childs[i])
            {
                if(childs[i].GetCost() > open-nodes[k].GetCost())
                    childs.remove(i);
                break;
            }
        }
    }
    for(int i = 0;i<childs.size();i++)
    {
        for(int k = 0;k<close-nodes.size();k++)
        {
            if(close-nodes[k] == childs[i])
            {
                if(childs[i].GetCost() > close-nodes[k].GetCost())
                    childs.remove(i);
                break;
            }

        }
    }
    return childs;
}

The cost of a node is the number of moves required to reach it. The initial node for example is 0, and his childs have cost 1. The childs of this childs have cost 2....

The p value is for give more importance to the heuristic or to the cost of the node. In this case i chose to give equal importance, but if your heuristic is good, you can increase this value from 0.5f to 0.8f for example.

If your heuristic is admissible, which means that it doesn't give better values to nodes which are worse than anothers, it will find the best solution.

Answer 2

This algorithm assumes that the game state progresses unavoidably towards an end state. However, it is possible for ms pac-man to move around (e.g. in a circle); with ghosts chasing her, whilst no pills are being consumed. If this happens, the algorithm will not terminate.

So, I think you have to figure out a way to detect (or avoid) cycles. There are better ways to prevent cycles, but I think the simplest way is to limit the number of moves (doing something like the code below).

 ...
 while(!q.isEmpty()){
        Game current = q.peek();
        q.remove();
        if (q.moveCount() < MAX_MOVES) {
            for ...
 ...

If you want to consider a alternative way to tackle this problem, have a look at behaviour trees, and work in the A* algorithm to aid behaviour decisions and improve behaviour actions.