2010-08-23
pac-man
| 
- SuperHackerコースの目玉。総当りで行けるのはLevel1までか
- 探索順をランダムに
- 一定の探索ステップ数に達したら中断
- 探索打ち切り数はT*1.3〜1.5ぐらいで適当にやってた
- ラップタイム毎の最高スコア（後に４位まで）を得たルートを記憶しておいて、時々（ランダムに）、過去に保存したあるラップタイム（ランダム）の保存ルートから再開する
- これはちょっとGAっぽい
- 移動可能な方向を毎回ステップ毎に調べてるのは馬鹿なので、
- グラフ構造を把握して、ある点からある点への距離（ステップ数）をdijkstraか何かで全部調べておく
- Level3だとちょっと時間がかかるので、この距離テーブルはファイルに保存しておく
- 目先にえさがない場合、残りのえさ全てからの「重力」の合計の大きい方からDFS
- この程度のことで500は簡単に行くようになった。
- しかし520前後までしか伸びない…
問題ファイル例 (level2)
300 20 17 #################### ###.....L..........# ###.##.##.##L##.##.# ###.##.##.##.##.##.# #.L................# #.##.##.##.##.##.### #.##.##L##.##.##.### #.................L# #.#.#.#J####J#.#.#.# #L.................# ###.##.##.##.##.##.# ###.##.##R##.##.##.# #................R.# #.##.##.##.##R##.### #.##.##.##.##.##.### #@....R..........### ####################
最後の頃のコード
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#include "cout.h"
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
const int infty = 987654321;
template <typename T> T infsum(T a, T b){
return (a == infty || b == infty)? infty : (a + b);
}
#include <stdlib.h>
#include <libgen.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#define DEFAULT_STEP_LIMIT 5000
#define DEFAULT_RAND_FREQ 20
#define DEFAULT_VH_WEIGHT 0 //.003
int rand_freq = DEFAULT_RAND_FREQ, step_limit = DEFAULT_STEP_LIMIT, hiscore = 0;
double vh_weight = DEFAULT_VH_WEIGHT;
vector<string> rawmap;
int T, H, W;
int meIdx, t=0, score=0, timebonus=0, esamax=0;
int dirx[5] = { 0, -1, 0, 1, 0 }, diry[5] = { 1, 0, -1, 0, 0 }; // CW: 下 左 上 右 .
char dirt[5] = { 'j', 'h', 'k', 'l', '.' };
vector<int> aIdx, aType, aToggle, ldir; int aN;
vector<int> hist;
char map_name[128];
int N; // number of nodes
vector<int> esa;
vector<char> trans;
vector<vector<int> > route;
vector<int> route_cnt;
vector<int> ord_to_idx, idx_to_ord;
vector<vector<int> > arc, distances;
class Frame {
public:
int _meIdx, _t, _score, _aN;
vector<int> _aIdx, _aType, _aToggle, _ldir, _hist;
vector<int> _esa;
public:
Frame(){
_meIdx = meIdx; _t = t; _score = score;
_aN = aN;
_aIdx.assign(all(aIdx)); _aType.assign(all(aType)); _aToggle.assign(all(aToggle));
_ldir.assign(all(ldir)); _hist.assign(all(hist));
_esa.assign(all(esa));
}
void call() {
meIdx = _meIdx; t = _t; score = _score;
aN = _aN;
aIdx.assign(all(_aIdx)); aType.assign(all(_aType)); aToggle.assign(all(_aToggle));
ldir.assign(all(_ldir)); hist.assign(all(_hist));
esa.assign(all(_esa));
}
~Frame() {
_aIdx.clear(); _aType.clear(); _aToggle.clear();
_ldir.clear(); _score = score;
_esa.clear();
}
string dump() {
stringstream ss;
ss << "t=" << _t << ", score=" << _score;
return ss.str();
}
};
int steps;
vector<int> hihi, memo_i;
Frame *memo[701][4], *frame_for_reset;
bool random_mode = false;
inline bool coince(int m0, int m1, int a0, int a1) {
return (a1==m1 || (a0==m1 && a1==m0));
}
inline double drand(){
return 1.0 / 65536 * (rand() % 65536);
}
vector<int> dijkstra(int start_v)
{
vector<int> distance(N, infty);
//vector<int> predecessor(N, -1);
set<int> S;
S.insert(start_v);
distance[start_v] = 0;
rep(v,N){
if (v == start_v) continue;
if (arc[start_v][v] == infty) continue;
distance[v] = arc[start_v][v];
//predecessor[v] = start_v;
}
while (S.size() < N) { // 各点へ
// find v* from V\S with distance(v*) = min{distance(v):v from V\S}
int v_ = -1;
int d_ = infty;
rep(v,N){
if (found(S,v)) continue;
// V\S
if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
}
if (v_ == -1) break;
S.insert(v_);
rep(v,N){ // FOR ALL v from V\S DO
if (found(S,v)) continue;
// V\S
int d_ = infsum(distance[v_], arc[v_][v]);
if (d_ < distance[v]) {
distance[v] = d_;
//predecessor[v] = v_;
}
}
}
return distance;
}
// MONITOR
void mon_(FILE *oport)
{
fprintf(oport, "\n%d score=%d timebonus=%d\n", T-t, score, timebonus);
vector<vector<char> > screen(H,vector<char>(W,'+'));
rep(idx,N){
int ord=idx_to_ord[idx], c=ord%W, r=ord/W;
screen[r][c] = esa[idx] ? '.' : ' ';
rep(i,aN){
if (idx==aIdx[i]) screen[r][c] = aType[i];
}
if (idx==meIdx) screen[r][c] = '@';
}
rep(r,H){
rep(c,W) fputc(screen[r][c], oport);
fputc('\n', oport);
}
fprintf(oport, "> ");
rep(i,t) fputc(hist[i], oport);
fputc('\n', oport);
}
void mon()
{
mon_(stdout);
}
void save()
{
if (!map_name[0]) return;
char path[256];
// ここではmkdirしないので先に自分で作ってね
sprintf(path, "ans/%s/%03d.scr", map_name, score+timebonus);
printf("path: %s\n", path);
FILE *fp = fopen(path, "wx"); // exclusive!!
if (fp != NULL) {
mon_(fp);
fclose(fp);
}
}
//
// 地図をファイルから読み取り
//
bool load_rawmap(char *path)
{
FILE *fp = fopen(path, "r");
if (fp == NULL){
cerr << "Read Error" << endl;
return false;
}
int dm0 = fscanf(fp, "%d%d%d", &T,&W,&H);
char rowbuf[256], *dm1;
dm1 = fgets(rowbuf,256,fp); // eat a crlf
rep(r,H){
dm1 = fgets(rowbuf,256,fp);
rawmap.pb(string(rowbuf));
}
fclose(fp);
//
esa.clear(); esamax = 0;
trans.clear();
route.clear(); route_cnt.clear();
ord_to_idx.assign(H*W,-1); idx_to_ord.clear();
aIdx.clear(); aType.clear(); // aToggle.clear();
aN = 0;
int idx = 0;
rep(r,H) rep(c,W) {
char ch = rawmap[r][c];
if (ch == '#') continue;
trans.pb(ch);
int ord = r*W + c;
idx_to_ord.pb(ord); ord_to_idx[ord] = idx;
bool esa_p = false;
switch (ch) {
case '.': esa_p = true; esamax++; break;
case ' ': break;
case '@': meIdx = idx; break;
default:
aIdx.pb(idx); aType.pb(ch); aN++; break;
}
esa.pb(esa_p ? 1 : 0);
route.pb(vector<int>(4,-1)); int cnt=0;
// CW: 下 左 上 右 .
if (rawmap[r+1][c] != '#') { route[idx][0] = ord+W; cnt++; }
if (rawmap[r][c-1] != '#') { route[idx][1] = ord-1; cnt++; }
if (rawmap[r-1][c] != '#') { route[idx][2] = ord-W; cnt++; }
if (rawmap[r][c+1] != '#') { route[idx][3] = ord+1; cnt++; }
route_cnt.pb(cnt);
idx++;
}
N = idx;
aToggle.assign(aN,0);
ldir.resize(aN);
// ord(y*W+x)-> idx
rep(i,N) {
rep(d,4) if (route[i][d] >= 0) route[i][d] = ord_to_idx[route[i][d]];
}
// arc
arc.assign(N, vector<int>(N,infty)); distances.clear();
rep(i,N) arc[i][i]=0;
rep(i,N){
rep(d,4){
int j = route[i][d];
if (j>=0) arc[i][j] = arc[j][i] = 1;
}
}
mon(); // 初期状態マップを表示。dijkstraを待ってる間の退屈しのぎ
string path_d(path); path_d += ".d";
int fd_d = open(path_d.c_str(), O_RDONLY);
if (fd_d != -1) {
short N_;
int e = read(fd_d, &N_, sizeof(short));
short *buf = (short *)malloc(sizeof(N_)*N*N);
if (buf != NULL) {
e = read(fd_d, buf, sizeof(short)*N*N);
distances.assign(N,vector<int>(N,infty));
rep(i,N) distances[i][i] = 0;
for(int i=0;i<N-1;++i)
for(int j=i+1;j<N;++j) {
short v = buf[i*N+j];
if (v >= 0) distances[i][j] = distances[j][i] = v;
}
free(buf);
}
close(fd_d);
} else {
// 各ノード間の距離（総当り）を求める。dijkstraですが。
rep(i,N) {
distances.pb(dijkstra(i));
printf("\rdijkstra #%3d/%d...", 1+i,N);
fflush(stdout);
}
printf("\r \r");
fd_d = creat(path_d.c_str(),0644);// open(path_d.c_str(), O_CREAT|O_WRONLY|O_TRUNC, 0644);
if (fd_d != -1) {
short N_ = N, *buf = (short *)malloc(sizeof(N)*N*N);
int e = write(fd_d, &N_, sizeof(short));
if (buf != NULL) {
rep(i,N) rep(j,N) {
int v = distances[i][j];
buf[i*N+j] = (v == infty)? -1 : (short)v;
}
e = write(fd_d, buf, sizeof(short)*N*N);
free(buf);
}
}
close(fd_d);
}
return true;
}
void reset(){
frame_for_reset->call();
}
//
// 敵機（全部）の動きを計算; ax[], ay[], ldir[]
//
int teki()
{
int me_ord=idx_to_ord[meIdx], me_x=me_ord%W, me_y=me_ord/W;
rep(i,aN){
int idx=aIdx[i], ord=idx_to_ord[idx], x=ord%W, y=ord/W;
if (t==0) {
/// t==0; 下、左、上、右
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else {
/// t>=1
int rcnt = route_cnt[idx];
if (rcnt == 1) {
// 行き止まりマス
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else if (rcnt == 2) {
// 通路マス
int ng_dir = (ldir[i]+2)%4;
rep(d,4){
if (route[idx][d]<0) continue;
if (d == ng_dir) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else {
//交差点マス
int dx=me_x - x, dy=me_y - y;
int ux=dx?(dx>0?1:-1):0, uy=dy?(dy>0?1:-1):0;
int dir_x = ux>0?3:1, dir_y = uy>0?0:2;
int at=aType[i];
aToggle[i]++;
switch (at){
case 'V':
if (dy != 0 && route[idx][dir_y]>=0) {
aIdx[i] = route[idx][dir_y];
ldir[i] = dir_y;
} else if (dx != 0 && route[idx][dir_x]>=0) {
aIdx[i] = route[idx][dir_x];
ldir[i] = dir_x;
} else {
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
case 'H':
if (dx != 0 && route[idx][dir_x]>=0) {
aIdx[i] = route[idx][dir_x];
ldir[i] = dir_x;
} else if (dy != 0 && route[idx][dir_y]>=0) {
aIdx[i] = route[idx][dir_y];
ldir[i] = dir_y;
} else {
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
case 'L': goto mode_l;
case 'R': goto mode_r;
case 'J': if (aToggle[i] & 1) goto mode_l; else goto mode_r;
//default: break;
mode_l:
{
int dz[3] = { (ldir[i]+3)%4, ldir[i], (ldir[i]+1)%4 };
rep(j,3){ int d=dz[j];
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
mode_r:
{
int dz[3] = { (ldir[i]+1)%4, ldir[i], (ldir[i]+3)%4 };
rep(j,3){ int d=dz[j];
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
}
}
}
}
}
ptrdiff_t myrandom(ptrdiff_t i){ return rand()%i; }
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
int sub()
{
if (++steps >= step_limit) return -2; // ABORT
if (steps % 10000 == 0) { printf("\r[%d] t=%d score=%d ",steps,t,score); fflush(stdout); }
if (score==esamax) {
timebonus = T - t;
if (score+timebonus > hiscore) {
mon(); save();
hiscore = score+timebonus;
steps = -step_limit*3;
printf("t=%d (CLEARED), score=%d+%d/%d (NEW RECORD)\n", t, score,timebonus,hiscore);
}
return -3;
} else if (t==T) {
//printf("!!TIME UP!!\n");
if (score > hiscore) {
timebonus = 0;
mon(); save();
hiscore = score;
steps = -step_limit*3;
printf("t=%d (TIME UP), score=%d/%d (NEW RECORD)\n", t, score,hiscore);
}
return 1;
}
if (hihi[t] <= score) {
hihi[t] = score;
if (t < 0 || 700 < t) {
printf("OUT OF BOUNDS... t=%d\n", t);
return -3;
}
// int j = rand() % 4;
int j = memo_i[t]++ % 4;
if (memo[t][j]) delete memo[t][j];
memo[t][j] = new Frame();
}
// 敵の動きをrollbackする為のもの。当たり判定にも利用
vector<int> aIdx_keep(all(aIdx)), aToggle_keep(all(aToggle)), ldir_keep(all(ldir));
// 先に敵の動きを決めれる
teki();
int safecount=0;
vector<int> tmp1, tmp0;
rep(d,4){
int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY
if (esa[nextIdx]) tmp1.pb(d); else tmp0.pb(d);
}
vector<int> choices;
if (sz(tmp1) > 0) {
random_shuffle(all(tmp1), p_myrandom);
tr(tmp1,it) choices.pb(*it);
if (sz(tmp0)) {
random_shuffle(all(tmp0), p_myrandom);
tr(tmp0,it) choices.pb(*it);
}
choices.pb(4);
} else {
vector<pair<double,int> > cx;
int denom = esamax - score; if (denom == 0) denom = 1;
double dist_here = 0.0;
rep(idx,N) {
if (idx == meIdx) continue;
int d_ = distances[meIdx][idx];
if (esa[idx]) dist_here += 1.0 / d_ / d_; //denom;
}
rep(i,aN){
if (aType[i]!='V' && aType[i]!='H') continue;
int d_ = distances[meIdx][aIdx[i]];
dist_here -= vh_weight / d_ / d_;
}
rep(d,4){
int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY
double dist = 0.0;
rep(idx,N) {
if (idx == nextIdx) continue;
int d_ = distances[nextIdx][idx];
if (esa[idx]) dist += 1.0 / d_ / d_; //denom;
}
rep(i,aN){
if (aType[i]!='V' && aType[i]!='H') continue;
int d_ = distances[nextIdx][aIdx[i]];
dist -= vh_weight / d_ / d_;
}
double dist_score = (dist - dist_here);
if (dist_score > .5) dist_score = .5;
if (esa[nextIdx]) dist_score += 0.75;
dist_score += 0.01 * drand();
cx.pb(make_pair(-dist_score,d));
}
cx.pb(make_pair(1.0, 4));
if (random_mode || (rand() % rand_freq == 0)) {
// cx.pb(make_pair(0.005-.00001*(rand() % 1000), 4));
tr(cx,it) it->first += 0.1 * drand();
}
sort(all(cx));
tr(cx,it) choices.pb(it->second);
}
tr(choices,ct){
int d=*ct;
int lmeIdx = meIdx; // 現時点(lme_x,lme_y)で生きている
if (d<4) meIdx = route[meIdx][d]; // MODIFIED (me_x,me_y)
bool safe=true;
rep(i,aN){
if (coince(lmeIdx, meIdx, aIdx_keep[i], aIdx[i])) { safe=false; break; }
}
if (safe) {
safecount++;
int eaten=0;
if (esa[meIdx]) { score++; eaten=1; esa[meIdx]=0; }
hist[t++] = dirt[d];
int res = sub();
t--;
if (res <= -2) {
return res; // abort
}
if (eaten) { esa[meIdx]=1; score--; }
} else {
;
}
meIdx = lmeIdx; // ROLLBACK (me_x,me_y)
}
if (safecount==0) {
if (score > hiscore) {
mon(); save();
hiscore = score;
printf("t=%d (GAMEOVER), score=%d/%d (higher)\n", t, score,hiscore);
} else {
;
}
}
// 敵の動きをrollback
aIdx.assign(all(aIdx_keep));
aToggle.assign(all(aToggle_keep));
ldir.assign(all(ldir_keep));
return safecount ? safecount : -1;
}
main(int argc, char **argv)
{
if (argc < 4){
printf("usage: %s <map_file> <hi_score> <step_limit> [<rand_freq> <vh_weight%%>]\n", basename(argv[0]));
// map_file には地図ファイルのpathを。(eg. problem/pacman_1)
// hi_score を設定しておくとそれ未満のものを表示しない。最初は0でok
// step_limit は試行打ち切り回数。大体T以上の値を設定。800〜1000とか
// 結果は画面表示だけでなく ans/pacman_1/41.scr のようなファイルにも保存される
return 0;
}
srand( (unsigned)time(NULL) );
if (!load_rawmap(argv[1])) return 0;
frame_for_reset = new Frame();
strcpy(map_name, basename(argv[1]));
hihi.assign(T+1,0); memo_i.assign(T+1,0);
rep(z,701) rep(j,4) memo[z][j] = NULL;
hiscore = atoi(argv[2]); if (hiscore < 0) hiscore = 0;
step_limit = atoi(argv[3]); if (step_limit < 0) step_limit = DEFAULT_STEP_LIMIT;
if (argc >= 5) {
rand_freq = atoi(argv[4]); if (rand_freq < 0) rand_freq = DEFAULT_RAND_FREQ;
}
if (argc >= 6) {
int vh_weight_percent = atoi(argv[5]); vh_weight = 0.01 * vh_weight_percent;
}
for (int trial=0; ;++trial){
steps = 0; // step_limit = 500000;
bool inited=false;
if (trial % 2 == 0) {
int z = rand() % T;
if (2<z && hihi[z]) {
int j = rand() % 4;
if (z < 0 || 700 < z) {
printf("OUT OF BOUNDS... t=%d\n", z);
return -3;
}
if (memo[z][j]) {
memo[z][j]->call(); // resume
inited = true;
}
}
}
if (!inited) {
reset();
hist.resize(T); t=0, score=0, timebonus=0;
}
random_mode = (rand() % rand_freq == 0);
int res = sub();
printf("\r// steps=%d, t=%d, score=%d+%d/%d ", steps,t,score,timebonus,hiscore ); fflush(stdout);
}
// dealloc
rep(z,701) rep(j,4) if (memo[z][j]) delete memo[z][j];
delete frame_for_reset;
}
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100823