Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
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 стратегий, код записал все дерево в файл. Это случилось через несколько итераций после начала.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 24 comments