How to solve Amen?

[HenryQuan]

I have posted something on reddit. This issue will collect some ideas from all the comments.

• Counting the max available combo and handling it differently by julchiar
  This could be a good idea because 7c, 8c, 9c, 10c and more are different if you think about it. The way how I did it doesn't consider the max combo
• More tomorrow

Update

After some testings, I found that this has to do with the algorithm. By increasing the size to 50000, I can found a solution when 10000 couldn't. The algorithm is too greedy and ignore the potential. Sometimes, even with 50000, it couldn't find a solution. The algorithm should look further. It is fine to be slower but yield better solutions. There can be two modes. Speed first or result first.

0.7 Beta

The performance has been improved 4 times compared to 0.6. I have tried size 100000 but it still couldn't find a better solution. This shows the limitation of the current implementation. V2 should resolve this or maybe with a better heuristic, it can also be resolved.

Better heuristics will definitely help the algorithm. I think I will try both approaches and keep improving the algorithm. Currently, size 10000 takes around 1.2s. In multiplay, every player has 30 seconds. That's the max step can be 200000. This is definitely unnecessary. I think size 20000 should produce a very good route.

[HenryQuan]

    int erased = 0;
    for (int i = 0; i < BOARD_SIZE; i++) {
        if (copy[i] == 0)
            erased++;
    }

    int remaining = BOARD_SIZE - erased;
    if (combo == 7 && remaining <= 3) {
        new_state.goal = true;
    }
    score -= remaining * 10;

    // for (const auto &c : list) {
    //     int size = c.loc.size();
    //     if (size == MIN_ERASE)
    //         score -= 10;
    //     score += (size - MIN_ERASE) * 5;
    // }

    new_state.combo = combo;
    if (combo < 7)
        score -= (7 - combo) * 30;
    if (combo == 7)
        score += 50;
    else if (combo > 7)
        score -= 50;
    new_state.score = score;

This one seems great so far. Make sure remaining is correct. This works surprisingly well.

[HenryQuan]

This evaluation can find the correct route almost all the time.