Ним (игра)

  • Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.

    Частный случай, когда кучка одна, но максимальное число предметов, которые можно взять за ход, ограничено, известен как игра Баше. Ним — конечная игра с полной информацией. Классическая игра Ним имеет фундаментальное значение для теоремы Шпрага-Гранди. Эта теорема утверждает, что обычная игра в сумму беспристрастных игр эквивалентна обычной игре в Ним. При этом каждой беспристрастной игре-слагаемому соответствует кучка Ним, число предметов в которой равно значению функции Шпрага-Гранди для игровой позиции данной игры.

Источник: Википедия

Связанные понятия

Ним Витхоффа, или игра Витхоффа, — стратегическая математическая игра для двоих игроков с двумя кучками фишек. Игроки по очереди берут фишки из одной или обеих кучек; в последнем случае из обеих кучек берется поровну фишек. Выигрывает тот, кто забирает последнюю или последние фишки.
Игра Гранди — это математическая игра на стратегию для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют одну кучу на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух и менее предметов и ни одна не может быть разделена на кучки разных размеров. В игру обычно играют как и в поддавки. Это означает, что последний игрок, который сможет сделать разрешенный ход, выигрывает.
Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход.
Игры Блотто (Игры Полковника Блотто) представляют собой класс игр двух лиц с нулевой суммой, в которой задача игроков состоит в распределении ограниченных ресурсов по нескольким объектам (полям битв). В классической версии игры игрок, выставивший больше ресурсов на поле, выигрывает битву на этом поле, а суммарный выигрыш (цена игры) равен сумме выигранных битв.
Быки и коровы — логическая игра, в ходе которой за несколько попыток один из игроков должен определить, что задумал другой игрок. Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова. После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»). Роли участников игры не равнозначны — угадывающий должен анализировать...

Упоминания в литературе

Таблица стратегии для блэкджека должна подсказывать игроку правильные действия в каждом из случаев, соответствующих одной из десяти возможных открытых карт дилера и одному из пятидесяти пяти возможных вариантов пар карт, сданных игроку. Чтобы найти наилучший вариант розыгрыша карт игроком в этих 550 разных ситуациях, нужно рассчитать все возможные варианты раздачи следующих карт, а также результаты игры и размеры выплаты для каждого из них. Могут существовать тысячи, даже миллионы разных вариантов розыгрыша каждой руки. Объем вычислений для всех 550 возможных ситуаций – и это если рассматривать только случай игры в одну полную колоду – огромен. Если игроку приходит пара, таблица стратегии должна подсказать ему, стоит ли разделять эту пару. После этого нужно решить, удваивать ли ставку: если игрок это делает, размер ставки увеличивается в два раза, а игрок получает в дополнение к двум первым картам руки еще одну, и только одну, карту. Наконец, нужно принять последнее решение – продолжать прикупать карты или «остановиться». Я собирался, определив выигрышную стратегию, изложить все эти мириады решений в форме маленькой наглядной карточки, такой же, какую я сделал себе для стратегии Болдуина. Это позволило бы получить визуальное представление о схемах игры и значительно облегчило бы запоминание оптимальных действий в каждом из 550 возможных случаев.
Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть будут иметь одинаковые платежи. Игры с нулевой суммой – особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. В играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Большинство игр дискретны: в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Метаигры – такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом).
Однако большинство из вас знают, как в худшем случае добиться хотя бы ничьей в игре в крестики-нолики на поле три на три. Так что есть простое решение этой игры, которое можно найти посредством обратных рассуждений, и истинный стратег способен существенно снизить сложность игры в ходе его поисков. Оказывается, как и в версии игры «два на два», многие возможные пути на дереве игры со стратегической точки зрения идентичны. В частности, девять начальных ходов могут быть только трех типов: вы ставите крестик на угловую позицию (четыре возможных варианта), на боковую позицию (также четыре возможных варианта) и на центральную позицию (один вариант). Использование этого метода для упрощения дерева игры поможет снизить уровень сложности задачи и приведет вас к описанию оптимальной равновесной стратегии, полученной методом обратных рассуждений. К примеру, мы могли бы показать, что игрок, который ходит вторым, может гарантированно добиться как минимум ничьей, сделав надлежащий первый ход и постоянно блокируя в дальнейшем попытки первого игрока выставить три символа в ряд[24].
Это подводит нас к центральной задаче, которую мне нужно было решить в рамках анализа игры в блэкджек: как игрок может в общем случае оценить частично израсходованную колоду, чтобы определить, выгодна ли для него данная ситуация, и если выгодна, то насколько именно? Эта задача была решена[30] при помощи нескольких вопросов, заданных высокоскоростному компьютеру IBM 704. Первый вопрос был таким: предположим, что в блэкджек играют колодой, из которой удалены только четыре туза. Какова в такой ситуации оптимальная стратегия игрока и каково преимущество заведения (или игрока)? Другими словами, компьютер должен был сделать в точности то же самое, что он делал при разработке базовой стратегии, но с одним отличием. На этот раз задачу нужно было решить для колоды, в которой отсутствуют четыре туза.
Интуитивный критерий лежит на поверхности. Предположим, следующим ходом (напомню, мы в качестве базовой игры рассматриваем шахматы) игрок теряет ферзя. С точки зрения простой оценочной функции, это очень плохо, и такой ход разумно исключить из рассмотрения. Предположим далее, что следующим ходом противник теряет ферзя. Обычный здравый смысл говорит, что на этом варианте следует сосредоточиться. Но мы сделаем несколько парадоксальный вывод, что этого хода также следует избегать. Дело в том, что, выстраивая теорию, мы исходили из предположения, что силы игроков равны. Из чего следует, что ни один из игроков выиграть слишком много не может. И следовательно, как выигрыш ферзя, так и его проигрыш необходимо признать делом нереальным. Математически расчетная схема выглядит так: определим для оценочной функции пределы значений, для которых ни одному из игроков не гарантирована победа. Эти два уровня опять-таки можно определить экспертной оценкой. Назовем нижний уровень уровнем альфа, а верхний – уровнем бета. Далее все очень просто. Идя по дереву перебора, будем выполнять оценку промежуточных ситуаций (в чистом минимаксе интересны только конечные позиции), и если эта оценка ниже уровня альфа или выше уровня бета, то такую игровую ветку отсекаем. На вопрос, как все же решиться взять ферзя противника, ответим немного позже.

