задачка (математическое)
Dec. 9th, 2013 01:40 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОчень милая задачка от Джона Конвея (изобретателя игры "Жизнь").
Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.
На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.
Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас.
(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).
Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.
На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.
Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас.
(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).
Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-12-09 11:47 am (UTC)глубина стопки видна?а, наверное не видна, иначе слишком простоno subject
Date: 2013-12-09 11:50 am (UTC)no subject
Date: 2013-12-09 11:51 am (UTC)Это почему это? Существует момент, когда я вижу карты и они лежат правильно. Или мне нужно вообще запретить смотреть на стол, что сводит задачу к медиумной.
no subject
Date: 2013-12-09 11:56 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-12-09 11:57 am (UTC)Are we sure we are talking about card? ;-)
no subject
Date: 2013-12-09 12:56 pm (UTC)no subject
Date: 2013-12-09 12:06 pm (UTC)no subject
Date: 2013-12-09 01:02 pm (UTC)Если вы не уверены на сто процентов и хотите проверить свое решение, то вот программа, которую я написал, чтобы проверить свое:
http://pastebin.com/BkQAKNKQ
Нужно в определении переменной decider в конце описать поведение своего алгоритма в ответ на любую конфигурацию карт, где _ означает пустую позицию. Сейчас я там вбил везде "12" вместо своего решения, что означает всегда передвинуть с первой позиции на вторую, и не работает, ясно. Нужно это поменять на "12", "13", "21", "23", "31" и "32" в соответствии со своим алгоритмом, потом запустить программу.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-12-09 12:07 pm (UTC)даже при случайных перекладываниях очень быстро будет решение)))вообще, очевидно, решение тут сводится к построению конечного автомата на состояниях картины которую мы видим
no subject
Date: 2013-12-09 12:25 pm (UTC)предвыигрышная позиция - король на даме, туз справа.
прочие промежуточные случаи тривиальны.
позиция при которой стопка слева, сверху туз достигается одноходовкамии
no subject
Date: 2013-12-09 12:57 pm (UTC)(no subject)
From:no subject
Date: 2013-12-09 12:52 pm (UTC)no subject
Date: 2013-12-09 12:56 pm (UTC)no subject
Date: 2013-12-09 01:31 pm (UTC)no subject
Date: 2013-12-09 08:49 pm (UTC)мой вариант. Всего три основных правила.
1. Если видны три карты, то ДКТ->К_Т, КТД->_КД, КДТ->К_Д, ТДК->Т_Д
2. Если видны 1 или 2 карты, то
- К_Т или КТ_ ->Т__ решено
- если нет, то карты слева от дырки двигаем на дырку. Если дырка слева, двигаем на нее правую карту
no subject
Date: 2013-12-09 01:53 pm (UTC)1)Очевидно, какая стратегия перекладывания если бы мы видели не только верхнюю, но и карты лежащие ниже (например, сначала отложить даму посередине, а все остальные карты справа, потом начинать укладывать в порядке их слева). Таким образом Для каждого состояния расположения карт у нас есть следующее действие диктуемое стратегией.
2) Теперь для случая, когда мы видим только верхнюю карту. В таком случае наблюдаемое состояния может соответствовать от 1 до 2 полных состояний (например если мы видим туза справа и все, то это может быть туз дама король или туз король дама). И действие алгоритма такое, если состояние полностью определено(например, лежат слева направо туз король дама), то действуем в соответствии с пунктом первым, если состояние не полностью определено, то с вероятностью 0.5 выбираем действие для соответствующее первому состоянию, с вероятностью 0.5 соответствующее второму состоянию.
Очевидно, что для каждого начального состояния, есть конечная вероятность достичь результата. Мат ожидание будет конечно. Но каждая конкретная игра может занять долгое время.
no subject
Date: 2013-12-09 02:15 pm (UTC)можно поломать голову и составить свод точных правил, а можно использовать случайный выбор карты и места, куда её переложить, и получить решение, затратив на порядок меньше времени
при этом, количество ходов, затрачиваемых на решение может быть в некоторых случаях быть меньше для случайного поиска, чем для детерминистического, но статистически время работы случайного метода будет, наверное, раза в полтора-два дольше
no subject
Date: 2013-12-09 05:40 pm (UTC)(no subject)
From:no subject
Date: 2013-12-09 02:18 pm (UTC)2. Прочие случаи с двумя или одной видимыми картами - кладем карту, справа от которой пусто, на это пустое место (правым от L считается M, от M - R, от R - L).
3. Если видны все три карты. Если дама на L - короля на даму. Если дама на M - даму на R. Если дама на R - L на M.
no subject
Date: 2013-12-09 04:23 pm (UTC)no subject
Date: 2013-12-09 02:36 pm (UTC)Условие : Действие
A K/Q Q/K : A на K
K Q/A A/Q : K на A
Q K/A A/K : K на Q
0 A/K Q : Q на 0
K A 0 : A на K
A Q 0 : A на 0
Q K/A 0 : Q на 0
A 0 0 : A на 0
K 0 0 : K на 0
Q 0 0 : Q на 0
Три правила
Date: 2013-12-09 03:12 pm (UTC)— если нет свободных ячеек и никто не на своем месте — кладем младшую на старшую так, чтобы потом два правых сдвига давали выигрыш или позицию «нет свободных ячеек и одна карта на месте»;
— если нет свободных ячеек и одна карта на месте, снимаем на правильно лежащую карту такую, чтобы два правых сдвига давали выигрыш.
Вроде работает.
Re: Три правила
Date: 2013-12-09 03:16 pm (UTC)Re: Три правила
From:Re: Три правила
From:Re: Три правила
From:Re: Три правила
From:no subject
Date: 2013-12-09 04:27 pm (UTC)1. Если видны только К и Т и К слева, то кладем Т на К
2. Если Д слева и видимы К и Т, то кладем К на Д
3. Если Д слева и видим только К и К посредине, то кладем К на Д.
4. Если Д видна и самое левое место свободно, то кладем Д туда
5. Если Д видна, но левое место не свободно, то берем карту оттуда и кладем НЕ на Д.
6. Если Д слева, но не видим К, а Т посредине, то двигаем Т на правое место.
7. Если Д слева, но не видим К, а Т справа, то двигаем Д на среднее место.
8. Если виден только К слева, то кладем его на самое правое место
9. Если Д слева, посредине пусто, а справа К, то двигаем К на средину.
10. Двигаем самую верхнуюю левую карту направо.
Только, кажется, я под конец запуталась.
no subject
Date: 2013-12-09 10:12 pm (UTC)По правилу 7 двигаем даму в центр.
Потом по правилу 4 двигаем даму влево, чем возвращаемся к исходной позиции.
Другой вариант. Слева туз-дама-король, король сверху.
По правилу 8 кладём короля вправо.
Потом по правилу 9 кладём короля в центр.
Потом по правилу 3 кладём короля на даму, приходим к исходной позиции.
no subject
Date: 2013-12-09 04:47 pm (UTC)Нормальный алгоритм тоже вроде придумал, надо записать теперь, пока не забыл.
no subject
Date: 2013-12-09 07:40 pm (UTC)no subject
Date: 2013-12-09 08:13 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2013-12-10 04:24 am (UTC)Он формулируется как «переносим поочерёдно либо меньший диск по часовой стрелке, либо второй по размеру диск». Как видно, во входных данных есть ещё и чётность номера хода. Интересно, можно ли от этой чётности избавиться. (Например, как-то «захешировав» все состояния)
no subject
Date: 2013-12-10 08:32 am (UTC)Вот такое решение.
0. Если все карты на одной позиции -- положить верхнюю куда попало.
1. Если две позиции заняты, а третья свободна -- переместить на свободную позицию карту, лежащую слева от неё. (На крайнюю левую позицию -- с крайней правой). В результате через один или два хода карты будут лежать по одной.
2. Если дама не слева -- переложить карту так, чтобы пункт 1 алгоритма привёл даму налево. (Дама на M -- переложить её на R; дама на R -- переложить карту с L на M.)
3. Если дама слева -- положить на неё короля.
4. (Исключение из правила 1.) Если король слева, а дамы не видно -- положить туза на короля. При этом мы либо выигрываем, либо дама оказывается под тузом и начинает действовать правило 1.
Бонус: если все карты на одной позиции, и мне смутно помнится, что я что-то с ними делал -- я выиграл. И даже наблюдателя не надо.
no subject
Date: 2013-12-10 08:56 am (UTC)no subject
Date: 2013-12-10 08:58 am (UTC)no subject
Date: 2013-12-10 09:33 am (UTC)Почему нельзя просто рэндомно перекладывать куда попало? рано или поздно мы получим выигрышное состояние, и сторонний наблюдатель нас остановит
no subject
Date: 2013-12-10 09:38 am (UTC)no subject
Date: 2013-12-10 09:41 am (UTC)no subject
Date: 2013-12-10 01:46 pm (UTC)no subject
Date: 2013-12-10 03:34 pm (UTC)no subject
Date: 2013-12-11 09:36 am (UTC)no subject
Date: 2013-12-11 10:36 am (UTC)no subject
Date: 2013-12-13 09:24 am (UTC)2. Передвижение влево от левого (L) слота переходит в правый (R), передвижение вправо от правого (R) - в левый (L)
3. Туз и дама всегда передвигаются влево, король - вправо.
4. Передвижение разрешено, если слот назначения пустой или в нем находится младшая карта (старшинство в порядке возрастания: дама, король, туз). Так, дама может передвигаться только в пустой слот.
5. За ход передвигается младшая карта из тех, у которых есть разрешенное передвижение.
:)
Date: 2014-01-05 10:52 pm (UTC)