BreadthFirstSearchSolver.java

package packman;

import static packman.Game.*;

import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class BreadthFirstSearchSolver {

	public static final int THRESHOLD = 3;

	Game game = null;
	Queue<byte[]> queue = new ArrayDeque<byte[]>();

	public static void main(String[] args) throws IOException {
		BreadthFirstSearchSolver solver = new BreadthFirstSearchSolver();
		solver.resolve();
	}

	private void resolve() throws IOException {
		game = new Game(new File(
				"/Users/vvakame/work/eclipse/GDD2010/src/packman/lv1"));
		byte[] work = new byte[0];
		enqueue(work);

		// 評価と新たな枝の探索
		while (queue.size() != 0) {
			byte[] walk = queue.poll();
			game.reset();
			int result = game.evaluate(walk);

			if (result == FINISH) {
				// 幅優先探索なので最初に見つけた解が最適手
				System.out.println(Game.toAnswer(walk));
				System.exit(0);
			} else if (result == DEAD) {
				// 死んでたらポイ
				continue;
			}

			// 足切り 現時点最善手より閾値以内のスコアじゃないとだめぷー
			if (result > 0 && result < (game.maxScore - THRESHOLD)) {
				continue;
			}

			// ここで死んでなければ新たにキューに詰める。
			enqueue(walk);
		}
	}

	private void enqueue(byte[] work) {

		byte[] next = null;
		if (work.length == game.time) {
			return;
		}

		next = Arrays.copyOf(work, work.length + 1);
		next[next.length - 1] = STAY;
		queue.add(next);

		if (game.packman.isUpInvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = UP;
			queue.add(next);
		}
		if (game.packman.isRightIvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = RIGHT;
			queue.add(next);
		}
		if (game.packman.isDownIvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = DOWN;
			queue.add(next);
		}
		if (game.packman.isLeftInvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = LEFT;
			queue.add(next);
		}
	}

	@SuppressWarnings("unused")
	private void enqueue2(byte[] work) {

		byte[] next = null;
		if (work.length == game.time) {
			return;
		}

		// 止まらなくても解けるらしいので刈る
		// next = Arrays.copyOf(work, work.length + 1);
		// next[next.length - 1] = STAY;
		// queue.add(next);

		// if (game.packman.isUpInvasion()) {
		if (game.packman.move != DOWN && game.packman.isUpInvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = UP;
			queue.add(next);
		}
		// if (game.packman.isRightIvasion()) {
		if (game.packman.move != LEFT && game.packman.isRightIvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = RIGHT;
			queue.add(next);
		}
		// if (game.packman.isDownIvasion()) {
		if (game.packman.move != UP && game.packman.isDownIvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = DOWN;
			queue.add(next);
		}
		// if (game.packman.isLeftInvasion()) {
		if (game.packman.move != RIGHT && game.packman.isLeftInvasion()) {
			next = Arrays.copyOf(work, work.length + 1);
			next[next.length - 1] = LEFT;
			queue.add(next);
		}
	}
}

Game.java

