Skip to content

Instantly share code, notes, and snippets.

@vvakame

vvakame/BreadthFirstSearchSolver.java

Created August 30, 2010 11:21
Show Gist options
  • Save vvakame/557303 to your computer and use it in GitHub Desktop.
Save vvakame/557303 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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);
}
}
}
Raw
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();
}
}
Raw
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!!");
}
}
Raw
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();
}
}
}
}
Raw
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();
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment