Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-08-23

pac-man

15:03 |  pac-man - naoya_t@topcoder を含むブックマーク はてなブックマーク -  pac-man - naoya_t@topcoder  pac-man - naoya_t@topcoder のブックマークコメント

  • SuperHackerコースの目玉。総当りで行けるのはLevel1までか
  • 探索順をランダムに
    • ステップ毎に、移動可能な方向(不動を含む)をシャッフルしてDFS
    • と思ったけどあまり伸びないので
    • えさを食えるかどうか(目先の利益)で優先度を変えるだけで伸びた。(食欲的な意味で)貪欲法
  • 一定の探索ステップ数に達したら中断
    • 探索打ち切り数はT*1.3〜1.5ぐらいで適当にやってた
  • ラップタイム毎の最高スコア(後に4位まで)を得たルートを記憶しておいて、時々(ランダムに)、過去に保存したあるラップタイム(ランダム)の保存ルートから再開する
    • これはちょっとGAっぽい
  • 移動可能な方向を毎回ステップ毎に調べてるのは馬鹿なので、
  • グラフ構造を把握して、ある点からある点への距離(ステップ数)をdijkstraか何かで全部調べておく
    • Level3だとちょっと時間がかかるので、この距離テーブルはファイルに保存しておく
  • 目先にえさがない場合、残りのえさ全てからの「重力」の合計の大きい方からDFS
    • この程度のことで500は簡単に行くようになった。
  • しかし520前後までしか伸びない…
    • 結果: 41, 248, 523

問題ファイル例 (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