?

Log in

и в заключение - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

и в заключение [окт. 9, 2013|11:38 pm]
Anatoly Vorobey
Теперь у меня есть "интуитивное" решение задачи про Алису, Боба и Казино. То самое, которого так долго ждали большевики и в поисках которого я вместе, кажется, с немалым числом читателей этого дневника бились головой об стенку в последние несколько дней. То самое, по поводу которого я уже решил было, что оно не существует.

Это не мое решение. Его придумал коллега из Гугла. Мне досадно, что все трюки, которые оно использует, я тоже пытался применить, но оно их все соединяет с еще большей хитроумностью и извращенностью, которые от меня ускользнули. Что я могу сказать - в Гугле работают умные люди.

(додумался бы я до этого решения, если бы еще несколько дней бился головой об стенку? Не знаю, но скорее нет, чем да)

Да, кстати, хоть оно, мягко скажем, не тривиальное, но действительно работает. Я проверил не только на глазок, но и программой, которую я написал для проверки решений.

Ну что, хотите узнать? Дальше идут одни спойлеры!

[Последний шанс не узнавать и думать самому!]


СПОЙЛЕРЫ



СПОЙЛЕРЫ





СПОЙЛЕРЫ



Итак, у нас есть 9 битов Казино, которые мы обозначим A-BCD-EFG-HI. Для простоты предположим, что в первом бите всегда есть ошибка, этого невозможно избежать в любом случае.

1. Сначала опишем "базовый алгоритм", который все уже пробовали. В своем бите A Боб обозначает наиболее частый бит среди BCD, и Алиса играет его в BCD. Если у нее есть одна ошибка, Боб использует свой бит на месте ошибки, чтобы передать самый частый бит среди EFG. Если там есть одна ошибка, то Боб использует этот бит, чтобы закодировать HI вместе, предполагая, что они одинаковы.

Этот алгоритм сработает, если BCD не все одинаковы, EFG не все одинаковы, и HI = 00 или 11. Кроме того, если BCD или EFG все одинаковы, он тоже сработает с легкими модификациями, и тогда даже не нужно, чтобы HI были одинаковы. Например, если BCD одинаковы, то у нас после BCD есть еще две ошибки в запасе: мы можем использовать E для большинства FGH, и тем же способом бит ошибки внутри FGH для I (а если бита ошибки нет, то и не надо, наплевать на I). А если EFG одинаковы, то у нас есть одна ошибка в запасе на HI, так что просто пользуемся H чтобы просигналить I.

2. Таким образом, мы пользуемся "базовым алгоритмом", и он работает во всех случаях, кроме HI=01 или HI=10. Более того, в этом случае мы можем предположить, что BCD не одинаковы и EFG не одинаковы, иначе базовый алгоритм все равно работает.

3. Теперь рассмотрим случай, когда HI=01, а EFG - любая неодинаковая комбинация, кроме 010 и 101. Таких комбинаций есть четыре, так что возможности для EFG-HI такие: 001-01, 110-01, 011-01, 100-01. Мы отклонимся от базового алгоритма следующим образом:

- в случаях 001-01 и 110-01 Боб специально делает ошибку во втором бите (F). Эта ошибка говорит Алисе (которая не ошиблась в этом бите, и поэтому знает, что это не "ошибочный бит" Боба в базовом алгоритме), что следующий бит противоположен плану, по которому она шла, и вдобавок в конце идет 01.

- в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.

- в обоих случаях после специальной ошибки Боба Алиса без дополнительных ошибок заканчивает игру.

4. У нас остались следующие неохваченные комбинации EFG-HI. Во-первых, 010-01 и 101-01, а во-вторых любые (но не все одинаковые) значения EFG, плюс HI=10. Все остальные варианты мы рассмотрели.

5. В этих оставшихся случаях мы меняем стратегию на BCD, и пользуемся трюком, который позволяет сделать две ошибки, но вытащить целых три бита. Это делается следующим образом. У нас есть два способа сделать две ошибки на BCD и закодировать там два бита:

- дать в бите A неправильное большинство для BCD, чтобы Алиса сделала две ошибки, и использовать эти два бита Боба.
- дать в бите А правильное большинство, Алиса делает одну ошибку (и Боб имеет в ней свой бит), но Боб делает еще одну дополнительную ошибку, причем он может выбрать одно из двух правильных мест, и этот выбор дает ему еще один бит.

