Created
December 16, 2010 09:33
-
-
Save methane/743228 to your computer and use it in GitHub Desktop.
Player implemented by KLab for JavaChallenge 2010.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package jp.ac.nii.icpc2010.players; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Queue; | |
import java.util.ArrayDeque; | |
import java.util.PriorityQueue; | |
import jp.ac.nii.icpc2010.players.BasePlayer; | |
import jp.ac.nii.icpc2010.playfield.FieldDirection; | |
import jp.ac.nii.icpc2010.playfield.IPlayField; | |
/** | |
* Player created by KLab Inc. | |
* | |
* @author INADA Naoki | |
* | |
*/ | |
public class KLabPlayer extends BasePlayer | |
{ | |
static final long MAX_SCORE = 100000000; | |
static final long MIN_SCORE =-100000000; | |
public static final class Field | |
{ | |
private byte[] map; // flag is set where can't to move. | |
private int width; | |
private int height; | |
public Field(int w, int h) { | |
map = new byte[h*w]; | |
width = w; | |
height = h; | |
} | |
public Field(Field other) { | |
width = other.width; | |
height = other.height; | |
map = (byte[])other.map.clone(); | |
} | |
public Object clone() { | |
return new Field(this); | |
} | |
public boolean getAt(int x, int y) { | |
int pos = y * width + x; | |
return map[pos] != 0; | |
} | |
public void setAt(int x, int y) { | |
int pos = y * width + x; | |
map[pos] = 1; | |
} | |
public static Field fromPlayField(IPlayField playField) { | |
int width = playField.getWidth(); | |
int height = playField.getHeight(); | |
Field f = new Field(width, height); | |
for (int y = 0; y < height; ++y) { | |
for (int x = 0; x < width; ++x) { | |
int obj = playField.getObjectAt(x, y); | |
if (obj != IPlayField.FIELD_FREE && obj != IPlayField.FIELD_COIN) { | |
f.setAt(x, y); | |
} | |
} | |
} | |
return f; | |
} | |
public String toString() { | |
String s = new String(); | |
for (int y = 0; y < height; ++y) { | |
for (int x = 0; x < width; ++x) { | |
if (getAt(x, y)) { | |
s += '@'; | |
} else { | |
s += '.'; | |
} | |
} | |
s += "\r\n"; | |
} | |
return s; | |
} | |
} | |
static class State implements Comparable<State> | |
{ | |
public Field field; | |
public int[] positions; | |
/// null means not searched yet. | |
/// empty means dead end. | |
public ArrayList<State> children; | |
int coin; | |
long score; | |
FieldDirection lastMove; | |
public State(Field field, int[] positions) { | |
this.field = field; | |
this.positions = positions; | |
this.children = null; | |
} | |
FieldDirection getMovement(int id, State prev_state) { | |
int x2 = positions[id*2]; | |
int y2 = positions[id*2+1]; | |
int x = prev_state.positions[id*2]; | |
int y = prev_state.positions[id*2+1]; | |
if (x == x2) { | |
if ((y + 1) % KLabPlayer.height == y2) { | |
return FieldDirection.Down; | |
} | |
return FieldDirection.Up; | |
} | |
else if ((x + 1) % KLabPlayer.width == x2) { | |
return FieldDirection.Right; | |
} | |
return FieldDirection.Left; | |
} | |
public int compareTo(State o) { | |
if (this.score < o.score) return 1; | |
if (this.score > o.score) return -1; | |
return 0; | |
} | |
} | |
static private int width, height; | |
static private int numPlayers; | |
public KLabPlayer(int id, IPlayField playField) { | |
super(id, playField); | |
width = playField.getWidth(); | |
height = playField.getHeight(); | |
numPlayers = playField.getNumOfPlayers(); | |
//System.out.print("ID: "); | |
//System.out.println(id); | |
//System.out.println(state_count_limit); | |
} | |
FieldDirection prev_dir; | |
boolean got_coin; | |
private Field tryMove(Field field, int x, int y, int id_, int[] pos_) { | |
got_coin = false; | |
x = (x + width) % width; | |
y = (y + height) % height; | |
if (field.getAt(x, y)) { | |
int i; | |
for (i = 0; i < id_; ++i) { | |
if (pos_[i*2] == x && pos_[i*2+1] == y) { | |
pos_[i*2] = pos_[i*2+1] = -1; | |
break; | |
} | |
} | |
if (i == id_) | |
return null; | |
x = y = -1; | |
} | |
Field newfield = (Field)field.clone(); | |
if (x >= 0) { | |
got_coin = isCoin(x, y); | |
newfield.setAt(x, y); | |
} | |
pos_[id_*2] = x; | |
pos_[id_*2+1] = y; | |
return newfield; | |
} | |
long state_count; | |
private void checkTroyMove(State parent, Field field, int[] positions, | |
Queue<State> queue, int next_id, int coin, | |
FieldDirection move) | |
{ | |
if (next_id >= numPlayers) { | |
state_count++; | |
State s = new State(field, (int[])positions.clone()); | |
queue.add(s); | |
s.coin = parent.coin + coin; | |
parent.children.add(s); | |
s.score = calcStandaloneScore(s); | |
s.lastMove = move; | |
return; | |
} | |
int x = parent.positions[next_id*2]; | |
int y = parent.positions[next_id*2+1]; | |
boolean died = true; | |
if (x >= 0) { | |
Field newfield; | |
newfield = tryMove(field, x-1, y, next_id, positions); | |
if (newfield != null) { | |
if (got_coin && next_id == id) coin++; | |
checkTroyMove(parent, newfield, positions, queue, next_id+1, coin, | |
(id == next_id) ? FieldDirection.Left : move); | |
died = false; | |
} | |
newfield = tryMove(field, x+1, y, next_id, positions); | |
if (newfield != null) { | |
if (got_coin && next_id == id) coin++; | |
checkTroyMove(parent, newfield, positions, queue, next_id+1, coin, | |
(id == next_id) ? FieldDirection.Right : move); | |
died = false; | |
} | |
newfield = tryMove(field, x, y-1, next_id, positions); | |
if (newfield != null) { | |
if (got_coin && next_id == id) coin++; | |
checkTroyMove(parent, newfield, positions, queue, next_id+1, coin, | |
(id == next_id) ? FieldDirection.Up : move); | |
died = false; | |
} | |
newfield = tryMove(field, x, y+1, next_id, positions); | |
if (newfield != null) { | |
if (got_coin && next_id == id) coin++; | |
checkTroyMove(parent, newfield, positions, queue, next_id+1, coin, | |
(id == next_id) ? FieldDirection.Down : move); | |
died = false; | |
} | |
} | |
if (died && next_id != id) { | |
// continue to search when enemy is died. | |
// don't continue when I'm died. | |
positions[next_id*2] = positions[next_id*2+1] = -1; | |
checkTroyMove(parent, field, positions, queue, next_id+1, coin, move); | |
return; | |
} | |
} | |
private void lookAhead(State parent, Queue<State> queue) | |
{ | |
if (parent.children != null) { | |
for (State s: parent.children) { | |
state_count++; | |
queue.add(s); | |
} | |
return; | |
} | |
int[] positions = (int[])parent.positions.clone(); | |
parent.children = new ArrayList<State>(16); | |
checkTroyMove(parent, parent.field, positions, queue, 0, 0, FieldDirection.Up); | |
} | |
FieldDirection best_direction; | |
int survive_count; | |
private State createStateFromPlayfield(int[] prev_pos) | |
{ | |
int[] positions = new int[numPlayers * 2]; | |
survive_count = numPlayers; | |
for (int i = 0; i < numPlayers; ++i) { | |
positions[i*2] = getXOf(i); | |
positions[i*2+1] = getYOf(i); | |
if (prev_pos != null) { | |
if ((prev_pos[i*2] < 0) || | |
(prev_pos[i*2] == positions[i*2] && | |
prev_pos[i*2+1] == positions[i*2+1])) { | |
positions[i*2] = positions[i*2+1] = -1; | |
survive_count--; | |
} | |
} | |
} | |
return new State(Field.fromPlayField(playField), positions); | |
} | |
int[] prev_positions = null; | |
State prev_state; | |
public FieldDirection getInput() | |
{ | |
State first_state; | |
state_count = 0; | |
//ArrayDeque<State> queue = new ArrayDeque<State>(); | |
PriorityQueue<State> queue = new PriorityQueue<State>(); | |
first_state = createStateFromPlayfield(prev_positions); | |
prev_positions = first_state.positions; | |
if (prev_state == null) { | |
queue.add(first_state); | |
} else { | |
boolean recycle = false; | |
for (State prev_next: prev_state.children) { | |
int i; | |
for (i = 0; i < first_state.positions.length; ++i) { | |
if (first_state.positions[i] != prev_next.positions[i]) | |
break; | |
} | |
if (i == first_state.positions.length) { | |
first_state = prev_next; | |
//System.out.println("Success to recycle."); | |
break; | |
} | |
} | |
queue.add(first_state); | |
} | |
prev_state = first_state; | |
while (getRemainingTime() > (38 + state_count/100)) { | |
State st = queue.poll(); | |
if (st == null) | |
break; | |
lookAhead(st, queue); | |
} | |
//System.out.println(i); | |
//System.out.println(Field.fromPlayField(playField).toString()); | |
//System.out.print("Turn: "); | |
//System.out.println(playField.getTurn()); | |
//System.out.println(state_count); | |
calcRecursiveScore(first_state, 0); | |
//System.out.println(best_direction); | |
//int remtime = getRemainingTime(); | |
//System.out.println(remtime); | |
//System.out.print("Survive: "); | |
//System.out.println(survive_count); | |
return best_direction; | |
} | |
private void printPlayField() { | |
int w = playField.getWidth(); | |
int h = playField.getHeight(); | |
for (int y = 0; y < h; ++y) { | |
for (int x = 0; x < w; ++x) { | |
int p; | |
for (p = 0; p < numPlayers; ++p) { | |
if (getXOf(p) == x && getYOf(p) == y) { | |
System.out.print(p); | |
break; | |
} | |
} | |
if (p < numPlayers) | |
continue; | |
switch (playField.getObjectAt(x, y)) { | |
case OBJECT_FREE: | |
System.out.print(' '); | |
break; | |
case OBJECT_COIN: | |
System.out.print('@'); | |
break; | |
case OBJECT_WALL: | |
System.out.print('#'); | |
break; | |
default: | |
System.out.print('*'); | |
break; | |
} | |
} | |
System.out.println(); | |
} | |
} | |
private static long getFreeSpace(int x, int y, byte[] work) | |
{ | |
int xx,yy; | |
long count = 0; | |
work[y*width + x] = 1; | |
int[] queue = new int[work.length*2]; | |
int end = 2; | |
queue[0] = x; | |
queue[1] = y; | |
while (end > 1) { | |
end -= 2; | |
x = queue[end]; | |
y = queue[end+1]; | |
xx = (x + width + 1) % width; | |
yy = y; | |
if (work[yy*width + xx] == 0) { | |
count++; | |
work[yy*width + xx] = 1; | |
queue[end] = xx; | |
queue[end+1] = yy; | |
end += 2; | |
} | |
xx = (x + width - 1) % width; | |
yy = y; | |
if (work[yy*width + xx] == 0) { | |
count++; | |
work[yy*width + xx] = 1; | |
queue[end] = xx; | |
queue[end+1] = yy; | |
end += 2; | |
} | |
xx = x; | |
yy = (y + height + 1) % height; | |
if (work[yy*width + xx] == 0) { | |
count++; | |
work[yy*width + xx] = 1; | |
queue[end] = xx; | |
queue[end+1] = yy; | |
end += 2; | |
} | |
xx = x; | |
yy = (y + height - 1) % height; | |
if (work[yy*width + xx] == 0) { | |
count++; | |
work[yy*width + xx] = 1; | |
queue[end] = xx; | |
queue[end+1] = yy; | |
end += 2; | |
} | |
} | |
return count; | |
} | |
private long calcStandaloneScore(State s) | |
{ | |
int[] work = new int[width*height]; | |
int[] pos_queue = new int[width*height*4]; | |
int pos_end = 0; | |
int pos_start = 0; | |
int[] scores = new int[numPlayers]; | |
int offs = 0; | |
for (int y = 0; y < height; ++y) { | |
for (int x = 0; x < width; ++x) { | |
work[offs] = s.field.getAt(x, y) ? -1 : 0; | |
offs++; | |
} | |
} | |
for (int p = 0; p < numPlayers; ++p) { | |
if (s.positions[p*2] < 0) continue; | |
int x = s.positions[p*2]; | |
int y = s.positions[p*2+1]; | |
pos_queue[pos_end] = x; | |
pos_queue[pos_end+1] = y; | |
pos_end += 2; | |
work[width*y + x] = p+1; | |
} | |
int limit = 2000; | |
while (pos_start < pos_end && limit > 0) { | |
limit--; | |
int x = pos_queue[pos_start]; | |
int y = pos_queue[pos_start+1]; | |
int p = work[y * width + x]; | |
pos_start += 2; | |
int xp = (x + width + 1) % width; | |
int xm = (x + width - 1) % width; | |
int yp = (y + height + 1) % height; | |
int ym = (y + height - 1) % height; | |
if (work[y*width + xp] == 0) { | |
if ((work[yp*width + xp] > p+1) || (work[ym*width + xp] > p+1)) { | |
work[y * width + xp] = -2; | |
} else { | |
scores[p-1]++; | |
work[y*width + xp] = p; | |
pos_queue[pos_end] = xp; | |
pos_queue[pos_end+1] = y; | |
pos_end += 2; | |
} | |
} | |
if (work[y * width + xm] == 0) { | |
if ((work[yp * width + xm] > p+1) || (work[ym * width + xm] > p+1)) { | |
work[y * width + xm] = -2; | |
} else { | |
scores[p-1]++; | |
work[y * width + xm] = p; | |
pos_queue[pos_end] = xm; | |
pos_queue[pos_end+1] = y; | |
pos_end += 2; | |
} | |
} | |
if (work[yp * width + x] == 0) { | |
if ((work[yp*width + xp] > p+1) || (work[yp*width + xm] > p+1)) { | |
work[yp * width + x] = -2; | |
} else { | |
scores[p-1]++; | |
work[yp * width + x] = p; | |
pos_queue[pos_end] = x; | |
pos_queue[pos_end+1] = yp; | |
pos_end += 2; | |
} | |
} | |
if (work[ym * width + x] == 0) { | |
if ((work[ym * width + xp] > p+1) || (work[ym * width + xm] > p+1)) { | |
work[ym * width + x] = -2; | |
} else { | |
scores[p-1]++; | |
work[ym * width + x] = p; | |
pos_queue[pos_end] = x; | |
pos_queue[pos_end+1] = ym; | |
pos_end += 2; | |
} | |
} | |
} | |
int self_score = scores[id]; | |
int sum_enemy_score = 0; | |
int best_enemy_score = 0; | |
for (int p = 0; p < numPlayers; ++p) { | |
if (p == id) | |
continue; | |
sum_enemy_score = scores[p]; | |
if (scores[p] > best_enemy_score) | |
best_enemy_score = scores[p]; | |
} | |
int coin_score = s.coin; | |
if (survive_count == 1) coin_score *= 100; | |
return self_score * (numPlayers+2) - sum_enemy_score | |
- best_enemy_score*2 + coin_score * 10; | |
} | |
private long calcRecursiveScore(State s, int depth) | |
{ | |
long upscore = MAX_SCORE; | |
long downscore = upscore; | |
long leftscore = upscore; | |
long rightscore = upscore; | |
if (s.positions[id*2] < 0) return MIN_SCORE; // I'm died... | |
if (s.children == null) | |
return s.score; | |
if (s.children.isEmpty()) | |
return MIN_SCORE; // dead... | |
for (State child : s.children) { | |
long score = calcRecursiveScore(child, depth+1) + 10; // bonus for living 1 turn. | |
switch (child.lastMove) { | |
case Up: | |
upscore = Math.min(upscore, score); | |
break; | |
case Down: | |
downscore = Math.min(downscore, score); | |
break; | |
case Left: | |
leftscore = Math.min(leftscore, score); | |
break; | |
case Right: | |
rightscore = Math.min(rightscore, score); | |
break; | |
} | |
} | |
if (upscore == MAX_SCORE) upscore = MIN_SCORE; | |
if (downscore == MAX_SCORE) downscore = MIN_SCORE; | |
if (leftscore == MAX_SCORE) leftscore = MIN_SCORE; | |
if (rightscore == MAX_SCORE) rightscore = MIN_SCORE; | |
//if (depth < 1) { | |
//System.out.print("Up: "); System.out.println(upscore); | |
//System.out.print("Down: "); System.out.println(downscore); | |
//System.out.print("Left: "); System.out.println(leftscore); | |
//System.out.print("Right: "); System.out.println(rightscore); | |
//} | |
long bestscore = Math.max(upscore, Math.max(downscore, Math.max(leftscore, rightscore))); | |
//System.out.print("Best: "); System.out.println(bestscore); | |
if (upscore == bestscore) best_direction = FieldDirection.Up; | |
if (downscore == bestscore) best_direction = FieldDirection.Down; | |
if (leftscore == bestscore) best_direction = FieldDirection.Left; | |
if (rightscore == bestscore) best_direction = FieldDirection.Right; | |
return bestscore; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment