Математика в играх

Уже с давних времен люди играли в кости, карты и другие игры, заключали пари («бились об заклад») по поводу исхода предстоящих событий. От невинных забав постепенно переходили к игре со значительными ставками. Два партнера, сражаясь в какую-нибудь интересную и увлекательную игру, получают большое творческое удовлетворение от борьбы, а подчас и эстетическое удовольствие. Ну, а победы и поражения, хитроумные замыслы и коварные ловушки соперников не мешают им оставаться друзьями. А можно ли высчитать исход игры, заранее предопределить результат?

Игра Ним

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

А как играть, если во всех кучках разное число камней? Оказывается, здесь ответ даёт двоичная система счисления. Запишем в этой системе число камней в каждой кучке. Посмотрим теперь, сколько единиц в каждом разряде. Например, если числа камней в кучках равны соответственно 3, 4 и 6, то эти числа в двоичной системе записываются так: 11, 100, 110. В разряде сотен у нас единицы (у второго и третьего числа), в разряде десятков тоже две, а в разряде единиц лишь одна единица (у первого числа). Назовём комбинацию чисел выигрывающей, если в каждом разряде чётное число единиц (то есть либо их нет совсем, либо равно две). Искусство игры в «Ним» состоит в том, чтобы передавать противнику каждый раз такую выигрывающую комбинацию. Например, если числа камней в кучках равны 3, 4 и 6, то надо исправить лишь положение дел в разряде единиц. Для этого берём один камень из первой кучки и передаём противнику комбинацию 2, 4, 6. В двоичной системе она записывается так: 10, 100, 110. Теперь в разрядах сотен и десятков по две единицы, а в разряде единиц ни одной единицы. Значит, это комбинация выигрывающая.

Партнёр не может перейти от выигрывающей комбинации к другой выигрывающей и обязательно своим ходом нарушает равновесие единиц. Тогда вы своим ходом восстанавливаете это равновесие и снова передаёте ему выигрывающую комбинацию. Например, если, получив комбинации. 2, 4, 6 партнёр возьмёт один камень из третьей кучки, то получится 2, 4, 5, или в двоичной системе счисления: 10, 100, 101. Беря теперь один камень из первой кучки, получаем комбинацию 1, 4, 5, то есть 1, 100, 101, которая снова выигрывающая. И так идёт игра, пока вы не дойдёте до выигрывающей комбинации 0, 0, 0, то есть пока вы не возьмёте последний камень.

Разумеется, переводить во время игры в уме числа двоичную систему счисления довольно сложно. Поэтому запоминают выигрывающие комбинации чисел, которые надо передавать партнёру. Лучше человека играет в «Ним» электронные вычислительные машины. И на многих выставках можно наблюдать, как люди безуспешно сражаются с машинами, на которых перевод чисел двоичную систему счисления и подбор удачного хода никакого труда не составляет.

Игра в кости

В кости (так издавна называли кубики с точками по бокам) играли не только на Востоке – чуть ли не во всех странах мира. Чаще всего играли двумя костями: каждый из партнёров бросал кубики на стол или на специальный поднос; выигрывал тот, у кого сумма очков оказывалась больше. Секрет выигрыша, оказывается, довольно прост. Чтобы разобраться в нём, займемся несложной арифметикой.

Бросая одну кость, можно получить одно, два, три, четыре, пять или шесть очков. Каждое число очков будет выпадать - в среднем – одинаково частою Можно сказать, что все шесть вариантов равновозможны. Говорят, что каждый вариант осуществляется – в среднем – в шестой части всех бросаний. Иначе, вероятность получения, скажем, пяти очков при одном бросание кости составляет 1/6. Такую же вероятность имеет и получение другого числа очков. Эти события равновероятны.

Легко заметить, что два очка получается лишь в одном варианте (1+1), а например 8 очков – в пяти вариантах: 2+6, 3+5, 4+4, 5+3, 6+2.

Значит, 8 очков будет выпадать в среднем в 5 раз чаще, чем 2 очка. Можно сказать, что вероятность получения при одном бросании пару костей двух очков составляет 1/36. Может ли на двух костях оказаться 13 очков? Нет, не может, поэтому Р(13) = 0. Вообще вероятность невозможного события равна нулю; точно так же вероятность события, которые неминуемо должно произойти, считается раной единице. Взойдёт ли завтра в Москве солнце? Да, обязательно, хотя можно проспать этот момент или не заметить его из-за облаков, таким образом, Р(завтра в Москве взойдёт солнце) = 1.

Продолжу рассуждения. При бросании трёх костей получается 6 х 6 х 6 = 6 = 216 вариантов. В каждом из них мы насчитываем от 3 до 18 очков. На 3 очка получается лишь в одном варианте: 1+1+1 = 3

5 очков можно получить шестью способами (в шести вариантах): 1+1+3 = 5, 1+3+1 =5, 3+1+1 =5, 1+2+2 =5, 2+1+2 = 5, 2+2+1 =5. Для 10 очков существует 27 вариантов. Значит, в среднем 10 очков будет выпадать в 27 раз чаще, чем 3 очка. Столь же часто может выпадать 11 очков; в 50 вариантах (из 216) оказывается 9 или 12 очков, немногим меньше вариантов для 8 или 13. Часто люди играли на деньги, можно строго доказать, что ставить рубль при этих условиях игры невыгодно. Конечно, кто-то может случайно выбросить 3 очка (или 18), но это будет чрезвычайно редким событием. При многократной игре в выигрыше всегда останутся организаторы игры.

Крестики – нолики

Самая простая игра – крестики-нолики на доске 3 х 3. Партнёры по очереди ставят на поля квадрата крестики и нолики, и выигрывает тот, кто первым выстроит три своих знака в ряд. Разумеется, игра длится не более девяти ходов. Если никому из игроков не удается добиться цели, партия заканчивается вничью.

Интересно, что даже на таком простом примере можно проиллюстрировать многие важные понятия математической теории игр. Игра «3 в ряд» относится к категории конечных, переборных, стратегических игр двух лиц с полной информацией. Будем обозначать вершинами (точками) возникающие в процессе игры «позиции» (расположения крестиков и ноликов). Пусть начинают крестики. Соединим начальную вершину (пустая доска) с теми девятью, которые отвечают первому ходу крестиков. Каждую из них соединим с восемью вершинами, отвечающими ходам ноликов, и т. д. В результате мы получаем дерево игры (дерево перебора). Начальная вершина – корень дерева, максимальная длина ветви (глубина перебора) в данном случае равна девяти. Проанализировав дерево при помощи так называемой минимаксимальной процедуры, мы математически точно определим, как должна закончиться партия при наилучших действиях обеих сторон.

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