Наконец, выбор одной из этих двух стратегий дает нам третий бит. После того, как Алиса ответила свои BCD согласно биту A Боба, она может определить, перешли ли мы на стратегию "две ошибки", на какую из двух, и узнать все три бита.

6. Эти три бита теперь дают нам возможность определить EFG-HI без единой ошибки. Первый бит определяет, верно ли, что EFG=010 или 101. Если это так, то второй бит скажет, какая из этих версий верна, а третий определит, HI=10 или HI=01. Если это не так, то обязательно HI=10, а для EFG осталось четыре возможности 001, 110, 011, 100,
и второй и третий бит вместе определяют, какая из них верна.


Уф. Ну как? Прекрасно, верно ведь?
СсылкаОтветить

Comments:
[User Picture]From: burrru
2013-10-09 08:55 pm
Да, это изящное решение.
(Ответить) (Thread)
[User Picture]From: vigourik
2013-10-10 02:20 pm
Изящное? Не смешите мои тапки! Изящные решения запоминаются, как стихи Пушкина. А с два раза менять стратегию - стопудово Алиса накосячит! :)
(Ответить) (Parent) (Thread)
[User Picture]From: homotub
2013-10-09 09:19 pm
охуенно. пойду пересплю с этим.
(Ответить) (Thread)
[User Picture]From: machin
2013-10-09 09:38 pm
5 пункт даже пугает извращённостью
(Ответить) (Thread)
[User Picture]From: dmarck
2013-10-09 10:41 pm
Вот да ;)
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-10-09 11:09 pm
Что-то мне это напоминает систему команд x86.
(Ответить) (Thread)
[User Picture]From: spamsink
2013-10-10 03:45 am
Ну да, mod-reg-r/m в практически чистом виде.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-10-10 08:22 am
Во-во.
(Ответить) (Parent) (Thread)
From: illy_drinker
2013-10-09 11:50 pm
Вы не помните несколько лет назад обсуждалась физическая задача о теле между которых и стеной двигается другое тело (отражаясь между ними) и один сотрудник гугл (кажется Игорь Н) предложил удивительное красивое решение?
(Ответить) (Thread)
[User Picture]From: avva
2013-10-10 06:31 am
Не помню, кажется...
(Ответить) (Parent) (Thread)
From: illy_drinker
2013-10-11 01:20 am
Я помню было какое-то удивительно красивое и "простое" решение
Поспрашиваю
(Ответить) (Parent) (Thread)
[User Picture]From: tandem_bike
2013-10-10 12:04 am
Авва, поздравляю. очень респект и за старания и за решение.
с моим АДД я не смогла вникнуть даже в условия.

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

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

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

так и живем.

у мамы айкью конечно 180, а у меня наверное 80, я не считала чтобы не огорчаться.
(Ответить) (Thread)
[User Picture]From: ripperfrvr
2013-10-10 12:52 am
Алиса делает одну ошибку (и Боб имеет в ней свой бит)
(Ответить) (Thread)
[User Picture]From: southwest
2013-10-10 04:24 am
Не согласен с вашим решением. Цитирую:

в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.

Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?

Я могу привести конкретные две комбинации казино, как их Алиса отличит?
101001101
101001111

Я тоже три дня думал, и по-моему придумал, на выходных напишу, время будет )
(Ответить) (Thread)
From: ger04ka
2013-10-10 05:47 am
Проущена всего одна буква, но реально немного смысл поменялся :)
Правильно так:
"в случаях 011-01 и 100-01 Боб похожим образом делает ошибку И в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01."

> Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?

Эту информацию Алиса получит после бита F, в котором Боб сделает ошибку в случае, если HI равно 01 и не сделает ошибку, если HI равно 11.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-10-10 05:52 am
Нет, не совсем так. Это не может работать, как вы говорите, потому что у Боба уже нет бюджета на две ошибки к этому времени, только на одну. См. мой комментарий ниже.
(Ответить) (Parent) (Thread)
From: ger04ka
2013-10-10 05:58 am
Да, сам понял, что был не прав, но не успел изменить)
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-10 05:54 am
всё равно не катит: если в этом случае Боб делает ошибку в бите F, то у них может получиться только 5 побед, а не 6
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-10-10 05:51 am
Алиса это знает, потому, что в этом случае она, следуя его указаниям, *ошибается* в этом бите. А когда он кодирует одинаковую цифру в битах HI, она, следуя его указаниям, *не ошибается* ошибку в этом бите.

Вот комбинации Боба для ваших примеров:

К 101001101: Б 000011101
К 101001111: Б 001011111

(биты нумеруются 1-9 слева направо)

В первом случае Алиса начинает отвечать 0 на биты 5-7, согласно указанию Боба в третьем бите. Но тут она видит, что в пятом бите Боб сделал ошибку, а она нет. Значит, надо изменить догадку на противоположную и отвечать 1 на биты 6-7, и 01 в конце.

Во втором случае Алиса начинает отвечать 1 на биты 5-7. В пятом бите Боб делает ошибку, но и Алиса тоже ошибается; поэтому она не меняет догадку, продолжает отвечать 11 на биты 6-7, и пользуется битом Боба для битов 8-9.




Edited at 2013-10-10 05:53 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-10 05:59 am
но в этих двух случаях, следую тому решению, что вы написали, Боб не должен менять стратегии на битах BCD, а в ваших примерах он меняет в бите C
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-10-10 06:32 am
Он не меняет стратегию в том смысле, что он продолжает битом A указывать на большинство в BCD, и в ошибочном бите (в данном случае C) давать Алисе указание, как отвечать в EFG. Он меняет сам этот бит, потому что он меняет стратегию на EFG.
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-10 06:52 am
в решении написано что Алиса играет его в BCD. Если у нее есть одна ошибка, Боб использует свой бит на месте ошибки, чтобы передать самый частый бит среди EFG

до того места нигде не написано, что Боб поступает иначе, как в вашем примере
К 101001101: Б 000011101

но я понял модификацию, буду думать дальше, т.к. мои похожие 'решения' все имели прореху





(Ответить) (Parent) (Thread)
From: ger04ka
2013-10-10 06:34 am
Изменение стратегии - это "отход" от пунктов 1-3? Тогда ошибка в бите С Боба - это не изменение стратегии. Изменением будет являться только 2 ошибки Боба в BCD.
(Ответить) (Parent) (Thread)
From: ger04ka
2013-10-10 06:16 am
Спасибо, теперь "прочувствовал" до конца решение.
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2013-10-10 06:20 am
> Откуда в этом случае Алиса знает, что он делает ошибку в бите Е? А не кодирует одинаковую цифру в битах HI?

Потому что её бит совпал с битом казино.
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-10 06:24 am
'решение' предполагает, что он как раз не совпал
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2013-10-10 07:05 am
Насколько я понял решение - как раз совпал.
То есть, в случаях EFG 011 и 100 Боб говорит неправильный преобладающий в EFG бит, Алиса угадывает первый из битов (E), но Боб не подтверждает её выбор. "Эта ошибка говорит Алисе, что следующие два бита противоположны плану" - то есть, следующие два бита она угадывает вопреки тому, что показал Боб ранее. И имеет дополнительную информацию о том, что HI = 01.
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-10 07:15 am
ну вот с разьяснениями я тоже понял, что совпал, надо в решении указать, что Боб использует свой бит на месте ошибки в BCD чтобы указать Алисе, как начать ходить в битах EFG.
(Ответить) (Parent) (Thread)
[User Picture]From: plakhov
2013-10-10 04:33 am
Эта задача напомнила мне высказывание, которое Норвиг приводит насчет игры Судоку: "a denial of service attack on human intellect".

Тот факт, что перебором на компьютере её решить проще, чем "вручную", является очень сильным тому свидетельством.
(Ответить) (Thread)
[User Picture]From: _winnie
2013-10-10 11:16 pm
Благодаря этому багу в человеческом мышлении, мешающему в обычной жизни, появилась сегодняшняя техническая цивилизация.

http://xkcd.com/356/

Edited at 2013-10-10 23:17 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: plakhov
2013-10-11 07:16 am
Я не имел в виду сложные задачи вообще, только (условно) переборные. Решая хорошую задачу, ты что-нибудь понимаешь лучше, или даже изобретаешь что-нибудь новое. В этом смысле задача про Alice/Bob/Casino кажется похожей на шахматы или судоку.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-10-11 07:26 am
"шахматы или судоку" кажется мне ужасным соединением - они отличаются именно что по "переборному" критерию! Судоку - чистый незамутненный перебор, а игра в шахматы, или даже решение задач (впрочем, скорее и в особенности этюдов, а не задач) треует понимания.
(Ответить) (Parent) (Thread)
[User Picture]From: plakhov
2013-10-11 08:48 am
Ну, я, возможно, просто не люблю и не понимаю шахматы, но.

