ААААААААААААААААААААА
Oct. 9th, 2013 04:59 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЯ ее решил!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Уже проверил и отослал решение.
Сразу скажу, что мое решение найдено с помощью компьютера, и я не могу его описать в виде интуитивно понятного алгоритма для Алисы и Боба. Теперь, когда оно у меня есть, я попробую, наверное, проанализировать и "понять" его и попробовать перевести в интуитивное описание, но у меня нет уверенности, что это вообще получится.
Дальше следует краткое описание того, как было найдено решение, в общих чертах, без точных подробностей и кода. Если кому-то нужен код или точные подробности, пишите мне в комментах или на почту. Если не хотите решительно никаких спойлеров, помогающих решить, не читайте дальше. Извините, если что-то непонятно, я пишу впопыхах, чтобы распрощаться наконец с этим, но готов объяснить, если надо.
СПОЙЛЕРЫ
СПОЙЛЕРЫ
СПОЙЛЕРЫ
Значит, так. Во-первых, мы предполагаем, что Алиса всегда начинает первый раунд с 0, а казино - с 1, так что в первом раунде у нас меняется только бит Боба. В случае, если казино в первом пишет 0, то Боб тоже пишет 0, они выигрывают первый раунд, и им остается угадать 5 из 8, что легко сделать "интуитивной" стратегией. Если вы уже бились над этой задачей, пытаясь сделать 6 из 9, то скорее всего 5 из 8 вы уже и так умеете, так что не буду тут описывать (если надо, спрашивайте). Поэтому по сути дела далее обсуждаются только 256 строк решения, для всех вариантов казино, в которых первый бит 1. Когда у меня это все заработало, я написал отдельно скрипт для создания остальных 256 строк вышеупомянутого интуитивного решения, и проверил их все вместе.
Далее, мы решаем проблему перебором с значительными эвристическими предположениями, потому что строгий перебор - безнадежное дело. Я перепробовал три разных способа написать программу перебора, и в третьем из них - около восьми разных вариантов эвристики, пока не заработало.
Сначала мы строим префиксное дерево, которое соединяет все возможные начала за Алису,Боба и Казино с их продолжениями. Например, предположим, что первые два раунда выглядят так: А:00 Б:00 К:10. Их теперь можно продолжить в третий раунд, добавляя по одному биту А,Б и К. Гипотетически есть 8 возможностей перебрать эти три бита, т.е. на каждый вариант одного раунда есть 8 продолжений. Но мы сразу будем отбрасывать невозможные продолжения, в которых между продолженными А,Б,К есть больше трех разногласий. Из-за этого только в первых нескольких раундах кол-во вариантов растет экспоненциально, а потом замедляется. В построенном до последнего 9 раунда дереве есть 140 тысяч листьев-концовок, т.е. возможных троек А,Б,К по девять бит каждая - это в тысячу раз меньше экспоненциального 512*512*512.
В том виде, в каком оно построено, это дерево не задает стратегию поведения Алисы, потому что оно постоянно расщепляется, давая ей оба варианта. Скажем, от А:00 Б:00 К:10 есть все 8 возможных вариантов продолжать: и А:0 Б:0 К:0, и А:1 Б:0 К:0, и так далее. То, что в этих продолжениях есть разные Б и К - нормально, они соответствуют разным возможностям, с которыми должна справиться Алиса. Но то, что в них есть как тройки с А=0, так и тройки с A=1, означает, что Алиса в этом месте не знает, что делать.
Мы хотим подрезать это дерево и отсечь в нем много ветвей так, чтобы у Алисы всегда было детерминистское поведение.
Находясь в каком-то узле, например А:00 Б:00 К:10, мы хотим выбросить либо все продолжения с A=0 и все, что ниже их до самого конца, либо все продолжения с A=1. Это можно сделать огромным количеством способов. Дело не только в самом выборе, что выбрасывать в данном узле, 0 или 1, но и в том, что сами узлы с расщеплениями от этого меняются: если мы обрежем огромное подддерево ближе к началу, то все узлы с расщеплениями в нем исчезнут и по ним уже не надо ходить. С другой стороны, обрезая любое поддерево, мы теряем все листья-концовки в нем, т.е. тройки из 9 битов А-Б-К, которые теперь уже никогда не случатся.
До того, как мы начали усекать дерево, любая из 512 возможных К-стратегий находится в нашем дереве в концовках огромное количество раз, в разных тройках А-Б-К. Но по мере того, как мы отрезам поддеревья, некоторые К-стратегии становятся более редкими, и в конце концов могут исчезнуть из дерева. Наша задача - этого не допустить. Если мы сможем достигнуть положения, в котором у Алисы всегда детерминированный выбор, а в листьях дерева все еще представлены все 256 К-стратегий, мы победили. Почему? Потому что возьмите тогда любую стратегию, найдите концовку А-Б-К с ней, она даст вам 9 битов Боба, и вы сможете проследить игру от корня дерева до этой концовки в точности по этому А-Б-К. У Алисы на каждом раунде нет выбора иначе как следовать по заданному пути к этой А-Б-К.
Значит, мы пытаемся в каком-то порядке и по какому-то принципу обрезать поддеревья, и проверяем по дороге, что все К-стратегии все еще достижимы. Когда доходим до дерева без выборов (для Алисы), мы победили. Само дерево не очень большое, но в нем много тысяч узлов с расщеплениями, и перебрать все возможные способы их отсекать непрактично. Но напрашивается, например, идти по дереву обходом BFS или DFS, в каждом проблемном узле смотреть на какую-то эвристику, которая поможет решить, отсечь ветки-0 или ветки-1 для Алисы.
В общем, это то, что я сделал. Перебрал разные варианты обхода и эвристики: например, "отсечь ту ветку, в которой больше узлов", и многие другие. Одной из лучших эвристик оказалась "посчитай минимальное количество путей достичь конкретной концовки, для всех концовок (если этот минимум упадет до 0, мы проиграли), и отсекай там, где этот минимум снижается меньше". Но одной ее тоже было недостаточно. Постепенно у меня кол-во "живых" концовок из 256 к концу работу выросло до 214, потом до 240. Наконец, я заметил, что когда я принимаю решение, у меня часто все эвристические критерии у обеих веток совпадают, и тогда я выбираю всегда отрезать ветку-0. Вместо этого я поставил случайный выбор между веткой-0 и веткой-1 в каждом случае, и запустил сто раз, так, чтобы после каждой итерации, если вдруг повезло и остались все 256 стратегий, код записал все дерево в файл. Это случилось через несколько итераций после начала.
Уже проверил и отослал решение.
Сразу скажу, что мое решение найдено с помощью компьютера, и я не могу его описать в виде интуитивно понятного алгоритма для Алисы и Боба. Теперь, когда оно у меня есть, я попробую, наверное, проанализировать и "понять" его и попробовать перевести в интуитивное описание, но у меня нет уверенности, что это вообще получится.
Дальше следует краткое описание того, как было найдено решение, в общих чертах, без точных подробностей и кода. Если кому-то нужен код или точные подробности, пишите мне в комментах или на почту. Если не хотите решительно никаких спойлеров, помогающих решить, не читайте дальше. Извините, если что-то непонятно, я пишу впопыхах, чтобы распрощаться наконец с этим, но готов объяснить, если надо.
СПОЙЛЕРЫ
СПОЙЛЕРЫ
СПОЙЛЕРЫ
Значит, так. Во-первых, мы предполагаем, что Алиса всегда начинает первый раунд с 0, а казино - с 1, так что в первом раунде у нас меняется только бит Боба. В случае, если казино в первом пишет 0, то Боб тоже пишет 0, они выигрывают первый раунд, и им остается угадать 5 из 8, что легко сделать "интуитивной" стратегией. Если вы уже бились над этой задачей, пытаясь сделать 6 из 9, то скорее всего 5 из 8 вы уже и так умеете, так что не буду тут описывать (если надо, спрашивайте). Поэтому по сути дела далее обсуждаются только 256 строк решения, для всех вариантов казино, в которых первый бит 1. Когда у меня это все заработало, я написал отдельно скрипт для создания остальных 256 строк вышеупомянутого интуитивного решения, и проверил их все вместе.
Далее, мы решаем проблему перебором с значительными эвристическими предположениями, потому что строгий перебор - безнадежное дело. Я перепробовал три разных способа написать программу перебора, и в третьем из них - около восьми разных вариантов эвристики, пока не заработало.
Сначала мы строим префиксное дерево, которое соединяет все возможные начала за Алису,Боба и Казино с их продолжениями. Например, предположим, что первые два раунда выглядят так: А:00 Б:00 К:10. Их теперь можно продолжить в третий раунд, добавляя по одному биту А,Б и К. Гипотетически есть 8 возможностей перебрать эти три бита, т.е. на каждый вариант одного раунда есть 8 продолжений. Но мы сразу будем отбрасывать невозможные продолжения, в которых между продолженными А,Б,К есть больше трех разногласий. Из-за этого только в первых нескольких раундах кол-во вариантов растет экспоненциально, а потом замедляется. В построенном до последнего 9 раунда дереве есть 140 тысяч листьев-концовок, т.е. возможных троек А,Б,К по девять бит каждая - это в тысячу раз меньше экспоненциального 512*512*512.
В том виде, в каком оно построено, это дерево не задает стратегию поведения Алисы, потому что оно постоянно расщепляется, давая ей оба варианта. Скажем, от А:00 Б:00 К:10 есть все 8 возможных вариантов продолжать: и А:0 Б:0 К:0, и А:1 Б:0 К:0, и так далее. То, что в этих продолжениях есть разные Б и К - нормально, они соответствуют разным возможностям, с которыми должна справиться Алиса. Но то, что в них есть как тройки с А=0, так и тройки с A=1, означает, что Алиса в этом месте не знает, что делать.
Мы хотим подрезать это дерево и отсечь в нем много ветвей так, чтобы у Алисы всегда было детерминистское поведение.
Находясь в каком-то узле, например А:00 Б:00 К:10, мы хотим выбросить либо все продолжения с A=0 и все, что ниже их до самого конца, либо все продолжения с A=1. Это можно сделать огромным количеством способов. Дело не только в самом выборе, что выбрасывать в данном узле, 0 или 1, но и в том, что сами узлы с расщеплениями от этого меняются: если мы обрежем огромное подддерево ближе к началу, то все узлы с расщеплениями в нем исчезнут и по ним уже не надо ходить. С другой стороны, обрезая любое поддерево, мы теряем все листья-концовки в нем, т.е. тройки из 9 битов А-Б-К, которые теперь уже никогда не случатся.
До того, как мы начали усекать дерево, любая из 512 возможных К-стратегий находится в нашем дереве в концовках огромное количество раз, в разных тройках А-Б-К. Но по мере того, как мы отрезам поддеревья, некоторые К-стратегии становятся более редкими, и в конце концов могут исчезнуть из дерева. Наша задача - этого не допустить. Если мы сможем достигнуть положения, в котором у Алисы всегда детерминированный выбор, а в листьях дерева все еще представлены все 256 К-стратегий, мы победили. Почему? Потому что возьмите тогда любую стратегию, найдите концовку А-Б-К с ней, она даст вам 9 битов Боба, и вы сможете проследить игру от корня дерева до этой концовки в точности по этому А-Б-К. У Алисы на каждом раунде нет выбора иначе как следовать по заданному пути к этой А-Б-К.
Значит, мы пытаемся в каком-то порядке и по какому-то принципу обрезать поддеревья, и проверяем по дороге, что все К-стратегии все еще достижимы. Когда доходим до дерева без выборов (для Алисы), мы победили. Само дерево не очень большое, но в нем много тысяч узлов с расщеплениями, и перебрать все возможные способы их отсекать непрактично. Но напрашивается, например, идти по дереву обходом BFS или DFS, в каждом проблемном узле смотреть на какую-то эвристику, которая поможет решить, отсечь ветки-0 или ветки-1 для Алисы.
В общем, это то, что я сделал. Перебрал разные варианты обхода и эвристики: например, "отсечь ту ветку, в которой больше узлов", и многие другие. Одной из лучших эвристик оказалась "посчитай минимальное количество путей достичь конкретной концовки, для всех концовок (если этот минимум упадет до 0, мы проиграли), и отсекай там, где этот минимум снижается меньше". Но одной ее тоже было недостаточно. Постепенно у меня кол-во "живых" концовок из 256 к концу работу выросло до 214, потом до 240. Наконец, я заметил, что когда я принимаю решение, у меня часто все эвристические критерии у обеих веток совпадают, и тогда я выбираю всегда отрезать ветку-0. Вместо этого я поставил случайный выбор между веткой-0 и веткой-1 в каждом случае, и запустил сто раз, так, чтобы после каждой итерации, если вдруг повезло и остались все 256 стратегий, код записал все дерево в файл. Это случилось через несколько итераций после начала.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-10-09 02:28 pm (UTC)Боб в первом раунде выбирает 1, если начиная со второго раунда они начинают использовать интуитивную стратегию и 0, если контринтуитивную (Алиса выбирает другое число в следующем раунде).
я написал тестовую программку, которая показывает, что решение работает. да и наверное действительно понятно, что 2 из 3х мы так или иначе возьмём.
действуя по любой из стратегий мы выигрываем 3-й, 5-й, 7-й и 9-й раунды.
и выбираем какие два выигрываем из 4-го, 6-го и 8-го.
no subject
Date: 2013-10-09 02:36 pm (UTC)no subject
Date: 2013-10-09 02:37 pm (UTC)no subject
Date: 2013-10-09 02:41 pm (UTC)no subject
Date: 2013-10-09 02:41 pm (UTC)100011011
no subject
Date: 2013-10-09 02:43 pm (UTC)пусть играют по интуитивной всегда, а в "неизвестных" раундах Алиса должна ставить либо то же, что на предыдущем, либо противоположное. надо доработать и додумать до конца.
no subject
Date: 2013-10-09 02:33 pm (UTC)no subject
Date: 2013-10-09 02:40 pm (UTC)no subject
Date: 2013-10-09 03:38 pm (UTC)А при долгой игре доля правильных ответов стремиться к 0,8107...
no subject
Date: 2013-10-10 02:08 am (UTC)no subject
Date: 2013-10-11 03:44 pm (UTC)no subject
Date: 2013-10-11 07:54 pm (UTC)no subject
Date: 2013-10-11 08:29 pm (UTC)no subject
Date: 2013-10-11 08:46 pm (UTC)no subject
Date: 2013-10-11 09:02 pm (UTC)no subject
Date: 2013-10-09 03:25 pm (UTC)no subject
Date: 2013-10-09 03:38 pm (UTC)Миша Лысов выложил вконтакте исследование общего случая, которое в том числе решает и эту задачу. Я пока еще не разобралась -- там довольно сложные рассуждения -- но надеюсь, что получится. Я собираюсь вечером выложить его текст себе в жж, а пока -- ссылка для пользователей http://vk.com/id2911480?w=wall2911480_201%2Fall
no subject
Date: 2013-10-09 04:59 pm (UTC)6 из 9
Date: 2013-10-09 07:16 pm (UTC)В начале два простых утверждения.
1. Если у Алисы есть два бита информации, то она может угадать 5 из 6.
2. С одним дополнительным битом угадывается 4 из 6.
При необходимости я докажу эти утверждения отдельно.
Теперь основная стратегия. На 2-ом и 3-ем ходах Алиса называет первый бит Боба. Она угадывает один или два раза.
Если она угадала один раз, то номер одгаданного числа это один бит, а ответ Боба при ошибке Алисы -- второй. Дальше используем метод 5 из 6. Если Алиса угадала дважды, то возникают два случая.
a)Боб тоже угадал дважды. Это бит информации, дальше применяем 4 из 6.
b)Боб один раз ошибся -- это один бит. Номер ошибочного хода Боба -- второй бит. Применяем 5 из 6.
P.S. Похоже ерунду написал. Если второй и третий биты казино разные, то все конечно работает. А если одинаковые, то ниоткуда не следует что Боб может реализовать эту стратегию. "Доказательство" не стираю, как свидетельство человеческой самонадеянности.
Re: 6 из 9
Date: 2013-10-09 07:57 pm (UTC)Re: 6 из 9
Date: 2013-10-09 08:41 pm (UTC)no subject
Date: 2013-10-10 10:09 am (UTC)no subject
Date: 2013-10-10 10:16 am (UTC)(В случае, если среди среди этих пяти битов не было двух ошибочных, а только 1 или 0, Боб не может передать ей два бита, но в таком случае у нее есть еще в запасе как минимум одна ошибка, и тогда биты 7-8 легко сделать, просто передав значение 8-го бита казино в 7-бите Боба).
:)
Date: 2014-01-07 02:50 am (UTC)