package packman;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Game {

	private static final int NONE = 0;
	public static final int WALL = 1 << 1;
	public static final int FOOD = 1 << 2;
	public static final int PACKMAN = 1 << 3;
	public static final int ENEMY_V = 1 << 4;
	public static final int ENEMY_H = 1 << 5;
	public static final int ENEMY_L = 1 << 6;
	public static final int ENEMY_R = 1 << 7;
	public static final int ENEMY_J = 1 << 8;

	public static final char C_NONE = ' ';
	public static final int C_WALL = '#';
	public static final int C_FOOD = '.';
	public static final int C_PACKMAN = '@';
	public static final int C_ENEMY_V = 'V';
	public static final int C_ENEMY_H = 'H';
	public static final int C_ENEMY_L = 'L';
	public static final int C_ENEMY_R = 'R';
	public static final int C_ENEMY_J = 'J';

	public static final int UNDEF = -1;

	public static final int STAY = 0;
	public static final int DOWN = 1;
	public static final int LEFT = 2;
	public static final int RIGHT = 3;
	public static final int UP = 4;

	public static final int DEAD = -1;
	public static final int FINISH = -2;

	public int time = UNDEF;
	public int width = UNDEF;
	public int height = UNDEF;
	public int[][] field;
	public int[][] bkField;
	public int now = 0;
	public int eat = 0;
	public int maxFood = 0;

	public int maxScore = 0;
	public byte[] maxRoute = null;
	public int routePointer = 0;
	public byte[] route = null;

	public File mapFile = null;

	private List<GameCharactor> characters = new ArrayList<GameCharactor>();
	public Packman packman = null;

	public Game(File file) throws IOException {
		mapFile = file;

		firstInit();
		reset();
	}

	private void firstInit() throws FileNotFoundException, IOException {
		time = UNDEF;
		width = UNDEF;
		height = UNDEF;
		field = null;
		now = 0;
		maxFood = 0;
		characters.clear();

		FileInputStream fin = new FileInputStream(mapFile);
		InputStreamReader isr = new InputStreamReader(fin);
		BufferedReader br = new BufferedReader(isr);
		String line = null;
		StringBuilder stb = new StringBuilder();
		while ((line = br.readLine()) != null) {
			if (time == UNDEF) {
				time = Integer.parseInt(line);
			} else if (width == UNDEF) {
				String[] args = line.split(" ");
				width = Integer.parseInt(args[0]);
				height = Integer.parseInt(args[1]);
				bkField = new int[width][height];
			} else {
				stb.append(line);
			}
		}
		int cnt = 0;
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				int point = convToInt(stb.charAt(cnt));
				if (point == PACKMAN) {
					packman = (Packman) factory(point, x, y);

				} else if (point > PACKMAN) {
					GameCharactor character = factory(point, x, y);
					characters.add(character);
				} else if (point == FOOD) {
					maxFood++;
				}
				bkField[x][y] = point;
				cnt++;
			}
		}
	}

	public void reset() {
		now = 0;
		eat = 0;
		packman = null;
		characters.clear();
		field = field != null ? field : new int[width][height];
		route = new byte[time];
		routePointer = 0;

		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				int point = bkField[x][y];
				if (point == PACKMAN) {
					packman = (Packman) factory(point, x, y);

				} else if (point > PACKMAN) {
					GameCharactor character = factory(point, x, y);
					characters.add(character);
				}
				field[x][y] = bkField[x][y];
			}
		}
	}

	public int evaluate(byte walk) {
		addRoute(walk);
		packman.resolve(walk);
		for (GameCharactor chara : characters) {
			chara.resolve();
		}

		// 接触判定
		// キャラを全て動かす
		for (GameCharactor chara : characters) {
			chara.move();
		}
		packman.move();

		// 当たり判定チェック
		for (GameCharactor chara : characters) {
			if (chara.x == packman.x && chara.y == packman.y) {
				return DEAD;
			} else if (chara.old_x == packman.x && chara.x == packman.old_x
					&& chara.y == packman.old_y && chara.old_y == packman.y) {
				return DEAD;
			}
		}

		// 餌の消化とスコア処理
		final int x = packman.x;
		final int y = packman.y;
		if ((field[x][y] & FOOD) != 0) {
			eat++;
			field[x][y] &= ~FOOD;
		}
		now++;

		return eat;
	}

	public int evaluate(byte[] walk) {
		int result = 0;
		for (int i = 0; i < walk.length; i++) {
			result = evaluate(walk[i]);
			if (result < 0) {
				return result;
			}
		}

		updateMax();

		if (maxFood == maxScore || maxRoute != null && time < maxRoute.length) {
			String ans = toAnswer(maxRoute);
			System.out.println(ans);
			return FINISH;
		}

		return eat;
	}

	public void updateMax() {
		if (maxScore < eat) {
			maxScore = eat;
			maxRoute = route;
			System.out.print(String.valueOf(now) + " "
					+ String.valueOf(maxScore) + " ");
			String ans = toAnswer(maxRoute);
			System.out.println(ans);
		}
	}

	public int getScore() {
		if (maxFood != eat) {
			return eat;
		} else {
			return eat + time - now;
		}
	}

	private void addRoute(byte walk) {
		route[routePointer] = walk;
		routePointer++;
	}

	@SuppressWarnings("unused")
	private void addRoute(byte[] walks) {
		for (byte walk : walks) {
			route[routePointer] = walk;
			routePointer++;
		}
	}

	private GameCharactor factory(int kind, int x, int y) {
		switch (kind) {
		case PACKMAN:
			return new Packman(x, y);
		case ENEMY_V:
			return new EnemyV(x, y);
		case ENEMY_H:
			return new EnemyH(x, y);
		case ENEMY_L:
			return new EnemyL(x, y);
		case ENEMY_R:
			return new EnemyR(x, y);
		case ENEMY_J:
			return new EnemyJ(x, y);
		default:
			return null;
		}
	}

	abstract class GameCharactor {
		int kind = UNDEF;
		int move = UNDEF;

		int x = UNDEF;
		int y = UNDEF;
		int old_x = UNDEF;
		int old_y = UNDEF;

		public GameCharactor(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public abstract void resolve();

		public boolean isUpInvasion() {
			return (field[x][y - 1] & WALL) == 0;
		}

		public boolean isLeftInvasion() {
			return (field[x - 1][y] & WALL) == 0;
		}

		public boolean isRightIvasion() {
			return (field[x + 1][y] & WALL) == 0;
		}

		public boolean isDownIvasion() {
			return (field[x][y + 1] & WALL) == 0;
		}

		public boolean isIvasion(int way) {
			if (way == UP) {
				return isUpInvasion();
			} else if (way == RIGHT) {
				return isRightIvasion();
			} else if (way == DOWN) {
				return isDownIvasion();
			} else if (way == LEFT) {
				return isLeftInvasion();
			} else if (way == STAY) {
				return true;
			}
			throw new IllegalArgumentException();
		}

		public int getIvasionRouteCount() {
			int ret = 0;
			if (isUpInvasion()) {
				ret++;
			}
			if (isLeftInvasion()) {
				ret++;
			}
			if (isRightIvasion()) {
				ret++;
			}
			if (isDownIvasion()) {
				ret++;
			}
			return ret;
		}

		public void move() {
			old_x = x;
			old_y = y;
			if (move == UP) {
				y--;
			} else if (move == RIGHT) {
				x++;
			} else if (move == DOWN) {
				y++;
			} else if (move == LEFT) {
				x--;
			} else if (move == STAY) {
				// なんもしない
			} else {
				throw new IllegalStateException();
			}
			field[old_x][old_y] &= ~kind;
			field[x][y] |= kind;
		}

		@Override
		public String toString() {
			return this.getClass().getSimpleName() + "(" + x + "," + y + ")";
		}
	}

	class Packman extends GameCharactor {

		public Packman(int x, int y) {
			super(x, y);
			kind = PACKMAN;
		}

		@Override
		public void resolve() {
			throw new IllegalAccessError();
		}

		public void resolve(int direction) {
			move = direction;
		}
	}

	abstract class EnemyBasic extends GameCharactor {

		public EnemyBasic(int x, int y) {
			super(x, y);
		}

		public int commonResolve() {
			if (move == UNDEF) {
				// 動作が未定義 ( t = 0 ) の場合、特別ルールに従って移動方向を決定
				if (isDownIvasion()) {
					return DOWN;
				} else if (isLeftInvasion()) {
					return LEFT;
				} else if (isUpInvasion()) {
					return UP;
				} else if (isRightIvasion()) {
					return RIGHT;
				}
			} else {
				int route = getIvasionRouteCount();
				if (route == 1) {
					// 一方通行コース
					if (isDownIvasion()) {
						return DOWN;
					} else if (isLeftInvasion()) {
						return LEFT;
					} else if (isUpInvasion()) {
						return UP;
					} else if (isRightIvasion()) {
						return RIGHT;
					}
				} else if (route == 2) {
					// 一本道コース 一個前にいた方向にはいけない
					if (move != UP && isDownIvasion()) {
						return DOWN;
					} else if (move != RIGHT && isLeftInvasion()) {
						return LEFT;
					} else if (move != DOWN && isUpInvasion()) {
						return UP;
					} else if (move != LEFT && isRightIvasion()) {
						return RIGHT;
					}
				}
			}
			return UNDEF;
		}
	}

	class EnemyV extends EnemyBasic {
		// 自機狙い Y優先
		public EnemyV(int x, int y) {
			super(x, y);
			kind = ENEMY_V;
		}

		@Override
		public void resolve() {
			int next = commonResolve();
			if (next != UNDEF) {
				move = next;
				return;
			}
			int dx = packman.x - x;
			int dy = packman.y - y;
			if (dy != 0) {
				if (dy < 0 && isUpInvasion()) {
					move = UP;
					return;
				} else if (dy > 0 && isDownIvasion()) {
					move = DOWN;
					return;
				}
			}
			if (dx != 0) {
				if (dx < 0 && isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (dx > 0 && isRightIvasion()) {
					move = RIGHT;
					return;
				}
			}
			// 一方通行のときと同じ動作
			if (isDownIvasion()) {
				move = DOWN;
				return;
			} else if (isLeftInvasion()) {
				move = LEFT;
				return;
			} else if (isUpInvasion()) {
				move = UP;
				return;
			} else if (isRightIvasion()) {
				move = RIGHT;
				return;
			}
			throw new IllegalStateException();
		}
	}

	class EnemyH extends EnemyBasic {
		// 自機狙い X優先
		public EnemyH(int x, int y) {
			super(x, y);
			kind = ENEMY_H;
		}

		@Override
		public void resolve() {
			int next = commonResolve();
			if (next != UNDEF) {
				move = next;
				return;
			}
			int dx = packman.x - x;
			int dy = packman.y - y;
			if (dx != 0) {
				if (dx < 0 && isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (dx > 0 && isRightIvasion()) {
					move = RIGHT;
					return;
				}
			}
			if (dy != 0) {
				if (dy < 0 && isUpInvasion()) {
					move = UP;
					return;
				} else if (dy > 0 && isDownIvasion()) {
					move = DOWN;
					return;
				}
			}
			// 一方通行のときと同じ動作
			if (isDownIvasion()) {
				move = DOWN;
				return;
			} else if (isLeftInvasion()) {
				move = LEFT;
				return;
			} else if (isUpInvasion()) {
				move = UP;
				return;
			} else if (isRightIvasion()) {
				move = RIGHT;
				return;
			}
			throw new IllegalStateException();
		}
	}

	class EnemyL extends EnemyBasic {
		// 左折

		public EnemyL(int x, int y) {
			super(x, y);
			kind = ENEMY_L;
		}

		@Override
		public void resolve() {
			int next = commonResolve();
			if (next != UNDEF) {
				move = next;
				return;
			}
			if (move == UP) {
				// 進行方向上向きの場合
				if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				}
			} else if (move == RIGHT) {
				// 進行方向右
				if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				}
			} else if (move == DOWN) {
				// 進行方向下
				if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				}
			} else if (move == LEFT) {
				if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				}
			}
			throw new IllegalStateException();
		}
	}

	class EnemyR extends EnemyBasic {
		// 右折
		public EnemyR(int x, int y) {
			super(x, y);
			kind = ENEMY_R;
		}

		@Override
		public void resolve() {

			int next = commonResolve();
			if (next != UNDEF) {
				move = next;
				return;
			}
			if (move == UP) {
				// 進行方向上向きの場合
				if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				}
			} else if (move == RIGHT) {
				// 進行方向右
				if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				}
			} else if (move == DOWN) {
				// 進行方向下
				if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				}
			} else if (move == LEFT) {
				if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				}
			}
			throw new IllegalStateException();
		}
	}

	class EnemyJ extends EnemyBasic {
		// 左、右、左、右
		private static final int L = 1;
		private static final int R = 2;
		private int turn = L;

		public EnemyJ(int x, int y) {
			super(x, y);
			kind = ENEMY_J;
		}

		@Override
		public void resolve() {
			int next = commonResolve();
			if (next == UNDEF) {
				if (turn == L) {
					resolveL();
					turn = R;
				} else {
					resolveR();
					turn = L;
				}
			} else {
				move = next;
			}
		}

		public void resolveL() {
			if (move == UP) {
				// 進行方向上向きの場合
				if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				}
			} else if (move == RIGHT) {
				// 進行方向右
				if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				}
			} else if (move == DOWN) {
				// 進行方向下
				if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				}
			} else if (move == LEFT) {
				if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				}
			}
			throw new IllegalStateException();
		}

		public void resolveR() {
			if (move == UP) {
				// 進行方向上向きの場合
				if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				}
			} else if (move == RIGHT) {
				// 進行方向右
				if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				} else if (isUpInvasion()) {
					move = UP;
					return;
				}
			} else if (move == DOWN) {
				// 進行方向下
				if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				} else if (isRightIvasion()) {
					move = RIGHT;
					return;
				}
			} else if (move == LEFT) {
				if (isUpInvasion()) {
					move = UP;
					return;
				} else if (isLeftInvasion()) {
					move = LEFT;
					return;
				} else if (isDownIvasion()) {
					move = DOWN;
					return;
				}
			}
			throw new IllegalStateException();
		}
	}

	private static char convToChar(int i) {
		if (ENEMY_J <= i) {
			return C_ENEMY_J;
		}
		if (ENEMY_R <= i) {
			return C_ENEMY_R;
		}
		if (ENEMY_L <= i) {
			return C_ENEMY_L;
		}
		if (ENEMY_H <= i) {
			return C_ENEMY_H;
		}
		if (ENEMY_V <= i) {
			return C_ENEMY_V;
		}
		if (PACKMAN <= i) {
			return C_PACKMAN;
		}
		if (FOOD <= i) {
			return C_FOOD;
		}
		if (WALL <= i) {
			return C_WALL;
		}
		if (NONE <= i) {
			return C_NONE;
		}
		throw new IllegalArgumentException(String.valueOf(i));
	}

	private char convToInt(char c) {
		switch (c) {
		case C_NONE:
			return NONE;
		case C_WALL:
			return WALL;
		case C_FOOD:
			return FOOD;
		case C_PACKMAN:
			return PACKMAN;
		case C_ENEMY_V:
			return ENEMY_V;
		case C_ENEMY_H:
			return ENEMY_H;
		case C_ENEMY_L:
			return ENEMY_L;
		case C_ENEMY_R:
			return ENEMY_R;
		case C_ENEMY_J:
			return ENEMY_J;

		default:
			throw new IllegalArgumentException(String.valueOf(c));
		}
	}

	public static int convInputToInt(char c) {
		switch (c) {
		case 'h':
			return LEFT;
		case 'j':
			return DOWN;
		case 'k':
			return UP;
		case 'l':
			return RIGHT;
		case '.':
			return STAY;
		default:
			throw new IllegalArgumentException();
		}
	}

	public static char convIntToInputChar(int i) {
		switch (i) {
		case LEFT:
			return 'h';
		case DOWN:
			return 'j';
		case UP:
			return 'k';
		case RIGHT:
			return 'l';
		case STAY:
			return '.';
		default:
			throw new IllegalArgumentException();
		}
	}

	public static String toAnswer(byte[] walk) {
		StringBuilder stb = new StringBuilder();
		for (int one : walk) {
			switch (one) {
			case UP:
				stb.append('k');
				break;
			case DOWN:
				stb.append('j');
				break;
			case LEFT:
				stb.append('h');
				break;
			case RIGHT:
				stb.append('l');
				break;
			case STAY:
				stb.append('.');
				break;

			default:
				throw new IllegalArgumentException();
			}
		}
		return stb.toString();
	}

	@Override
	public String toString() {
		StringBuilder stb = new StringBuilder();
		stb.append("score ").append(eat).append('\n');
		stb.append("time ").append(now).append("/").append(time).append("\n");
		stb.append(width).append(" ").append(height).append("\n");
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				stb.append(convToChar(field[x][y]));
			}
			stb.append("\n");
		}
		return stb.toString();
	}
}

