Техника - молодёжи 1958-03, страница 14

между живыми, разумными существами и раскрыть его закономерности.

Около тридцати лет назад математики Нейман, Уолд и другие создали основы математической теории игр. Она имеет большое принципиальное значение и практическое применение в экономике; военном деле и других областях. Эта теория и лежит в основе руководства к действию при «обучении» машины различным играм.

«Научить» электронную машину искусной игре в шахматы очень трудно. Но более простые игры — «в камешки» или «крестики-нулики»— она осваивает быстро и проводит безошибочно.

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

Найти общие закономерности игры «в камешки» не так уж просто, но можно, и это было доказано опытом.

В одном из павильонов научной выставки, организованной во время Британского фестиваля 1956 года, ежедневно с утра до позднего вечера царило необычайное оживление.

Нетерпеливая молодежь, степенные отцы семейств и почтенные леди с увлечением играли в камешки с электронной машиной «Нимрод», специально построенной для игры в «Ним».

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

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

Познакомимся с принципами математического обоснования игр на примере игры «Ним». Перед нами три кучки. В первой тринадцать, во второй — девять, в третьей — пять камней. Ход наш.

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

Как же выбрать первый ход и создать благоприятные условия игры?

Для ответа нужно составить весь план игры. Необходимо, во-первых, четко определить все возможные си

туации, при которых предстоит сделать очередной ход. Во-вторых, нужно решить, -какой выбрать ход в каждой ситуации из всех возможных вариантов.

Вот пример одного из возможных планов для игрока, начинающего игру.

Взять первым ходом все камни иэ первой кучки. Бели противник возьмет все камни второй кучки, то вторым ходом взять оставшуюся кучку камней. Если же противник ответным ходом возьмет один камень из второй кучки, то вторым ходом взять из той же кучки еще три камня. Если после этого партнер возьмет один камень из третьей кучки, то своим третьим ходом взять тоже один камень, но из второй кучки, и так до взятия последнего камня.

Точно так же можно построить второй, третий и последующие варианты плана Даже для нашей простой игры с малым числом камней их существует много сотен. Эти планы игры называются стратегиями.

Чтобы правильно вести игру, каждый участник должен рассмотреть всевозможные стратегии своей игры и выбрать из них наилучшую — оптимальную. Она и должна служить ему руководством к действию.

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

Это, безусловно, верно! И именно поэтому так трудно безошибочно проводить достаточно сложные игры.

Но оказывается, что для игры в «Ним» (или другие игры в камешки) можно обойтись без .нудного перечисления всех ситуаций и анализа всех вариантов стратегии, один из которых мы пытались проделать

Можно дать простое правило игры, всегда приводящее к выигрышу. Конечно, это правило не поможет, если уже в самом начале игра была безнадежной и партнер пользуется тем же правилом. Короче говоря ее исход предопределен начальной ситуацией.

Правило игры в .«Ним» выглядит особенно просто, когда числа камней в кучках представлены в двоичной системе счисления. В нашем случае числа выражаются так:

1-я кучка ..... 1 101 камень (13)

2-я кучке..... 1 001 камень (ч)

3-я кучки.....0 101 камень (5)

2 203

Под чертой мы выписали сумму единиц в каждом из одинаковых разрядов наших чисел. Заметьте, что

в первых трех разрядах эти суммы четные — 2, 2, 0 (ноль тоже считается четным числом), а в последнем разряде сумма нечетная — 3.

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

Перед очередным ходом машины в ее память вводятся данные о ситуации: число оставшихся кучек и сколько камней в каждой. Эти сведения подаются в десятичной системе счисления. Машина переведет их в двоичную систему. При сигнале «ход» машина начнет складывать числа по двоичным разрядам.

При образовании нечетной суммы единиц в. каком-либо из разрядов машина напечатает свой очередной ход: «Снять столько-то камней иа кучки такой-то».

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

После знакомства с принципами механизации простых игр . можно представить себе те огромные трудности, которые возникают при «обучении» машины квалифицированной шахматной игре.

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

Как ни парадоксально, но наше увлечение шахматами зиждется на том, что мы не знаем математического решения этой игры.

Бельгийский математик М. Край-чих попытался хотя бы приблизительно подсчитать общее число всевозможных вариантов шахматных партий. Оно равно 2ХЮ^,1в.

Если бы все население земного шара круглые сутки играло в шахматы, делая ежесекундно по одному ходу то потребовалось бы не менее 10¹⁰⁰ веков, чтобы переиграть все варианты шахматных партий.

Любители шахматной игры могут не беспокоиться. Составить список всех стратегий — решить до конца задачу шахматной игры — ближайшим поколениям не удастся даже с помощью самых быстродействующих вычислительных машин. Шахматам пока не угрожает участь «Нима».