gomipuyoai

gomipuyoai.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cout << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;

const int dir_dx[] = { 0, 1, 0, -1 };
const int dir_dy[] = { 1, 0, -1, 0 };


namespace PuyoAI
{
struct Pos
{
    int x, y;
    Pos(int x, int y)
        : x(x), y(y)
    {
    }

    Pos()
    {
    }
};

const int MAX_WIDTH = 8;
const int MAX_HEIGHT = 16;
const int WIDTH = 6;
const int VANISH_SIZE = 4;
const int VISIBLE_HEIGHT = 13;
const int MAX_COLORS = 4;

// puyo colors
// >= 0 color is normal puyo
const int OJAMA = -1;
const int EMPTY = -2;
class Field
{
public:
    Field()
    {
        rep(y, height()) rep(x, width())
            field[y][x] = EMPTY;
    }

    int width() const
    {
        return WIDTH;
    }
    int height() const
    {
        return MAX_HEIGHT;
    }

    int get(int x, int y) const
    {
        assert(in_field(x, y));
        return field[y][x];
    }
    int get(const Pos& pos) const
    {
        return get(pos.x, pos.y);
    }

    void set(int x, int y, int color)
    {
        assert(in_field(x, y));
        assert(color >= -2);
        field[y][x] = color;
    }
    void set(const Pos& pos, int color)
    {
        set(pos.x, pos.y, color);
    }

    bool in_field(int x, int y) const
    {
        // 上方向に画面外はありで
        return 0 <= x && x < WIDTH && 0 <= y && y < MAX_HEIGHT;
    }

    bool fall()
    {
        bool any_fall = false;
        rep(x, width())
        {
            for (int y = 0, set_y = 0; y < height(); ++y)
            {
                if (get(x, y) != EMPTY)
                {
                    set(x, set_y, get(x, y));
                    if (set_y < y)
                        set(x, y, EMPTY);
                    ++set_y;

                    any_fall = true;
                }
            }
        }
        return any_fall;
    }

    vector<Pos> connected_puyo_pos(int x, int y)
    {
        int color = get(x, y);
        if (color < 0)
            return vector<Pos>();

        vector<Pos> pos;
        bool visited[MAX_HEIGHT][MAX_WIDTH];
        clr(visited, 0);
        list_connected_puyo_pos(x, y, color, visited, pos);
        return pos;
    }

    vector<Pos> puyo_pos_to_vanish_in_one_step()
    {
        vector<Pos> vanish_pos;
        bool visited[MAX_HEIGHT][MAX_WIDTH];
        clr(visited, 0);
        rep(y, height()) rep(x, width())
        {
            if (!visited[y][x] && get(x, y) >= 0)
            {
                vector<Pos> cpos = connected_puyo_pos(x, y);
                for (Pos& p : cpos)
                    visited[p.y][p.x] = true;
                if (cpos.size() >= VANISH_SIZE)
                    vanish_pos.insert(vanish_pos.end(), cpos.begin(), cpos.end());
            }
        }
        return vanish_pos;
    }

    int vanish_all()
    {
        int chain = 0;
        while (vanish_one_step())
            ++chain;
        return chain;
    }

    bool vanish_one_step()
    {
        vector<Pos> vanish_pos = puyo_pos_to_vanish_in_one_step();
        if (vanish_pos.empty())
            return false;

        for (Pos& p : vanish_pos)
            set(p, EMPTY);
        fall();

        return true;
    }

    vector<int> vanish_all_with_num()
    {
        vector<int> num;
        for (;;)
        {
            auto vpos = puyo_pos_to_vanish_in_one_step();
            if (vpos.empty())
                break;

            num.push_back(vpos.size());
            vanish_one_step();
        }
        return num;
    }

    string to_s() const
    {
        string s;
        for (int y = height() - 1; y >= 0; --y)
        {
            rep(x, width())
            {
                int c = get(x, y);
                if (c == EMPTY)
                    s += ' ';
                else if (c == OJAMA)
                    s += '*';
                else
                    s += 'A' + c;
            }
            s += "\n";
        }
        s = string(width(), '-') + s + string(width(), '-');
        return s;
    }

    string to_s_with_vanish()
    {
        auto vpos = puyo_pos_to_vanish_in_one_step();
        bool vani[MAX_HEIGHT][MAX_WIDTH];
        clr(vani, 0);
        for (Pos& p : vpos)
            vani[p.y][p.x] = true;

        string s;
        for (int y = height() - 1; y >= 0; --y)
        {
            rep(x, width())
            {
                if (vani[y][x])
                    s += '@';
                else
                {
                    int c = get(x, y);
                    if (c == EMPTY)
                        s += ' ';
                    else if (c == OJAMA)
                        s += '*';
                    else
                        s += 'A' + c;
                }
            }
            s += "\n";
        }
        s = string(width(), '-') + s + string(width(), '-');
        return s;
    }

private:
    int field[MAX_HEIGHT][MAX_WIDTH];

