puyopuyo zenbu mieteru

main.cc

#include <gflags/gflags.h>
#include <glog/logging.h>

#include "base/base.h"
#include "core/algorithm/plan.h"
#include "core/algorithm/rensa_detector.h"
#include "core/client/ai/ai.h"
#include "core/core_field.h"
#include "core/frame_request.h"
#include "core/sequence_generator.h"

#include <iostream>
using namespace std;


string makePuyopURL(const KumipuyoSeq& seq, const vector<Decision>& decisions)
{
    static const char ENCODER[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ[]";
    stringstream ss;

    ss << "http://www.puyop.com/s/_";

    for (size_t i = 0; i < 50; ++i) {
        const Kumipuyo& kp = seq.get(i);
        int d = 0;
        switch (kp.axis) {
        case PuyoColor::RED:
            d += 0;
            break;
        case PuyoColor::GREEN:
            d += 1 * 5;
            break;
        case PuyoColor::BLUE:
            d += 2 * 5;
            break;
        case PuyoColor::YELLOW:
            d += 3 * 5;
            break;
        default:
            CHECK(false);
        }

        switch (kp.child) {
        case PuyoColor::RED:
            d += 0;
            break;
        case PuyoColor::GREEN:
            d += 1;
            break;
        case PuyoColor::BLUE:
            d += 2;
            break;
        case PuyoColor::YELLOW:
            d += 3;
            break;
        default:
            CHECK(false);
        }

        if (i < decisions.size()) {
            int h = (decisions[i].x << 2) + decisions[i].r;
            d |= h << 7;
        }

        ss << ENCODER[d & 0x3F] << ENCODER[(d >> 6) & 0x3F];
    }

    return ss.str();
}



struct State
{
    CoreField field;

    double score;
    int max_chains_until;
    int fired_chains;

    vector<Decision> decisions;

    bool fired_main_chain() const
    {
        return fired_chains > 0;
    }
};
std::vector<State> next_states(const State& current_state, const Kumipuyo& kumipuyo)
{
    std::vector<State> nexts;
    auto drop_callback = [&](const RefPlan& plan)
    {
        const CoreField& field = plan.field();
        RensaResult rensa_result = plan.rensaResult();
        if (2 < rensa_result.chains && rensa_result.chains < 6)
            return;

        std::vector<Decision> decisions = current_state.decisions;
        DCHECK(plan.decisions().size() == 1);
        decisions.push_back(plan.decision(0));

        if (rensa_result.chains >= 10)
        {
//             cout << kumipuyo.toString() << endl;
//             cout << current_state.field.toDebugString() << endl;
//             std::cout << rensa_result.chains << std::endl;
            State next = State {
                .field = field,
                .score = (double)rensa_result.score,
                .max_chains_until = current_state.max_chains_until,
                .fired_chains = rensa_result.chains,
                .decisions = decisions
            };
            nexts.push_back(next);
            return;
        }

        int max_chains = current_state.max_chains_until;
        bool prohibits[FieldConstant::MAP_WIDTH]{};
        auto complement_callback = [&max_chains](CoreField&& complemented_field, const ColumnPuyoList&)
        {
            RensaResult rensa_result = complemented_field.simulate();
            max_chains = std::max(max_chains, rensa_result.chains);
        };
        RensaDetector::detectByDropStrategy(field, prohibits, PurposeForFindingRensa::FOR_FIRE, 2, 13, complement_callback);

        State next = State {
            .field = field,
            .score = (double)max_chains,
            .max_chains_until = max_chains,
            .fired_chains = 0,
            .decisions = decisions
        };
        nexts.push_back(next);
    };
    Plan::iterateAvailablePlans(current_state.field, {kumipuyo}, 1, drop_callback);
    return nexts;
}
void beamsearch(KumipuyoSeq seq)
{
    const int TURNS = 50;
    const int BEAM_WIDTH = 10000;
    DCHECK(seq.size() >= TURNS);

    std::vector<State> fired[TURNS + 1];
    std::vector<State> state_q[TURNS + 1];
    State init_state = State {
        .field = CoreField(),
        .score = 0,
        .max_chains_until = 0,
        .fired_chains = 0,
        .decisions = {}
    };
    state_q[0].push_back(init_state);

    int max_chains = 0;
    for (int turn = 0; turn < TURNS; ++turn)
    {
        for (const State& state : state_q[turn])
        {
            for (const State& next : next_states(state, seq.get(turn)))
            {
                if (next.fired_main_chain())
                {
                    fired[turn + 1].push_back(next);
                    max_chains = std::max(max_chains, next.fired_chains);
                }
                else
                    state_q[turn + 1].push_back(next);
            }
        }

        std::sort(state_q[turn + 1].begin(), state_q[turn + 1].end(), [](const State& a, const State& b){ return a.score > b.score; });
        if (state_q[turn + 1].size() > BEAM_WIDTH)
            state_q[turn + 1].erase(state_q[turn + 1].begin() + BEAM_WIDTH, state_q[turn + 1].end());
    }

    vector<State> fired_states;
    for (int turn = 0; turn < TURNS; ++turn)
    {
        std::sort(fired[turn].begin(), fired[turn].end(), [](const State& a, const State& b){ return a.fired_chains > b.fired_chains ; });
        for (const State& state : fired[turn])
        {
            if (state.fired_chains == max_chains)
            {
                cout << state.fired_chains  << " chains / URL: " << makePuyopURL(seq, state.decisions) << endl;
                return;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    google::ParseCommandLineFlags(&argc, &argv, true);
    google::InitGoogleLogging(argv[0]);
    google::InstallFailureSignalHandler();

//     KumipuyoSeq seq = generateRandomSequenceWithSeed(0);
    KumipuyoSeq seq = generateRandomSequence();
    beamsearch(seq);
}