ManualSolver.java

package packman;

import static packman.Game.*;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class ManualSolver {

	private static String highscore_dat = null;
	Game game = null;
	Queue<byte[]> queue = new ArrayDeque<byte[]>();

	int highscore = 0;

	public static void main(String[] args) throws IOException {
		ManualSolver solver = new ManualSolver();
		highscore_dat = "./highscore" + args[0] + ".dat";
		solver.resolve(args[0]);
	}

	private void resolve(String lv) throws IOException {
		game = new Game(new File("./lv" + lv));
		byte[] walk = new byte[0];
		try {
			FileInputStream fin = new FileInputStream(new File(highscore_dat));
			InputStreamReader isr = new InputStreamReader(fin);
			BufferedReader br = new BufferedReader(isr);
			String line = br.readLine();
			highscore = Integer.parseInt(line);
		} catch (Exception e) {
			System.out.println("can't find hiscore data.");
		}

		System.out.println(game.toString());

		while (true) {
			System.out
					.println("input values, left=a down=s up=w right=d stat=. playback=z");

			BufferedReader br = new BufferedReader(new InputStreamReader(
					System.in));
			String line = br.readLine();
			for (int i = 0; i < line.length(); i++) {
				char in = line.charAt(i);
				if (in == 'a') {
					in = 'h';
				}
				if (in == 'w') {
					in = 'k';
				}
				if (in == 'd') {
					in = 'l';
				}
				if (in == 's') {
					in = 'j';
				}

				try {
					if (in == 'z') {
						System.out.println("playback");
						walk = Arrays.copyOf(walk, walk.length - 1);
						game.reset();
						game.evaluate(walk);
						System.out.println(game.toString());
						continue;
					}
					byte input = (byte) Game.convInputToInt(in);
					if (input == UP) {
						if (!game.packman.isUpInvasion()) {
							System.out.println("ignore input=UP");
							continue;
						}
					} else if (input == RIGHT) {
						if (!game.packman.isRightIvasion()) {
							System.out.println("ignore input=RIGHT");
							continue;
						}
					} else if (input == DOWN) {
						if (!game.packman.isDownIvasion()) {
							System.out.println("ignore input=DOWN");
							continue;
						}
					} else if (input == LEFT) {
						if (!game.packman.isLeftInvasion()) {
							System.out.println("ignore input=LEFT");
							continue;
						}
					}

					walk = Arrays.copyOf(walk, walk.length + 1);
					walk[walk.length - 1] = input;
					game.reset();
					int result = game.evaluate(walk);

					System.out.println(game.toString());

					if (result == FINISH) {
						System.out.println("Clear!!");
						System.out.println(Game.toAnswer(walk));
						if (highscore < game.eat) {
							highscore = game.eat + game.time - game.now;
							System.out.println("High score!! score="
									+ String.valueOf(highscore));
							writeHighscore(walk);
						}
					} else if (result == DEAD) {
						System.out.println("you are dead... press Z key.");
					} else {
						if (highscore < game.eat) {
							highscore = game.eat;
							writeHighscore(walk);
						}
					}
				} catch (IllegalArgumentException e) {
					System.out.println("ignore input=" + in);
				}
			}
		}
	}

	private void writeHighscore(byte[] walk) throws FileNotFoundException,
			IOException {
		FileOutputStream fout = new FileOutputStream(highscore_dat);
		OutputStreamWriter out = new OutputStreamWriter(fout);
		out.write(String.valueOf(game.eat));
		out.write('\n');
		out.write(Game.toAnswer(walk));
		out.flush();
		out.close();
		System.out.println("High score updated!!");
	}
}

