Игра «Ним» оценка игровой ситуации. Алгоритм игры Текст научной статьи по специальности «Математика»
Статья содержит описание алгоритма для игры "Ним". Игра состоит в следующем. В начальной позиции перед двумя игроками сложено несколько кучек одинаковых мелких предметов например, спичек. Игроки по очереди могут выбрать одну из кучек и взять из нее одну или несколько спичек. Выигрывает тот, кто возьмет последнюю спичку. Предложенная выигрышная стратегия связана с представлением натуральных чисел в двоичной системе счисления.
Похожие темы научных работ по математике , автор научной работы — Пискарев Алексей Валерьевич
Текст научной работы на тему «Игра «Ним» оценка игровой ситуации. Алгоритм игры»
Пискарев Алексей Валерьевич
ОЦЕНКА ИГРОВОЙ СИТУАЦИИ. АЛГОРИТМ ИГРЫ
Широко известна игра «Ним». Правила ее очень просты. Играют двое. На столе перед ними лежат несколько кучек каких-то предметов, например, спичек. Игроки ходят по очереди, и каждый игрок в свой ход выбирает одну из кучек и изымает из нее любое количество спичек. Если он изымет все спички из выбранной кучки, то она перестает существовать. Выигрывает тот игрок, который своим очередным ходом сумеет забрать все оставшиеся спички.
Пусть перед нами лишь одна кучка спичек. Что делать — ясно: забрать все спички из этой кучки и выиграть.
Что, если перед нами две кучки, и в них одинаковое количество спичек? Тог-
. лефаН Нескольку кугек клких-Наа прерме&аб, Например,, спигек.
да мы, вероятнее всего, проиграем: сколько бы мы ни брали из одной кучки, наш партнер будет брать столько же из другой и в результате выиграет.
А если две кучки, но с разным количеством спичек? Тогда опять ситуация в нашу пользу: мы можем своим ходом уравнять две кучки и свести ситуацию к предыдущей, которая теперь будет проигрышной уже для нашего партнера.
Можно придумать много разных ситуаций, которые при рассмотрении оказываются заведомо выигрышными или проигрышными.
Возникает вопрос: любая ли ситуация окажется выигрышной или проигрышной?
Выходит, что да, любая. И вот почему. Ситуация с одной-единственной спичкой заведомо выигрышная. Далее будем рассматривать последовательно все варианты более сложных ситуаций для любого количества спичек. Если в какой-то ситуации найдется такой ход, который обеспечивает противнику проигрышную ситуацию (более простую, уже рассмот-
"ЧЛаа если пере^ Нлми <р£е куиси, и 6 Них а^иНлсобое калигеоНба спигек?
ренную), то эту ситуацию следует считать выигрышной; если же такого хода не найдется и любой ход будет переводить игру к выигрышной для противника ситуации, то такая ситуация для нас — проигрышная.
Итак, любая ситуация в игре «Спички» или выигрышная, или проигрышная. Но как определить тип сложившейся ситуации на практике, по ходу игры? Способ прямого перебора в действительности неприменим из-за своей трудоемкости. Для ответа на этот вопрос обратимся к представлению чисел в двоичной системе счисления.
Дальнейшие рассуждения сопровождаются рассмотрением примера конкретной игровой ситуации <18, 8, 14, 9, 23>-в фигурных скобках перечислены объемы имеющихся пяти кучек.
Представим все заданные числа в двоичной системе счисления: 18=(10010)2 8=(1000)2 14=( 1110)2 9=(1001)2 23=(10111)2
Теперь все эти представления чисел выпишем в столбик цифра под цифрой так, чтобы одна под другой оказались цифры одинаковых разрядов (то есть как при сложении в столбик):
Крестиками следует отметить те столбики, в которых стоит нечетное количество цифр 1. Теперь рассмотрим два возможных случая: какое-то количество столбиков отмечено («крестики есть») и ни один столбик не отмечен (если во всех столбиках количество цифр 1 четно -«крестиков нет»).
Пусть «крестики есть». Тогда найдем первый слева из них и выберем любое из заданных чисел, в котором цифра над этим крестиком равна 1 (здесь таких чисел три: 8, 14 и 9; выберем, например, 8). Проделаем над числом 8 такую операцию: те цифры 1 и 0 двоичной записи этого числа, под которыми оказались крестики, заменим на противоположные (0 на 1 и 1 на 0), остальные цифры оставим без изменения:
Получилась двоичная запись числа 2. Следует совершить ход, оставив из 8 спичек 2 (забрать 6). Сложится новая ситуация <18, 2, 14, 9, 23>.
Покажем, что в любом случае новое число (С) будет строго меньше старого (А). Действительно, пусть есть выбранное нами двоичное число
— двоичные цифры, стоящие в столбиках левее первого слева крестика (возможно, их вовсе нет, п = 0), а Ь , Ь , . , Ь
— цифры, стоящие правее первого слева крестика (их тоже может не быть, т = 0). После описанного выше преобразования числа А мы получим число
Первые п цифр останутся неизменными, следующая цифра поменяется с 1 на 0, и как-то могут поменяться остальные цифры. Из наглядного поразрядного сравнения чисел А и С:
С = (а а л. ал0с с
"Нре^сЛ-авим. все уадлЯЯш гисмя в фвиг^ой сисйеме сшсмшя.
ясно, что А > С (так как 1 > 0).
Теперь после нашего хода партнер, совершая подсчет аналогичным образом, не получит ни одного крестика (подумайте, почему). Рассмотрим этот вариант.
Итак, «крестиков нет». Тогда ход партнера не станет последним в игре. Вот почему: ход мог бы стать последним, только если на столе ле-
жит лишь одна кучка, но в таком случае хотя бы один крестик обязательно получится. Значит, на столе осталось более одной кучки, и ближайший ход не завершит игру.
Пусть игрок совершит любой ход. Найдется столбик двоичных цифр, который изменится от этого хода, причем ровно на одну единицу. И тогда количество цифр 1 в этом столбике станет нечетным, и мы при подсчете поставим под ним крестик и без крестиков, таким образом, не останемся.
Понятно, что если игра будет так продолжаться (то есть если мы будем продолжать придерживаться того же метода
выбора хода), то выиграем в результате именно мы, так как ни один ход нашего партнера не сможет завершить игру (рассмотрите самостоятельно, к чему приведет этот метод, если на столе останется только одна кучка спичек).
@пособ пр&мого перебарл 6 $ейаНбиАел-&НосНи неприменим и^-^л с6ош НруддемкооНи.
От редакции. Полезным упражнением для читателей будет написание программы для игры в «Ним», для этого можно использовать логическую операцию ХОЯ — исключающее «ИЛИ», которая позволит простыми вычислениями определять правильные ходы.
Прочитав статью Борзых А.К. «Универсальная самообучающаяся машина из спичечных коробков» в этом же номере журнала и познакомившись с самообучающимися машинами, можно попробовать сделать программу, которая научится играть в «Ним», не зная правильной стратегии! А в качестве учителя использовать программу, которая эту стратегию знает!
Пискарев Алексей Валерьевич, студент V курса СПбГЭТУ (ЛЭТИ) кафедры автоматизированных систем обработки информации и управления.
Игра «Ним»
Рассмотрим следующую игру. Даны $n$ кучек, в каждой из них какое-то количество камней. За один ход игрок может выбрать кучку и выбросить оттуда любое ненулевое число камней. Выигрывает тот игрок, который забрал последний камень.
При оптимальной игре в ниме на кучках размера 3, 4 и 5 выигрывает первый игрок
Немного переформулируем условие. Состояние игры однозначно описывается неупорядоченным набором неотрицательных чисел — пронумеруем их и обозначим количество камней в $i$-й кучке как $a_i$. Теперь, за один ход разрешается строго уменьшить любое из чисел. Терминальное состояние — когда все числа стали нулями.
Теорема. Состояние игры выигрышное тогда и только тогда, когда xor-сумма размеров кучек отлична от нуля:
$$ S = a_1 \oplus a_2 \oplus \ldots \oplus a_n \ne 0 $$
Доказательство проведём по индукции.
Для терминального состояния кучек уже нет, и xor-сумма равна нулю, и оно действительно проигрышное. База доказана — теперь докажем переходы.
Из состояния с нулевой xor-суммой все переходы ведут в выигрышные состояния, то есть в состояния с ненулевой суммой. В самом деле, достаточно убрать сколько угодно спичек из любой кучки — xor-сумма изменится с нуля на $a_i \oplus b_i $, где $b_i < a_i$ равно числу камней в $i$-й кучке после нашего действия.
Противоположный случай сложнее. Нужно показать, что если xor-сумма ненулевая, то всегда существует такой $b_i < a_i$, что xor-сумма станет нулевой, то есть
$$ S \oplus a_i \oplus b_i = 0 $$
Для этого посмотрим на старший единичный бит $S$ и возьмём любой $a_i$, у которого этот бит тоже единичный. Такой $a_i$ найдётся хотя бы один — по свойствам xor , их должно быть нечетное число. Из условия выше следует, что искомый $b_i$ должен быть равен $S \oplus a_i$.
Выясняется, что это корректный новый размер кучки, то есть $b_i < a_i$. Почему так? Потому что все старшие биты в выражении остались нетронутыми, $k$-й бит изменился на единицу, а что происходило с дальнейшими битами нам не важно, потому что эти изменения точно не больше, чем $2^k$.
Получается, что оптимальная стратегия такая: посчитать xor-сумму всех $a_i$, найти такой $a_i$, у которого старший бит взведен, и заменить его на $S \oplus a_i$. (А если xor-сумма $S$ оказалась нулевая, то сдаться.)
#Модификации
#Ним в поддавки (misère nim)
В противоположность обычному ниму, существует также «ним в поддавки»: когда игрок, совершивший последний ход, не выигрывает, а проигрывает.
Решение такого нима удивительно просто. Выигрышность позиции определяется так же, как и в обычном ниме — xor-суммой размеров кучек — но с одним исключением: если размеры всех кучек равны единице, то выигрышность и проигрышность меняются местами.
С учетом этого исключения, будем делать ходы как в обычном ниме, переходя в позицию с нулевой xor-суммой, но если такой ход ведёт в позицию, в которой размеры всех кучек равны единице, то этот ход надо изменить так, чтобы количество остающихся непустых кучек изменило свою чётность.
Доказательство. Рассмотрим некоторое течение игры: выберем произвольную стартовую позицию и выпишем ходы игроков вплоть до завершения игры. В любой игре двух оптимальных игроков рано или поздно наступает момент, когда размеры всех непустых кучек равны единице. Обозначим через $k$ число непустых кучек в этот момент — тогда для текущего игрока эта позиция выигрышна тогда и только тогда, когда $k$ чётно.
Откатимся теперь на один ход назад. Мы оказались в позиции, где ровно одна кучка имеет размер $a_i > 1$, а все остальные кучки (возможно, их было ноль) имеют размер $1$. Эта позиция выигрышна, так как мы всегда можем сделать такой ход, после которого останется нечетное число кучек размера $1$:
- Если всего непустых кучек нечетное количество, то заменяем $a_i$ на $1$.
- В противном случае, заменяем $a_i$ на $0$.
Далее, если продолжим откатываться по игре назад, то для всех состояний выигрышность также будет совпадать с «нормальным» нимом — просто потому, что когда у нас есть более одной кучки размера $>1$, то все переходы ведут в состояния с одной и более кучкой размера $>1$, а для всех них, как мы уже показали, ничего по сравнению с «нормальным» нимом не изменилось.
Таким образом, изменения в ниме «в поддавки» затрагивают только состояния, когда все кучки имеют размер, равный единице — что и требовалось доказать.
#Ним Мура (k-ним)
Условие. Есть $n$ кучек камней размера $a_i$. Также задано натуральное число $k$. За один ход игрок может уменьшить размеры от одной до $k$ кучек (то есть теперь разрешаются одновременные ходы в нескольких кучках сразу). Проигрывает тот, кто не может сделать хода.
Очевидно, при $k=1$ ним Мура превращается в обычный ним.
Решение. Запишем размер каждой кучки в двоичной системе счисления. Затем просуммируем эти нули и единицы вдоль каждого разряда и возьмём эту сумму по модулю $(k+1)$. Если во всех разрядах получился ноль, то текущая позиция проигрышная, иначе — выигрышная.
Доказательство, как и для обычного нима, заключается в описании стратегии игроков — нужно показать, что
- из игры с нулевым значением мы можем перейти только в игры с ненулевыми значениями, и
- из любой игры с ненулевым значением найдется ход в игру с нулевым значением.
Первый пункт доказывается следующим рассуждением. Если для всех разрядов сумма бит по модулю $(k+1)$ была равна нулю, то после изменения от одного до $k$ элементов снова получить нулевую сумму можно только «уравновешиванием» всех изменений: для всех элементов, где определенный бит удаляется, должен быть другой элемент, где этот бит добавляется. В частности, это должно выполняться и для самого старшего разряда, для которого хотя бы один бит у любого числа меняется. Но тогда это будет означать, что существует какой-то элемент, для которого добавилась единица в этом разряде, а все более старших разрядах ничего не менялось — значит, этот элемент будет больше исходного, что нарушает правила.
Осталось научиться переходить из состояний с ненулевыми суммами в нулевые. Назовём проблемными те позиции, для которых сумма битов получилась ненулевой. Переберем все биты от старшего к младшему и будем по очереди делать каждую проблемную сумму нулевой, уменьшая какое-то количество элементов.
Обозначим за $u$ количество кучек, которые мы уже начали изменять; изначально, $u = 0$. Обратим внимание, что так в этих $u$ кучках мы уменьшали какой-то из предыдущих, более старших, битов, то все более младшие биты мы можем ставить как угодно.
Пусть мы рассматриваем текущий бит, в котором сумма по модулю $(k+1)$ получилась ненулевой. В идеале, мы хотим сделать её нулевой, изменяя в этом разряде только те $u$ элементов, которые мы и так уже собрались изменять. Мысленно поставим во всех из этих $u$ элементов единицы в соответствующем разряде и пересчитаем сумму, обозначив её за $s$. Теперь рассмотрим два случая:
- Если $s \le u$, то мы можем обойтись уже выбранными элементами, убрав в $s$ из них единичный бит.
- В противном случае, если $s > u$ найдем $(s — u)$ дополнительных кучек, у которых рассматриваемый бит единичный, и будем уменьшать их вместе с $u$ уже имеющимися.
После каждой итерации число $u$ изменяемых кучек станет равным $u’ = \max(s, u) \le k$.
Таким образом, мы показали способ выбирать множество изменяемых кучек и какие биты следует в них изменять, чтобы общее их количество $u$ никогда не превысило $k$. Следовательно, мы доказали, что искомый переход из состояния с ненулевой суммой в состояние с нулевой суммой всегда существует, что и требовалось доказать.
#Зачем это вообще надо?
Цугцвангом (от немецкого zug — ход, и zwang — принуждение) в шахматах и многих других стратегических играх называют ситуацию, когда у игрока закончились хорошие ходы, и если бы правила позволяли, он бы просто стоял на месте и передал ход оппоненту.
Ход белых. Мат в 2 хода.
Выясняется, что игр, основанных на идее приведения противника к цугцвангу, очень много, и они все эквивалентны ниму — в том смысле, что их графы с точки зрения выигрышности суммы отдельных игр работают точно так же, как графы нима.
Задачи на логику, головоломки, загадки, ребусы — Л О Г О — Р А Й
Имеется две кучки спичек. В первой 7 спичек, во второй — 5. За один ход разрешается взять любое количество спичек, но из одной кучки. Проигрывает тот, кому нечего брать. Кто выигрывает при правильной игре — начинающий или его партнер? И как для этого ему надо играть?
При правильной игре выигрывает начинающий игрок. Его стратегия: первым ходом он должен сравнять количество спичек в кучках, т.е. взять из первой кучки 2 спички. Каждый следующий его ход должен быть «симметричен» ходу второго игрока, т.е. если «второй» берет n спичек из одной кучки, то «первый» должен взять также n спичек, но из другой кучки. Таким образом, если может сделать ход «второй» игрок, то может сделать ход и «первый». Так как после каждого хода количество спичек уменьшается, то наступит момент, когда «второй» не сможет сделать ход (ни в одной из кучек спичек не останется) и проиграет.
Стратегические игры и решение задач. Игра Ним и ей подобные
Сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми.
В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
Взаимосвязь между математикой и играми может касаться различных аспектов игр. Применительно к стратегическим играм математика особенно полезна для определения выигрышной стратегии. Стратегическая игра очень похожа на процесс решения математической задачи: речь идет не о том, чтобы выиграть одну партию, совершая более удачные ходы, но о том, чтобы найти способ, как выигрывать всегда. По этой причине при определении выигрышных стратегий используются эвристические методы: способ «от обратного»; предположение, что игра «решена»; применение симметрии; проведение аналогии с другой, уже решенной игрой и прочие. Они аналогичны тем, что используются при решении математических задач. Поэтому когда для некоторой игры известна выигрышная стратегия, игра из развлечения превращается в решенную задачу. Понятно, что это верно только для определенных игр, которые выходят за рамки простых развлечений и описываются в математических теориях. О подобных теориях, порой достаточно сложных, мы, возможно, поговорим позже.
Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр
подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она будет рассматриваться в следующих постах под названием «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
Игра 1: выигрывает первый
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если вы незнакомы с этой игрой, перед прочтением попробуйте сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну
фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2017), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру
можно обобщить и дальше, изменив число фишек, которые можно брать на каждом
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, . 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 — n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Игра 3: общий случай
Допустим, что на столе m фишек и каждым ходом можно брать от 1 до m фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?
Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:
1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n + 1. Для этого на каждом ходу, если первый игрок берет ρ фишек (0 < ρ < n + 1), второй должен брать
n + 1 — ρ фишек. Это число всегда положительно, так как находится на интервале от 0 до n.
2. Остаток от деления равен r (0 < r < n + 1).В этом случае существует выигрышная стратегия для первого игрока. На первом ходу он должен взять r фишек, оставив на столе число фишек, кратное n + 1. Теперь он может действовать подобно второму игроку из первого случая. Иными словами, если второй игрок берет ρ фишек (0 < ρ < n + 1), первый должен взять n + 1 — ρ.
Это общее решение применимо к бесконечному множеству игр. Вы можете применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно
m — 1, а не m.
. для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно
m — 1, а не m.
Вроде бы автор дал нам все что надо, что бы найти выигрышную стратегию для такого случая. Но для таких как я, которых не поняли у кого преимущество объясню подробнее:
В этом случае если, игрок берёт последнюю фишку и проигрывает, то определение преимущества немного меняется.
Стратегия остаётся той же: поделим m на n + 1 и определим остаток от деления.
Но теперь нам нужны другие остатки от деления.
Если остаток 0 или от 2 до n — 1 (1 ; n), то действует случай 2.
Соответственно, если остаток 1 или n, то действует случай 1. Все эти случаи описаны выше, но для них добавляется одна маленькая деталь:
теперь надо оставлять на столе число фишек равное i + 1 (i — это число кратное n + 1).
Все подобные игры, в которых используется только одна группа фишек, можно
считать упрощенными вариантами игры Ним, о которой я напишу в следующем посте.
Дорогой товарищ @moderator, добавьте пожалуйста тег Ним.
Я никак не могу его добавить, так как такого тега никто не использовал, и при нажатии Enter Ним меняется на тег Аниме
интересно. И ниразу не слышал про игру ним — надо будет попробовать.
Игра с природой, или что такое математическое ожидание? Часть 1
Всем привет ! Я решила немного повыкладывать научпоп, надеюсь, кому-нибудь зайдёт. Вначале будет немного математики, это самая скучная часть, но нужна будет, чтобы по-настоящему насладиться тем, что будет дальше. Это курс по теории игр для начинающих, который я в своё время вела на олимпиадных школах при физтехе (был жутко популярным), а потом сильно переработанный (и изданный в виде книги) читала и читаю во Франции на научпоп-лекциях. Итак, поехали !
Что такое случайность?
Все мы знакомы (ну или думаем, что знакомы) с таким понятием, как «случайность». Какое представление вы имеете о значении этого термина?
Самый распространенный ответ на этот вопрос: «Случайность случается, когда случаются неожиданные вещи». Что это за неожиданные вещи? Я думаю, вы и сами понимаете, что такое определение не имеет особого смысла. Вот определение, которое Аристотель дает термину «случайность»: «Когда этот случайный характер проявляется в фактах, произведенных с определенной целью, тогда мы говорим о действиях фортуны и случайности», но он утверждает, что «. является определенной причиной всего, что, как мы говорим, происходит случайно или по счастливой случайности».
Введём более формальное определение. «Случайность − это фактор, который определяет исход эксперимента из множества возможных исходов, известных заранее».
Но можем ли мы говорить о случайности, если мы не знаем заранее множество возможных исходов? Например, приходите вы на контрольную и получаете задачи. Являются ли они для вас случайными? А являются ли они случайными для вашего преподавателя? Подумайте об этом.
Случайность можно разделить на два различных типа:
Онтологическая случайность − случайность является частью бытия. Например, подбрасывание монетки можно отнести к данному типу случайности.
Эпистемологическая случайность −это случайность, которая возникает из-за незнания, невежества или невозможности понимания каких-то процессов, но на самом деле тут вполне всё предопределено.
Например, приходите вы в школу и выясняете, что сегодня у вас будет контрольная. Вам кажется, что это случайно, а на самом деле это было давно запланировано на педагогическом совете. Но вы об этом просто не знали. Фраза «Случайности не случайны» − как раз об эпистемологической случайности.
Очень многие люди и по сей день, не говоря уже о более ранней поре, считали и считают, что онтологической случайности не существует, что вся случайность носит только эпистемологический тип. Большинство учёных от эпохи Просвещения до начала двадцатого века считали, что, возможно, мы просто не знаем, как именно что-то работает, но всё предопределено заранее. Течение, в котором утверждается, что всё предопределено, называется детерминизмом. На принципе детерминизма построена классическая физика, а вот в квантовой физике всё достаточно сложно, и философы, и физики пока сами не до конца определились. Например, Поль Тири д’Гольбах, ученый-материалист и философ немецкого происхождения и французского выражения (1723-1789), писал: «В пылевом вихре, поднятом стремительным ветром, каким бы беспорядочным он ни казался нашим глазам, в самой страшной буре, возбуждаемой встречными ветрами, возмущающими волны, нет ни одной молекулы пыли или пылинки, у которой нет достаточной причины, чтобы занять то место, где она находится, и которое не действует строго так, как должно действовать. Геометр, точно знавший различные силы, действующие в этих случаях, и свойства движущихся молекул, показал бы, что, согласно данным причинам, каждая молекула действует именно так, как должна действовать, и не может действовать иначе, чем она действует.».
Гольбах связывает причинности разной природы, в частности механическую модель, основанную на всеобщей связи движения, и химическую модель, основанную на сродствах и включающую в себя человеческие страсти и желания. Он утверждает основной принцип всеобщей необходимой причинности: каждое следствие имеет естественную причину. Таким образом, он настаивает на «простых и общих законах», потому что они предлагают постоянный, обнадеживающий и достаточный критерий против сверхъестественного. Особенно сильно данное мнение у дуалистов, утверждающих, что помимо материи существуют элементы метафизики, в том числе божественное начало. Очевидно, что случайность онтологическая абсолютно несовместима с принятием чего-то всемогущего и всезнающего.
Изучение философии, надеюсь, не пройдёт мимо вас − в большинстве высших учебных заведений она включена в программу, а в аспирантуре по любой специальности она вообще является основным предметом. Но добавлять в наш курс помимо математики, экономики и психологии ещё и философию было бы жестоко с моей стороны.
Что такое вероятность?
Никто не умеет предсказывать, упадёт монета, если её бросить, орлом, решкой или вообще ребром. Поэтому подбрасывание монеты так часто и используют для определения своего действия в спорной ситуации − например, идти ли на первый урок или остаться в постели.
Первое использование этой игры в такой форме датируется созданием металлических денег. Однако до этого существовали другие формы подобных «запросов к мирозданию», в которых использовались предметы с двумя выделенными сторонами, например, раковина. Тогда выбор был оставлен на волю случая. Даже сегодня, мы загадываем «орёл или решка, когда мы хотим оставить решение на волю случая, в зависимости от того, какая сторона монеты выпадет после подбрасывания.
В каких ситуациях мы бросаем монету? Когда хотим, чтобы за нас решила «судьба», то есть, чтобы одинаково вероятно нам попался любой из двух исходов (падение на ребро обычно исходом не считают и просто перебрасывают монетку). В таких случаях вероятность выпадения орла оценивают как один к двум, ещё зачастую говорят о процентном соотношении орлов и решек «50 на 50».
Сколько примерно орлов выпадет, если мы подбросим монетку 1000 раз? Вероятность выпадения одного орла необходимо умножить на количество действий, так как, можно сказать, что в каждом броске в среднем у нас выпадает «пол-орла». Тогда получим, что в среднем выпадет 1000/2=500 орлов.
Так что такое вероятность? Обычно в рамках школьной программы дают следующее определение:
Вероятностью называют отношение числа благоприятных исходов к общему количеству равновероятных исходов.
Что такое благоприятный исход? Например, выпадение орла при подбрасывании монетки. Общее количество исходов − это всё множество исходов − в данном случае «орёл и решка», то есть их два.
Зачем же в определении вероятности есть слово «равновероятных»? Может, стоит просто делить устраивающие нас исходы на их общее количество?
Данное определение можно проиллюстрировать следующим анекдотом:
Спрашивают блондинку: Какова вероятность того, что, выйдя на улицу, вы встретите динозавра.
Б: 50 процентов.
Б: Ну, или я его встречу, или нет..
Тут каноническая блондинка как раз и поделила один благоприятный исход «встречи с динозавром» на возможные два исхода.
Ну вы уже поняли, что оно так не работает. Мало того, если монетку подпилить, то она перестанет быть идеально симметричной и вероятности выпадения орла и решки теперь могут перестать быть равными. Так, например, поступают мошенники.
Игры с природой
Одна из главных причин популярности, да и вообще возникновения и развития теории вероятностей — это желание получить много денег сразу и без труда. Например, выиграть их в лотерею или в рулетку. Попытка найти закономерности и «обмануть систему» − это мощный стимул к развитию соответствующего математического аппарата.
Кажется, что если мы знаем законы вероятности и правила, управляющие случайностью, то можем выиграть в любой игре, то есть найдём некую выигрышную стратегию (называемую специальным термином «мартингейл»). На самом деле это несбыточная мечта, и мы собираемся это доказать.
Главное, что мы должны понимать — игра является случайной, если игрок не может иметь вообще никакого влияния на исход игры. Например, шахматы неслучайны, преферанс не совсем случаен, а вот подбрасывание монеты, рулетка и даже русская рулетка — игры случайные. Будем называть те игры, в которых важную роль играет случай, пусть и подчинённый неким математическим зависимостям, «играми с природой». Можно играть только с природой, подбрасывая монетку. Можно сыграть с кем-то и природой − например, в «дурака». Тогда, с одной стороны, карты вам раздала природа (или шулер, но мы верим в доброту и честность людей, и вообще, колода у нас своя), но действия второго игрока уже неслучайны.
Есть ряд игр, в которых игроку суждено только приобрести билет и после этого никакого участия он не принимает. Так обстоит дело, например, с простой лотереей. Игра в рулетку − пример другого класса игр, в которых игроку дают возможность выбрать ставку и тип игры. С математической точки зрения игра в рулетку не является справедливой, так как при любом типе игры в выигрыше всегда оказывается казино. А как мы определяем, справедливая ли игра? Для этого потребуется понятие математического ожидания, впервые введённого в 1670 году голландским математиком Яном де Виттом. Он опубликовал первый современный трактат об оценке пожизненной ренты с помощью математического ожидания (приведенной стоимости будущих платежей).
Математическое ожидание
Что же такое, это математическое ожидание? Представим, что мы играем в какую-либо игру. Пока нам не важно, игра это с природой или с другим соперником. Пусть это будет игра в кости с игральным кубиком. За право сделать бросок мы платим 10 рублей. Если в сумме брошенных двух костей выпадет 7 очков, то нам дают 50 рублей, если выпадет другая сумма − ничего не дают. Выгодна ли эта игра? Стоит ли принимать в ней участие?
В этой игре нужно посчитать вероятность выпадения ровно 7 очков в сумме на двух костях. Всего существует ровно 36 равновероятных событий (мы полагаем, что в этой игре организаторы не являются такими явными шулерами, что предлагают плохие кубики). Какие же это исходы ? 1 + 1, 1 + 2, 1 + 3, итд. Из них ровно 6 событий (1+6, 2+5, 3+4, 4+3, 5+2, 6+1) благоприятны. То есть, вероятность выигрыша равна 6/36 = 1/6 . Вероятность проигрыша, соответственно, равна 1 − 1/6 = 5/6.
Исход броска − случайная величина.
Случайная величина может принимать в результате эксперимента неизвестные заранее значения из заданного множества.
В нашем случае множество возможных значений броска каждой из костей нам известно — это числа от 1 до 6. Нам неизвестно, какое же число выпадет после очередного броска, это − онтологическая случайность (если организаторы игры − шулеры, то для нас это было бы эпистемологической случайностью). Нас интересует средний выигрыш для одной игры.
Введём определение среднего выигрыша на более формальном языке:
Математическое ожидание случайной величины есть сумма произведения вероятностей появления всех возможных значений на величину этих значений.
В нашем случае при успехе мы выигрываем 50 рублей, сумма выигрыша равна 40 рублям, (не забываем, что мы уже 10 рублей отдали!), а при неуспехе − проигрываем 0 рублей, сумма выигрыша равна минус десяти рублям. Итого: E=1/6∙40+5/6∙-10=-10/6.
Математическое ожидание выигрыша в данной игре отрицательное, то есть, игра для нас невыгодна. Чем больше партий мы в неё сыграем, тем большим будет математическое ожидание выигрыша (по модулю), а, значит, тем больше мы проиграем.
Христиан Гюйгенс, со своей стороны, в «Du calcul dans les jeux de hasard» 1657 года интересовался суммой ставок, чтобы игра была честной. Он установил, что если в игре у нас есть вероятность p выиграть сумму a, и вероятность q выиграть сумму b, мы должны поставить сумму S = (ap+bq)/(p+q), чтобы игра была честной. Другими словами,
Если математическое ожидание выигрыша за одну игру равно нулю, игра считается справедливой.
Понятие математического ожидания − достаточно базовая вещь, которая используется далеко не только в теории игр, но об этом попозже.