Связанные понятия (продолжение)

Элузис — индуктивная карточная игра, в которой один игрок загадывает правило раскладки карт, а другие, глядя на разложенные карты, должны его угадать. Элузис — одна из первых игр, моделирующих изучение законов природы и развивающих не только логическое, но и индуктивное мышление.
Двадцать четыре — это китайская арифметическая карточная игра, цель которой — найти такое использование четырёх целых чисел, чтобы результат равнялся 24.
Реверси (другое название — оте́лло) — настольная игра для двух человек на доске 8 на 8 клеток.
Баше́ — математическая игра, в которой два игрока из кучки, содержащей первоначально N предметов, по очереди берут не менее одного и не более М предметов. Проигравшим считается тот, кому нечего брать.
Игра в кубики (игра в плитки, плиточки) была популярна среди детей всех возрастов во Владивостоке, а также в Cредней Азии в начале-середине 80-х годов XX века. Интерес к игре начал увядать приблизительно в 1986 году, когда стали осуществляться попытки получить коммерческую выгоду от продажи кубиков, что быстро привело к их девальвации.
Руле́тка — азартная игра ( слово рулетка (roulette) происходит от французского слова "ру" в переводе с французского означает "колесо, ролик , бегунок "). Рулетка впервые появилась во Франции. Она называлась "хока" и в ней было 40 пронумерованных гнёзд и три были помечены "зеро". Во времена короля Луи XIV, кардинал Мазарини, чтобы пополнить казну, повсеместно разрешил во Франции, открывать казино. После смерти Мазарини в 1661 году вышел Указ, гласивший что всякий кто осмелится открыть казино для игры...
В теории игр, игра в нормальной или стратегической форме (англ. normal form) состоит из трех элементов: множества игроков, множества чистых стратегий каждого игрока, множества платежных функций каждого игрока. Таким образом, игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора. Эта таблица называется платёжной матрицей (англ. payoff matrix).

