задачка (математическое)
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
Date: 2013-12-09 11:57 am (UTC)Are we sure we are talking about card? ;-)
no subject
Date: 2013-12-09 12:06 pm (UTC)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:52 pm (UTC)no subject
Date: 2013-12-09 12:56 pm (UTC)no subject
Date: 2013-12-09 12:56 pm (UTC)no subject
Date: 2013-12-09 12:57 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
Date: 2013-12-09 01:03 pm (UTC)no subject
Date: 2013-12-09 01:31 pm (UTC)no subject
Date: 2013-12-09 01:37 pm (UTC)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:14 pm (UTC)Сорри, у вас дама лежит слева, поэтомы вы вернулись к первоначальным указаниям "все скидываем направо, пока не получим [_] [_] [cards]", и на этом вы зависли навсегда.
У вас нет возможности сказать себе: "ок, этот этап работы закончился, теперь ведем себя по-другому". У вас нет памяти о том, сколько до сих пор было ходов, как вы себя в них вели и какие в них были карты.
no subject
Date: 2013-12-09 02:15 pm (UTC)можно поломать голову и составить свод точных правил, а можно использовать случайный выбор карты и места, куда её переложить, и получить решение, затратив на порядок меньше времени
при этом, количество ходов, затрачиваемых на решение может быть в некоторых случаях быть меньше для случайного поиска, чем для детерминистического, но статистически время работы случайного метода будет, наверное, раза в полтора-два дольше
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 02:30 pm (UTC)no subject
Date: 2013-12-09 02:35 pm (UTC)Если Q на месте 0, а на остальных двух A и K, положить K на Q (идеальный сценарий)
Если K на месте 0, а на остальных двух A и пусто, положить A на K (в надежде, что это продолжение идеального сценария)
Если справа от карты X есть пустое место Y, положить карту X на это пустое место Y (разбиваем стопки в 1, 2, или 3 шага)
Положить карту справа от Q на карту слева от Q (если карты лежат плоско, передвигаем их в идеальную ситуацию)
Кстати, легко масштабируется на любое n, где n - количество карт и мест.
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)