Про теорию игр
От: Shtole  
Дата: 24.09.20 22:58
Оценка: +1

Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.

— Википедия изо всех сил пытается объяснить суть теории игр. Нет, я не шучу.


http://files.rsdn.org/139866/dilemma.png

Много лет назад в каком-то научно-популярном журнале я, среди прочих головоломок, наткнулся на следующую задачу:

Двое преступников — А и Б — попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и каждый из них приговаривается к полугоду тюрьмы. Если оба свидетельствуют друг против друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?


Перечитывая условие сегодня, мне трудно сдержать своего внутреннего поручика: «Что будет, что будет... На жопу ...сь, вот что будет!». Задача шла в ряду прочих сортировок садовыми гномиками и определений направления тока воды. Что интересно, ответа не давалось, а предлагалось, типа, подумать над ответом в свободное время. (К вопросу о редакционных троллях). Спасибо и на том, что публикация была начала 90-х и в нагрузку не прилагался кусок марксистско-ленинистского учения о пользе сотрудничества со следствием .

Немного позднее я восстановил, наконец, культурный и научный контекст: оказалось, это ни много, ни мало — известная «дилемма (или даже парадокс) заключённого». А занимается её изучением некая наука, известная как «теория игр». Что, кстати, в этой дилемме такого парадоксального? Всего лишь наблюдение, что если каждый негодяй наплюёт на интересы другого и будет стремиться к своей цели напрямую, оба в результате побреются тупой бритвой. Парадокс, надо же.

Узнав, что есть целая теория, направленная на решение таких задач, я задался закономерным вопросом: так что же, всё-таки, будет? Что говорит нам госпожа Наука о правильном поведении в таких непростых жизненных обстоятельствах? Ради этого я готов был читать скучные книжки вроде «Теория игр для флота» и обводить вершины сплошной линией. Увы: понимания не приходило. В чём я не знал, кого винить: то ли своё малоумие, то ли корявое изложение (см. цитату в эпиграфе). В отчаянии я метался между «если это кто-то понимает, он будет играть на бирже, а не учить других» и «всё это шарлатанство, типа фейнмановского высказывания о квантовой механике» («Если вы думаете, что понимаете КМ, значит вы её не понимаете»).

Кстати, шарлатанство ли процитированное утверждение? Безусловно! Наука не может постулировать бессмысленность попыток понять изучаемый предмет, иначе зачем она нужна? Наука это поиск разумных объяснений, стремление к пониманию. Эх, конечно же, вы пошутили, мистер Фейнман! С тех пор я, хотелось бы надеяться, хотя бы немного приблизился к пониманию как КМ, так и теории игр. Давайте сверим наше понимание на примере ответа к той самой задаче. (Я, как видите, подумал над ответом. В свободное время). Итак: преступления совершать не надо, вот что. Ну, или, по крайней мере, попадаться, лол. Дальнейшее есть подробное объяснение этого ответа. Вы можете считать его годной популяризацией или бредом за(в,р)авшегося дилетанта, в любом случае я не обижусь. Можете считать и так, что я ломлюсь в открытую дверь, но судя по википедийной статье, что-то непохоже.

1. Задача про заключённых — статистическая (НЕ статическая! Это важно!). Да, парни, нас обманули: полностью она должна выглядеть как-то так: вы живёте миллион лет. Профессионально воруете. Иногда — что поделать! — попадаетесь. Как вести себя так, чтобы минимизировать года отсидки? Вот это будет что-то похожее на теорию игр. Но, как изящно подметил недавно один известный вор, которому сегодня конкретно корячится казённый дом и дальняя дорога, «Люди не пятигорские орлы, столько не живут». (Оставим в стороне напрашивающееся дополнение: а если б и жили, то и срокА бы больше были). 10 лет это слишком большая ставка для одной игры, чтобы в неё играть. Все усилия надо сосредоточить на том, чтобы не оказаться в комнате со злым и добрым дяденьками следователями. Например, не воровать (что, конечно, тоже ничего не гарантирует).

2. Ответ на вопрос: «Как себя вести?» имеет форму алгоритма. Это неявно подразумевается, конечно, а зря: надо бы эксплицировать (оговорить явно).

Во-первых, алгоритм имеет условные переходы. Даже если брать единственную партию в игру заключённого, разумный ответ должен начинаться со слова «если». Если улики сильны... Если мой напарник слаб духом... Если, если, если.

Во-вторых, он может нуждаться в генерации случайных чисел. Нет, известная строчка кода `int randomNumber = 4; // 4 is random enough` не годится. Значения для каждой сессии могут потребоваться разные и равномерно распределённые. Например, в ситуации буриданова осла. Осёл, заведомо выбирающий левую стопку при видимом равенстве в пределах погрешности, становится лёгкой добычей хитрожопых буриданов с весами. (На достаточно длинной серии кормёжек).

В-третьих, алгоритм имеет вычислительную сложность и подвержен проблемам останова. (Вспомним, опять же, буриданова осла).

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

3. Рассматриваемые последовательности игр — динамические. Это значит, что нельзя просто взять из справочника результат первых 100 игр и подать на вход алгоритму. Нужен (когда нужен) результат 100 игр именно из текущей серии. Ведь благодаря тому, что алгоритм может включать рандомизацию, а игрок является компьютером с памятью, становится возможным реализовать стратегии, оперирующие понятиями «наказание», «прощение» и «поощрение». Заключённый первоначально ничего не знает об алгоритме поведения своего подельника в кризисной ситуации. (В Матроске половина сидельцев думала, что знает, хе-хе. Теперь ждут этап в Мордовию. Почитайте для примера тюремные дневники Сергея Мавроди. Очень остужает нездоровый оптимизм). Нужна серия игр, чтобы прощупать его поведение, попытаться смоделировать внутреннее устройство и — всё это одновременно — донести до него некоторое послание. Например, что за «кидком» последует N твоих, не взирая на последствия. (То есть, послание, на самом деле будет: «Не советую меня кидать»). Как, например, посылает окружающим сообщение суперкомпьютер «Рамзан», грозящий убить 100 федералов за каждого соплеменника.

4. Алгоритм-ответ не может быть задан однозначно. После каждой серии игр (серия в реальной жизни определяется произвольно) он должен (если хочет выиграть) уметь модифицировать себя, чтобы включать опыт взаимодействия с другими алгоритмами. Что, вообще говоря, называется «обучение».

Самообучающийся компьютер? Ой, да это же теория мышления! Да. Теперь два последних утверждения. Первое, слабое, таково: посмотрите на результат компьютерного перевода в нынешнем году, и вы поймёте, в каком зачаточном состоянии находится эта наука. Какого ответа на задачу о заключённых вы ожидаете? Там ещё пилить и пилить. Второе, сильное: если гипотеза об отсутствии ограничений, налагаемых законами физики на создание знаний, верна (например, нельзя ни в какой момент времени получить полный список научных открытий), универсального ответа к этой задаче нет и не будет, будет лишь нескончаемая серия последовательных приближениий. И значит нам будет чем заняться в ближайшую вечность.
Do you want to develop an app?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.