2048_playground.cpp

#include <iostream>
#include <vector>
#include <cassert>
#include <string>

void print_tab(int t)
{
    for (int i = 0; i < t; i++)
    {
        std::cout << "\t";
    }
}

constexpr int w = 4;
constexpr int h = 4;

struct Board
{
    uint8_t board[w][h];

    Board()
    {
        for (size_t i = 0; i < w; i++)
            for (size_t j = 0; j < h; j++)
            {
                board[i][j] = 0;
            }
    }

    void add(const int x, const int y, const uint8_t v)
    {
        if (board[x][y] != 0) { std::cout << "yo" << std::endl; }
        board[x][y] = v;
    }

    static bool IsSame(const Board& a, const Board& b)
    {
        for (int x = 0; x < w; x++)
        {
            for (int y = 0; y < h; y++)
            {
                if (a.board[x][y] != b.board[x][y])
                {
                    return false;
                }
            }
        }
        return true;
    }

    Board move_up(bool& moved) const
    {
        Board result;
        // each column
        for (int x = 0; x < w; x++)
        {
            // each row
            int yp = 0;
            for (int ys = 0; ys < h; ys++)
            {
                int cys = ys;
                uint8_t val = board[x][ys];

                // skip empty space
                if (val == 0)
                {
                    continue;
                }

                // search until the end of the row
                for (int ye = ys + 1; ye < h; ye++)
                {
                    if (board[x][ye] == 0)
                    {
                        ys++;
                        continue;
                    }

                    if (val == board[x][ye])
                    {
                        ys++;
                        val += 1;
                    }

                    // if (result.board[x][ys] == result.board[x][ye])
                    break;
                }

                result.board[x][yp++] = val;

            }
        }
        moved = !IsSame(result, *this);
        return result;
    }

    Board move_down(bool& moved) const
    {
        Board result;
        // each column
        for (int x = 0; x < w; x++)
        {
            // each row
            int yp = h - 1;
            for (int ys = h - 1; ys >= 0; ys--)
            {
                int cys = ys;
                uint8_t val = board[x][ys];

                // skip empty space
                if (val == 0)
                {
                    continue;
                }

                // search until the end of the row
                for (int ye = ys - 1; ye >= 0; ye--)
                {
                    if (board[x][ye] == 0)
                    {
                        ys--;
                        continue;
                    }

                    if (val == board[x][ye])
                    {
                        ys--;
                        val += 1;
                    }

                    // if (result.board[x][ys] == result.board[x][ye])
                    break;
                }

                result.board[x][yp--] = val;
            }
        }
        moved = !IsSame(result, *this);
        return result;
    }

    Board move_right(bool& moved) const
    {
        Board result;
        // each column
        for (int y = 0; y < h; y++)
        {
            // each row
            int xp = w - 1;
            for (int xs = w - 1; xs >= 0; xs--)
            {
                int cxs = xs;
                uint8_t val = board[xs][y];

                // skip empty space
                if (val == 0)
                {
                    continue;
                }

                // search until the end of the row
                for (int xe = xs - 1; xe >= 0; xe--)
                {
                    if (board[xe][y] == 0)
                    {
                        xs--;
                        continue;
                    }

                    if (val == board[xe][y])
                    {
                        xs--;
                        val += 1;
                    }

                    // if (result.board[x][ys] == result.board[x][ye])
                    break;
                }

                result.board[xp--][y] = val;
            }
        }
        moved = !IsSame(result, *this);
        return result;
    }

    Board move_left(bool& moved) const
    {
        Board result;
        // each column
        for (int y = 0; y < h; y++)
        {
            // each row
            int xp = 0;
            for (int xs = 0; xs < h; xs++)
            {
                int cxs = xs;
                uint8_t val = board[xs][y];

                // skip emptx space
                if (val == 0)
                {
                    continue;
                }

                // search until the end of the row
                for (int xe = xs + 1; xe < h; xe++)
                {
                    if (board[xe][y] == 0)
                    {
                        xs++;
                        continue;
                    }

                    if (val == board[xe][y])
                    {
                        xs++;
                        val += 1;
                    }

                    // if (result.board[y][xs] == result.board[y][xe])
                    break;
                }

                result.board[xp++][y] = val;
            }
        }
        moved = !IsSame(result, *this);
        return result;
    }

    Board move(const int m, bool& moved) const
    {
        if (m == 0) return this->move_left(moved);
        if (m == 1) return this->move_right(moved);
        if (m == 2) return this->move_up(moved);
        if (m == 3) return this->move_down(moved);
        assert(false);
    }

    void print(const int tab = 0) const
    {
        for (int x = 0; x < w; x++)
        {
            print_tab(tab);
            std::cout << " |";
            for (int y = 0; y < h; y++)
            {
                //std::cout << " " << char('0' + board[y][x]) << " ";
                if (board[y][x] == 0)
                {
                    print_tab(tab);
                    std::cout << "\t" << ".";
                }
                else
                {
                    print_tab(tab);
                    std::cout << "\t " << ((1 << static_cast<int>(board[y][x])));
                }
            }
            print_tab(tab);
            std::cout << "| " << std::endl;
        }
        return;
    }

