1 Replies - 1296 Views - Last Post: 29 March 2013 - 01:14 PM Rate Topic: -----

#1 richard333  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 29-March 13

Iterative Deepening PacMan

Posted 29 March 2013 - 09:45 AM

Hi All,

I am trying to do something that implements the following... any ideas would be greatful. I have looked through online tutorials for Iterative Deepening and anything I have tried to implement has ultimatly lead to my code crashing (an by that I mean the whole computer)

Use iterative deepening to gradually increase the depth level at which the game tree is cut off. In this way, the algorithm can keep track of the best move found so far, which means that the search for an optimal move can be ended at any point. Use this idea to ensure that the ghosts take at most 300ms to choose their (combined) move.
public class PacMan Ghost extends GhostPlayer {

    static State lastStateProcessed;
    static List<Move> lastStateMove;

    public Move chooseMove(Game game, int ghostIndex) {
        State state = game.getCurrentState();
        if (!state.equals(lastStateProcessed)) {
            Set<List<Move>> ghostMoves = Game.getLegalCombinedGhostMoves(state);
            List<Move> bestMove = null;
            double bestScore = 0;
            for (List<Move> m : ghostMoves) {
                State next = Game.getNextState(state, m);
                int score = getMinScore(next, 10, Integer.MIN_VALUE, Integer.MAX_VALUE);
                if (bestMove == null || score > bestScore) {
                    bestMove = m;
                    bestScore = score;
                }
            }
            lastStateProcessed = state;
            lastStateMove=bestMove;
        }        
        return lastStateMove.get(ghostIndex);
    }

    private int getMinScore(State s, int depth, int alpha, int beta) {
        if (depth == 0 || Game.isFinal(s))
            return evaluateState(s);
        List<Move> pacmanMoves = Game.getLegalPacManMoves(s);
        int res = Integer.MAX_VALUE;
        for (Move move : pacmanMoves) {
            State next = Game.getNextState(s, move);
            int score = getMaxScore(next, depth - 1, alpha, beta);
            res = Math.min(res, score);
            beta = Math.min(beta, score);
            if (beta <= alpha)
                break;
        }
        return res;
    }

    private int getMaxScore(State s, int depth, int alpha, int beta) {
        if (depth == 0 || Game.isFinal(s))
            return evaluateState(s);
        Set<List<Move>> ghostMoves = Game.getLegalCombinedGhostMoves(s);
        int res = Integer.MIN_VALUE;
        for (List<Move> move : ghostMoves) {
            State next = Game.getNextState(s, move);
            int score = getMinScore(next, depth - 1, alpha, beta);
            res = Math.max(res, score);
            alpha = Math.max(alpha, score);
            if (beta <= alpha)
                break;
        }
        return res;
    }

    public int evaluateState(State s) {
        int score = 5000;
        if (Game.isLosing(s))
            score+= 10000;
        if (Game.isWinning(s))
            score-=10000;        
        Location pacManLocation = s.getPacManLocation();

        List<Location> ghostLocations = s.getGhostLocations();
        int minX = 1000;
        int maxX = -1000;
        int minY = 1000;
        int maxY = -1000;
        for (int i = 0; i < ghostLocations.size(); i++) {
            Location loc = ghostLocations.get(i);
            score -= Location.euclideanDistance(pacManLocation, loc);
            minX = Math.min(minX,loc.getX());
            maxX = Math.max(maxX,loc.getX());
            minY = Math.min(minY,loc.getY());
            maxY = Math.max(maxY,loc.getY());

        }
        if(minX<=pacManLocation.getX() && maxX>=pacManLocation.getX())
            score+=1;
        if(minY<=pacManLocation.getY() && maxY>=pacManLocation.getY())
            score+=1;
        return score;
    }   
}


Is This A Good Question/Topic? 0
  • +

Replies To: Iterative Deepening PacMan

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2205
  • View blog
  • Posts: 5,239
  • Joined: 10-September 10

Re: Iterative Deepening PacMan

Posted 29 March 2013 - 01:14 PM

I'm going to suggest this be moved to the Gaming thread. You'll probably have better luck there.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1