Pull to refresh
34
0
Send message
Это верно, если команды, играющие как в первоначальную, так и в новую игру используют одну и ту же стратегию.

Я считаю вторую перестановку случайной и независимой от первой именно потому, что не фиксирую стратегию, которой пользуется команда, играющая в новую игру. С другой стороны, что мешает нам зафиксировать её? Ведь по свойству 2 вероятность победы в новую игру не зависит от алгоритма действий участников.

Таким образом, мы действительно можем условиться, что новое испытание команда проходит, используя базовую стратегию. Тогда очевидно, что условие выигрыша как в первоначальную, так и во вторую игру одно и тоже — как вы и сказали. Доказательство действительно можно упростить, спасибо!
Если перестановка (i1, i2, ..., i100), описывающая как разложены жетоны по коробкам (в первой коробке лежит жетон с номером i1, во второй — с номером i2, и т.д., в сотой — с номером i100) содержит цикл длины больше 50, то команда, играющая в первоначальную игру и следующая базовой стратегии, проиграет. В то же время команда, играющая в новую игру, при этом же расположении жетонов по коробкам выиграет всё с той же вероятностью около 31,2%.

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

Множество таких перестановок, появление которых означает успешное прохождение командой нового испытания, обозначено как A. Число элементов в этом множестве в точности совпадает с числом перестановок, не содержащих циклов длины больше 50 (множество таких перестановок обозначено как B). Чтобы это показать построено взаимно-однозначное отображение из A в B.

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

Доказательство свойства 3, скорее всего, можно упростить, только поясните свою идею.
Скорее всего утверждение (У1) действительно можно доказать, насколько просто и изящно — сходу оценить сложно. Правда оно даже в формулировке опирается не на исходную предметную область (игру 2048), а как раз на ту модель, которую вы считаете излишне трудной и от которой хотите уйти.

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

В любом случае спасибо! Приятно, что кто-то углубился именно в теоретические аспекты исследования. Пределов совершенства нет и все здравые мысли обязательно пригодятся, не сейчас — так чуть позже.
Удалось. Может именно поэтому мне слегка удивителен скептицизм некоторых участников обсуждения, считающих, что собрать максимальный тайл с сохранением ничего не стоит. Хотя это вовсе не предмет дискуссии.
Слушайте, если бы я не проникся тактикой игры и умением выпутываться из всяких хитрых положений, думаю никакие сохранения мне не помогли бы. Это же было бы невыносимо скучно, только представьте!

Я, конечно же, получал удовольствие от игры, старался нащупать как по-максимуму нивелировать случайность — в этом суть головоломки, её интерес. Зачем же играть в тетрис с одними палками? Просто наряду с самой игрой мне показались увлекательными и другие вопросы, которым и посвящен пост. Он же никак не связан с достижением максимального тайла — это только вдохновило доработать и оформить родившиеся ранее (ещё на этапе сбора 16 тыс. блока) размышления.

Что касается механики игры, возможно даже, что я достаточно глубоко её понимаю и близок к идеальной тактике. Но у меня нет в этом уверенности и нет идей, как строго сформулировать и обосновать эту самую абсолютно правильную теорию игры. Это же совсем другой предмет исследования, который мне пока не под силу. В то же время просто вывалить на сообщество своё непродуманное до конца, бесструктурное мнение о том, как лучше проходить головоломку, нет никакого желания и, уверен, никому не нужно.
Вы решили от меня избавиться надолго? :)
Выбор модели — вопрос творческий. Главное, чтобы она позволяла решить поставленную задачу, а так — чем проще, тем лучше, полностью согласен!

Касательно вашего замечания — немного повторюсь с norlin. Даже если в наборе есть одна или несколько пар одинаковых чисел это не значит, что человек обязан хоть одну из них объединять в более крупный блок. В реальной игре такая ситуация не редкость. И что самое главное — это никоим образом не лишает смысла подсчет максимума ходов! Наоборот, только подчеркивает насколько это интересный результат! Ведь оказалось, что наибольшее возможное количество действий не зависит от выбранной пользователем стратегии (если при этом ему удалось добраться-таки до финала). Напротив, искомое число зависит только от ходов машины — сколько четвёрок она сгенерирует. Чем больше — тем быстрее всё закончится и тем меньше очков нам светит.

