Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Детские игры про камни
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория игр
33 classificações
Na lição
Динамическая теория игр
Мы переходим к изучению динамической теории игр, то есть игр, в которых игра длится несколько раундов.
Conheça os instrutores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Так.
Следующий небольшой раздел игр,
который связан с алгоритмичностью, называется «Детские игры»,
или «Кто выиграет при правильной
игре?» [БЕЗ
СЛОВ] Здесь
просто будет несколько примеров игр,
в которых сложность смещена в сторону именно нахождения того,
как нужно действовать, чтобы победить.
По теореме Цермело есть какая-то стратегия у кого-то из игроков оптимальная,
но мы ее изначально-то не знаем, ее надо как-то угадывать.
Иногда совершенно неочевидно она...
Иногда она совершенно непонятна.
Ну вот скажем в «крестиках-ноликах» в принципе известно,
что побеждает 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 такие игры, в которых ничего теория игр не дает.
Но она говорит: «Ну да, можно изучить позиции и спрашивать про них,
какие выигрышные, какие нет в соответствии с принципом Цермело.
Но все-таки угадать общее правило, это уже, ну как бы, это уже математика,
программирование, олимпиада и так далее».
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
