![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ААААААААААААААААААААА
Oct. 9th, 2013 04:59 pmЯ ее решил!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Уже проверил и отослал решение.
Сразу скажу, что мое решение найдено с помощью компьютера, и я не могу его описать в виде интуитивно понятного алгоритма для Алисы и Боба. Теперь, когда оно у меня есть, я попробую, наверное, проанализировать и "понять" его и попробовать перевести в интуитивное описание, но у меня нет уверенности, что это вообще получится.
Дальше следует краткое описание того, как было найдено решение, в общих чертах, без точных подробностей и кода. Если кому-то нужен код или точные подробности, пишите мне в комментах или на почту. Если не хотите решительно никаких спойлеров, помогающих решить, не читайте дальше. Извините, если что-то непонятно, я пишу впопыхах, чтобы распрощаться наконец с этим, но готов объяснить, если надо.
СПОЙЛЕРЫ
СПОЙЛЕРЫ
СПОЙЛЕРЫ
Значит, так. Во-первых, мы предполагаем, что Алиса всегда начинает первый раунд с 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 стратегий, код записал все дерево в файл. Это случилось через несколько итераций после начала.
