Учебный проект по математике «Теория игр»


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

МБОУ СОШ № 92крестики и нолики на языке теории игр Игра — и вдруг математика? Оказывается, математики занимаются изучением закономерностей некоторых игр, а эти исследования, в свою очередь, способствуют возникновению новых математических понятий. Теория игр (более подходящее название - теория конфликта, или теория конфликтных ситуаций) зародилась как теория рационального поведения  двух игроков с противоположными интересами. Но только ли игры можно рассматривать с математической точки зрения? В 30-е годы этот вопрос поставил выдающийся американский математик Джон фон Нейманн. В результате его исследований возник новый, очень важный, раздел математики — «теория игр». Американский учёный пришёл к выводу, что с математической точки зрения можно рассматривать также такие общественные явления первостепенной важности, как соперничество в области производства или торговли, военные действия и другие.Ах, эта математика! Видимо, нигде и никому не обойтись без неё! Везде математика приходит нам на помощь. ТЕОРИЯ ИГР ИГР ТЕОРИЯ, раздел математики, предметом которого является анализ принятия оптимальных решений в условиях конфликта. Возникнув из задач классической теории вероятностей, теория игр превратилась в самостоятельный раздел в 1945–1955. Таким образом, теория игр – один из новейших разделов математики Классификация игр По выигрышу игры можно разделить на игры с нулевой и ненулевой суммой. Игры двух игроков с нулевой суммой называются антагонистическими.По полноте имеющейся информации – на игры с полной и неполной информацией.По характеру получения информации — на игры в нормальной форме (игроки получают всю предназначенную им информацию до начала игры) и динамические игры (информация поступает игрокам в процессе развития игры).По характеру информационного взаимодействия – игры с сообщениями или без оных. Сообщения могут содержать, например, предложения или угрозы.По количеству стратегий — на конечные и бесконечные игры.По количеству розыгрышей игры – на однократно разыгрываемые и повторяющееся игры.  Следует особо подчеркнуть: Теория игр является очень сложной областью знания.Теория игр прививает человеку дисциплину ума.Теория игр всегда имеет дело с особым типом мышления, стратегическим.Человек, знакомый с теорией игр, реже считает других глупее себя, - и потому избегает многих непростительных ошибок. Теория игр не рассчитана на то, чтобы придать решительности, настойчивости в достижении целей, невзирая на неопределенность и риск. Знание основ теории игр не дает нам  явного выигрыша, но  оберегает нас от свершения глупых и ненужных ошибок. крестики и нолики на языке теории игр На языке теории игр крестики и нолики можно назвать конечной (то есть доигрываемой до конца за конечное число ходов) строго детерминированной (то есть не содержащей элемента случайности) игрой двух сторон с полной информацией. Последнее означает, что обоим игрокам известны все сделанные ходы. Если обе стороны играют «рационально», игра должна закончиться вничью. Единственный способ выиграть заключается в том, чтобы заманить неосторожного противника в ловушку, заготовив для следующего своего хода два почти готовых ряда (противник может помешать достроить лишь один ряд). Рациональность игроков Представим себе идеального игрока, который в любой игровой ситуации принимает наилучшее решение. Он обеспечивает себе наибольший выигрыш, по сравнению с любым другим игроком, который от него отличается. Если бы мы могли описать поведение такого игрока, то мы смогли бы ответить на вопрос: как надо играть, и решили бы задачу теории игр Игра в крестики и нолики монетами или фишками. За много веков до нашей эры были известны гораздо более интересные с математической точки зрения варианты крестиков и ноликов, чем тот, в который принято играть в наше время. Во всех этих вариантах для игры нужно взять шесть фишек, по три у каждого игрока (у одного, например, три монеты одного достоинства, а у другого три монеты другого), и доску. Игра «крестики-нолики» имеет древнее происхождение Ее родиной является Китай, дельта реки Хуанхэ. Считается, что именно там она появилась впервые в 20 веке до нашей эры, и таким образом история этой игры насчитывает уже более 4000 лет. Современное название этой игры – «Рэндзю», что в переводе с китайского значит «нить жемчуга».В 270 г до н.э. игра была завезена в Японию, и там получила свое второе рождение. В 1906 году была создана Токийская Ассоциация Рэндзю. С этих пор игра стала «спортивной» игрой. Постепенно игра вышла и на международный уровень  Правила игры крестики-нолики Основные термины и определения РЯД - Набор камней одного цвета, расположенных на одной горизонтальной, вертикальной или диагональной линии.Непрерывный ряд - Набор камней одного цвета, расположенных на одной горизонтальной, вертикальной или диагональной линии в котором между любыми двумя камнями нет пустых пересечений. Процесс игрыДва игрока (Черные и Белые), поочередно, размещают камни своего цвета, по одному за ход, на пересечениях пустой игровой доски, которая состоит из 15 горизонтальных и 15 вертикальных линий. Первый ход всегда делают Черные в центр доски. Играют два соперника: один чёрными фишками (камнями), его соперник — белыми. Игра проходит на расчерченной в клетку доске размером 15 на 15 линий.Игроки делают ходы по очереди. Первыми ходят чёрные. Каждым ходом игрок выставляет на доску, в точку пересечения линий, один камень своего цвета. Побеждает тот, кто сможет первым построить непрерывный ряд из пяти камней своего цвета — по горизонтали, по вертикали или в диагональном направлении. 60-е годы – игра «тико» Известно много разновидностей крестиков и ноликов, в которых игра ведется на доске размером 4 клетки на 4. У каждого игрока имеется по четыре фишки, и их нужно попытаться выстроить в один ряд. В шестидесятые годы появилась игра «тико» — разновидность крестиков и ноликов, для которой нужна доска размером пять клеток на пять. Каждый из игроков по очереди выставляет свои четыре фишки, а затем передвигает их на одну клетку в любом направлении. Выигрывает тот, кто сумеет либо поставить свои четыре фишки в ряд (по горизонтали, вертикали или диагонали), либо выстроит их в виде квадрата на четырех клетках с общей вершиной. Играть в крестики и нолики можно и без фишек, от этого игра не становится менее увлекательной. Рассмотрим, например, игру в крестики и нолики «наоборот» — тоу-так-тик (это название предложил М. Шоделл). Играют в нее, как в обычные крестики и нолики, но тот, кто первым закончит ряд из трех знаков, не выигрывает, а проигрывает. В игре тоу-так-тик у второго игрока имеется бесспорное преимущество. Первый может закончить вничью, лишь заняв первым же ходом центр, а в дальнейшем повторив по симметрии все ходы противника. Тик-Так-Тоу На первый взгляд кажется непонятным, что может так увлекать в этой детской забаве. Правда, даже в самом простом варианте игры число возможных комбинаций чрезвычайно велико (если ограничиться лишь пятью первыми ходами, то и тогда наберется 9x8x7x6x5 = 15120 различных вариантов), но на самом деле существенно различных вариантов немного, и любой мальчишка за час может стать непобедимым чемпионом. В то же время игра в крестики и нолики имеет и более сложные разновидности, и более глубокую стратегию. Первый игрок (ему принадлежат крестики) может сделать любой их трех ходов. Во избежание проигрыша второй игрок (ему принадлежат нолики) должен в каждом случае занять лишь одну из указанных клеток. Дерево игровых ситуаций Дерево игровых ситуаций для игры крестики-нолики, где игрок за «крестики» ходит первым и поступает по приведенному выше алгоритму, а игрок за «нолики» может поступать как угодно (причем приведено по одной вершине для рационального и для нерационального поступка, то есть любого другого), состоит из 50-ти узлов.  Фрагмент дерева игры «крестики-нолики» В начальной позиции фрагмента игроки сделали по 3 хода. Очередь хода за «крестиками». Позиции дерева расположены уровнями. Очередь хода на каждом уровне отмечена в левой стороне рисунка. Рисунок 1 Фрагмент дерева игры «крестики-нолики» Алгоритм Цермело-Куна. В позиционных играх главным вопросом является выбор хода. Какой ход является наилучшим в текущей позиции? Для игр с конечным деревом игры ответ на этот вопрос дает алгоритм Цермело-Куна. Для таких игр нет особого смысла выписывать вектор выигрышей для каждой терминальной позиции. Достаточно указать лишь выигрыш одного какого-нибудь игрока, например первого. Выигрыш второго игрока всегда равен выигрышу первого, взятому с обратным знаком. Назовем оценкой позиции выигрыш, гарантированный в ней первому игроку, то есть для терминальных позиций . В частности для позиций нижнего уровня на рис 1 оценки этих позиций равны (слева направо): 0, 1, 0, 1. Рисунок 2 Алгоритм Цермело-Куна. Жирным выделены лучшие ходы Что такое выигрышная стратегия?  Позиции, в которых выигрывает тот, кто ходит первым, назовём выигрышными, а в которых выигрывает второй — проигрышными. Игрок ''выигрывает'' в данной позиции значит, что он имеет возможность ходить так, и так отвечать на ходы противника, чтобы выиграть у него, независимо от того, как противник будет ходить. Эта возможность + описание того, как нужно отвечать на ходы соперника, называется выигрышной стратегией. Другими словами, если игрок умный и ходит первым из выигрышной позиции, то он выиграет. Но как бы ни был умён игрок, он может проиграть, если будет ходить первым из проигрышной позиции. ЗадачаТема:   Теория игр Классы: 7,8,9Докажите, что в игре в "крестики-нолики" на поле 3*3 при правильной игре первого игрока второй игрок выиграть не сможет. РешениеПусть первый игрок первым ходом ставит крестик в центр поля. У второго игрока есть две различные возможности: поставить нолик в угол или в середину боковой стороны. Как несложно проверить перебором, в каждом из этих случаев первый игрок может не допустить победы второго.  Родственные игры5 в ряд. Играют на бесконечном поле (либо на листе бумаги в клетку). Фолов нет. Построение длинного ряда (более 5) приносит победу.Гомоку. Игра «5 в ряд» на доске 19х19 или 15х15 линий. Фолов нет. Построение длинного ряда не приносит победы ни одной из сторон.5 в ряд с центральным запретным квадратом (ЦЗК). Другое название — «свободное рэндзю». На Западе именно эту разновидность игры называют «5 в ряд». Игра по правилам гомоку (фолов нет, длинный ряд не приносит победы) на доске 15х15 линий. Дополнительное правило: второй ход чёрных (то есть третий ход в партии) должен быть сделан за пределами центрального квадрата 5х5.Пента. 5 в ряд на доске 19х19. Ряд из двух камней, закрытый с двух сторон камнями противника, становится «добычей» и снимается с доски. Второй ход чёрных делается за пределы центрального квадрата 5х5. Выигрывает тот, кто первым построил ряд из 5 или более камней, либо первым захватил 5 добыч. Пента — упрощённый вариант японской игры нинуки-рэндзю, распространённой в Японии в первой половине XX века.Connect6 Интересная попытка уйти от искусственных ограничений рэндзю, уравняв возможности чёрных и белых за счёт порядка ходов. Игра идёт на доске 19Ч19, победа достигается построением ряда из шести камней или более. На первом ходе чёрные выставляют один камень, далее на каждом ходе игрок выставляет не один, а два камня за ход. Вывод: Анализ даже весьма простых игр показывает, что идеальный игрок не более чем утопия. Тем не менее, вопрос «как играть» остается. Рациональный игрок должен на основе всех своих знаний об игре и всей имеющейся информации о ее ходе выжать из игры максимум возможного и принять решение, которое в каком то смысле будет оптимальным. ПРИЛОЖЕНИЕ:"Крестики-нолики 3D" - победитель конкурсной программы специализированной выставки "Игрушка 2007" в номинации "Знания и обучение". "Крестики-нолики 3D" развивает пространственное мышление, учит планировать свои действия и ориентироваться в трехмерном пространстве. Итак, как это выглядит?Вообще-то, игру можно было назвать "Шарики-шарики". Никаких крестиков и ноликов здесь нет. Вместо них - красные и синие шарики 1, 5 см. Но поскольку использован принцип известной нетленной головоломки, название игры полностью себя оправдывает.Роль «крестиков» и «ноликов» исполняют разноцветные шарики. Задача игроков – закрыть как можно больше линий шариками «своего» цвета.Линиями в Настольной игре Крестики-нолики 3D считаются:- Горизонтали на верхнем, среднем и нижнем ярусе.- Вертикали по всему объему куба.- Диагонали, которые идут от верхних вершин куба через его центр к нижним вершинам.- Диагонали каждого яруса.- Диагонали каждой грани.- Линии, соединяющие середины противоположных ребер. СПАСИБО ЗА ВНИМАНИЕ!

Приложенные файлы


Добавить комментарий