Подробнее: Нормальная форма игры
Солитер — это настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita.
Пешечная дуэль — это логическая игра на шахматной доске. В ней участвуют два игрока, у каждого перед началом игры по три (иногда более) пешки, расположенные друг против друга на противоположных крайних горизонталях. Первыми ходят белые. Каждый ход состоит из передвижения одной из пешек своего цвета. Первым ходом каждый из игроков может идти не далее, чем до середины доски, и на любое количество клеток во все последующие ходы. Пешки ходят вперёд либо назад. Задача каждого из игроков — оставить противника...
Патолли — настольная игра, распространённая среди ряда народов Доколумбовой Америки, в том числе среди майя и ацтеков. Была популярна как среди простолюдинов, так и среди знати. Ацтекское слово «патолли» означает «боб». Некоторые исследователи считают её тождественной древнеиндийской игре пачиси, в то время как другие находят такое сходство чисто визуальным.
Варианты правил го — различные своды правил настольной игры го. Отличаются отдельными деталями, трактовкой некоторых редко встречающихся в реальных партиях позиций, правилами определения результата в спорных случаях и порядком подсчёта разности очков. Все используемые на практике варианты эквиваленты в абсолютном большинстве случаев, их различия проявляются только в редких ситуациях.
Блэкдже́к, блек-дже́к (англ. Blackjack) — одна из самых популярных карточных игр в казино по всему миру. Большая популярность игры обуславливается простыми правилами, скоростью игры и наиболее простой стратегией в подсчёте карт. Тем не менее популярность игра завоевала не сразу. Игорным домам Соединённых Штатов приходилось стимулировать интерес к игре различными видами бонусов и выработкой нескольких разновидностей правил для блек-джека. Считается, что предшественником этой игры была карточная игра...
Се́ка — карточная игра, известная в СССР и странах, образовавшихся после его распада.
Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «Кто выиграет при правильной игре?»
Парадокс пари (Парадокс галстуков) — известный парадокс, похожий на задачу о двух конвертах, также демонстрирующий особенности субъективного восприятия теории вероятностей.
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно...
Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет). Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянии.
Парадо́кс Парро́ндо — парадокс в теории игр, который обычно характеризуют как комбинацию проигрышных стратегий, которая выигрывает. Парадокс назван в честь его создателя, Хуана Паррондо, испанского физика. Утверждение парадокса выглядит следующим образом...
Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.
«Па́лочки» («точки и квадраты», «сундучки», цветные крестики-нолики), «точки» — настольная игра для 2-х и более человек на листке бумаги в клетку.
Мус — является испанской карточной игрой, как утверждается, это самая популярная карточная игра в Испании. Это игра со взятками, с аспектом соперничества, происходящая из Наварры и страны Басков в Испании. Оттуда она распространилась по всей стране, где сейчас является самой популярной карточной игрой, порождая бесчисленные клубы Мус или Пеньяс и становясь основной игрой среди студентов колледжа. Она высоко ценится, рассматривается многими как одна из лучших игр в карты.
Битва полов или семейный спор (англ. Battle of the sexes (BoS), альтернативное расшифровка аббревиатуры — англ. Bach or Stravinsky, «Бах или Стравинский») — одна из основополагающих некооперативных моделей в теории игр, которая предполагает участие двух игроков с разными предпочтениями.
«Балда» — лингвистическая настольная игра для 2—4 игроков, в которой необходимо составлять слова с помощью букв, добавляемых определённым образом на квадратное игровое поле. В наиболее популярном варианте игры, который имеет множество компьютерных реализаций, слова составляются посредством переходов от буквы к букве под прямым углом. Правила варианта игры под названием «Королевский квадрат» допускают диагональные переходы.
Эволюция (англ. Evolution: The Origin of Species) — настольная игра, основанная на теории Дарвина. Игра была создана кандидатом биологических наук Дмитрием Алексеевичем Кнорре в 2010 году, и входит в серию «Правильные игры» (www.rightgames.ru). В 2011 году вышла также на английском, французском и немецком языках. Игра была признана лучшей игрой 2010 года многими российскими игровыми порталами и стала известна также за пределами России.
Стохастическая игра (англ. stochastic game) в теории игр — повторяющаяся игра со случайными переходами состояний, разыгрываемая одним и более игроками.
Покер на костях — азартная игра в кости. В неё могут играть от двух человек и более, оптимальное число игроков — четыре. Для игры используют 5 кубиков с числовыми достоинствами от 1 до 6. В зависимости от игровой ситуации, выбрасываются от одного до пяти кубиков одновременно. За выполнение определённых комбинаций даются очки. Все комбинации и результаты их выполнения записываются в таблицу. Цель игры — набрать наибольшую сумму очков.
Заимствование стратегии (англ. strategy stealing) — стандартный приём, доказывающий для многих настольных игр, что у второго игрока не может быть выигрышной стратегии, то есть при идеальной игре либо выигрывает первый игрок, либо ничья. В общих чертах: предполагаем, что у второго игрока есть выигрышная стратегия, затем несложными выкладками преобразуем её в стратегию для первого игрока, противоречие. Если вдобавок в игре отсутствует ничья (например, гекс или «перебрось мостик»), заимствование стратегии...
Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность».
«Свободная ячейка» (англ. FreeCell) — карточный пасьянс. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет. В Windows XP игра некорректно названа «Солите́р» (этот пасьянс отличается от «Свободной ячейки» одним правилом).
Парадокс Монти Холла — одна из известных задач теории вероятностей, решение которой, на первый взгляд, противоречит здравому смыслу. Эта задача не является парадоксом в узком смысле этого слова, так как не содержит в себе противоречия, она называется парадоксом потому, что ее решение может показаться неожиданным. Более того, многим людям бывает сложно принять правильное решение даже после того, как его им рассказали.
Задача о двух конвертах (Парадокс двух конвертов) — известный парадокс, демонстрирующий как особенности субъективного восприятия теории вероятностей, так и границы её применимости.
См. также джетан из «Марсианских шахмат» Э. Р. Берроуза.Марсианские шахматы — абстрактная стратегическая игра, придуманная Эндрю Луни. Играется пирамидками Луни на шахматной доске. Количество игроков — от двух до шести. Чтобы играть количеством игроков, отличных от двух и четырех, нужно использовать неевклидову поверхность для получения доски необходимого размера.

Подробнее: Марсианские шахматы (игра)
Пентамино́ (от др.-греч. πέντα пять, и домино) — пятиклеточные полимино, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.
Домино́ — настольная игра, в процессе которой выстраивается цепь костяшек («костей», «камней»), соприкасающихся половинками с одинаковым количеством точек, обозначающим число очков. Также этим термином называют и другие настольные игры, цель которых состоит в расположении на столе или специальном игровом поле костей с нанесёнными на них одним или несколькими символами так, чтобы они касались одноимёнными символами друг друга. Каждый символ из набора, как правило, имеет численное значение.
«Абалон» (фр. Abalone) — настольная абстрактная стратегическая игра для двух игроков, придуманная французскими дизайнерами игр Мишелем Лале (Michel Lalet) и Лораном Леви (Laurent Lévi) в 1987 году под названием «Сумито». В игре используются шарики разных цветов (по 14 шаров каждого цвета) и шестиугольное игровое поле, содержащее 61 пункт. Целью игры является выталкивание шести шаров соперника за пределы поля. Существуют варианты правил для трёх-шести игроков.
Это статья об азартной игре. См. также Пасьянс Маджонг.Маджонг или мацзян (кит. трад. 麻將, упр. 麻将, пиньинь: májiàng, палл.: мацзян) — китайская азартная игра с использованием игральных костей для четырёх игроков (каждый играет за себя). Широко распространена в Китае, Японии и других странах Восточной и Юго-Восточной Азии. Игра ведётся костями, напоминающими костяшки домино, по правилам подобна покеру, требует от играющих таких качеств, как опыт, память и наблюдательность. В игре присутствует также...

Подробнее: Маджонг
Префера́нс (фр. préférence — предпочтение, преимущество) — карточная игра со взятками. Получила распространение в России в середине XIX века. Предшественником преферанса считается вист. Игра ведется втроём или вчетвером (в последнем случае каждый игрок по очереди пропускает раздачу, что называется «сидит на прикупе») или вдвоём (тогда игру называют «гуса́рик»). Возможно играть и больше, чем вчетвером, но тогда игра теряет динамичность и интерес к ней снижается, так как карты раздаются только троим...
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Верю-не-верю — карточная игра, основной чертой которой является умение блефовать или разгадать обман соперников.

