Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Детские игры про камни
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория игр
42 classificações
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
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.
© 2019 Coursera Inc. Todos os direitos reservados.
