struct CutmanGlitchNavigatorv2
{
    // How many frames to analyze each time
    static const unsigned Try_length   = 25;
    // How many frames to actually preserve
    static const unsigned Keep_length  = 6;
    
    // Define the range of parameters to be passed to Mutate().
    static const double MINMUTAATIO = 0.0010; // Minimum value, given to first candidates
    static const double MAXMUTAATIO = 6.4000; // Maximum value, given to last candidates
    // This controls the curve of mutation distribution 
    // (larger value = more big mutations, smaller value = more small mutations).
    // 1 = even distribution
    static const double LOGMUTAATIO = 0.4;
    
    static const unsigned WINNERS = 16; // number of winners to take each round for refinement

    // number of past-round winners to take each round, in case they were good but unlucky
    // (should only be used when the tasks given to the candidates are not identical)
    static const unsigned OLD_WINNERS = 0;

    // number of variations per each generation (PLUS WINNERS, which are preserved for competition)
    // larger number increases the chances of finding the Right Thing
    static const unsigned NUM_VARIATIONS = 900;
    
    // number of entirely randomly generated candidates to add each round
    static const unsigned NUM_RANDOMS = 400;

    // accept rule when no improvements have been found within this number of generations
    // larger number decreases the chances of missing the Right Thing
    static const unsigned min_generations_no_improvement = 80;

    static const unsigned NUM_FORKS = 2;
    static const unsigned NUM_CANDIDATES_PER_PROCESS = 300;

    template<unsigned Length>
    struct RandomInputCandidate
    {
        struct InputType
        {
            float A, B, Dir;
            //InputType() : A(0),B(0),Dir(0) { }
            
            static unsigned CountStates() { return 4*3; }
            void SetState(unsigned n)
            {
                A = (n%2 + 0.5) / 2.0; n/=2;
                B = (n%2 + 0.5) / 2.0; n/=2;
                Dir = (n%3 + 0.5) / 3.0; n/=3;
            }
            
            static unsigned CountSimpleMutations() { return 4; }
            void DoSimpleMutation(unsigned n)
            {
                switch(n)
                {
                    case 0: A=fmod(A + 1/2.0,1); break; // Flip A
                    case 1: B=fmod(B + 1/2.0,1); break; // Flip B
                    case 2: Dir = fmod(Dir+ 1/3.0, 1); break; // Change Dir to other value
                    case 3: Dir = fmod(Dir+ 2/3.0, 1); break; // Change Dir to another value
                }
            }
            
            const unsigned char GetKey() const
            {
                unsigned char res = 0;
                switch(((unsigned)(A*2))%2) { case 1: res |= K_A; }
                switch(((unsigned)(B*2))%2) { case 1: res |= K_B; }
                switch(((unsigned)(Dir*3))%3) { case 1: res |= K_R; break;
                                                case 2: res |= K_L; break; }
                return res;
            }
            
            void Mutate(double mut_amount)
            {
                unsigned r = lrand48();
                if(r & 0x0000F00F) // Chance: 10 bits
                    A = fmod(A+mut_amount, 1);
                if(r & 0x003F03F0) // Chance: 12 bits
                    Dir = fmod(Dir+mut_amount, 1);
                if(r & 0x04000400) // Chance: 2 bits
                    B = fmod(B+mut_amount, 1);
            }
            
            void Dump() const
            {
                printf("{%g,%g,%g}", A,B,Dir);
            }
        };

        InputType input[Length];
        
        double scoring,RockX; int scrolled, keepable;
        unsigned confidence;
        unsigned key;

        void Dump() const
        {
            printf("{ {");
            for(unsigned a=0; a<Length; ++a)
            {
                printf("%s", a?",":"");
                input[a].Dump();
            }
            printf("}, 0}");
        }
        
        static unsigned CountSimpleMutations()
        {
            return InputType::CountSimpleMutations() * Length;
        }
        
        void DoSimpleMutation(unsigned n)
        {
            input[n % Length].DoSimpleMutation(n / Length);
        }
        
        void Mutate(double amount)
        {
            amount *= Length;
            while(amount > 0.0001)
            {
                unsigned ind = lrand48() % Length;
                unsigned method = 0;
                if(amount > 0.2) method = lrand48() % 4;
                double mut_amount =
                    std::min(amount, std::min(0.95, 0.03+drand48()));
                /* Maximum of above is 0.95. */
                switch(method)
                {
                    case 0:
                    case 1:
                    { DoMut:
                        input[ind].Mutate(mut_amount);
                        break;
                    }
                    case 2: // insert a random item
                    {
                        for(unsigned b=Length-1; b > ind; --b)
                            input[b] = input[b-1];
                        goto DoMut;
                    }
                    case 3: // delete a random item
                    {
                        for(unsigned b=ind; b+1<Length; ++b)
                            input[b] = input[b+1];
                        ind = Length-1;
                        goto DoMut;
                    }
                }
                amount -= mut_amount;
            }
        }
        