MonteSolver.java

package packman;

import static packman.Game.*;

import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

import net.goui.util.MTRandom;

public class MonteSolver {

	Game game = null;
	Queue<byte[]> queue = new ArrayDeque<byte[]>();

	// private static final int TRY_MAX = 1000000;
	private static final int TRY_MAX = 100000;

	byte[] maxRoute = new byte[0];
	int maxScore = 0;

	MTRandom random = new MTRandom();

	private long[] total = null;
	private int bestScore = 0;
	private byte[] bestRoute = null;

	public static void main(String[] args) throws IOException {
		MonteSolver solver = new MonteSolver();
		solver.resolve();
	}

	private void resolve() throws IOException {

		game = new Game(new File(
				"/Users/vvakame/work/eclipse/GDD2010/src/packman/lv2"));

		byte[] walk = new byte[0];

		for (int progress = 0; progress <= game.time; progress++) {
			long max = 0;
			byte next = UNDEF;
			total = new long[5];
			for (byte way = 0; way < 5; way++) {
				game.reset();
				game.evaluate(walk);
				if (game.packman.isIvasion(way)) {
					for (int i = 0; i < TRY_MAX; i++) {
						total[way] += playout(walk, way);
					}
					if (max < total[way]) {
						max = total[way];
						next = way;
					}
				}
			}
			walk = Arrays.copyOf(walk, walk.length + 1);
			walk[walk.length - 1] = next;

			System.out.println("Now progress " + String.valueOf(progress) + " "
					+ Game.toAnswer(walk));
			if (bestRoute != null) {
				System.out.println("Now best score "
						+ String.valueOf(bestScore) + " "
						+ Game.toAnswer(bestRoute));
			}
		}
		System.out.println("End");
	}

