Операция «Кооперация» или Пусть 1+1 будет 3

Давным-давно, когда персональные компьютеры еще были «дикими» и в руки не давались, а аббревиатура IBM PC означала машину с процессором 8086 (не XT, не AT, и уж точно не 286/386/486), мне довелось поработать в одном детском компьютерном лагере.

Давным-давно, когда персональные компьютеры еще были «дикими» и в руки не давались[Дикими — значит «не домашними», потому что денег на покупку такого компьютера домой практически ни у кого еще не было], а аббревиатура IBM PC означала машину с процессором 8086 (не XT, не AT, и уж точно не 286/386/486), мне довелось поработать в одном детском компьютерном лагере[Других компьютерных лагерей в те годы не было, так что если кто-то сильно захочет — найдет информацию и поймет, о каком лагере идет речь. А сейчас такие лагеря есть, и поэтому я не хочу рекламировать тот конкретный]. Там я познакомился с замечательным математиком и педагогом Андреем Тоомом, а от него услышал про недавно придуманную им игру[Разумеется, другие неантагонистические игры были известны и раньше. Классический пример — «дилемма заключенных». Известно, что если один из двух пойманных преступников согласится сотрудничать с полицией, а другой будет упрямо отпираться, то сотрудничающего освободят немедленно, а отпирающемуся впаяют срок 10 лет. Если оба будут продолжать отпираться, каждый получит минимальный срок — 6 месяцев. Однако если оба согласятся сотрудничать, то полиция быстро выведает, что к чему, и в результате каждый получит 2 года. Какой «ход» следует выбрать каждому из заключенных? Дилемма состоит именно в том, что выбор сотрудничества обоими заключенными приводит каждого к двухгодичному сроку, тогда как обоюдная «молчанка» грозит всего лишь полугодом. А как надо играть, если игра состоит из многих таких «ходов», а результаты предыдущих ходов известны? Подробности см. на www.en.wikipedia.org/wiki/Prisoner’s_dilemma].

Кооперация. Два игрока делают ходы одновременно. Каждый ход состоит в том, что игрок называет 1 или 2. Если оба назвали единицу, то они теряют по очку. Если оба назвали двойку — получают по очку. Если же игроки выбрали различные действия, то назвавший единицу получает три очка, а назвавший двойку — теряет три очка.

Партия состоит из заранее оговоренного (большого) числа ходов. Игроки могут быть как людьми, так и компьютерными программами. В последнем случае программе передается информация о предыдущих ходах каждого из игроков. Цель — не выиграть партию, а набрать в ней как можно больше очков. Победителем турнира считается тот, кто набрал больше всего очков во всех партиях, а число выигранных партий роли не играет.

Для удобства восприятия я свел правила начисления очков в табличку:

Из таблички хорошо видно, что для каждого игрока ход 1 вроде бы предпочтительнее, чем ход 2, потому что возможный выигрыш втрое больше возможного проигрыша (а в случае хода 2 — наоборот). Однако тут-то и зарыта собака: если оба игрока будут постоянно делать ход 1, то оба будут неуклонно терять очки. В то же время если оба будут играть двойками, то оба будут набирать.

Понятно, что интереснее всего сражаться в «Кооперацию» программами, но в те годы это было весьма затруднительно (см. сноску о диких PC), а потом Андрей Леонович Тоом уехал преподавать в США, и, видимо, на первый план у него вышли совсем другие проблемы[www.mccme.ru/edu/index.php?ikey=toom-03 — замечательная статья А. Л. Тоома «Русский учитель в Америке»]. Если не ошибаюсь, ни одного полноценного турнира программ, играющих в «Кооперацию», проведено так и не было. Так или иначе, ни о каких других аналогичных проектах я не слышал вплоть до последнего времени[Это не значит, что их не было. Например, можно сыграть с апплетом в «дилемму заключенных» на www.gametheory.net/Web/PDilemma].
Через пятнадцать лет после рождения «Кооперации» очень похожую идею воплотили в жизнь уральцы — создатели лаборатории интеллектуальных игр «Эквивалент»[eq.ur.ru] Дмитрий Филимоненков и Алексей Малев. Придуманная ими игра называется «Консенсус».

Консенсус. В начале каждой партии в банке находится некоторое, наперед оговоренное нечетное количество условных единиц. Ход состоит в том, что два игрока в тайне друг от друга выбирают, сколько у. е. они хотят получить. После этого задуманные числа оглашаются. Если их сумма равна количеству у. е., находящихся в банке, то партия заканчивается — каждый получает столько очков, сколько заказал. Если же сумма заказанных величин не равна тому количеству, которое находится в банке, то из банка отнимаются две условные единицы (штраф за отсутствие взаимопонимания), и игроки делают следующий ход, разыгрывая уже меньшую сумму. Когда в банке останется одна условная единица, партия автоматически заканчивается, а каждый игрок получает 0.

В демо-версию «Консенсуса» можно поиграть на сайте лаборатории «Эксперимент», где в качестве спарринг-партнеров вам предложат трех поросят, но меня больше всего заинтересовала не онлайновая игра с поросятами, а турнирная составляющая (все программы по разу сражаются каждая с каждой, и результат определяется общей суммой набранных очков). Я написал свою версию программы и отправил ее на сайт.

Поскольку турнир уже прошел, могу немного раскрыть карты. Я решил сразу отдавать игровую инициативу соперникам: первые несколько ходов моя программа играла предельно предсказуемо. Если этого хватало сопернику, чтобы «договориться», то партия быстро заканчивалась, мы оба набирали достаточно много очков. И только если за первые ходы договориться не удавалось, моя программа начинала анализировать, как же с ней играет соперник. Увы, видимо, я недостаточно хорошо продумал стратегию и поэтому занял только 12-е место из 19 возможных — вполне заслуженное наказание за плохую «сговорчивость» со слабыми соперниками[Посмотреть итоги можно тут: eq.ur.ru/kons/PlayArh.pl?id=t1&name=Весенний%20турнир%202005].

Как же нужно играть, чтобы выиграть турнир? Внятного ответа на этот вопрос пока нет (возможно, что-то станет ясно после второго турнира, намеченного на двадцатые числа мая). Однако не могу не процитировать обзор, написанный Дмитрием Филимоненковым[eq@mail.ur.ru]:

«Первый вопрос: как лучше играть — строго детерминировано или используя случайные стратегии? Среди присланных программ случайные вычисления так или иначе использовали шесть игроков.Нас, разумеется, волнует, насколько закономерны полученные результаты. Для определения этого мы после опубликования результатов несколько раз неофициально повторили турнир. Итоги: во всех повторах победу одержал antuan[Автор игровой стратегии antuan — Антон Некрасов , студент 4-го курса матмеха УрГУ], а второе место занял frodo. Участники, занявшие места с 3-го по 6-е, в большинстве случаев оставались в этом же диапазоне. Так что результаты могут считаться вполне объективными.

Второй вопрос: а все ли исходные данные нужны? Четверо участников применили алгоритмы без обратной связи, то есть вообще не анализировали предыдущие ходы. Еще две программы использовали только предыдущий ход противника, одна программа — два предыдущих хода, и еще две — три хода. А все остальные — всю предоставленную информацию. В первой пятерке всю информацию использовали четыре программы».