[Community Puzzle] 2048

https://www.codingame.com/multiplayer/optimization/2048

Send your feedback or ask for help here!

Created by @eulerscheZahl,validated by @wlesavo,@darkhorse64 and @Illedan.
If you have any issues, feel free to ping them.

4 Likes

That’s a perfect puzzle to study Beam Search Algirothm!
I used this as a tutorial: https://www.codingame.com/playgrounds/11358/breadth-first-search-and-beam-search-comparison
Climbed up to 32/109 without thinking about 2048 strategy.

10 Likes

Hi there. I liked the puzzle but it was a bit of a let down to discover
all test cases pass on submission without changing the code.
Looks like the right answer is always ‘U’. =/
I tried to submit using C#

Would be nice if you fixed it <3

2 Likes

This is an optimization puzzle, you’re supposed to get the best score possible. If you keep the default code, all testcases will pass, but you won’t have a very good score.

1 Like

Huh… doh.

My appologizes, I will try to read the full description next time. :confused:

Thank you!

Kind Regards

2 Likes

Same for C++

1 Like

And did you read the reply from hemhel right below?
Print something else than “U” and climb the leaderboard.

I don’t see 100% with the default code as a bug per se, the contribution just wasn’t created with the puzzle of the week achievement of the quest map in mind.
And I won’t change it now, as it would totally mess up the chances of new players to climb the leaderboard (at least for the lower and medium ranks).

3 Likes

Hello!
Very nice puzzle, it reminds me of my school years!!

However the spawnTile method copy-pasted from the github repo doesn’t seem to work for me… the spawned tile isn’t in the right place (the seed seems well managed however). And the direction values are reversed compared to the github repo (“URDL” on github, “LDRU”) in my code. But I can’t see why as my board seems oriented the same way as on github (rows = rows on the screen, col = columns on the screen).
Any idea why this is happening? @eulerscheZahl

Has anyone else had the same problem?

Thanks a lot if you can help me :slight_smile:

IIRC you have to count free cells column by column, not row by row, to determine which one gets a spawn.

3 Likes

oh thank you so much!!

How does the seed affect the new tiles that are spawned each turn :p?

The github link in the problem text takes you straight to the spawnTile() code.

1 Like

found this on HN today:
The Mathematics of 2048: Optimal Play with Markov Decision Processes (2018) | Hacker News
article:
The Mathematics of 2048: Optimal Play with Markov Decision Processes

2 Likes
Can't figure out how to calculate the position of the spawned number.

Example:
turn=1,seed=48610991
[[0 0 0 0]
 [0 2 0 0]
 [0 0 0 0]
 [0 2 0 0]]

turn=2,seed=35171608
[[0 0 0 0]
 [0 0 2 2]
 [0 0 0 0]
 [0 0 0 2]]
 
turn2 ist state after move 'RIGHT'. 
The spawned number 2 has position (1,2)

This is what I have tried:
If I make move 'RIGHT' form turn 1, the result is:
[[0 0 0 0]
 [0 0 0 2]
 [0 0 0 0]
 [0 0 0 2]]
 

Then I calculate the freeCells like its done in the Java-Github Code:
freeCells = []
for x in range(4):
    for y in range(4):
        if grid[x,y]==0:
            freeCells.append(x+4*y)
print(freeCells)
>>> [0, 4, 8, 12, 1, 5, 9, 2, 6, 10, 14, 3, 7, 11]