        // transform the floating point value (0..<1) into an actual input
        const unsigned char get(unsigned ind) const
        {
            return input[ind].GetKey();
        }
        
        void DeleteFirst(unsigned n)
        {
            if(n > Length) return;
            unsigned remain = Length-n;
            for(unsigned a=0; a<remain; ++a)
                input[a] = input[a+n];
        }
        RandomInputCandidate<Length> CreateSeed(unsigned type)
        {
            scoring=0; confidence=0; key=0;
            for(unsigned a=0; a<Length; ++a)
                input[a].SetState(type);
            return *this;
        }
        
        RandomInputCandidate<Length> CreateRandom()
        {
            unsigned d = lrand48() % InputType::CountStates();
            for(unsigned pos=0; pos < Length; ++pos)
            {
                input[pos].SetState(d);
                if(!(lrand48()%5)) d = lrand48() % InputType::CountStates();
            }
            return *this;
        }
        
        bool IsSameAs(const RandomInputCandidate<Length>& b) const
        {
            for(unsigned a=0; a<Length; ++a)
                if(get(a) != b.get(a)) return false;
            return true;
        }
        bool IsSimplerThan(const RandomInputCandidate<Length>& b) const
        {
            unsigned complx_me=0, complx_b=0;
            for(unsigned a=0; a<Length; ++a)
            {
                complx_me += CountInputComplexity(get(a));
                complx_b  += CountInputComplexity(b.get(a)); 
            }
            return complx_me < complx_b;
        }
        
        static unsigned CountInputComplexity(unsigned char c)
        {
            unsigned res=0;
            for(unsigned a=1; a<=128; a*=2) if(c&a) ++res;
            return res;
        }
        
        /* Although this is "operator<", it really returns
         * whether this is "better" than the other, i.e.
         * higher score etc.
         */
        bool operator< (const RandomInputCandidate<Length>& b) const
        {
            if(scoring != b.scoring) return scoring > b.scoring;
            return IsSimplerThan(b);
        }
        
        const std::string GetAsString() const
        {
            unsigned char Buf[Length];
            for(unsigned a=0; a<Length; ++a)
                Buf[a] = get(a);
            return std::string(Buf, Buf+Length);
        }
    };

    void Run()
    {
        #define RunFrameWith(k)  \
            do { \
                CurInput = (k); FCEUI_FrameAdvance(); scrReturnV; \
                if(!Active)goto EndLoop; \
            } while(0)

        scrBegin;

        typedef RandomInputCandidate<Try_length> CandidateType;
        typedef std::deque<CandidateType> CandidateListType;
        static CandidateListType WinnerList;
        
        WinnerList.clear();

#if 0
        static const CandidateType model =
{ {{0,0,0.3},
   {0,0,0.3},
   {0,0,0.7},
   {0,0,0.3},
   {0,0,0.3},

   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},

   {0,0,0.7},
   {0,0,0.3},
   {0,0,0.7},
   {0,0,0.7},
   {0,0,0.3},

   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3},
   {0,0,0.3}
   }}
       ;WinnerList.push_back(model);