Подробнее: Верю не верю
Равнове́сие Нэ́ша — концепция решения, одно из ключевых понятий теории игр. Так называется набор стратегий в игре для двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Джон Нэш доказал существование такого равновесия в смешанных стратегиях в любой конечной игре.
То́чки — логическая настольная игра для двух человек, сочетающая позиционное стратегическое планирование с тактическим перебором вариантов. Ведётся на плоском игровом поле, расчерченном на клетки одинакового размера. Игроки поочерёдно ставят точки двух цветов в перекрестия линий. Цель — окружить точки соперника замыканием вокруг них непрерывной цепи своих точек.
Деберц (де-берц, дэ-берц) — карточная игра. Существуют её разновидности в портовых черноморских городах: клабор и белот.
Карточная игра — игра с применением игральных карт, характеризуется случайным начальным состоянием, для определения которого используется набор (колода) карт.
Шахматы для троих — семейство вариантов шахмат, разработанных специально для игры втроем. Относятся к коалиционным играм. Существует множество вариаций шахмат для троих игроков. Как правило, в них используется нестандартная доска. Например, шестиугольная доска, доска с клетками — правильными треугольниками или трехсторонняя с четырёхугольными клетками, соединяющимися в центре доски особым образом.

Упоминания в литературе (продолжение)

