Так.

Следующий небольшой раздел игр,

который связан с алгоритмичностью, называется «Детские игры»,

или «Кто выиграет при правильной

игре?» [БЕЗ

СЛОВ] Здесь

просто будет несколько примеров игр,

в которых сложность смещена в сторону именно нахождения того,

как нужно действовать, чтобы победить.

По теореме Цермело есть какая-то стратегия у кого-то из игроков оптимальная,

но мы ее изначально-то не знаем, ее надо как-то угадывать.

Иногда совершенно неочевидно она...

Иногда она совершенно непонятна.

Ну вот скажем в «крестиках-ноликах» в принципе известно,

что побеждает 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 такие игры, в которых ничего теория игр не дает.

Но она говорит: «Ну да, можно изучить позиции и спрашивать про них,

какие выигрышные, какие нет в соответствии с принципом Цермело.

Но все-таки угадать общее правило, это уже, ну как бы, это уже математика,

программирование, олимпиада и так далее».

Детские игры про камни

Теория игр

Meet the Instructors