I made a new variant of the famous 2048 game. In this variant there are two types of tiles (2 and 3) that need to be merged separately. This makes the game considerably harder than the original.
I was wondering what is the optimal algorithm for playing this game that can achieve the highest score? I wrote a bot based on Monte Carlo. For a given state it runs K random simulations until the end of the game and records their final scores. It then plays the starting move that gave the highest average end-game score. I also noticed that if I limit my simulations to just 3 moves (down, left and right) then it achieves higher scores. After running this bot for a week with K=1000 I obtained a score of 3060. The final board position looked like this:
3 2 3 2 2 6 32 6 32 24 96 64 3 128 192 3
Even though this is higher than any score obtained by a human, I am wondering how we can do better and what is the highest score we can achieve?
I was inspired to write this question when I saw a similar question for the original game. In fact, one of the algorithms there (3rd popular) is the same as mine. However, I am not sure if other algorithms described there would work as well here, since they use heuristic evaluation functions that have been specifically tuned to the original game.
UPDATE 22nd September 2021
I tried the Monte Carlo Tree Search algorithm (UCT) with varying values for the exploration parameter. However the best it found was only around 1800, which seems rather low. Perhaps the implementation wasn't correct.
I also tried the Expectiminimax algorithm that returns the current score at depth 3. This gave me a score of 2972, which comes close to my best result. I tried adding bonuses for empty cells and adjacent numbers of the same colour, but they didn't help.