#endif
        
        /* Every iteration (Keep_length frames long) */
        for(;;)
        {
            /* Append the seed group to this list */
            for(unsigned a=0; a< CandidateType::InputType::CountStates(); ++a)
                WinnerList.push_back(CandidateType().CreateSeed(a));
            
            static SaveState itbegin;
            static double begin_x;
            static double best_scoring;
            static CandidateType best_candidate;
            static SaveState best_progress_snapshot;
            itbegin.Create();

            static unsigned generationno;
            static unsigned n_generations_no_improvement;

            begin_x = (unsigned short)(RAM[0x480]*256 + RAM[0x4A0])/ 256.0 + RAM[0x460]*256;
            best_scoring = -99999;
            n_generations_no_improvement = 0;

            static hash_set<std::string> covered_candidates;
            covered_candidates.clear();
            
            /* Generate NUM_VARIATIONS for as many generations as needed */
            for(generationno=1; ; ++generationno)
            {
                static CandidateListType CandidateList;
                /* generate new scorings from models */
                CandidateList = WinnerList;
                
                for(unsigned b=0; b<WinnerList.size(); ++b)
                for(unsigned a=0; a<CandidateType::CountSimpleMutations(); ++a)
                {
                    CandidateType tmp = WinnerList[b];
                    tmp.DoSimpleMutation(a);
                    tmp.confidence = 0;
                    
                    std::string c = tmp.GetAsString();
                    if(covered_candidates.find(c) != covered_candidates.end()) continue;
                    covered_candidates.insert(c);
                    
                    CandidateList.push_back(tmp);
                }
                
                if(n_generations_no_improvement > 0 || generationno==1)
                for(unsigned a=0; a<NUM_VARIATIONS; ++a)
                {
                    // Take one of the best as a model, and mutate a copy of it
                    unsigned randi = lrand48() % WinnerList.size();
                    CandidateType tmp = WinnerList[randi];

                    static const double minlog  = pow(LOGMUTAATIO, MINMUTAATIO);
                    static const double maxlog  = pow(LOGMUTAATIO, MAXMUTAATIO);
                    const double logpos = minlog + (a*(maxlog-minlog))/(NUM_VARIATIONS-1);
                    const double mut_amount = log(logpos) / log(LOGMUTAATIO);
                    
                    //if(generationno == 1)
                    //    fprintf(stderr, "Gen %u: mut_amount=%g\n", a, mut_amount);

                    tmp.confidence = 0;
                    tmp.Mutate(mut_amount);

                    std::string c = tmp.GetAsString();
                    if(covered_candidates.find(c) != covered_candidates.end()) continue;
                    covered_candidates.insert(c);

                    CandidateList.push_back(tmp);
                }
                //if(generationno==1){Active=0;}
                
                if(n_generations_no_improvement > 0 || generationno==1)
                for(unsigned a=0; a<NUM_RANDOMS; ++a)
                {
                    CandidateType tmp; tmp.CreateRandom();

                    std::string c = tmp.GetAsString();
                    if(covered_candidates.find(c) != covered_candidates.end()) continue;
                    covered_candidates.insert(c);

                    CandidateList.push_back(tmp);
                }

                WinnerList.clear(); // list of old winners not needed at this point
                
                ++n_generations_no_improvement;
                    
                static std::map<int, unsigned> pid_list;
                pid_list.clear();
                static unsigned candno;
                BotFrontDisableVideo=2;
                for(candno=0; candno<CandidateList.size(); candno+=NUM_CANDIDATES_PER_PROCESS)
                {
                    static int pid;
                    {int waitflag = (pid_list.size() < NUM_FORKS) ? WNOHANG : 0;
                    do {
                        int status=0;
                        int pid = waitpid(-1, &status, waitflag);
                        if(pid > 0)
                        {
                            if(WIFSIGNALED(status))
                            {
                                fprintf(stderr, "Child died at signal %d\n",
                                    WTERMSIG(status));
                            }
                            pid_list.erase(pid);
                        }
                        waitflag=0;
                    } while(pid_list.size() >= NUM_FORKS); }
                    
                    fflush(stdout);
                    fflush(stderr);
                    pid = fork();
                    if(pid > 0)
                    {
                        pid_list[pid] = candno;
                        fprintf(stderr, "."); fflush(stderr);
                        continue;
                    }
                    if(pid < 0)
                    {
                        perror("fork");
                    }
                    MovieForkIntoTempFiles();
                    
                    static unsigned candcounter;
                    for(candcounter=0; candno<CandidateList.size()
                                    && candcounter<NUM_CANDIDATES_PER_PROCESS;
                                    ++candcounter, ++candno)
                    {
                        static CandidateType* candit;
                        candit = &CandidateList[candno];

                        itbegin.Load();
                        /*
                        fprintf(stderr, "Trying(%u) input:", (unsigned)framecount);
                        for(frameno=0; frameno<Try_length; ++frameno)
                            fprintf(stderr, " %02X", candit->get(frameno));
                        */
                        
                        candit->scoring = 0.0;
                        candit->scrolled= 0;
                        BqtScrolled=0;
                        BqtMegaKilled=0;
                        static unsigned frameno;
                        for(frameno=0; frameno<Try_length; ++frameno)
                        {
                            //fprintf(stderr, "pid %d: frame %u\n", getpid(), frameno);
                            BqtMegaKilled=0;
                            RunFrameWith(candit->get(frameno));
                            if(BqtMegaKilled) goto BadScore; // death occurred!
                            if(BqtScrolled)
                            {
                                // ycoordinate hack
                                //if(RAM[0x460] >= 0x29) goto BadScore;
                                if(frameno+1 < Try_length)
                                    ++frameno; // break the NEXT frame to prevent Infinity
                                break;
                            }
                        }
                        static unsigned keepable_frames;
                        keepable_frames = frameno < Keep_length ? frameno : Keep_length;
                        
                        /* TODO: In the vertical fall in Wily2, calculate score
                         * by the horizontal distance from the spot where the
                         * teleporter appear.
                         */
                         
                        /* Clone robot room:
                         *     Optimal X = 10576
                         */
                        
                        static double RockX;
                        RockX = (unsigned short)(RAM[0x480]*256 + RAM[0x4A0])/ 256.0 + RAM[0x460]*256;
                        
                        //if(!BqtScrolled && RockX >= 8312) goto BadScore; // TOO FAR
                        
                        if(BqtScrolled)
                            RockX /*+*/= 256 + 5*(Try_length-frameno); // Award scrolling justly!

                        if(BqtScrolled)
                        {
                            // Minimal distance to Clone robot's spot is important
                            if(RAM[0x460] < 0x28)
                                RockX = RockX*16 - std::abs(RAM[0x480] + RAM[0x4A0]/256.0
                                                  - 0x36)*16;
                            else
                            {
                                unsigned sweetspot = 0x50;
                                if(RAM[0x600] < 252) RockX=1;
                                else RockX -= (sweetspot - RAM[0x480]) & 255;
                                if(!(RAM[0x420] & 0x40)) goto BadScore; // should be facing right
                            }
                         //   candit->scoring = RockX;
                        }
                        else
                            candit->scoring = 0;//(RockX - begin_x) / frameno;
                        //if(BqtScrolled) candit->scoring = RAM[0x600]; - ycoordinate hack
                        // Extra award for scrolling on how soon it happened!
                        //if(BqtScrolled) candit->scoring += (Try_length-frameno)*1.1;
                        candit->confidence++;
                    BadScore:
                        char candfn[128]; sprintf(candfn, "/tmp/cand%d.res", (int)candno);
                        FILE*fp = fopen(candfn, "wt");
                        if(fp)
                        {
                            fprintf(fp, "%g,%d,%g,%d,%d\n",
                                candit->scoring,
                                candit->confidence,
                                RockX,BqtScrolled,keepable_frames);
                            fclose(fp);
                        }
                        else
                            perror(candfn);
                    }
                    fflush(stdout);
                    fflush(stderr);
                    _exit(0);
                }
                BotFrontDisableVideo=1;

                while(pid_list.size() > 0)
                {
                    int status=0;
                    int pid = waitpid(-1, &status, 0);
                    if(pid > 0)
                    {
                        if(WIFSIGNALED(status))
                        {
                            fprintf(stderr, "Child died at signal %d\n",
                                WTERMSIG(status));
                        }
                        pid_list.erase(pid);
                    }
                }
                
                fprintf(stderr, "\r");
                /* Read the results from the tasks */
                for(candno=0; candno<CandidateList.size(); ++candno)
                {
                    CandidateType* candit = &CandidateList[candno];
                    candit->key = candno;

                    char candfn[128]; sprintf(candfn, "/tmp/cand%d.res", (int)(candno));
                    if(FILE*fp = fopen(candfn, "rt"))
                    {
                        fscanf(fp, "%lg,%d,%lg,%d,%d",
                            &candit->scoring,
                            &candit->confidence,
                            &candit->RockX,
                            &candit->scrolled,
                            &candit->keepable);
                        fclose(fp);
                    }
                    else
                    {
                        perror(candfn);
                    }
                    unlink(candfn);
                }

                // Sort the new-round candidates, best-first
                std::sort(CandidateList.begin(), CandidateList.end());
                
                /* Check if there was a new winner */
                for(candno=0; candno<CandidateList.size(); ++candno)
                {
                    static CandidateType* candit;
                    candit = &CandidateList[candno];

                    if(candit->scoring > best_scoring)
                    {
                    MakeNewBest:
                        fprintf(stderr, "New record [%u/%u]: %g (RockX=%g%s)\n",
                            candit->key, (unsigned)CandidateList.size(),
                            candit->scoring,
                            candit->RockX, candit->scrolled?" SCROLLED":"");

                        {std::vector<unsigned char> seq;
                        for(unsigned frameno=0; frameno < Try_length; ++frameno)
                            seq.push_back(candit->get(frameno));
                        DisplaySeq(seq);}
                        printf("\n");
                        candit->Dump();
                        printf("\n");
                    
                        best_scoring   = candit->scoring;
                        best_candidate = *candit;
                        
                        // Replay the first N frames of the input and make a snapshot
                        itbegin.Load();
                        static unsigned frameno;
                        for(frameno=0; frameno < candit->keepable; ++frameno)
                            RunFrameWith(candit->get(frameno));
                        
                        best_progress_snapshot.Create();
                        // save a progress snapshot (savestate) on disk for manual inspection
                        FCEUSS_Save("botfront2-middle");
                        
                        // reset the no-progress counter
                        n_generations_no_improvement = 0;
                    }
                    else if(candit->scoring == best_scoring)
                    {
                        // If this candidate has the same score as the winner,
                        // check if this one is simpler.
                        
                        if(candit->IsSimplerThan(best_candidate))
                            goto MakeNewBest;
                        else if(best_candidate.IsSimplerThan(*candit))
                            candit->scoring /= 2.0; // Forget it!
                    }
                }
                
                std::sort(CandidateList.begin(), CandidateList.end());

                // Regenerate the inheritor list.
                
                {unsigned keycode=0;
                for(CandidateListType::iterator
                      i=CandidateList.begin();  
                      i!=CandidateList.end(); ++i)
                {
                    i->key = keycode++;
                }}

                if(OLD_WINNERS > 0)
                {
                    // Pass 1: Take the previous-pass winners that still are living.
                    for(CandidateListType::iterator
                          i=CandidateList.begin();  
                          i!=CandidateList.end(); ++i)
                    {
                        if(i->confidence > 1) // >1 signifies a previous-pass winner
                        {
                            // It loses 1 life, but still has a chance
                            CandidateType tmp = *i;
                            --tmp.confidence;
                            WinnerList.push_back(tmp);
                        }
                    }
                    // Sort them, best first.
                    std::sort(WinnerList.begin(), WinnerList.end());

                    // Crop the previous-pass winners list to the maximum size.
                    if(WinnerList.size() > OLD_WINNERS)
                        WinnerList.erase(WinnerList.begin() + OLD_WINNERS,
                                           WinnerList.end());
                }
                
                if(WINNERS > 0)
                {
                    unsigned take_winners = WINNERS;
                    if(!n_generations_no_improvement) take_winners = 1;
                    
                    // Pass 2: Take best candidates from the new round
                    unsigned newwinners = 0;
                    for(CandidateListType::const_iterator i=CandidateList.begin();
                          newwinners < take_winners && i!=CandidateList.end(); ++i)
                    {
                        CandidateListType::const_iterator j;
                        
                        /* Ensure that the candidate in question wasn't already
                         * included in the list (previous-round winners)
                         */
                        for(j=WinnerList.begin(); j!=WinnerList.end(); ++j)
                        {
                            if(j->key == i->key) goto Already_Had;
                            if(i->IsSameAs(*j)) goto Already_Had;
                        }
                        
                        WinnerList.push_front(*i);
                        ++newwinners;
                    Already_Had: ;
                    }
                }
                 
                Averaging quality_all, quality_best;
                for(CandidateListType::const_iterator i=WinnerList.begin();
                      i!=WinnerList.end(); ++i)
                    quality_best.Cumulate(i->scoring);
                for(CandidateListType::const_iterator i=CandidateList.begin();
                      i!=CandidateList.end(); ++i)
                    quality_all.Cumulate(i->scoring);
                
                best_progress_snapshot.Load();
                fprintf(stderr, "Average quality of generation %u @ %u: %g (all), %g (inheritors)\n",
                    generationno, (unsigned)framecount,
                    quality_all.GetValue(), quality_best.GetValue());
    
                if(n_generations_no_improvement >= min_generations_no_improvement) break;
                
                /*if(n_generations_no_improvement >= 6
                && quality_best.GetValue() == 0.0)
                {
                    fprintf(stderr, "Giving up, nothing seems to happen in this frame\n");
                    break;
                }*/
            } // proceed to next generation
            
            covered_candidates.clear();
            
            fprintf(stderr, "- next %u frames!\n", Keep_length);
            best_progress_snapshot.Load();
            
            for(CandidateListType::iterator i=WinnerList.begin();
                  i!=WinnerList.end(); ++i)
                i->DeleteFirst(Keep_length);
        }
    EndLoop: ;

        scrFinishV;
        #undef RunFrameWith
    }
};