Предлагаемая вами модель, действительно, проще, но не ставит ли она новых, ещё более сложных вопросов? Например, обоснуйте кратко почему если в игре 2048 можно собрать тайл 2n, то и в условиях модели это обязательно удастся? Ведь её состояния никак не связаны с процессом игры — пользователь может собрать несколько блоков за один ход, в том числе и одинаковых, а в модели это невозможно.

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

Спасибо за комментарий!
Вот так да, век живи — век учись! Оказывается и правда можно было делать несколько дубликатов текущего состояния. Я почему-то был уверен, что только одно.
Жаль, что вас одолевают столь негативные чувства. Постараюсь сгладить впечатление:

1. Я специально упомянул про сохранения, как раз чтобы развеять возможные заблуждения о «честном» прохождении. Дело в том, что никакой идеальной стратегии, которая бы стопроцентно позволила нивелировать фактор случайности в этой игре, по-видимому, не существует. Посудите сами — двойка появляется гораздо чаще четверки, но именно последняя непременно должна возникнуть в левом верхнем углу змейки на освободившейся (после создания блока 4 чуть правее) клетке. Что делать если нам не повезло? Честно переигрывать с самого начала?

По собственному опыту — понадобилось попыток 30 для получения этой желанную четвёрки в углу. При этом в посте вычислено количество ходов, сделанных для достижения представленного результата — порядка 60 тыс. без учета переигрываний. Даже из расчета 1 секунда на действие — это более 16 с половиной часов игры! На мой взгляд «честность» (всегда переигрывать с самого начала) в этом случае слишком явно граничит с безрассудством и делает попросту невозможным создание максимального тайла.

2. Даже с сохранениями всё не так просто. Дело в том, что продублировать вкладку можно только один раз. Чтобы снова засейвиться, надо сделать хотя бы один ход. Частенько он становится фатальным, прежде всего в острых ситуациях, когда змейка замыкается уже в верхнем ряду и никакого пространства для маневра ходами просто нет.

Попробуйте сами собрать какой-нибудь большой тайл. Уверен, вы испытали бы радость от своих достижений, даже если бы пришлось сохраняться.
По определению функции g (n) — это минимальное количество двоек (тайлов 2), необходимое для создания блока 2n.

Цель рассмотрения этой функции — узнать сколько тайлов 2 необходимо для того, чтобы достичь одного из двух финальных состояний: (2, 8, 16, 32, ..., 131 072) или (4, 8, 16, 32, ..., 131 072). Для этого надо просуммировать её значения для n = 17, 16, ..., 3 (со штрафом -2, обусловленным необходимостью появления как минимум 15 четвёрок). На базе этого уже можно вычислить искомое нами количество ходов.

Само по себе значение g (n) не равно количеству ходов, необходимому для получения блока 2n, хотя тесно с ним связано.
Простой пример: g (4) = 8, то есть для получения тайла 16 нужно 8 двоек. В то же время, чтобы объединить 8 двоек в блок 16 может потребоваться, например, 3, 7, 10 или не пойми ещё сколько ходов, в зависимости от того как расположены тайлы, какие действия совершаем мы и машина.

Всё переплетено между собой и вроде как одно и то же, но стоит немного отступиться от строгости и точности определений, как начинается сумятица. Я сам не сразу сориентировался и в конечном итоге выбрал такой способ формализации — через g. Мои попытки сразу ввести функцию, значение которой равно необходимому количеству ходов для построения 2n, успехом не увенчались. Просто непонятно, как дать её грамотное определение и вычислить все значения.