Then I calculate the spawnIndex with the seed from turn1 
spawnIndex = freeCells[48610991 % len(freeCells)]
print(spawnIndex)
>>> 10
Then I calculate the position of the new number:
print(spawnIndex % 4,spawnIndex // 4) 
>>> 2,2

But the position of the new number is (1,2). What am I missing?

Found the error:
this should be:

for y in range(4):
    for x in range(4):

What is the technique over 2,000,000 ? it’s my score. And the max command in one time.
2000000, it’s copy reverse the grid on diagonal, do a beam search, use the algorithm of the source code to calculate the score on the grid, and spawn a new tile with the same technique on the source code. Repeat the beam search with k=10 and depth=20, and keep path[0:7]. How to improve that ?

I thought I’d share my scores on the individual testcases. The color coding is as follows:

Green: My score is achieved online and is the theoretical maximum. There are 15 such cases.

Yellow: My score is partially hardcoded. I run an online solver, usually to around 1.74M and then it would get stuck online, but the rest of my solution is hardcoded (and heavily compressed). There are 12 cases like this.

Orange: Same as yellow but I was not able to find the theoretical maximum. There are 3 such cases.

By the way, the theoretical maximum is achieved by ignoring all movement restrictions and just letting tiles fall on top of eachother when they need to combine. It is entirely possible my scores are the actual highest possible, even for the orange 3. It is hard to be sure.

5 Likes

Hello everybody and especially MSmits (impressive 1st place),
I spent lot of time working on this puzzle and I’m pretty happy from my score (i’m just an amateur) :grin:

Nevertheless, I’m wondering how you can push a command list which size is greater than 2900 character with the limitation of 100 ko for a coding game file (29 x 3 ko is the maximum for all the cases) ?
Indeed, I wrote a C++ simulator in xcode which can double my score (by example : about 710 Ko for the first case seed = 290797) but i’m unabled to submit it because the produced string is 16 Ko for one case !!

You explain that you use heavily compressed “strings” but I studied theory about string compression and I don’t know how is possible to do that and CG dont permit use of zlib library …

Do you have some tips to share please :wink: ?

thanks !

Certainly I can do that. It’s not “compression” in the traditional sense. It’s more making use of the maximum capacity you can store in a character. I believe I did the following:

I store 4 moves in a single uint8_t (2 bits each, which means the array below has a capacity of 88k moves). Then I cram as many bytes as possible in as few unicode characters as I can. You can fit around 15 bit in a single unicode character, skipping some problematic characters that might be an issue copy/pasting into the CG IDE (at around unicode 8232 and in the early part of the unicode range)

Forgive the poor variable names in the code below. I did not bother renaming it to something sensible.
The code below is just the encoding. To decode, you need to do something similar. Try it yourself. If you can’t make it work, just reply here in a while and I will share the decoding function as well.

uint8_t outputCompact[22000] = { 0 };

void BytesToString()
{
    int bitIndex = 0;
    int number = 0;

    for (int i = 0; i < 1 + outputIndex / 4; i++)
    {
        uint8_t byte = outputCompact[i];
        number |= byte << bitIndex;
        bitIndex += 8;
        if (bitIndex >= 15)
        {
            int charNumber = number & 0x7FFF;
            charNumber += 95;
            if (charNumber + 97 >= 8232)
                charNumber += 2;

            wstring b = L"a";
            b[0] += charNumber;

            outputString += b;
            number = number >> 15;
            bitIndex -= 15;
        }
    }

    if (bitIndex > 0)
    {
        int charNumber = number & 0x7FFF;
        charNumber += 95;
        if (charNumber >= 8232)
            charNumber += 2;

        wstring b = L"a";
        b[0] += charNumber;
        outputString += b;
    }
    const std::locale utf8_locale = std::locale(std::locale(), new std::codecvt_utf8<wchar_t>());
    wofstream f(L"sample.txt");
    f.imbue(utf8_locale);
    f << outputString << endl;
    f.close();
}

1 Like

Ouaou !!! :ok_hand: :ok_hand: :ok_hand: :ok_hand:

thank you very much for the explanation !

I thought about ASCII “compression” (by example LL, LR, LD, LU = 1 ascii code) but i forgot unicode has many more possibilities !!

I’m not sure to be able to understand your code but I’m happy you shared it.
I will study it and certainly learn something new thanks to you

thank you very much
:clap: :clap: :clap: :clap: :clap:

1 Like