	private int playout(byte[] walk, byte thisTime) {

		game.reset();
		if (walk.length != 0) {
			game.evaluate(walk);
		}
		game.evaluate(thisTime);

		int result = 0;
		int test = 0;
		while (true) {
			byte next = (byte) random.nextInt(5);
			if (next == STAY) {
				continue;
			}
			if (!game.packman.isIvasion(next)) {
				continue;
			}
			result = game.evaluate(next);
			game.updateMax();

			test++;

			// ゲーム終了評価
			if (result == DEAD) {
				int score = game.getScore();
				if (bestScore < score) {
					bestScore = score;
					bestRoute = game.route;
				}
				return score;
			}
			if (result == FINISH) {
				int score = game.getScore();
				if (bestScore < score) {
					bestScore = score;
					bestRoute = game.route;
				}
				return score;
			} else if (game.time == game.now + 1) {
				return game.getScore();
			}
		}
	}
}

WithHintMonteSolver.java

package packman;

import static packman.Game.*;

import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

import net.goui.util.MTRandom;

public class WithHintMonteSolver {

	Game game = null;
	Queue<byte[]> queue = new ArrayDeque<byte[]>();

	private static final int TRY_MAX = 500000;

	byte[] maxRoute = new byte[0];
	int maxScore = 0;