Если кто-нибудь решит задачу другим способом, будет здорово сравнить результаты!
Вынужден еще раз признать правильность сделанного вами замечания. Как выяснилось, оно верно и играет роль не только в теоретическом, но и практическом плане. Несколько дней назад мне удалось собрать блок 131 072 или 217. Окрыленный я доработал с учетом нового опыта и свежих идей начатые рассуждения об игре 2048 и оформил их в виде отдельного поста. Заходите, комментируйте — всегда рад услышать ваше мнение, а также замечания и предложения — они, как правило, весьма конструктивны.
Ура! Я тоже в клубе достигших 65 тыс. тайла!
Поздравляю! Суперский результат! Представляете вам бы сразу предложили сыграть в игру 65536?
Искренне надеюсь, что в период между двумя комментариями в 01:52 и 10:37 удалось поспать :).
Жаль только, что нет скрина со змейкой, которая приводит к появлению блока. У меня пока рядом с 32 тыс. появились блоки 16 и 8, так что не исключено, что мне довется поделиться такой картинкой тоже.
Вы правы насчет максимального тайла. Если нам будет везти на четверки, то в игре можно добраться до 217. И максимальное количество очков соответственно больше. Я не рассматривал этот случай (о чем сразу оговорился в комментарии) просто для конкретизации и упрощения задачи.

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

Я ведь писал выше — без переигрываний такую картинку получить, как мне кажется, крайне маловероятно. Случайный фактор, видимо, непреодолим. Поэтому если вдруг мой компьютер перезагрузится, например, или еще какой сбой произойдет, то мне не удастся увидеть нижний ряд состоящий сплошь из черных тайлов (на собирание 64 тыс. блока я всерьез не рассчитываю).
В продолжение темы еще один пример эффективности стратегии «змейка». Мне-таки удалось добраться до 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 тыс.) по отношению к максимально возможному их числу.
Долгие убитые часы жизни, но зато получилась отличная иллюстрация для стратегии «змейки». После того как собрал тайл 16384, имею более 200 тыс. очков. Почему-то сомневаюсь, что удастся собрать 32-тысячный блок, но если не будет сбоев, попробую на неделе довести дело до победного конца.

По-настоящему конструктивные комментарии!
Ваши оценки суммы биномиальных коэффициентов привели к замечательной формуле, спасибо большое! Мне она очень понравилась!
Так же как alexeykuzmin0, минут за 15 выписал рекуррентную формулу для наименьшего числа испытаний и понял алгоритм поиска. Правда перед этим я довольно долго возился с задачей про радиоактивные шары, где формальный подход, в принципе, тот же. Ну и решал не в экстремальных условиях собеседования, а в спокойной обстановке.

Вообще говоря, не обрадовался бы услышать подобную задачку при приеме на работу. В частном случае: сто этажей и два шара — она всё-таки значительно проще.
Да-да, я же сослался на вашу статью в разделе "«Явная» формула подсчета наименьшего числа испытаний". Теперь, когда буду вносить в пост коррективы, укажу ее автора.
Не пробовали по изложенному в работе принципу рассмотреть случай k шаров?
Спасибо, такая красивая и очевидная оценка биномиального коэффициента снизу!
Я сравнил ее со своей. Для достаточно больших k (т.е. близких к m) она немного хуже, но для остальных (что нам, в принципе, более актуально) — лучше.
Проведу еще немного численных экспериментов и попробую отразить ваши идеи в самом посте, если не возражаете.

Что касается асимптотики — хорошая идея. Меня останавливают два фактора:
1. Насколько корректно при выводе формулы наименьшего числа испытаний исходить из предположения, что k — фиксировано, а m стремится к бесконечности?
2. Можно ли оценить ошибку асимптотической оценки наименьшего числа испытаний для конкретных заданных n и k? И не получится ли она сравнимой с тем диапазоном, который мы получаем с помощью изложенного в посте подхода (возможно, модернизированного с учетом вашей идеи)?

Эти вопросы адресованы и Mrrl. Такое точное попадание — 76.95 при правильном ответе 76, конечно, впечатляет! Но насколько можно доверять полученному результату, когда мы не знаем ответа?
1

Information

Rating
Does not participate
Registered
Activity