Так. Следующий небольшой раздел игр, который связан с алгоритмичностью, называется «Детские игры», или «Кто выиграет при правильной игре?» [БЕЗ СЛОВ] Здесь просто будет несколько примеров игр, в которых сложность смещена в сторону именно нахождения того, как нужно действовать, чтобы победить. По теореме Цермело есть какая-то стратегия у кого-то из игроков оптимальная, но мы ее изначально-то не знаем, ее надо как-то угадывать. Иногда совершенно неочевидно она... Иногда она совершенно непонятна. Ну вот скажем в «крестиках-ноликах» в принципе известно, что побеждает 1-й на доске 3 х 3. Что для этого ему надо сделать? Ему надо для этого пойти в центр — это единственный правильный ход. Если он из своих 9 ходов не выберет этот единственный ход в центр, то 2-й его победит. И более того, дальше тоже... Дальше тоже ситуация разворачивается неочевидно. То есть при правильных хитрых реакциях 2-го на ход в центр, 3-й ход 1-го тоже должен быть очень аккуратно продуман, иначе он тоже проиграет. То есть вопрос о том, как найти выигрышную стратегию, он полностью за рамками теории игр на самом деле. Теория игр говорит: «Выигрышная стратегия существует». Да? Где мы есть? Мы на воздушном шаре. Спасибо, это мы знаем. То есть в данном случае теория игр, она как бы не может помочь, я просто именно для этого хочу... Я хочу привести несколько примеров ситуаций, в которых теория игр, ну она говорит, что есть стратегия, но на самом деле ее еще надо находить. То есть в детских играх наша высокая наука почти ничего не дает. Некоторые исключения будут в следующем сюжете. Пока ряд примеров. «Камушки – 1». Будут «Камушки – 1», «Камушки – 2» и «Камушки – 3», а на дом еще «Камушки – 4» в качестве упражнения. «Камушки – 2». «Камушки – 3». Во всех случаях я лишь очень кратко опишу игру. В каких-то случаях я открою секрет победы, в каких-то оставлю его на дом. «Камушки – 1». Есть некоторая гора камней, в которой n штук, n камней. И игроки последовательно ходят, забирая из кучи некоторое количество камней. Количество строго определенное между {1, 2, 3}, то есть строго ограниченное: 1, 2 или 3 камня можно забрать. Тот, кто забрал последний камень — выиграл. [БЕЗ СЛОВ] [БЕЗ СЛОВ] Всего камней 99. Кто победит: кто начинает или 2-й? Это очень простая задача, и я предлагаю каждому ее решить самостоятельно. Замечу, кстати, на ее примере, что полностью... Полностью строить дерево в данном случае необязательно, потому что некоторые позиции дерева, они эквивалентны друг другу. В самом деле важно только знать следующее: важно знать, сколько камней остается, и кто в данный момент ходит. Каким образом мы пришли к этой ситуации, нам на самом деле не важно при ответе на вопрос о том, кто выиграет при правильной игре. Вот. То есть, есть некоторый специальный способ записывать такие игры. Можно назвать их позиционными и записывать на множестве всевозможных позиций, тем самым сильно экономя место. Вместо выписывания деревьев с историей всей игры, можно только выписывать, что происходит в каждой позиции и в какие позиции из нее можно ходить. Вот. Но это отдельная ветвь теории детских игр, которую я только упомяну и всё. Касаться глубоко ее не будем. Вот. Но вот вопрос: как если есть 99 камней, кто выиграет? Ну я не буду открывать секрет. 2-я игра. Опять есть куча камней. Секрет этой игры я открою в конце этого сюжета, а вот секрет этой игры я вообще не открою. N камней. Только на этот раз забирать можно только степени 2: {1, 2, 4, 8, 16, ...} Опять 99 камней. Кто победит? Кто победит, если можно забирать только степени 2? Заметьте, что на первый взгляд кажется, что это какая-то очень сложная задача. Потому что, смотрите, нам нужно на каждую позицию понять там что-то, нужно на нее долго смотреть, изучать, если остался 1 камень, если осталось 2 камня, если осталось 3 камня. Каждый раз нужно анализировать и так вот вверх, вверх идти. Но на самом деле, если вы допишете до 7-го, 8-го, где-то до позиции с 7-ю, 8-ю камнями, вы, скорее всего, закономерность угадаете, после этого уже докажете. А здесь выигрывает 1-й, а именно: он забирает 3 камня, после этого каждый раз идет на ход в ответ на ход 2-го, — он добирает количество камней до кратного 4-м. То есть 1-й ход, правильный победный ход, — сделать количество камней 96. Дальше, как бы ни пошел вот этот игрок, который забирает 1, 2 или 3 камня, всегда можно оставить 92. Если он заберет 1 надо забрать 3, если заберет 2 — забрать 2, если заберет 3 — забрать 1. Ну и понятно, что таким образом вы по 4 будете идти до 0 и выиграете. Здесь это совершенно удивительный и неожиданный ответ, который я предлагаю всем получить самому. «Камушки – 3» — это известнейшая игра. Известнейшая алгоритмистам и программистам. Она, эта игра такая: есть конечное количество камней. Извините... Конечное количество кучек, в каждой из которых некоторое количество камней: n1 — в 1-й куче, n2 — во 2-й и так далее. Игра называется «Ним». Игроки: 2 игрока, ходят по очереди и каждый имеет право забрать любое количество камней, но только из 1 кучки. Вопрос, кто выиграет при правильной игре для данной комбинации n1, ..., nk, и как универсально ответить на этот вопрос? Универсальный ответ существует, он лежит в области чистого программирования. Поэтому я считаю, что это выходит за пределы теории игр. Это уже алгоритмическая теория игр. Она вообще... Ну это наполовину, это наука уже для программистов, если не на 2/3, поэтому я не буду даже в эту сторону залезать. Вот. Ну и можете подумать еще над «Камушками – 4». Это когда есть 2 кучи камней, забирать можно либо какое угодно количество камней отсюда, либо какое угодно отсюда, либо ровно по 1 из каждой кучи, ну и понять, есть ли здесь какой-то алгоритм правильной игры. Сразу предупреждаю: когда мы с друзьями эту игру, там один мой друг придумал, какие-то первые рисования, рисования позиций выигрышных и проигравших, и проигрышных, ничего не дали. То есть мы... Мне ответ неизвестен. Наверное, он в Интернете известен, но я не знаю, насколько это трудная задача в частности, но, тем не менее, даю на подумать. Это вот, значит, 4, 4 такие игры, в которых ничего теория игр не дает. Но она говорит: «Ну да, можно изучить позиции и спрашивать про них, какие выигрышные, какие нет в соответствии с принципом Цермело. Но все-таки угадать общее правило, это уже, ну как бы, это уже математика, программирование, олимпиада и так далее».
