Пользователь
0,0
рейтинг
15 марта 2014 в 18:23

Разработка → Простая стратегия игры 2048

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

Студентам физфака тоже было весело, поэтому мы придумали простую эвристическую выигрышную (по крайней мере, нам удалось набрать 2048 в 9 из 10 раз) стратегию этой игры.

Занумеруем идущие подряд столбцы (можно и строки, но в дальнейшем я буду говорить о столбцах) от 1 до 4 (последовательно слева направо или справа налево). Основополагающим принципом стратегии является расположение чисел, при котором мы полностью заполняем 1ый столбец наибольшими доступными числами. При этом, во 2ом столбце числа в среднем меньше, чем в 1ом, а в 3ем меньше, чем во 2ом. Причем, только на последних этапах игры в 3ем столбце возможно появление чисел среднего номинала (где-то до 32).

Из этого принципа следует, что при выборе хода предпочтение мы должны отдать такому, который увеличивает числа первых столбцов. Таким образом, мы всегда сохраняем градиент заполнения чисел и соответственно не отклоняемся от вышеизложенного принципа.

Например, используя в качестве 1ого столбца левый, мы никогда не будем использовать клавишу →, чтобы не отклоняться от принципа.

Существенный тонкий нюанс: при заполнении выбранных столбцов нужно избегать ситуации, когда новое появившееся число может полностью заполнить столбец так, что нам придется сделать ход →, что полностью сведет на нет возможность продолжать играть по нашей стратегии.

Для наглядности прилагается картинка и видео:

image
@WhatIsGTO
карма
7,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (43)

  • +4
    Например, используя в качестве 1ого столбца левый, мы никогда не будем использовать клавишу →, чтобы не отклоняться от принципа.

    Может быть ситуация, когда столбцы слева полностью заполнены и тогда придется нажать эту клавишу.
    • 0
      Да, спасибо, забыл разобрать в статье этот нюанс.
      • +1
        Добавил.
        • 0
          Замечу, что что такая ситуация не приводит к неминуемому проигрышу. Достаточно на 1 ход сместиться вправо, а потом опять влево. Главное — поскорее слить «двойку» в левой колонке.
          • +1
            Согласен, замечу, что слить эту двойку в левой колонке возможно, правда довольно сложно, особенно к концу игры, поэтому этот ход мы не включили в стратегию.
          • 0
            Да, это вообще не проблема, даже если приходится идти на такой ход несколько раз за игру.
  • +19
    Есть более выйгрышная стратегия:

    Заполняем первый ряд по убыванию значения фишек слева направо. Второй ряд заполняем фишками по убыванию справа налево. Получается змейка из возрастающих фишек. Таким образом задача сводится к меньшей: чтобы собрать 1024, нужно собрать сначала 512, а для этого надо собрать 256 и т.д.

    image

    Такая стратегия позволила нам собрать фишку 8192.

    Кстати да, версии посложнее: 4096, 8192
    • +1
      Согласен, что ваша лучше, и моя стратегия не претендует на идеальную. Ее основное преимущество в простоте набора фишки номинала 2048.
    • +2
      Я тоже применял эту стратегию и добился выигрыша. Отмечу еще, что в начале и середине игры эффективным получается заполнять матрицу по диагонали, так чтобы образовывался треугольник максимальным значением в выбранной вершине и далее по градиенту.

      Тогда очень часто удается делать множественные слияния и получается избегать значений, выбивающихся из желаемого порядка (это если всегда стремиться слить как можно быстрее).
    • +3
      Я тоже использовал такую стратегию. Стоит заметить что при такой стратегии надо следить что бы не делать ходы < — и -> если верхний столбец не заполнен.
    • 0
      Тоже практически сразу пришел к этой стратегии.

      Еще получить 128 (иногда 256) можно постоянно быстро нажимая верх/право (если мы собираем самое большое число в правом верхнем углу) и иногда вниз или влево. Это намного быстрее, чем делать это разумно.
    • 0
      При этой стратегии возникает проблема, когда после частичного схлопывания первого ряда (на вашей картинке — верхнего) его приходится двигать вправо (так как ходов влево и вверх не осталось). И слева от 2048 вдруг возникает двойка. Как вы с этим боретесь?
      • 0
        Стараться не допускать такой ситуации. Если возникла двойка, то затем есть маленький шанс поставить все как было, но у меня редко получается.
    • +3
      Долгие убитые часы жизни, но зато получилась отличная иллюстрация для стратегии «змейки». После того как собрал тайл 16384, имею более 200 тыс. очков. Почему-то сомневаюсь, что удастся собрать 32-тысячный блок, но если не будет сбоев, попробую на неделе довести дело до победного конца.

      • +2
        В продолжение темы еще один пример эффективности стратегии «змейка». Мне-таки удалось добраться до 32768, ура!
        В итоге 452 тыс. очков.


        Надо сказать, что переигрывать приходится все чаще, так как случайный фактор никакой стратегией и тактикой в этой игре не преодолим (по-моему).
        И еще возникло несколько интересных вопросов и гипотез (на любителей, конечно). А именно: если бы нужное число (двойка или четверка) появлялось всегда в нужной нам клетке, то
        1) какой в принципе максимальный тайл можно собрать?
        2) какое максимальное количество очков можно набрать?
        3) сколько может длиться самая длинная (по количеству ходов) игра?
        Чтобы не усложнять задачи, можно считать, что выпадает всегда 2-ка или всегда 4-ка. Так как двойка выпадает по игре чаще я решил остановиться на первом варианте.

        Мои гипотезы таковы:
        1. Руководствуясь стратегией «змейка», можно заключить, что максимальный тайл — это 216, т.е. 65536. Для этого нужно построить змейку с началом в левом верхнем углу (2-ка) и концом в левом нижнем (32768).

        2. После получения максимального тайла можно будет продолжить выстраивать змейку, пока не заполним все шестнадцать клеток числами 2, 4, 8, 16, ..., 216. Сколько очков мы при этом заработаем?

        Предположим, мы впервые получили на поле тайл «4». Это означает, что у нас не менее 4 очков (не менее, так как нет гарантий, что мы не получили одним ходом сразу несколько тайлов «4»).
        Далее, увидев на поле тайл «8», можем не сомневаться, что очков как минимум 16 (4+4+8).
        В случае тайла «16» — призовых уже не менее чем 48 (16+16+16). В свою очередь «32» обещает нам целых 128 поинтов (48+48+32).
        Если обозначить сопутствующее тайлу «2n» количество очков через функцию f (n), то верно следующее рекуррентное соотношение:
        f (n) = 2f (n — 1) + 2n.
        Его можно решить, заметив, что f (n) = 4f (n — 2) + 2*2n = 8f (n — 3) + 3*2n =… = 2(n — 2)f (2) + (n — 2)2n. С учетом f (2) = 4, получаем:
        f (n) = 2n(n — 1).

        Когда все игровое поле будет заполнено как указано выше (двойками в степени от 2 до 16), количество заработанных очков уже будет составлять не «не менее», а ровно: S = f (16) + f (15) +… + f (2). Вычисления показывают, что S = 1 835 012.

        Итого, максимальное количество очков, которое можно набрать в игре 2048, это 1 835 012.

        Что касается третьей задачи — пока никаких изящных идей не возникает.

        Беда в том, что полученные мной ответы на первый и второй вопросы не имеют строгого обоснования и мне пока не совсем понятно, как можно доказать сделанные выводы.

        Тем не менее, если принять мои гипотезы на веру, то можно констатировать не слишком радостный для меня факт: я прошел игру всего лишь где-то на 25%, если судить по доли набранных очков (452 тыс.) по отношению к максимально возможному их числу.
        • +1
          Можно получить 2^17 — если после построения змейки 4..2^16 на последнем поле появляется четверка :)

          Немного смущает соотношение Score и Best на картинке. Вам удалось получить 16384 и построить змейку от него больше одного раза??? Вот это упорство!
          • +1
            Вы правы насчет максимального тайла. Если нам будет везти на четверки, то в игре можно добраться до 217. И максимальное количество очков соответственно больше. Я не рассматривал этот случай (о чем сразу оговорился в комментарии) просто для конкретизации и упрощения задачи.

            А насчет соотношения Score и Best — в запале игры начал сворачивать змейку на пути к 32 тыс. блоку, а потом вспомнил, что не сделал скрин. Пришлось переигрывать с последнего «сейва» (он делается путем дублирования вкладки).

            Я ведь писал выше — без переигрываний такую картинку получить, как мне кажется, крайне маловероятно. Случайный фактор, видимо, непреодолим. Поэтому если вдруг мой компьютер перезагрузится, например, или еще какой сбой произойдет, то мне не удастся увидеть нижний ряд состоящий сплошь из черных тайлов (на собирание 64 тыс. блока я всерьез не рассчитываю).
            • 0
              Дублирование — это хорошая идея. Сразу игра пошла :) Пока что в нижнем ряду есть 1024, 16К и 32К, так что шансы на черный ряд сохраняются :)
              • 0
                Есть чёрный ряд! Только бы компьютер не сломался…
                • +1
                  Собственно, вот…
                  image
                  Хотел остановиться на 65536, но посмотрел на счёт, и решил довести его до круглого значения. Чуть-чуть перескочил.
                  • +1
                    Поздравляю! Суперский результат! Представляете вам бы сразу предложили сыграть в игру 65536?
                    Искренне надеюсь, что в период между двумя комментариями в 01:52 и 10:37 удалось поспать :).
                    Жаль только, что нет скрина со змейкой, которая приводит к появлению блока. У меня пока рядом с 32 тыс. появились блоки 16 и 8, так что не исключено, что мне довется поделиться такой картинкой тоже.
                    • +1
                      Спасибо!
                      А, да, змейка… Куда же без неё :)

                      image

                      Это было в 12:23, так что очередные 1024 собирались в среднем за 12 минут. Чистого времени на игру получилось 14-16 часов. Не так много — приходилось решать головоломки и на 96 часов. Правда, они были с сохранением.
                  • 0
                    Ура! Я тоже в клубе достигших 65 тыс. тайла!
          • 0
            Вынужден еще раз признать правильность сделанного вами замечания. Как выяснилось, оно верно и играет роль не только в теоретическом, но и практическом плане. Несколько дней назад мне удалось собрать блок 131 072 или 217. Окрыленный я доработал с учетом нового опыта и свежих идей начатые рассуждения об игре 2048 и оформил их в виде отдельного поста. Заходите, комментируйте — всегда рад услышать ваше мнение, а также замечания и предложения — они, как правило, весьма конструктивны.
  • +13
    Слава б-гу, два раза попробовал ни разу не получилось. А то уже думал, эти зануды весь кайф обломали.
  • 0
    Я в итоге пришёл к аналогичной стратегии, хотя и не следовал принципу «всегда идти налево, если есть такая возможность». Ещё для того, чтобы побыстрее набрать первые две-три тысячи очков, я пользовался «читом» — быстро-быстро лупил по клавишам «влево, вверх, вниз, влево, вверх, вниз …», а потом, набрав тысячи три, уже спокойно играл.
  • 0
    Дошёл до аналогичной штуки, только с верхним рядом, а не правым. В принципе, если пользоваться подобной стратегией, то всё зависит от генератора случайных чисел — случится попасть в невыигрышную ситуацию («шахматы») или нет.
  • 0
    Возможно написать AI, который будет всегда выигрывать или есть безвыходные ситуации? Было бы здорово написать саму игру так, чтобы всегда была возможность выиграть.
    • +5
      Вот демонстрация ИИ — ov3y.github.io/2048-AI/
      Вкратце, используется алгоритм минимакс с альфа-бета отсечением.
      Исходный код — github.com/ov3y/2048-AI
      Подробное объяснение работы от автора — stackoverflow.com/a/22389702/1056032
      • 0
        Демка выглядит потрясающе, и элегантность, с которой ИИ гоняет самую толстую плитку из угла в угол, но всё равно умудряется разруливать сложные ситуации, поражает. Впрочем, уже ближе к концу, имея плитки на 1024, 512 и 128, эта штука запуталась и сдохла.
        Любопытно, что воспользовавшись изложенным выше подходом с построением «змейки» я смог собрать 2048 с первой попытки.

        Допускаю, что полного детерминизма достичь нельзя, просто потому что новые плитки появляются в произвольных местах, и иногда один неудачный вброс может стоить проигрыша.
  • +3
    Zuma deluxe для гиков.
  • –4
    Не уверен какой мне сделать следующий шаг.
    image
    • +3
      ↓↓←←←←↓→→→→

      Не вижу других заведомо беспроигрышных вариантов. Этот даст 4092+ очков, если я нигде не обсчитался.
      • +1
        Это была шутка, конечно же я знал куда ходить. У вас слишком много стрелочек в стороны.
  • +3
    Забавно. Неоднократно набирал 2048+ очков без каких либо стратегий… Но айтишников хлебом не корми, заставь компьютер играть сам с собой. :)
    • +1
      После случайного нажатия стрелок на клавиатуре получилось набрать 3148 очков с первого раза, благодаря энтропии. Последующие 3 попытки показали худший результат, несмотря на то, что при следующих попытках я учитывал правила игры. Если бы клеток было больше, то можно было играть, нажимая случайные стрелки намного дольше.
    • +1
      дык надо не 2048 очков набрать (это тривиально), а до плашки 2048 добраться!
  • +1
    Мультиплеер emils.github.io/2048-multiplayer/
    • +1
      Забавно, играя в этот мультиплеер я придумал довольно простую стратегию:

      1) Жмем как можно быстрее на все стрелочки, кроме -> (собственно, как описано в этой статье, только времени на раздумия особо нет, поэтому можно жать просто более-менее все подряд случайным образом)
      2) Если свободное место начинает заканчиваться, снижаем темп. Если совсем закончилось, останавливаемся совсем и стараемся схлопнуть какие-нибудь фишки.
      3) По мере роста свободного места можно увеличивать темп обратно.

      Пример на видео (видео не ускорено, действие происходит в реальном времени!):

  • 0
    Заметил что разные люди собирают цифры в разных углах (при тактике сбора большего числа в углу). Вот я например в правом нижнем углу. Девушка моя в левом нижнем, коллега на работа в левом верхнем вообще. Мне интересно чем это обусловлено? Я вот в другом углу вообще не могу собрать, неудобно и туплю.
    • 0
      Дело привычки.
  • 0
    Злостная штуковина. Пока не выиграл, не отстал. Стратегия почти такая же, только использую еще одну штуку. Сначала собираю только четверки, потом восьмерки, потому 16 и т д. Это позволяет более менее ровно развивать всё поле.
  • 0
    Кто-нибудь проходил игру 10?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.