#include /* for FILE */ #include /* for va_list, va_start, va_end */ #include /* for std::vector */ #include /* for std::min, std::rotate */ #include /* for std::ostringstream */ /******************************************************/ /* defines for interface with emulator */ /* these are actually defined in fceu's header files, */ /* but I brought them here so that this compiles */ /**/ enum Keys /* Bitmasks for different buttons */ { K_A = 0x01, K_B = 0x02, K_SE= 0x04, K_ST= 0x08, K_U = 0x10, K_D = 0x20, K_L = 0x40, K_R = 0x80 }; extern unsigned char RAM[0x800]; /* RAM for reading */ extern void FCEUSS_Save(const char *); /* create savestate to named file */ extern int FCEUSS_Load(const char *); /* load savestate from named file */ extern int FCEUSS_SaveFP(FILE *); extern int FCEUSS_LoadFP(FILE *, int); extern unsigned char CurInput; /* player 1 input for the next frame */ extern void FCEUI_FrameAdvance(); /* advance frame */ static inline void RunFrameWith(unsigned input) { CurInput = input; FCEUI_FrameAdvance(); } /* This BqtItemAcquired variable is supposed to be set to the value * of the CPU register A whenever the ROM location C4D0 is executed, * or the CPU register A + 0x80 whenever the ROM location A56C is executed. */ extern int BqtItemAcquired; /******************/ /* Randomness functions */ #include #include static boost::mt19937 rng; template static inline unsigned GetRnd() { static boost::uniform_int g(0, mod-1); return g(rng); } static inline unsigned GetRnd(unsigned mod) { return boost::uniform_int (0,mod-1) (rng); } /******************/ #include /* For file locking */ void BotFrontMsg(const char*fmt, ...) /* Like printf, renders and logs a message */ { FILE*fp; va_list ap; va_start(ap,fmt); vfprintf(stderr, fmt, ap); va_end(ap); fflush(stderr); fp = fopen("rockman.log", "at"); if(!fp) fp = fopen("rockman.log", "wt"); if(!fp) return; flock(fileno(fp), LOCK_EX); fseek(fp,0,SEEK_END); va_start(ap,fmt); fprintf(fp, "[%d]", (int)getpid()); vfprintf(fp, fmt, ap); va_end(ap); fclose(fp); } /* Displays the generated input sequence as text */ static void DisplaySeq(const std::vector& Seq) { std::ostringstream msg; for(unsigned a=0; a Data; void Create() { #if defined(FCEU_VERSION_NUMERIC) && FCEU_VERSION_NUMERIC >= 9899 /* fceux */ memorystream ms; FCEUSS_SaveMS(&ms, 0); Data.resize(ms.size()); memcpy(&Data[0], ms.buf(), Data.size()); #else FILE*fp = tmpfile(); FCEUSS_SaveFP(fp); rewind(fp); fseek(fp,0,SEEK_END); long pos = ftell(fp); rewind(fp); SaveState result; Data.resize(pos); fread(&Data[0], 1, pos, fp); fclose(fp); #endif } void Load() const { #if defined(FCEU_VERSION_NUMERIC) && FCEU_VERSION_NUMERIC >= 9899 /* fceux */ memorystream ms; ms.write( (const char*) &Data[0], Data.size()); ms.seekg(0); FCEUSS_LoadFP(&ms, SSLOADPARAM_NOBACKUP); #else FILE*fp = tmpfile(); fwrite(&Data[0], 1, Data.size(), fp); rewind(fp); FCEUSS_LoadFP(fp, 0); fclose(fp); #endif } }; static const unsigned MinimumStallsBeforeSimplify = 4; static const unsigned MinimumStallsBeforeGoAhead = 2500; static unsigned DoorAcquired, KeyAcquired; struct SoloKeyBot { static bool Death() /* detects death */ { return RAM[0x590] == 0xBC || RAM[0x590] == 0xBE || RAM[0x590] == 0x9E; } static bool Dingel() /* Unused - don't even remember what this does. * Possibly tests if Dana is in star form */ { for(unsigned a=0x218; a<=0x278; a+=8) if(RAM[a] != 0xF8 && (RAM[a] == 0xB0 || RAM[a] == 0xB2)) return true; return false; } static void GetTimer(unsigned& timer) { // 042C..042D seems to be a frame counter (16-bit)? // 043C..043D seems like another (also increments 043E sometimes)? timer = RAM[0x43B]*10000 + RAM[0x43A]*1000 + RAM[0x439]*100 + RAM[0x438]*10; } static unsigned char GenInput(size_t frameno, bool gennow=false) { static unsigned char LeftRight = 0x00; static const unsigned char c[] = { 0, K_L, K_R, K_L, K_R, K_L }; unsigned char genchar = c[GetRnd()]; bool did_gennow = (!gennow && (! GetRnd<15> () || frameno == 0)); if(did_gennow) LeftRight = genchar; unsigned char result = LeftRight; if(gennow) result = genchar; //if(! GetRnd<120> () ) result |= K_U; if(! GetRnd<150> () ) { result |= K_A; if(! GetRnd<10> () ) result |= K_D; } //if(! GetRnd<900> () ) result |= K_B; if(result & (K_A | K_D)) result &= ~(K_L|K_R|K_U); return result; } /* Compare two inputs, and decide whether newinput is simpler than oldinput */ static bool IsSimpler(const std::vector& newinput, const std::vector& oldinput) { int goodness = 0; int changes_old = 0, changes_new = 0; for(size_t a=0; a0 && oldinput[a]!=oldinput[a-1]) ++changes_old; if(a>0 && newinput[a]!=newinput[a-1]) ++changes_new; } if(!goodness) return changes_new < changes_old; return goodness > 0; } struct Objective { int x1,x2, y1,y2; int max_frames; bool Done() const { if(Death()) return false; //if(DoorAcquired) return true; if(y1 >= 0xF0) return false; int DanaX = RAM[0x589], DanaY = RAM[0x586]; if(DanaY >= 0xF8) return false; // handled by DoorAcquired //if(!KeyAcquired) return false; //For key if(DanaX < x1 || DanaX > x2) return false; if(DanaY < y1 || DanaY > y2) return false; return true; } bool EstImpossible(int curframe, int maxframe) const { if(max_frames < maxframe) maxframe = max_frames; int frames_left = maxframe - curframe; ++frames_left; // just in case :P int cur_x = RAM[0x589], cur_y = RAM[0x586]; if(cur_y == 0xF8) return false; if(y1 >= 0xF0) return false; int diff_x = 0, diff_y = 0; if(cur_x < x1) diff_x = x1-cur_x; else if(cur_x > x2) diff_x=cur_x-x2; if(cur_y < y1) diff_y = y1-cur_y; else if(cur_y > y2) diff_y=cur_y-y2; if(diff_y > frames_left*2) return true; if(diff_x > frames_left+4) return true; return false; } }; void Run() { /* Level 1 objectives: */ static const Objective objectives[] = { /* - level 1 { 0x28,0xFF, 0x00,0xF7, 5 }, { 0x51,0xFF, 0x00,0x80, 79 }, { 0x81,0xFF, 0x00,0x80, 83 }, { 0xB0,0xFF, 0x00,0x80, 85 }, { 0xC0,0xFF, 0x00,0x7E, 50 }, { 0x00,0xBC, 0x91,0xFF, 40 }, { 0x00,0xAC, 0xB1,0xFF, 50 }, { 0x00,0x98, 0x00,0xC1, 50 }, { 0x01,0xFF, 0xF8,0xFF, 60 } */ // Level 2: // { 0x6E,0xFF, 0x80,0xFF, 250 }, // { 0xA8,0xFF, 0x00,0x50, 400 }, // { 0x00,0xFF, 0xF0,0xFF, 3000 }, // { 0x00,0xFF, 0xF0,0xFF, 3000 }, // Level 3: // { 0x4F,0xFF, 0x00,0x3B, 100 }, // { 0x61,0xFF, 0x31,0xE0, 300 }, // { 0xC3,0xFF, 0x00,0xE0, 300 }, // { 0x00,0xFF, 0x52,0xE0, 300 }, // { 0xC0,0xCD, 0x70,0x80, 300 }, // alt 1 (left) // { 0xE2,0xFF, 0x80,0x80, 300 }, // alt 2 (right) // { 0xD8,0xE2, 0x81,0x82, 300 }, // alt 3 (down) // { 0x00,0xD1, 0xA2,0xE0, 60 }, // { 0x00,0xA1, 0x00,0xE0, 400 }, // { 0x00,0x9C, 0x00,0xE0, 400 }, // { 0x00,0x5D, 0x80,0xE0, 400 } // { 0x00,0x17, 0x00,0x90, 600 } // { 0x48,0xFF, 0x70,0x90, 300 } // Level 4: // { 0x00, 0x55, 0x50,0x60, 1500 } // { 0x70,0x84, 0x80,0x80, 200 } // Level 6: // { 0xA8,0xFF, 0x40,0x60, 600 } // { 0x0,0xA0, 0x90,0xA1, 1000 } // level 9: // { 0x46,0xFF,0x60,0x70, 300 } // { 0x7E,0xFF,0xB0,0xFF, 400 } // level 10: // { 0x00,0x60, 0x80,0xE0, 300 } // { 0x00,0xC0, 0x00,0x70, 400 } // { 0x00,0x42, 0x00,0x60, 400 } // level 11: // { 0x00,0x23, 0x00,0x90, 400 } { 0x25,0xFF, 0x60,0x70, 1059+50 } }; static const unsigned num_objectives = sizeof(objectives) / sizeof(*objectives); SaveState beststate; beststate.Create(); unsigned cur_objective = 0; NextObjective: BotFrontMsg("Trying objective %u\n", cur_objective); if(true) { SaveState obj_begin; obj_begin.Create(); unsigned num_stalls = 0; unsigned best_time = 9999, best_timer = 0, best_itemvalue = 0; unsigned best_timerchangeframe=0; std::vector BestInput; std::vector ModelInput; int TryingSimplify=-1; RebeginObjective: obj_begin.Load(); unsigned cur_frame = 0; int hadflames = 0, timerchangeframe=0; unsigned last_magic = 9999; unsigned itemvalue = 0; DoorAcquired=0; KeyAcquired=0; BqtItemAcquired=-1; if(cur_objective == 0 && BestInput.empty())// various { #define d(c,k) for(size_t n=0; n 0) { bool had_best = true; ModelInput = BestInput; size_t want_frames = objectives[cur_objective].max_frames; if(!BestInput.empty()) want_frames = BestInput.size(); // generate new model input if(best_time < 9999 && (best_time > want_frames || GetRnd<3>() == 0)) ModelInput.clear(); while(ModelInput.size() < want_frames) { had_best = false; unsigned char TryInput = GenInput(ModelInput.size()); ModelInput.push_back(TryInput); } // mutate it somehow if(had_best) { if(TryingSimplify >= 0 && num_stalls >= MinimumStallsBeforeSimplify) { int SimplifyCount=0; for(size_t n=1; n 0) { ++SimplifyCount; if(ModelInput[n] != ModelInput[n-1]) { if(TryingSimplify <= SimplifyCount) { TryingSimplify = SimplifyCount+1; ModelInput[n] = ModelInput[n-1]; if(ModelInput != BestInput) goto DoneSimplify; } } } } TryingSimplify = -1; } if(true) { // types of mutations: // delete a frame from somewhere, add new into beginning or end // duplicate an existing frame // add a new frame somewhere ReMutate:; size_t insert_minimum = ModelInput.empty() ? 0 : (rand() % ( ModelInput.size() - std::min((int)ModelInput.size(), 20) )); size_t maxmutationpos = insert_minimum + rand() % ( std::min( (int)(ModelInput.size() + 1 - insert_minimum), 10 + rand() % (60 + rand()%300) )); if(maxmutationpos==insert_minimum) ++maxmutationpos; size_t num_mutations = 1 + rand() % (4 + rand() % 70); int n_extra = 0; for(size_t n=0; n ModelInput.size()) maxmutationpos = ModelInput.size(); while(maxmutationpos<=insert_minimum && insert_minimum>0) --insert_minimum; if(insert_minimum == 0 && maxmutationpos == 0) break; switch(rand() % 9) { case 0: // delete a frame from some point case 1: { size_t delpos = insert_minimum + rand() % (maxmutationpos-insert_minimum); ModelInput.erase(ModelInput.begin() + delpos); --n_extra; --maxmutationpos; insert_minimum = delpos; // passthru } case 2: // add new frame somewhere case 3: { size_t inspos = insert_minimum + rand() % (maxmutationpos+1-insert_minimum); ++n_extra; if(GetRnd<8>() == 0 || inspos == ModelInput.size()) ModelInput.insert( ModelInput.begin() + inspos, GenInput(inspos,true)); else ModelInput.insert( ModelInput.begin() + inspos, ModelInput[inspos]); break; } case 4: case 5: case 6: case 7: { size_t rot_min = insert_minimum + rand() % (maxmutationpos-insert_minimum); size_t rot_max = rot_min + rand() % (maxmutationpos - rot_min); if(rot_max > rot_min) { size_t rot_mid = rot_min + rand() % (rot_max - rot_min); std::rotate(ModelInput.begin() + rot_min, ModelInput.begin() + rot_mid, ModelInput.begin() + rot_max); } break; } case 8: { size_t chg_min = insert_minimum + rand() % (maxmutationpos-insert_minimum); size_t chg_max = chg_min + rand() % (maxmutationpos - chg_min); if(chg_max > chg_min) for(size_t s=chg_min; s 0) ModelInput.resize(ModelInput.size() - n_extra); } DoneSimplify: if(ModelInput.size() > want_frames) ModelInput.resize(want_frames); //for(size_t n=0; n<30; ++n) ModelInput[n] &= ~K_U; if(best_time < 9999 && ModelInput == BestInput) goto ReMutate; /*fprintf(stderr, "%u,%u differ: ", ModelInput.size(), BestInput.size()); DisplaySeq(ModelInput); fprintf(stderr, " vs "); DisplaySeq(BestInput); fprintf(stderr, "\n");*/ } } MoreObjectiveFrames: int cur_x = RAM[0x589], cur_y = RAM[0x586]; { const Objective* obj = &objectives[cur_objective]; if(Death() || cur_frame > obj->max_frames || cur_frame > best_time || (cur_frame > 0 && obj->EstImpossible(cur_frame, best_time)) ) { RetryObjective: goto RebeginObjective; } static unsigned Timer, PrevTimer; PrevTimer=Timer; GetTimer(Timer); if(Timer != PrevTimer) timerchangeframe=cur_frame; switch(BqtItemAcquired) { case 0x00: if(cur_frame > 0) KeyAcquired=1; break; case 0x01: if(cur_frame > 0) DoorAcquired=1; break; case 0x09: case 0x12: case 0x85: itemvalue += 500; break; // fairy bell case 0x0F: itemvalue += 1500; break; // map tile: short fireball case 0x10: itemvalue += 2000; break; // long fireball case 0x86: itemvalue += 1000; break; // 1up, even rarer case 0x88: itemvalue += 1; break; case 0x89: itemvalue += 2; break; case 0x8A: itemvalue += 5; break; case 0x8B: itemvalue += 10; break; case 0x8C: itemvalue += 20; break; case 0x8D: itemvalue += 50; break; case 0x8E: itemvalue += 100; break; case 0x8F: itemvalue += 200; break; case 0x1A: itemvalue += 9000; break; // solomon seal } for(size_t n=0x210; n<0x2A0; n+=8) if(RAM[n]!=0xF8) if(RAM[n+1]==0xDE) ++hadflames; BqtItemAcquired = -1; /* level 3 hack 1: if(cur_x == 0xE2 && cur_y == 0x80) { RunFrameWith(K_L); RunFrameWith(K_A | K_D); for(size_t a=0; a<20; ++a) RunFrameWith(K_L); }*/ /* level 3 hack 2: if(cur_x > 0x5E) goto RetryObjective; */ /* level 4 hack: if(cur_y < 0x4E) goto RetryObjective; if(cur_y > 0xA0) goto RetryObjective; */ int hasghosts = 0; for(size_t n=0x210; n<0x2A0; n+=8) if(RAM[n]!=0xF8) if(RAM[n+1] >= 0x74 && RAM[n+1] <= 0x7C) ++hasghosts; if( //(DoorAcquired || KeyAcquired) || (last_magic >= 20 && obj->Done() // && itemvalue >= 9000 // && KeyAcquired // && !hasghosts //&& hadflames )) { if((num_stalls < MinimumStallsBeforeSimplify || TryingSimplify == -1) && cur_frame == best_time) ++num_stalls; size_t real_nframes = cur_frame; if(real_nframes > 0) --real_nframes; BotFrontMsg("wai %u? %u frames (%02X,%02X), %u stalls; timer=%u @ %u, simp=%d, items=%d\n", cur_objective, cur_frame, RAM[0x589],RAM[0x586], num_stalls, Timer,timerchangeframe, TryingSimplify, itemvalue); if(cur_frame < best_time || (cur_frame == best_time && ( Timer > best_timer || (Timer == best_timer && ( timerchangeframe > best_timerchangeframe || (timerchangeframe == best_timerchangeframe && ( itemvalue > best_itemvalue || (itemvalue == best_itemvalue && ( IsSimpler(ModelInput, BestInput) ))))))))) { std::vector ModelBackup = ModelInput; if(ModelInput.size() > real_nframes) ModelInput.resize(real_nframes+1); DisplaySeq(ModelInput); BotFrontMsg("\n"); if(ModelInput.size() > real_nframes) ModelInput.resize(real_nframes); obj_begin.Load(); for(size_t tmp = 0; tmp < ModelInput.size(); ++tmp) RunFrameWith(ModelInput[tmp]); FCEUSS_Save("best_mid.fcs"); if(cur_frame != best_time || (TryingSimplify <= 0 && IsSimpler(ModelInput, BestInput)) || Timer > best_timer || timerchangeframe > best_timerchangeframe || itemvalue > best_itemvalue ) num_stalls = 0; best_time = cur_frame; best_timer = Timer; best_itemvalue = itemvalue; best_timerchangeframe = timerchangeframe; if(BestInput != ModelBackup) { BestInput = ModelBackup; if(num_stalls > 0 && TryingSimplify > 0) --TryingSimplify; else TryingSimplify = 0; } goto RetryObjective; } if(cur_frame == best_time) { if(num_stalls >= MinimumStallsBeforeGoAhead) goto DoneObjective; goto RetryObjective; } } } if(cur_frame >= ModelInput.size()) goto RetryObjective; unsigned char TryInput = ModelInput[cur_frame]; /* if(cur_y >= 0x3F && cur_y <= 0x40 && cur_x <= 0xA4 && (TryInput & K_L)) goto RetryObjective; if(cur_y >= 0x5F && cur_y <= 0x60 && cur_x >= 0x40 && (TryInput & K_R)) goto RetryObjective; if(cur_y >= 0x7F && cur_y <= 0x80 && cur_x <= 0xA4 && (TryInput & K_L)) goto RetryObjective; if(cur_y >= 0x9F && cur_y <= 0xA0 && cur_x >= 0x40 && (TryInput & K_R)) goto RetryObjective; */ if(cur_y >= 0x54 && cur_y <= 0x5C) goto RetryObjective; ++last_magic; if(TryInput & (K_A | K_B)) last_magic = 0; RunFrameWith(TryInput); ++cur_frame; goto MoreObjectiveFrames; } DoneObjective: FCEUSS_Load("best_mid.fcs"); beststate.Create(); ++cur_objective; if(cur_objective < num_objectives) goto NextObjective; beststate.Load(); FCEUSS_Save("botfrontS-final.fcs"); } }; void MainLoop() { SoloKeyBot code; code.Run(); }