Запишите числа от 1 до 100 либо загрузите поле для игры в классики с веб-сайта «Тайн 4исел». Первый игрок берет фишку и кладет ее на простое число, отстоящее от квадрата 1 не более чем на 5 шагов. Затем фишку берет второй игрок, он должен положить ее на большее простое число, отстоящее от предыдущего положения фишки не более чем на 5 шагов. Далее снова делает ход первый игрок, ему необходимо переместить фишку на еще большее простое число, которое удалено не более чем на 5 шагов. Проигравшим считается тот участник, который не может сделать ход по правилам. Правила таковы: 1) фишку нельзя передвигать более чем на 5 шагов; 2) ее нужно класть на простое число; 3) нельзя ходить назад либо оставаться на месте.
Это была всего лишь короткая научная статья, но она имела большое значение. Она доказала, что система кодирования Рипа подходит для научного анализа, а также впервые продемонстрировала, что некоторые аспекты игры следуют четким и постоянным числовым шаблонам. Рип и Бенджамин выяснили, что команды в среднем забивают примерно один гол из каждых девяти ударов по воротам. Они обнаружили, что шансы команды завершить пас в целом равны шансам игры в «орла или решку» – около 50 процентов, но они снижаются с каждым дополнительным завершенным пасом. Они пришли к заключению, что футбол является вероятностным (то есть беспорядочным) процессом: один из девяти ударов по воротам заканчивается голом, но какой именно – трудно сказать.
У некоторых читателей уже наверняка возник вопрос, как же можно рассчитывать столь сложные таблицы, ограничиваясь только сложением и вычитанием? Неужели они там вместо того, чтобы умножать, многократно складывали? Но тогда не то что девяти, и девяноста лет не хватило бы… Нет, конечно. Использовался уже достаточно хорошо известный к тому времени метод конечных разностей. В совсем популярном изложении идея этого метода выглядит следующим образом. Рассмотрим последовательность квадратов натуральных чисел: 1, 4, 9, 16, 25, 36, 49… Попарно вычитая друг из друга соседние числа, мы увидим другую последовательность: 3, 5, 7, 9, 11, 13… – т. е. последовательность нечетных чисел. Линейную. А в этой последовательности разность соседних чисел всегда одна и та же – 2. Именно так разъяснял этот метод сам Бэббидж, так продолжают разъяснять его и популяризаторы. Для более искушенных в алгебре читателей PC Magazine/RE я бы написал много короче. Если f(x) – полином степени n, то несложно показать, что f(x+a) – f(x) всегда будет полиномом степени n–1. Продолжая этот процесс, мы неизбежно дойдем до полинома нулевой степени, т. е. до константы. Все. При заполнении таблиц поступаем в обратном порядке: рабочая таблица состоит из ряда столбцов, каждый из которых содержит значения полинома очередной степени. Для получения новой величины требуется сложить значение из предыдущей строки со значением из предыдущего столбца. Окончательным результатом будет самый правый столбец. А математики из второй группы в команде де Прони должны были всего-навсего вычислить все начальные значения. Работа кропотливая и муторная (я попробовал!), но вполне подъемная. Наверное, можно было бы и не упоминать о том, что все вычисления малограмотные «счетоводы» из последней третьей группы выполняли (как они думали) над целыми числами, а на самом деле над числами в формате с фиксированной запятой.
Некоторые великие задачи встречаются и в начальном курсе математики, хотя мы этого не замечаем. Вскоре после того, как ребенок осваивает умножение, он знакомится с концепцией простого числа. Известно, что некоторые числа могут быть получены при перемножении двух меньших чисел, к примеру: 6 = 2 × 3. Другие, такие как 5, невозможно разложить подобным образом на сомножители. Максимум, что можно сделать, это записать 5 = 1 × 5, но в этом выражении нет двух меньших чисел. Числа, которые можно разбить на сомножители, называют составными, а те, что разложить невозможно, – простыми. Простые числа кажутся такой несложной темой! Если вы уже умеете перемножать натуральные числа, то способны разобраться и в том, что представляет собой простое число. Простые числа – первичные строительные кирпичики для всех натуральных чисел, и обнаружить их можно в самых разных разделах математики. Но в них есть тайна, и, на первый взгляд, они раскиданы среди положительных целых чисел почти случайным образом. Нет никаких сомнений: простые числа – настоящая загадка. Возможно, это естественное следствие их определения – ведь определяются они не через какое-либо присущее им свойство, а напротив – через свойство, которое у них отсутствует. С другой стороны, для математики это фундаментальное понятие, поэтому мы не можем просто так в ужасе поднять руки и сдаться. Нам необходимо с ними освоиться и каким-то образом вызнать их потаенные секреты.
Как бы то ни было, проблема не слишком сложна. Во-первых, не существует точного определения «шести самых непопулярных номеров». При каждом розыгрыше вы узнаёте (всего-то), какое количество участников выбрало определенный набор номеров. Существует несколько способов определения, сколько человек выбрало тот или иной номер, и все они основаны на математических моделях. Результаты в целом совпадают с небольшими вариациями.
Потому может показаться неожиданным тот факт, что современные компьютеры, решая сложную задачу, действуют совсем иначе. Сама по себе арифметика, разумеется, не представляет большой сложности для современного компьютера. Вот, например, взаимодействие с человеком, восстановление поврежденного файла или победа в игре го (задачи, в которых нет четких правил, частично отсутствует необходимая информация или же поиск единственно верного ответа требует рассмотрения астрономического числа вариантов) действительно бросают вызов компьютерному интеллекту. И алгоритмы, разработанные учеными для решения задач самых сложных категорий, избавили компьютеры от необходимости всецело полагаться на всевозможные расчеты. На самом деле для разрешения реальных жизненных ситуаций необходимо смириться с тем, что в жизни есть место случаю или вероятности, что нам приходится максимально аккуратно использовать время и зачастую работать только с приближенными значениями величин. По мере того как компьютеры приближаются к решению повседневных проблем, они могут предложить не только алгоритмы, которые человек может использовать в жизни, но и более совершенный стандарт, по которому можно оценить когнитивные способности человека.
Треугольник устроен таким образом, что каждое число в нем равно сумме двух чисел, расположенных непосредственно над ним. Полученные числа определяют, как следует разделить выигрыш в любой прерванной игре. Например, если Ферма до победы не хватает двух выигранных партий, а Паскалю – четырех, нужно взять строку треугольника номер 2 + 4 = 6 и найти сумму первых четырех чисел и сумму последних двух. Эти суммы дают пропорцию, в которой следует разделить выигрыш. В данном случае получается пропорция 1 + 5 + 10 + 10 = 26 к 1 + 5 = 6. Таким образом, Ферма получает 26/32 · 64 = 52 фунта, а Паскаль – 6/32 · 64 = 12 фунтов. В общем случае решение для игры, в которой Ферма не хватает n, а Паскалю – m выигранных партий, можно найти в (n + m) – й строке треугольника Паскаля.
Компьютеры произвели в этом деле настоящую методологическую революцию. Вместо расчета приближенных формул движения, а затем подстановки чисел в эти формулы теперь можно с самого начала работать с числами. Предположим, вы хотите предсказать, где некоторая система тел – скажем, спутники Юпитера – будет находиться через сто лет. Начните с первоначальных позиций и параметров движения Юпитера, его спутников и всех остальных тел, которые могут иметь значение, – в данном случае это Солнце и Сатурн. Затем, постепенно, один крошечный временной шаг за другим, вычисляйте, как изменяются числа, описывающие все задействованные тела. Повторяйте это действие до тех пор, пока не дойдете до временной отметки сто лет. Стоп. Человек, проводящий вычисления при помощи карандаша и бумаги, не смог бы воспользоваться этим методом для расчета сколько-нибудь реалистичной задачи. На это потребовалось бы несколько жизней. Однако при наличии быстрого компьютера метод становится вполне реализуемым, а современные компьютеры очень и очень быстры.
У нас получился прямоугольник из 5 рядов и 6 столбцов – всего 30 кружков. Значит, в каждом из двух наших треугольников была половина общего их количества, то есть по 15 кружков. Мы, это, разумеется, уже знаем, но давайте применим этот же принцип к двум прямоугольникам, количество рядов в которых равно n. Точно так же составим из них прямоугольник с n рядов и n + 1 столбцов. Кружков в нем будет n × (n + 1) – ну или в более привычной записи – n(n + 1). В результате мы получим формулу, которая позволит нам подсчитывать сумму первых n чисел:
Как и в предыдущем примере, эти два вопроса практически одинаковы. Казалось бы, как следует поразмыслив, вы должны дать на них одинаковые ответы, однако исследования показывают, что большинство людей, отказываясь от риска в первом случае, соглашаются на него во втором. Это обусловлено тем, что в данных вопросах используются различные точки отсчета. В первой формулировке точка отсчета равна нулю, что подчеркивает размер отдельно взятого выигрыша или проигрыша, а мысль о неблагоприятном исходе приводит в действие механизм консервативного мышления. Во второй формулировке точка отсчета равна $2000, что наглядно демонстрирует финансовые последствия того или иного решения.
С помощью круговой диаграммы легко представить себе процентные соотношения – то, каким образом распределены разные части единого целого. Например, вы хотите узнать, какой процент школьного бюджета тратится на зарплаты учителям, на учебные материалы, на ремонт. Или же вам хочется выяснить, какая часть денег, ассигнованных на учебные материалы, идет на естественные науки, язык, физкультуру, музыку и т. д. Главное правило круговых диаграмм – сумма процентов во всех секторах должна быть равна 100. Представьте себе пирог: ведь круговая диаграмма – не что иное, как пирог, поделенный на кусочки. Если девять человек хотят разделить его поровну, мы не можем порезать его на восемь частей. И тут ничего нельзя поделать.
Вернемся теперь к другому, более трудному и более содержательному аспекту параллелизма между головоломками и проблемами нормальной науки. Проблема, классифицируемая как головоломка, должна быть охарактеризована не только тем, что она имеет гарантированное решение. Должны существовать также правила, которые ограничивают как природу приемлемых решений, так и те шаги, посредством которых достигаются эти решения. Например, решить составную картинку-загадку не значит «составить картинку». Ребенок или современный художник мог бы сделать это, складывая разбросанные, произвольно выбранные элементы, как абстрактные формы, на некотором нейтральном фоне. Картинка, созданная таким образом, может оказаться намного лучше и быть более оригинальной, чем та, из которой головоломка была сделана. Тем не менее такая картинка не могла бы быть ее решением. Чтобы получить настоящее решение, должны быть использованы все фрагменты, их плоская сторона должна быть обращена вниз и они должны быть собраны без усилий и использованы без остатка. Таковы некоторые правила решения картинки-головоломки. Подобные ограничения, накладываемые на приемлемые решения кроссвордов, загадок, шахматных задач и т. д., вскрываются без труда.
Человек не осознает действия этих двух систем, поскольку результатом их работы становится одно ясное решение. Мы замечаем их, только если они вступают в противоречие, как в задаче о бейсбольной бите и мяче. Автоматически мы понимаем вычисления, но интуиция предлагает другой ответ. Бегло взгляните на таблицу на рисунке 1.4 и назовите вслух как можно быстрее цвета слов, начиная с верхней левой ячейки. Итак, зеленый, черный, красный…
Герберт Саймон и Аллен Ньюэлл, крупнейшие специалисты в области компьютерных наук середины XX в., также полагали, что заучивание отвлеченных правил не способствует развитию логического мышления, и представили более наглядное тому доказательство. Однако их доводы основывались на весьма ограниченных наблюдениях. Они установили, что человеку, который справлялся с задачей с игрушечными пирамидками (в которой нужно перенести кольца с одного стержня на другой, при этом нельзя класть большее кольцо на меньшее – возможно, вы играли в эту игру в детстве), это не помогало справиться с задачей про волка, козла и капусту, которых нужно переправить на другой берег реки. Формально эти задачи имеют одинаковую структуру, но для решения одной из них нельзя применить знание, приобретенное при решении другой задачи. Полученный Саймоном и Ньюэллом результат был интересным, но он не мог доказать, что навык в решении определенной задачи никогда не переносится на задачу с подобной структурой.
Айовский эксперимент – это всего лишь простая карточная игра, небольшое число испытуемых и детектор стрессового состояния. Однако это и яркая иллюстрация работы нашего мозга. Перед нами ситуация, когда ставки высоки и все происходит очень быстро, а участникам приходится обрабатывать большой объем новой и противоречивой информации за очень короткое время. Что мы узнали из данного эксперимента? Мы узнали, что в такие моменты, чтобы оценить ситуацию, наш мозг использует две совершенно разные стратегии. С первой из них мы все в основном знакомы – это стратегия осмысленного познания: мы обдумываем полученную информацию и делаем вывод. Данная стратегия основана на логике и доказательствах. Но нам нужно целых восемьдесят карт, чтобы добраться до истины. Это требует времени и массы дополнительной информации. Однако есть и вторая стратегия, которая запускается уже после десяти карт – т. е. очень быстро. В этой стратегии проблема с колодами из красных карт фиксируется почти моментально. Однако у нее имеется существенный недостаток: поначалу, и довольно долго, она используется исключительно на уровне подсознания. Мозг сообщает нам о ней обиняком, например через потовые железы на ладонях. Другими словами, наш мозг приходит к определенному выводу, но сообщать об этом не спешит.
Какое именно время потребовалось компьютеру для достижения цели – не имеет значения. Если вам интересно, в первый раз он справился с задачей, пока я выходил пообедать. То есть где-то за полчаса. (Читатели, увлекающиеся компьютерами, сочтут это неоправданно долгим. Причина в том, что программа была написана на бейсике – компьютерной разновидности детского лепета. Когда я переписал ее на паскале, выполнение заняло 11 секунд.) В таких делах компьютеры несколько проворнее обезьян, но на самом деле разница не принципиальна. Что действительно существенно, так это разница между сроком, потребовавшимся для накапливающего отбора, и тем промежутком времени, который потребовался бы для достижения той же самой цели тому же самому компьютеру, работающему точно с такой же скоростью, но методом одноступенчатого отбора: около миллиона миллионов миллионов миллионов миллионов лет. Это более чем в миллион миллионов миллионов раз больше сегодняшнего возраста Вселенной. Лучше даже будет сказать так: по сравнению с тем временем, которое понадобится обезьяне или компьютеру, чтобы случайно набрать нужную фразу, нынешний возраст вселенной – пренебрежимо малая величина, столь малая, что наверняка попадает в пределы погрешности, допускаемой нами в наших приблизительных вычислениях. А компьютеру, работающему тоже наугад, но при ограничивающем условии накапливающего отбора, для выполнения той же задачи потребуется срок, вполне доступный простому человеческому пониманию: от 11 секунд до времени, необходимого, чтобы пообедать.
Данное определение является самым широким по объему среди всех, которые уже были приведены. Это вызвано тем, что с точки зрения необходимости достижения частного выигрыша, «игровое действие» является тем общим понятием, которое дает возможность поставить знак равенства между (например) ударом по мячу «топ-спин» в настольном теннисе, длящимся долю секунды, и многоходовой атакой целой команды футболистов, которая может длиться несколько минут; оба они – игровое действие.
Словарное определение игры подразумевает ее свободный, развлекательный характер, а также получение удовольствия от процесса. Тем не менее, наблюдая за тем, как играют дети, можно понять, что они относятся к игре с чрезвычайной серьезностью. Некоторые ученые-теоретики полагают: чтобы тот или иной вид деятельности можно было назвать игрой, он должен обладать определенными характеристиками. К примеру, Краснор и Пеплер (1980) утверждают, что игра должна обладать следующими свойствами: добровольность участия, получение удовольствия, высокая мотивация, использование игровых ролей и сосредоточенность на процессе, а не на результате. Увы, проблема заключается в том, что эти особенности заметны лишь в некоторых типах игр, тогда как в других обнаружить их достаточно сложно, если вообще возможно. Пеллегрини (1991) утверждает: чем больше свойств из этого списка обнаруживается в ходе той или иной деятельности, тем с большей уверенностью мы можем причислить ее к играм. Но можно ли предположить, что некоторые из этих характеристик более значимы по сравнению с другими? А может, разные наблюдатели просто видят вещи по-разному? К примеру, кто-то может считать, что добровольный характер участия куда важнее, чем отсутствие конечного результата, а другой может считать процесс игрой лишь на основе того, что участники получают от него откровенное удовольствие. Для иллюстрации этого тезиса давайте рассмотрим два случая детской игры с деталями конструктора «Лего».
В тот день, когда я посетил лабораторию Гальвеза, одна из оптических скамей была отдана под эксперимент по изучению запутанности, цель которого заключалась не только в демонстрации запутанности, но и в исследовании возможной причины этого явления. Мне кажется, что установка по существу является высокотехнологичной машиной Руба Голдберга[6] для подбрасывания монет. Они падают орлом или решкой в зависимости от того, проходят через фильтр или нет. Система настроена таким образом, что вероятность пройти его – 50 на 50, как в случае подбрасывания правильной монеты. В сущности, план такой: создать пару таких монет, подбросить их одновременно, посмотреть, какой стороной они упадут, создать еще одну пару, подбросить ее и т. д. Повторить опыт несколько тысяч раз и собрать статистику. Кажется, что мы тратим много усилий ради предсказуемого результата, пока не вспомнишь о том, что разговор идет о квантовых монетах. Ясно, что представление частиц в виде монет – это метафора, но если не воспринимать ее слишком буквально, то она вполне законна. Физики сами понимают явления при помощи метафор.
После просмотра первой передачи публику поразил гораздо более простой эксперимент, пробудивший ее живейший интерес, – «магический квадрат». Участнику соревнования дают трехзначное число, которое он должен разложить на такое количество чисел, сколько их потребуется для заполнения шахматной доски, чтобы суммы этих чисел в колонках и строках равнялись первоначальному числу. Чтобы усложнить задание, он должен был заполнять доску ходом коня со случайного поля. Естественно, он должен был выполнять задание в уме и спиной к доске.
Существует еще и третья формулировка, основанная на качественно иных понятиях. Если вам не нравится действие на расстоянии, то я показал вам, как можно без него обойтись. Теперь я дам вам формулировку, которая в философском смысле прямо противоположна предыдущей. Тут нам не нужно переходить от момента к моменту, от точки к точке; мы опишем все сразу, целиком. Пусть у нас имеется несколько частиц и вы желаете знать, как одна из них перемещается из одного места в другое. Вообразим все возможные пути перехода из одного места в другое за данный отрезок времени (рис. 17). Скажем, частица должна перейти из точки X в точку Y за час и вы желаете знать, по какому пути она может двигаться. Вы воображаете всевозможные кривые и для каждой кривой подсчитываете определенную величину. (Я не хочу рассказывать, какая это величина, но для тех, кто о ней наслышан, напомню, что для каждого пути она равна среднему значению разности между кинетической и потенциальной энергией.) Если вы подсчитаете эту величину для одного пути, а затем для другого, то для разных путей получите разные числа. Но один из путей дает наименьшее возможное число – именно этим путем и воспользуется на самом деле частица! Теперь мы описываем действительное движение, эллипс, высказывая нечто о кривой в целом. Нам не нужно думать о причинности, о том, что частица чувствует притяжение и движется в согласии с ним. Вместо этого мы говорим, что она разом «обнюхивает» все кривые, все возможные пути и решает, какой выбрать. (Выбирает тот, для которого наша величина – минимальная.)
Вторая разновидность интуиции помогает нам справляться с огромными потоками информации. Количество данных, которые поступают в наш мозг, каждый год удваивается, особенно с наступлением эры компьютеров и Интернета. Однако сознательно мы можем удерживать в голове семь (плюс-минус две) порций информации единовременно. Чтобы понять, что это значит, попробуйте выполнить такое простое упражнение. Попросите кого-нибудь произнести вслух ряд из множества чисел, а сами в это время держите руки поднятыми вверх. Как только почувствуете, что дальше запомнить числа вам уже не удастся, опустите руки. Если вы не владеете какими-либо продвинутыми техниками запоминания, то, наверное, сумеете удержать в памяти от пяти до девяти чисел – как раз в пределах нормальных человеческих возможностей. А что же происходит, когда вы подвергаетесь воздействию тысяч и даже миллионов порций информации? Чтобы справиться с ними, вы развиваете некую оценочную эвристику (методы, требующие наименьших затрат времени и сил). Существует множество известных эвристических методов, задокументированных психологами в течение последних 20 лет, и Куртис проделал большую работу, изучив роль этой эвристики в трейдинге.
На данный момент исследователи, изучающие решения, дают ясный ответ: преувеличенное ощущение собственного контроля – обычная вещь. Наиболее известные исследования были проведены в 1970-х Эллен Лангер, психологом из Гарвардского университета. Представьте, что вы собираетесь сыграть в лотерею. Вы хотите выбрать номер самостоятельно или были бы счастливы, если бы кто-то сделал это за вас? Вероятно, это не должно вас волновать, ведь выигрышные номера выпадут случайно и независимо от того, кто выбирал лотерейный билет. Но людей это волнует, и даже до такой степени, что они готовы заплатить за право выбрать номер.[40] Другой эксперимент заключался в разрезании карт. И опять испытуемые действовали так, как будто могли повлиять на результаты, даже если совершенно точно не могли. Лангер назвала это иллюзией контроля.[41] С тех пор как в 1975 году были впервые опубликованы ее выводы, опыты множество раз воспроизводились, и всегда с одними и теми же результатами: мы часто действуем так, как будто можем контролировать события, даже в тех случаях, когда не можем.
Итак, в теории – это количество моих прямых конкурентов. Огромное число, но стоит немного подумать – и становится понятно, что не все так страшно. Сразу отсеем тех, кто не может позволить себе играть круглые сутки напролет: они не конкуренты. Так, опять заходим на теорикрафт-форум и смотрим неофициальную статистику распределения игроков по времени пребывания в игре. Смотрю на кривую, похожую на график среднего распределения, и радуюсь. В этом со мной может конкурировать только один процент! Итого – примерно десять тысяч; что же, цифра уже не настолько пугающая! Две трети из них не играют по сути, а зарабатывают в игре, добывая игровые ресурсы, обмундирование и оказывая прочие услуги за реальные деньги. Они заняты иным, им не до короны. Итого – чуть больше трех тысяч соперников. Конечно, многие из них плевали на титулы и имеют другой интерес, иные захотят примерить корону других государств. Но лучше думать, что все они – самые натуральные соперники, идущие по одному со мной пути! Так надежнее. Эх! Если бы не фора в семь месяцев у многих из них, я бы, наверное, даже порадовался получившимся цифрам. Но семь месяцев реальности – это год и три четверти в мире «Трона»! Прорва времени! И мне придется это наверстывать, хорошо, что у меня уже сложился вполне определенный план!
Рене была не в курсе подхода Стива и потому разработала свой собственный способ запоминания: вместо того чтобы разбивать цифры на группы по три-четыре штуки, как Стив, она использовала сложную систему мнемонических правил, основанную на днях, датах и времени суток[16]. Важным отличием было и то, что Стив всегда заранее решал, какой подход он будет использовать – например разбивая последовательность на группы из 3–4 цифр и одной группы из 4–6 в конце. Он повторял про себя эти группы снова и снова, пока не запоминал, как они звучат. Например, ряд из 27 цифр Стив разбивал на три группы по 4 цифры, три группы по 3 цифры и группу из 6 цифр. Этот шаблон мы назвали «возвратным». Он позволял Стиву концентрироваться на запоминании отдельных наборов цифр и их положении в общей последовательности. Этот подход оказался на редкость эффективным: с его помощью Стив «привязывал» каждую группу к времени забегов, перемещал ее в долговременную память и вспоминал только в самом конце, когда начинал перечислять все цифры в последовательности.
Игра в рулетку ведется двумя или тремя крупье – в зависимости от типа стола (с одним или двумя игровыми полями). Единственное преимущество игрового стола с двумя игровыми полями, расположенными по обе стороны от самой рулетки, состоит в том, что он вмещает вдвое большее число участников, которые, в свою очередь, имеют возможность сделать больше ставок. Разметка обоих игр совершенно идентична.
Чтобы показать, как аналитическая машина могла генерировать числа Бернулли, Ада описала последовательность операций, а затем составила диаграмму, показывающую, как каждая из них может быть закодирована в машине. Попутно она помогла разработать концепцию подпрограмм (последовательности инструкций, которые выполняют определенную задачу, например вычисление косинуса или сложных процентов, и которые могут по мере необходимости вставляться в более крупные программы), а также рекурсивных вложенных циклов (последовательности повторяющихся инструкций)[8]. Это стало возможным сделать благодаря применению перфокарт. Для определения каждого числа Бернулли, как она объяснила, необходимо семьдесят пять карт, затем процесс становится итерационным, поскольку это число отправляется обратно и используется в процессе уже для получения следующего числа. Она пишет: “Очевидно, что те же самые семьдесят пять переменных карт могут быть использованы для вычисления каждого последующего числа”. Она предвидела, что будет создана библиотека часто используемых подпрограмм, и действительно, спустя столетие ее интеллектуальные наследники, в том числе такие женщины, как Грейс Хоппер из Гарварда, а также Кей Макналти и Джин Дженнингс из Пенсильванского университета, создадут такую библиотеку. Кроме того, машина Бэббиджа позволяла переходить туда и обратно внутри последовательности команд на картах в зависимости от полученных промежуточных результатов, и таким образом появилось то, что в будущем станет операцией условного перехода – когда тот или иной тип инструкций выбирается в зависимости от условий.
Хотя это правило совершенно идентично варианту с цифрами и буквами, его проверка обычно не вызывает сложности. Примерно 80 процентов испытуемых сразу же понимают, что необходимо перевернуть карточку «машина». Судя по всему, им очевидно, что если карточка «машина» с обратной стороны подписана «Лос-Анджелес», то это немедленно опровергает правило, в то время как совершенно не имеет значения обратная сторона карточки «самолет», поскольку по правилу в Нью-Йорк можно добираться любым видом транспорта.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я