Мне для того, чтобы начать хоть сколько-нибудь прилично играть, всегда не хватало именно "переборного терпения". Я знаю, что сильные игроки совсем не считают игру переборной, но мне кажется, так происходит не потому, что они вообще перебором не занимаются совсем, а потому, что они научились не замечать этот процесс сознательно (а кое-где "выучили" значительные объемы оного, например, в дебютах).

Из-за этого, например, опыт шахматной игры не переносится ни на какую сколько-нибудь похожую область деятельности; оттуда нельзя позаимствовать интересные идеи (во всяком случае, я о таком не слышал).
(Ответить) (Parent) (Thread)
[User Picture]From: alex_levit
2013-10-11 02:02 pm
Не могу удержаться от оффтопика. Все-таки шахматы и судоку несравнимы по сложности. Обобщенные шахматы лежат в классе EXPTIME-Complete, а судоку всего лишь в NP-Complete.
Перебор в шахматах важен, но сильный игрок может играть и почти без перебора. Гроссмейстер имея секунду на ход все равно будет играть сильно. И обратный пример: сам наблюдал, как сильный гроссмейстер по шашкам не мог просчитать простую позицию в поддавках, хотя эти игры совпадают как графы. На мой взгляд, в шахматоподобных играх работает распознавание типичных патернов. То-есть, грубо говоря, при такой-то пешечной структуре, такой-то план должен быть эффективным. А дальше следует проверка гипотезы частичным перебором. Кроме того опытный игрок сразу видит стандартные последовательности ходов, подобно тому как мы сразу распознаем знакомое слово, а не читаем его по слогам.
С последним абзацем я пожалуй соглашусь: опыт шахматной игры отчасти переносится на другие игры. Другие полезные применения мне неизвестны.
(Ответить) (Parent) (Thread)
From: ext_2087110
2013-10-13 02:12 am
Поддержу предыдущего оратора. Я не знаю что Плахов подразумевает под "хоть сколько-нибудь прилично играть", но уровня мастера спорта вполне можно достичь практически без перебора, только на знании и понимании. Дальше - не скажу, потому что у меня просто нет подобного опыта, поэтому было бы самонадеянно что-то утверждать.
А по поводу переноса идей в шахматной игры - опять же непонятно что Плахов подразумевает под "хоть сколько-нибудь похожая область деятельности". Шашки и го - достаточно похожая область деятельности? При создании программ для этих игр ряд методов, изобретенных для шахмат весьма пригодился.
В общем, эта атака на шахматы больше похожа на личную неприязнь и непонимание, чем на что-то имеющее смысл.

Edited at 2013-10-13 02:12 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: amarao_san
2013-10-10 09:47 pm
Кстати, решение для 50%+: первым битом Боб сообщает Алисе какой бит будет более популярным среди оставшихся 9 вариантов. Их будет минимум 5.

Дальше Боб может на каждом "ошибочном" варианте (то есть когда казино будет выкидывать "непопулярный" бит), зная о выборе Алисы, передавать ей биты в обратном порядке - то есть вариант №10, №9, etc.

Алгоритм Алисы:

1) Выбрать что-то.
2) Запомнить выбор Боба
3) Выбирать выбор Боба, пока число отложенных битов не совпадёт с числом оставшихся раундов. Тогда использовать отложенные биты.
4) Если Алиса ошибается (кроме раунда1), то запоминать ответ Боба и помечать его как №10, №9 и т.д. и увеличивать число запомненных битов.

Рассчитывать вероятность победы затрудняюсь, но примерная оценка:

если из 9 вариантов 5 правильных будут сначала, значит из оставшихся 4 боб сможет передать 2.

Если из 9 вариантов правильные будут с конца, то увы, будет только 5 гарантированных побед.

ЗЫ Пребываю в сомнении, что лучше, передавать следующий вариант, или последний...
(Ответить) (Thread)
[User Picture]From: gul_kiev
2013-10-16 08:07 pm
Теперь меня в этой задаче вот что занимает.
Если результат 2/3 - это не асимптотический предел, а реально достижимый на небольших сериях, каков же тогда максимальный процент угадывания при N стремящемся к бесконечности?
(Ответить) (Thread)
[User Picture]From: _pk_sly
2017-03-14 05:38 am
мне "на пальцах" удалось получить примерно 0.77, но это тоже не совсем ассимптотика, а блоки. но они сильно длиннее 9.
(Ответить) (Parent) (Thread)