?

Log in

No account? Create an account

Previous Entry | Next Entry

Про наши будни

Решаю я тут на днях, собственного удовольствия и практики ради, олимпиадную задачку. Всё идёт отлично, пока я не обнаруживаю, что мой красивый алгоритм в некоторых случаях не работает. Что тут поделаешь? Нахожу контрпример. Понимаю, что алгоритм придётся полностью переписать. Но вот беда: моя единственная идея на данный момент -- брут-форс, который потребует два в девяностой операций. Прихожу к М. искать поддержки.

-- У, -- говорю ему. -- Два в девяностой.
А у него сочувствия ни в одном глазу.
-- У! -- с нажимом повторяю я.
-- А как ты хочешь, чтобы я сочувствовал? -- уточняет он.
-- Ну, ты можешь сказать, что всё будет хорошо. Что два в девяностой -- совсем не так страшно.
-- Всё будет хорошо. Два в девяностой -- совсем не так страшно. Просто построй квантовый компьютер.

Вот так всегда.

А завтра у меня на работе турнир, в котором боты будут играть друг против друга в какую-то игру. Правила ещё не известны, зато дан общий расклад. С теорией игр и теорией принятия решений я почти не знакома, поэтому сижу, просматриваю на всякий случай самые применимые алгоритмы. М. же на эту тему вспомнил отличную историю, которую я хочу вам пересказать.

Дело происходит в тренировочном лагере USACO в ранних две тысячи нулевых. Проводится турнир. Боты бьются не на жизнь, а на смерть в "камень-ножницы-бумага". Один раунд: кто-то победил, кто-то проиграл, участники бегут дорабатывать код. Не успели оглянуться, уже следующий раунд.

Постепенно в играх выявляется лидер. Им оказывается бот, который принимает решения случайно. В соревновании с ним не выдерживает никто. Драма нарастает. Неужели именно он победит в турнире?

И вот идёт один из последних раундов. Участников два: случайный бот и какой-то другой. Выигрывает в основном случайный, как от него уже и ждут.

Но в середине раунда происходит нечто неожиданное. Второй бот начинает выигрывать. Затаив дыхание, участники наблюдают, как второй бот выигрывает каждую игру до конца раунда. Он оказывается победителем турнира.

Спрашивается, как он это сделал?

Он вычислил random seed случайного бота.

Comments

( 3 comments — Leave a comment )
doublle_troub
Jun. 27th, 2016 02:48 pm (UTC)
Ассоциации с идеальной отмычкой :)
be_unafraid
Jun. 28th, 2016 12:37 am (UTC)
А что за история про идеальную отмычку? :)
doublle_troub
Jun. 30th, 2016 11:02 am (UTC)
Истории нет, просто вот представилось, что отмычка - всем отмычкам отмычка :)
( 3 comments — Leave a comment )