	MTRandom random = new MTRandom();

	private long[] total = null;
	private int bestScore = 0;
	private byte[] bestRoute = null;

	public static void main(String[] args) throws IOException {
		WithHintMonteSolver solver = new WithHintMonteSolver();
		solver.resolve();
	}

	private void resolve() throws IOException {

		game = new Game(new File(
				"/Users/vvakame/work/eclipse/GDD2010/src/packman/lv3"));

		String hint = "lkklllkkkhhhllljjllllllllllllkkkhhhlll";

		byte[] walk = null;

		total = new long[5];
		restart: while (true) {
			walk = new byte[hint.length()];
			for (int i = 0; i < hint.length(); i++) {
				walk[i] = (byte) Game.convInputToInt(hint.charAt(i));
			}

			for (int progress = 0; progress <= game.time; progress++) {
				long max = 0;
				byte next = UNDEF;
				for (byte way = 0; way < 5; way++) {
					total[way] = 0;
					game.reset();
					int result = game.evaluate(walk);
					if (result == DEAD) {
						continue restart;
					}
					if (game.packman.isIvasion(way)) {
						for (int i = 0; i < TRY_MAX; i++) {
							total[way] += playout(walk, way);
						}
						if (max < total[way]) {
							max = total[way];
							next = way;
						}
					}
				}
				if (next == UNDEF) {
					continue restart;
				}
				walk = Arrays.copyOf(walk, walk.length + 1);
				walk[walk.length - 1] = next;

				System.out.println("Now progress " + String.valueOf(progress)
						+ " " + Game.toAnswer(walk));
				if (bestRoute != null) {
					System.out.println("Now best score "
							+ String.valueOf(bestScore) + " "
							+ Game.toAnswer(bestRoute));
				}
			}
		}
	}

