Теория игр. Кубик Рубика

Муниципальное бюджетное общеобразовательное учреждение «Коелгинская средняя общеобразовательная школа имени дважды Героя Советского Союза С.В. Хохрякова» информационно­познавательная проектная работа                           Тема:  «Теория игр. Кубик Рубика ».                                                               Предмет: математика Вид проекта: информационно­познавательный                                                                                                     Выполнил:   ученик 9 б класса Кравченко Иван Сергеевич 1 Наставник: Рыбак Марина Александровна                                                                                                       2018 Содержание: 1.Введение  ……..3             2.Основная часть……..              2.1.Теория игр    2.1.1. Понятие о теории игр    2.1.2.История Теории игр                2.1.3.Представление об играх   2.2.Кубик Рубик.    2.2.1.Биография Эрно Рубика    2.2.2.Понятие о кубике Рубика    2.2.3.История кубика Рубика    2.2.4.Механизм              2.3.Математика кубика Рубика                2.3.1.Алгоритм Бога                2.3.2.Алгоритм Тистлетуэйта                2.3.3.Алгоритм Коцембы             3.Заключение             4.Проведённый опрос             5.Интересные факты             6.Список литературы 2 Введение «Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего.» Джон фон Нейман К сожалению рассматриваемая нами тема не столь популярна среди учеников, да и   вообще   большая   часть   людей   совсем   с   ней   не   знакомы,   так   как   в   школе   это   не затрагиваться. Но на самом деле теория игр очень интересна и вполне применима в нашей повседневной жизни. Многие считают изучая математику, что нужно научиться по большей части считать и всё, интегралы и тригонометрические формулы в жизни не пригодятся, но хотя теория игр и опирается на более сложную математику я считаю что с   ней   должен   познакомится   каждый,   при   чём   изучать   её   нужно   после   цифр   и   до алфавита.   Просто   потому   что   слишком   многие   люди   принимают   важные   решения, основываясь   на   интуиции,   тайных   пророчествах,   расположении   звёзд   и   других подобных. Я сам только недавно познакомился с теорией игр, и теперь хочу рассказать вам о её основах. Возможно, это добавит здравого смысла в вашу жизнь. Тема моего проекта ­ Теория игр. Кубик Рубика Я выбрал эту тему, потому слышал о теории игр ранее, и мне стало интересно узнать о ней поподробнее                                                          3 Теория игр Понятие о теории игр Само значение теории игр расшифровывается так: Теория игр — математический метод изучения оптимальных стратегий в играх. Под  игрой  воспринимается   процесс,   в  котором  участвуют   две  и   более   сторон(лиц), ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости   от   поведения   других   игроков.   Теория   игр   помогает   выбрать   лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных 4 поступках.  Также Теория игр — это раздел прикладной математики, точнее исследования операций.   Чаще   всего   методы   теории   игр   находят   применение   в   международных отношениях,   экономике,   чуть   реже   в   других   общественных   науках   —   социологии, политологии, психологии, этике, юриспруденции и других. Начиная с 1970­х годов её взяли   на   вооружение   биологи   для   исследования   поведения   животных   и   теории эволюции.   Очень   важное   значение   она   имеет   для   искусственного   интеллекта   и кибернетики, особенно с проявлением интереса к интеллектуальным агентам. 5 История Теории игр Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге   1944   года   Джона   фон   Неймана   и   Оскара   Моргенштерна«Теория   игр   и экономическое поведение» Эта область математики нашла некоторое отражение в общественной культ 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона   Форбса   Нэша,   лауреата   премии   по   экономике   памяти   Альфреда   Нобеля   и учёного в  области  теории  игр;  а  в  2001 по  мотивам  книги  был  снят  фильм  «Игры разума». Большой вклад в изучение теории игр внёс Джон Нэш. В   1949 году он пишет диссертацию по теории игр. В своих трудах Нэш разработал принципы «управленческой динамики».   Первые   концепции   теории   игр   анализировали   антагонистические   игры, когда есть проигравшие и выигравшие за их счёт игроки. Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили   названия   «равновесие   по   Нэшу»,   в   ситуации   стороны   используют оптимальную   стратегию,   что   и   приводит   к   созданию   устойчивого   равновесия.     Эти работы   Нэша   сделали   серьёзный   вклад   в   развитие   теории   игр,   показав   что   более выгодны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.  Хотя теория игр первоначально и рассматривала экономические модели, вплоть до 1950­х она оставалась формальной теорией в рамках математики. Но уже с 1950­х гг. начинаются   попытки   применить   методы   теории   игр   не   только   в   экономике,   но   в биологии,   кибернетике,   технике,   антропологии.   Во   время   Второй   мировой   войны   и сразу после неё теорией игр серьёзно заинтересовались военные, которые увидели в ней мощный аппарат для исследования стратегических решений. Большим   вкладом   в   применение   теории   игр   стала   работа   Томаса   Шеллинга, «Стратегия   конфликта».   Шеллинг   рассматривает   различные   «стратегии»   поведения 6 участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии (психологическая дисциплина) и в управлении конфликтами в организации (теория менеджмента). В   настоящие   время   математическая   теория   игр   сейчас   бурно   развивается, рассматривая динамические игры. Однако математический аппарат теории игр затратен. Его   применяют   для   оправданных   задач:   политика,   экономика   монополий   и распределения рыночной власти и т. п.  Представление об играх(краткая форма) Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще  используют  нормальную  или   экстенсивную   форму.  Характеризующие  признаки игры как математической модели ситуации: 1. наличие нескольких участников; 2. неопределённость поведения участников, связанная с наличием у каждого из них нескольких вариантов действий; 3. различие (несовпадение) интересов участников; 4. взаимосвязанность   поведения   участников,   поскольку   результат, получаемый каждым из них, зависит от поведения всех участников; 5. наличие правил поведения, известных всем участникам. 7 Биография Эрно Рубика Прославленный   венгерский   изобретатель,   одаренный   скульптор,   популярный профессор. Эрно получил огромнейшую известность благодаря головоломкам, которые он создавал. В 1974 году им была изобретена вещь, перевернувшая бытие скульптора – «Кубик Рубика». До сих пор данная головоломка пользуется немалой популярностью, 8 как среди детей, так и среди взрослых. К числу разработок Рубика не возбраняется отнести и такую головоломку, как «Змейка Рубика» (1977 год). Недавно поклонникам профессора Рубика был преподнесен новоиспеченный сюрприз. Дело в том, что Эрно создал   очередную   головоломку,   которая   получила   наименование   Rubik’s   360   (или «Шарик   Рубик»).   Многие   прогнозируют,   что   новая   ребус­игра   Рубика   будет пользоваться такой же популярностью, как и ее кубический собрат. Эрно Рубик родился 13 июля 1944 года в Будапеште, в Венгрии, ­ когда Вторая Мировая война была в самом разгаре. Отец изобретателя работал авиаинженером на заводе в городе Эстергоме. Мать Рубика занималась противоположным ремеслом – она была поэтессой. С раннего детства в Эрно обнаружился крупный дар к наукам, а кроме того – страстное   вожделение   обучаться.   Вскоре   Рубику   удалось   заполучить   отличное образование   ­   в   1967   году   венгр   окончил   инженерный   факультет   технического университета.   Затем   изобретатель   решил   сменить   ориентиры   и   стал   обучаться   на скульптора   и   дизайнера.   Достигнув   и   на   данном   поприще   больших   успехов,   Эрно получил профессию архитектора и начал работать в данном направлении. После   многолетнего   труда   в   области   строительства   и   дизайна,   Рубик   решил попробовать собственные силы в издательском деле – он стал редактором одного из журналов,   где   публиковались   всевозможные   занимательные   головоломки,   загадки, ребусы. В 1983 году ученый и изобретатель создал собственную студию, занимающуюся разработкой и изготовлением логических головоломок. В начале 90­х годов, Рубик стал   Вместе   со   своим активно   развивать   школу   национального   образования. единомышленником   Яношем   Гинстлером   Эрно   создал   венгерскую   техническую академию, которая функционирует до сих пор. В   настоящее   время   Эрно   Рубик   (Ernő   Rubik)   участвует   в   разработке всевозможных   видеоигр,   пишет   статьи   по   различным   темам   архитектуры.   В   разное время профессор был награжден такими почетными наградами, как «Кошутовская премия», «Премия имени Дениса Габора» и прочими премиями понятие о кубике рубика 9 Понятие о кубике Рубика уу К бик   Р бика   —   механическая   головоломка,   изобретённая   в   1974   году уу венгерским скульптором Эрнё Рубиком. Головоломка представляет  собой пластмассовый куб3×3×3 (в первоначальном варианте)   с   54   видимыми   цветными   наклейками.   Грани   большого   куба   способны вращаться вокруг 3 внутренних осей куба. Каждая из шести граней состоит из девяти квадратов и окрашена в один из шести цветов, в одном из распространённых вариантов окраски, расположенных парами друг напротив друга: красный — оранжевый, белый — жёлтый,   синий   —   зелёный.   Повороты   граней   позволяют   переупорядочить   цветные квадраты множеством различных способов. Задача игрока заключается в том, чтобы «собрать   кубик   Рубика»:   поворачивая   грани   куба,   вернуть   его   в   первоначальное состояние, когда каждая из граней состоит из квадратов одного цвета. Считается, что кубик Рубика — лидер среди игрушек по общему количеству продаж:   по   всему   миру   было   продано   порядка   450   млн   кубиков   Рубика,   как оригинальных, так и различных аналогов 10 История создания. История кубика Рубика началась в марте 1970 года, когда Ларри Николс изобрел головоломку 2×2×2 с вращающимися частями, собранными на магнитах.  Изобретатель сразу подал заявку на оформление канадского патента и уже 11 апреля   1972   года   Николс   получил   американский   патент,   (под   номером   3655201) позднее, в 1986 году апелляционный суд подтвердил, что карманный кубик Рубика, по причине сходства изобретений, нарушает авторские права Николса.  В середине 1970­х Эрнё Рубик работал (в отделе Дизайна интерьера) в академии Прикладного искусства в Будапеште. Занимаясь группами, Рубик однажды сделал 27 деревянных   кубиков,   раскрасил   каждый   в   шесть   цветов.   Неожиданно   оказалось довольно трудно сложить из них один куб, чтобы каждая грань была окрашена в свой цвет.   Сам   Рубик   бился   над   задачей   целый   месяц   (хотя     первый   кубик   Рубика   был построен как обучающий инструмент, чтобы помочь его студентам понять трехмерные объекты). Но самым сложным оказалось придумать механизм. 30 января 1975 года Э. 11 Рубик получил венгерский патент(HU170062) на своё изобретение, «Магический кубик» . Игрушкой   совершенно   случайно   заинтересовался   немецкий   компьютерный предприниматель Тибор Лаци, зайдя во время деловой поездки  выпить кофе, он увидел вещицу   в   руках   у   официанта   кафе.   Увлекающийся   математикой   Тибор   пришёл   в восхищение от кубика и буквально на следующий день прибыл уже в государственную торговую   фирму   Konsumex   и   предложил   продавать   кубик   на   Западе.   Тогда   же   он познакомился и с Рубиком. Заинтересованный Тибор Лаци вышел на владельца Seven Towns   Ltd.,   англичанина   Тома   Кремера.   После   чего   Кремер   взялся   добиться привлечения интереса к разноцветному чуду. В сентябре 1979 года, на переговорах в Будапеште, был заключён договор с крупной американской компанией Ideal Toy Corporation на поставку в США одного миллиона кубиков. В процессе переговоров всплыла ещё одна проблема — Кубик был запатентован лишь в Венгрии. Американцы же могли торговать товарами, авторские права на которые официально зарегистрированы на территории США. Чтобы хоть как­ то уладить это препятствие, в самом начале 1980­го «Магический куб»  решено было переименовать в кубик Рубика . С февраля 1980 года головоломка начинает набирать огромную популярность во всём   мире.   Никаких   проблем   со   сбытом   головоломки   не   было,   были   проблемы   с производством.   Только   до   конца   1982   г.   было   продано   свыше   100   миллионов официальных кубиков  и в полтора раза больше подделок. Сегодня права на кубик Рубика и другие головоломки Эрнё Рубика принадлежат английской компании Seven Towns Ltd., которой уже 40 лет владеет близкий друг Эрнё Рубика   —   Том   Кремер.   Под   контролем   англичан   кубик   Рубика   производится   и продаётся во всем мире. Механизм Из центральных и рёберных элементов с внутренней стороны вырезан фрагмент таким образом, что получается полость в виде объединения трёх цилиндров . Помимо 12 этого, на рёберных и угловых элементах имеются выступы особой формы. Эти выступы образуют   фрагмент   цилиндра,   плотно   входящий   в   полость.   Благодаря   такой конструкции грани кубика свободно вращаются. В   центре   конструкции   вместо   «невидимого   кубика»   находится   трёхмерная крестовина,   на   которой   свободно   вращаются   центральные   элементы.   Все   остальные элементы держатся друг за друга, входя выступами в вышеуказанную выемку. Объединяет понятия Кубик Рубика и Теория игр следующий термин –   Математика кубика Рубика.   Матем тика к бика Р бика — совокупность математических   методов   для   изучения   свойств   кубика   Рубика   с   абстрактно­ математической точки зрения. Изучает алгоритмы сборки кубика, оценки алгоритмов уу ау уу его   сборки   и   др.   Основана   на   теории   графов,   групп,   вычислимости   и комбинаторике.История поиска алгоритма Бога кубика Рубика началась не позже 1980 года,   когда   открылся   список   рассылки   для   любителей   кубика   Рубика.   С   тех   пор математики,   программисты   и   просто  любители   стремились   найти   алгоритм   Бога   — алгоритм,   который   бы   позволил   на   практике   решать   кубик   Рубика   за   минимальное число ходов. С этой проблемой была связана проблема определения числа Бога — числа   ходов,   всегда   достаточного   для   сборки   головоломки.Существует   множество способов,   предназначенных   для   перевода   кубика   Рубика   из   произвольной   формы   в начальную.   13 Алгоритм Бога  .Один из них это алгоритм Бога ­ понятие, возникшее в ходе обсуждения   способов   решения   кубика   Рубика.   Под   алгоритмом   Бога   головоломки подразумевается любой алгоритм, который позволяет получить решение головоломки, содержащее минимально возможное число ходовИстория поиска алгоритма Бога кубика Рубика началась не позже 1980 года, когда открылся список рассылки для любителей кубика Рубика. С тех пор математики, программисты и просто любители стремились найти алгоритм Бога — алгоритм, который бы позволил на практике решать кубик Рубика   за   минимальное   число   ходов.   С   этой   проблемой   была   связана   проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.В июле   2010  года   программист   из   Пало­Альто   Томас   Рокики,   учитель   математики   из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. А в августе 2014 года Томас Рокики и Морли Дэвидсон доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 26 ходов без использования поворотов на 180°. 14 Алгоритм ТистлетуэйтаДругой способ, алгоритм Тистлетуэйта. В начале 1980­ х   английский   математик   Морвин   Тистлетуэйт   разработал   алгоритм,   позволивший значительно   улучшить   верхнюю   оценку.   Детали   алгоритма   были   опубликованы Дугласом Хофштадтером в 1981 году в журнале Scientific American. Алгоритм был основан на теории групп и включал в себя четыре этапаМарвин Тистлетуэйт специалист по   прикладной   математике   из   Лондона,   использовал   «идеи   математической   теории групп для компьютерных исследований».Тистлетуэйту  принадлежал первый мировой рекорд самого короткого алгоритма приведения куба в порядок всего 52 поворота. 15 Алгоритм   Коцембы.  Алгоритм   Тистлетуэйта   был   в   1992   году   улучшен учителем   математики   из   Дармштадта   Гербертом   Коцембой.   Коцемба   сократил количество этапов алгоритма до двух.Алгоритм Коцембы позволяет быстро находить короткие, субоптимальные решения.Собственно алгоритм Корфа работает следующим образом.   В  первую   очередь   определяются   подзадачи,   достаточно   простые   для   того, чтобы   осуществить   полный   перебор.   Были   использованы   следующие   три подзадачи:Состояние головоломки определяется только восемью угловыми кубиками, положения   и   ориентации   рёбер   игнорируются.Состояние   головоломки   определяется 16 шестью из 12 рёберных кубиков, другие кубики игнорируются.Состояние головоломки определяется другими шестью рёберными кубиками.Хотя этот алгоритм будет всегда находить   оптимальные   решения,   он   не   позволяет   напрямую   определить,   как   много ходов может потребоваться в худшем случае. Заключение Собирать кубик не только интересно, но и полезно. Это развивает гибкость и скорость   мышления,   помогает   быстро   оценивать   обстановку   и   принимать   решение, 17 развивает усидчивость и способность добиваться результата. Лично для меня, во время этого проекта, я узнал много нового и интересного про кубик Рубик, познакомился поближе с темой теории игр.               Результаты проведенного опроса 18 Интересные факты ● Кубик Рубика был признан Игрушкой года в 1980 и 1981 годах. ● Кубик   Рубика   имеет   6   граней,   12   рёбер,   8   углов   и   образован   из   26   мелких деталей. Игрок ориентируется по цвету центрального элемента на каждой грани. ● У кубика Рубика 43 252 003 274 489 856 000 возможных конфигураций. ● Самый большой кубик Рубика размером 3 метра и весом 500 кг находится в городе Ноксвилл, в штате Теннесси США. ● Самый   маленький   кубик   Рубика   шириной   10   мм   был   сделан   российским программистом Евгением Григорьевым. ● Самым   дорогим   кубиком   стал   "Кубик­шедевр"   созданный   Diamond   Cutters International в 1995 году. Кубик был выполнен из 22,5 карат аметиста, 34 карата рубинов, 34 карата изумрудов и 18­каратного золота, и оценивался в 1,5  миллиона долларов. ● Первый чемпионат мира по сборке кубика Рубика состоялся в Будапеште в 1982 году.   В   нем   приняли   участие   представители   19   стран   мира.   Победителем чемпионата   стал  16­летний  студент  из   Лос­Анджелеса   Минх  Тхай,   которому понадобилось на сборку всего 23 секунды.  ● В 15 марта 2014 года кубик Рубика был собран роботом CubeStormer III за 3,253 сек.  ● Если выложить все проданные кубики в один ряд, он протянется от Северного до Южного Полюса.  19 Список литературы 1. https://ru.wikipedia.org/wiki/Математика_кубика_Рубика 2. https://ru.wikipedia.org/wiki/Теория_игрa 3. https://ru.wikipedia.org/wiki/Кубик_Рубика 4.https://it­lenta.ru/sut­teorii­igr/ 5.https://it­lenta.ru/sut­teorii­igr/ 20 Приложения 21 22 23 24