Каков оптимальный слепой алгоритм для игры, 2048?

Игра 2048 взорвалась в популярности с момента ее выпуска в феврале 2014 года. Для описания игры и обсуждения оптимальных алгоритмов, см. Каков оптимальный алгоритм игры 2048?. Вот исходный код .

A слепой алгоритм для 2048 - тот, который не может видеть плату; единственная обратная связь, получаемая алгоритмом, заключается в том, произошел или нет попыток скольжения (мы можем предположить, что заблокированный слайд создает звуковой сигнал). Слепой алгоритм практически полезен для начала работы в 2048 году без необходимости уделять игре ваше пристальное внимание.

Вот мой конкретный вопрос: существует ли скрытый алгоритм для 2048, который последовательно делает лучше, чем средний балл 3500 в 10 ^ 6 испытаниях? (только после ответа, который вы подтвердили)

Это производительность алгоритма LADDER, который может быть обозначен как (LD * RD *) * (+ U). То есть, один цикл переместится "слева", "вниз" до тех пор, пока не застрянет, правый, вниз, пока он не застрянет "и нажимает вверх, если слева, справа и внизу заблокированы, что происходит, если верхний ряд (строки) полностью пуст, а нижний строки (строки) полностью заполнены. Я называю этот алгоритм LADDER из-за букв LDDR, и потому, что я думаю, что он поднимается по лестницам, таким как Марио в Donkey Kong. Мотивация алгоритма состоит в том, чтобы поддерживать растущий градиент сверху донизу, подобно многим неслепым алгоритмам.

Вот гистограмма для 10 ^ 6 испытаний LADDER, окрашенных верхней плитой на финальной доске с шириной 32 бункера и средним значением 3478.1. Я генерировал эти данные, моделируя игру и алгоритм в Python, используя вероятность 0,9, что каждая новая плитка равна 2, как в исходной игре. Вы не можете видеть 1024 игры в этой вертикальной шкале, но они распределены между 8000 и 16000. Распределение фракталов связано с количеством вхождений верхней плитки, второй-верхней плитки и т.д. Для сравнения, случайное затирание кнопок дало среднее значение около 800 в 10 ^ 4 испытаниях.

Ответ 1

Самое важное в игре 2048 года - сконцентрировать большие числа вдоль границ, а не посередине. Таким образом, очень хорошая стратегия состоит в том, чтобы положить все по дну как можно дольше. Ваш алгоритм LADDER делает это, но я хотел бы больше сосредоточиться на левой стороне, а не полностью переключиться на правую сторону. Это алгоритм в псевдокоде:

while(true)
    {
    if (down)
        continue;
    elseif(left)
        continue;
    elseif (right)
        continue;
    else
        {
        up;
        down; //if forced to go up; go back down immediately
        }
    }

Используя ваше соглашение, это будет:

((D*L)*R)U

в словах: опускайтесь столько, сколько сможете; если ты не можешь; иди налево; если вы не можете идти влево; Иди направо. Вам редко нужно подниматься.

Так как у меня не будет времени, чтобы реализовать это, чтобы использовать его в 10 раз; Я надеюсь, что кто-то другой может дать правильную статистику для этого, но я предполагаю, что это превзойдет ваш алгоритм LADDER.