	private int playout(byte[] walk, byte thisTime) {

		game.reset();
		if (walk.length != 0) {
			game.evaluate(walk);
		}
		int result = game.evaluate(thisTime);

		if (result == DEAD) {
			int score = game.getScore();
			if (bestScore < score) {
				bestScore = score;
				bestRoute = game.route;
			}
			return 0;
		}
		if (result == FINISH) {
			int score = game.getScore();
			if (bestScore < score) {
				bestScore = score;
				bestRoute = game.route;
			}
			return score;
		} else if (game.time == game.now) {
			return game.getScore();
		}

		result = 0;
		int test = 0;
		while (true) {
			byte next = (byte) random.nextInt(5);
			if (next == STAY) {
				continue;
			}
			if (!game.packman.isIvasion(next)) {
				continue;
			}
			result = game.evaluate(next);
			game.updateMax();

			test++;

			// ゲーム終了評価
			if (result == DEAD) {
				int score = game.getScore();
				if (bestScore < score) {
					bestScore = score;
					bestRoute = game.route;
				}
				return score;
			}
			if (result == FINISH) {
				int score = game.getScore();
				if (bestScore < score) {
					bestScore = score;
					bestRoute = game.route;
				}
				return score;
			} else if (game.time == game.now) {
				return game.getScore();
			}
		}
	}
}