    float eval_score() const
    {
        float score = 0;
        float num_non_empty_space = 0;
        for (int x = 0; x < w; x++)
        {
            for (int y = 0; y < h; y++)
            {
                if (board[y][x] != 0)
                {
                    //score += powf(2.0f, float(board[y][x]));
                    score = std::max(score, 2.0f);
                    num_non_empty_space += 1.0f;
                }
            }
        }
        return score * (w * h - num_non_empty_space);
    }

    int count_empty_space() const
    {
        int empty = 0;
        for (int x = 0; x < w; x++)
        {
            for (int y = 0; y < h; y++)
            {
                if (board[y][x] == 0)
                {
                    empty += 1;
                }
            }
        }
        return empty;
    }
};

const char* dir_to_c_str(const int m)
{
    if (m == 0) return "left";
    if (m == 1) return "right";
    if (m == 2) return "up";
    if (m == 3) return "down";

    return "";
}

struct Ans
{
    int m_direction;
    float m_score;
};

enum class Mode
{
    AdvMin,
    AdvAverage
};

constexpr Mode adv_mode = Mode::AdvMin;

Ans alg(const Board& b, bool& moved, const int depth, const std::string str)
{
    int max_m = 0;
    float max_score = 0;
    for (int m = 0; m < 4; m++)
    {
        std::string str1 = str + "  move(" + dir_to_c_str(m) + ")";

        bool hyp_moved = false;
        Board c = b.move(m, hyp_moved);
        if (hyp_moved)
        {
            moved = true;
        }
        else
        {
            continue;
        }

        if (depth == 0)
        {
            const float s = c.eval_score();
            /*
            c.print();
            std::cout << s << std::endl;
            std::cout << str1 << std::endl;
            */
            if (s >= max_score)
            {
                max_m = m;
                max_score = s;
            }
        }
        else
        {
            // place 2 or 4
            // try to find an x, y, k combination that minimize the score
            float adv_score = std::numeric_limits<float>::infinity();
            float p = 0.0f;
            for (int y = 0; y < h; y++)
            {
                for (int x = 0; x < w; x++)
                {
                    if (c.board[x][y] != 0)
                    {
                        continue;
                    }

                    for (int k = 1; k <= 2; k++)
                    {

                        c.board[x][y] = k;
                        std::string str2 = str1 + "  place(" + std::to_string(y) + ", " + std::to_string(x) + ", " + std::to_string(1 << k) + ")";

                        bool c_moved = false;
                        Ans ans = alg(c, c_moved, depth - 1, str2);
                        if (c_moved)
                        {
                            if (adv_mode == Mode::AdvMin)
                            {
                                adv_score = std::min(ans.m_score, adv_score);
                            }
                            else if (adv_mode == Mode::AdvAverage)
                            {
                                adv_score += ans.m_score;
                                p += 1.0f;
                            }
                        }

                        c.board[x][y] = 0;
                    }
                }
            }

            // average
            if (adv_mode == Mode::AdvAverage)
            {
                adv_score /= p;
            }

            if (adv_score >= max_score)
            {
                max_m = m;
                max_score = adv_score;
            }
        }
    }

    return Ans{ max_m, max_score };
}

int main()
{
    std::srand(1);

    Board b;
    int x, y, v;

    constexpr bool test = false;
    if constexpr (test)
    {
        std::cin >> y >> x >> v;
        b.add(x, y, int(std::log2(v)));
    }
    else
    {
        x = 0;
        y = 0;
    }

    int index = 0;

    /*
    b.add(0, 0, 1);
    b.add(0, 1, 2);
    b.add(0, 2, 3);
    b.add(0, 3, 4);

    b.add(1, 0, 1);
    b.add(1, 1, 2);
    b.add(1, 2, 3);
    b.add(1, 3, 4);

    bool p = false;
    const int result_dir = alg(b, p, 1, "").m_direction;
    if (!p)
    {
        return 0;
    }
    std::cout << dir_to_c_str(result_dir) << std::endl;;
    return 0;
    */

    while (true)
    {
        std::cout << "index : " << index << std::endl;
        if constexpr (test)
        {
            std::cin >> y >> x >> v;
        }
        else
        {
            // rejection sampling
            while (true)
            {
                x = std::rand() % w;
                y = std::rand() % h;
                v = 2;

                if (b.board[x][y] == 0)
                {
                    break;
                }
            }
            std::cout << y << " " << x << " " << v << std::endl;
        }
        b.add(x, y, int(std::log2(v)));
        b.print();

        bool moved = false;

        const int result_dir = alg(b, moved, 2, "").m_direction;
        if (!moved)
        {
            break;
        }
        std::cout << dir_to_c_str(result_dir) << std::endl;;
        b = b.move(result_dir, moved);
        b.print();
        index++;
    }

    return 0;
}