    void list_connected_puyo_pos(int x, int y, int color, bool visited[MAX_HEIGHT][MAX_WIDTH], vector<Pos>& pos)
    {
        visited[y][x] = true;
        pos.push_back(Pos(x, y));
        rep(dir, 4)
        {
            int nx = x + dir_dx[dir];
            int ny = y + dir_dy[dir];
            if (in_field(nx, ny) && !visited[ny][nx] && get(nx, ny) == color)
                list_connected_puyo_pos(nx, ny, color, visited, pos);
        }
    }
};

typedef pair<int, int> Tumo;
vector<pair<Pos, Pos>> cand_pos_to_put(const Field& field)
{
    const int out_y = VISIBLE_HEIGHT;
    vector<pair<Pos, Pos>> cand;

    // 横置き
    rep(x, field.width() - 1)
    {
        int y1 = out_y;
        while (y1 > 0 && field.get(x, y1 - 1) == EMPTY)
            --y1;

        int y2 = out_y;
        while (y2 > 0 && field.get(x + 1, y2 - 1) == EMPTY)
            --y2;

        if (y1 < out_y && y2 < out_y)
        {
            cand.push_back(make_pair(Pos(x, y1), Pos(x + 1, y2))); // AB
            cand.push_back(make_pair(Pos(x + 1, y2), Pos(x, y1))); // BA
        }
    }

    // 縦置き
    rep(x, field.width())
    {
        int y = out_y;
        while (y > 0 && field.get(x, y - 1) == EMPTY)
            --y;

        if (y < out_y)
        {
            cand.push_back(make_pair(Pos(x, y), Pos(x, y + 1)));
            cand.push_back(make_pair(Pos(x, y + 1), Pos(x, y)));
        }
    }

    return cand;
}

Tumo rand_tumo()
{
    return Tumo(rand() % MAX_COLORS, rand() % MAX_COLORS);
}

class SimpleAI
{
public:
    pair<Pos, Pos> solve(const Field& field, const vector<Tumo>& nexts)
    {
        dfs(field, nexts, 0);
        return result;
    }

private:
    pair<Pos, Pos> result;
    double dfs(const Field& field, const vector<Tumo>& nexts, int depth)
    {
        if (depth >= nexts.size())
            return eval(field);

        vector<pair<Pos, Pos>> cand = cand_pos_to_put(field);

        double max_score = -1;
        for (auto& pp : cand)
        {
            Field f = field;
            f.set(pp.first, nexts[depth].first);
            f.set(pp.second, nexts[depth].second);
            int chain = f.vanish_all();

            double score = dfs(f, nexts, depth + 1);
            if (chain >= 10)
                score = chain;
            if (score > max_score)
            {
                max_score = score;
                if (depth == 0)
                    result = pp;
            }
        }
        return max_score;
    }

    double eval(const Field& field)
    {
        double max_score = -1e80;
        rep(x, field.width())
        {
            int y = 0;
            while (y < field.height() && field.get(x, y) != EMPTY)
                ++y;

            for (int ty = y; ty < min(field.height(), y + 2); ++ty)
            {
                rep(color, MAX_COLORS)
                {
                    Field f = field;
                    f.set(x, ty, color);

                    double score = f.vanish_all();
                    upmax(max_score, score);
                }
            }
        }
        return max_score;
    }
};

void test_AI()
{
    SimpleAI ai;

    const int MAX_TURNS = 60;
    vector<Tumo> tumos;
    rep(i, MAX_TURNS)
        tumos.push_back(rand_tumo());

    map<int, int> chain_log;
    Field field;
    rep(turn, MAX_TURNS)
    {
        if (cand_pos_to_put(field).empty())
            break;

        const int SEEN_NEXTS = 3;
        vector<Tumo> nexts;
        for (int j = turn; j < min((int)tumos.size(), turn + SEEN_NEXTS); ++j)
            nexts.push_back(tumos[j]);

        pair<Pos, Pos> result = ai.solve(field, nexts);
        Field before_put = field;
        field.set(result.first, nexts[0].first);
        field.set(result.second, nexts[0].second);

#if 1
        Field before_vanish = field;
        int chain = field.vanish_all();
        ++chain_log[chain];
        if (chain > 0)
            fprintf(stderr, "turn %3d: %2d chains\n", turn, chain);
        if (chain >= 8)
        {
//             dump(turn);
//             dump(chain);
//             for (auto& it : chain_log)
//                 printf("%2d: %d\n", it.first, it.second);
//             cout << "===========\n" << endl;
// //             cout << before_put.to_s() << endl;
//             cout << before_vanish.to_s() << endl;
//
//             cout << "chain move" << endl;
//             Field tf = before_vanish;
//             do
//             {
//                 cout << tf.to_s_with_vanish() << endl;
//             } while (tf.vanish_one_step());

            return;
        }
#endif

//         cout << field.to_s() << endl;
    }
//     cout << "aa" << endl;
}

} // namespace PuyoAI

int main()
{
    using namespace PuyoAI;

    srand(time(NULL));
    test_AI();
//     for (;;)
//         test_AI();
}