Стратегически игри и решаване на проблеми
(Това ще бъде за историята на Nim и подобни игри, така че ако сте твърде мързеливи, превъртете надолу до „Относно определянето на стратегията“ (Това е под втората снимка))
Нека се спрем на така наречените стратегически игри. Те могат да бъдат разделени на два вида. Тези, които са описани с прости правила, продължават кратко време и количеството информация в което е ограничено или относително малко, ще наричаме малки стратегически игри.
В други, като шах или го, пълен контрол не е възможен поради продължителността на играта, сложността на правилата и особено големия брой възможни ходове във всяка позиция. Използвайки примера на малки стратегически игри, ще видим как математиката се използва в анализа на играта, за да се определи предимството на един от играчите и да се намери печеливша стратегия.
Връзката между математиката и игрите може да се отнася до различни аспекти на игрите. Когато се прилага към стратегически игри, математиката е особено полезна за определяне на печеливша стратегия. Стратегическата игра е много подобна на процеса на решаване на математически проблем: не става дума за спечелване на една игра чрез правене на по-добри ходове, а за намиране на начин винаги да печелите. Поради тази причина при определяне на печелившите стратегии се използват евристични методи: обратен метод; предположението, че играта е "решена"; прилагане на симетрия; правене на аналогия с друга, вече решена игра и други. Те са подобни на тези, използвани при решаването на математически задачи. Следователно, когато за дадена игра е известна печеливша стратегия, играта се превръща от забавление в решен проблем. Ясно е, че това важи само за определени игри, които надхвърлят обикновеното забавление и са описани с математически термини.теории. За такива теории, понякога доста сложни, може да говорим по-късно.
Същността на малка стратегическа игра за двама играчи, известна като Nim, е, че играчите поставят една или повече групи чипове на масата и определят правилата, по които чиповете трябва да бъдат премахнати от масата. Целта на играта е да вземете последния чип или, обратно, да принудите противника да вземе последния чип. Произходът на тази игра е неизвестен. Някои смятат, че тя идва от Изтока. Произходът на името също е неясен. Сред възможните версии е староанглийската дума "nim", означаваща "да взема", "крада". Някой много остроумен забеляза, че ако приложите централна симетрия към думатаNIM, ще получите думатаWIN- "спечеля" в превод от английски. Както и да е, играта Nim е на повече от сто години: първият анализ на печеливша стратегия за игри
Тази игра придоби популярност в Европа през70-тегодини на XX век благодарение на филма „Миналата година в Мариенбад“ (1961), режисиран от френския режисьор Ален Рене. Героите на филма играят няколко пъти един от вариантите на тази игра. Следователно филмовата версия на играта (която ще бъде обсъдена в бъдещи публикации под заглавието „Игра5“) понякога се нарича Мариенбад, на името на малкото спа градче в Чехия, където се развива действието на филма.
Определянето на цялостната печеливша стратегия, приложима за всяка игра от този тип, е едно от най-ясните прояви на това как математиката се използва за анализиране на игри и по-специално колко ефективно е представянето на числата в двоична система.
Относно дефинирането на стратегия
Първо анализираме игри с една група чипове, в които при всеки ход можете да вземете понеедини максимумnчипа от масата. Тогава ще разгледаме два специални случаядаваме обобщение. Най-простата версия на такава игра е следната.
Игра 1: Първият печели
20чипа от един и същи цвят са разположени на масата. На всеки ход един от двамата играчи може да вземееднаилидвефигури. Който вземе последния чип печели. Кой играч има предимство - този, който отива първи, или вторият участник? Как трябва да играете, за да печелите винаги? Какво се случва, ако броят на чиповете се промени? Какво ще се промени, ако променим правилата на играта и този, който вземе последния чип, ще загуби? Това е доста проста игра, така че може да се анализира в нейната цялост, да се определи печеливша стратегия и да се обобщи за произволен брой чипове. Ако не сте запознати с тази игра, преди да прочетете, опитайте да я играете сами и се опитайте да отговорите на въпросите по-горе.
След като изиграете няколко игри, бързо ще разберете, че ако някой от играчите е оставил3чипа на масата, тогава следващият ход той определено ще спечели. Правилно отбелязано, но това няма да ни помогне винаги да печелим: не знаем какви ходове трябва да направим, за да ни останат3чипа на масата. Но сега знаем, че победител е този, който е взел номер на чипа17. По този начин броят на чиповете в играта намалява. Като предприемем друга подобна стъпка, ще видим, че играчът, който е оставил6чипа на масата, също винаги ще печели. По принцип този, който остави броя на чиповете на масата, кратен на3, винаги печели. Това ни позволява да формулираме печеливша стратегия: когато има20чипа в първоначалната позиция на масата, първият играч винаги ще печели, ако вземе2чипа на първия ход и след това винаги оставя брой чипове на масата, който е кратен на3(ако вторият играч премахнеедин
фигура, първият играч трябва да вземедвеи обратно).В тази игра първият играч има предимство, защото за него има печеливша стратегия.
Промяната на първоначалния брой чипове може частично да повлияе на тази стратегия и дори кой играч ще има предимство. Сега знаем, че печелившата стратегия е да оставите брой чипове на масата, който е кратен на3. За да разберете коя страна има предимство, е достатъчно да разделите първоначалния брой чипове на3и да видите какъв е остатъкът от делението. Ако остатъкът е2(както в оригиналния случай), тогава първият играч винаги печели, ако вземе2чипа на първия ход и след това остави брой чипове на масата, който е кратен на3(ако опонентът вземеединчип, първият играч вземадваи обратно). Ако остатъкът от разделението е1(например броят на чиповете е19,25,100или2017), тогава първият играч също печели. За целта е достатъчно да вземетеединчип на първия ход. И накрая, ако остатъкът е0(броят на чиповете се дели на3), тогава вторият играч печели: той трябва да вземедвачипа, ако първият играч е взеледин, и обратно. В този случай първият играч никога няма да може да остави брой чипове на масата, който е кратен на3.
По този начин сме обобщили играта за произволен първоначален брой чипове. игра
може да се обобщи допълнително чрез промяна на броя чипове, които могат да бъдат взети за всеки
Игра 2: вторият печели
Първият играч пише число от1до10на хартия. Вторият играч измисля число от1до10и записва резултата от добавянето на това число към първия. На всеки ход играчът добавя към общата сума ново измислено от него число от1до10. Играчът, който запише трицифрено число (100или повече), губи. кактрябва ли да играеш, за да спечелиш? Кой играч има предимство: този, който се движи първи или втори? Какво се случва, ако целта на играта или правилата се променят?
Както беше предложено по-рано, ще бъде удобно сами да изиграете няколко игри, за да се опитате да определите печеливша стратегия за един от играчите и да разберете как тази игра е свързана с предишната. Ще анализираме играта по следния начин: ако този, който напише100загуби, този, който напише99печели. Какво число трябва да се напише преди това, за да се гарантира получаването на99на следващия ход? Това е88, тъй като в този случай противникът ще напише произволно число между89и98, след което първият играч лесно ще получи99. Както в предишната игра, продължавайки подобно разсъждение (отивайки до числото88, след това77,66, .11), ще видим, че този път трябва да формираме групи от11. Сега знаем печелившата стратегия: този, който първи напише11и следващите кратни на11, ще бъде първият, който ще получи99и ще спечели. Ако опонентът добавиn, трябва да добавите11 - n. Тъй като на първия ход първият играч не може да получи11, но вторият може, това означава, че има печеливша стратегия за втория играч. Както в предишната игра, когато крайното число се промени, първият играч ще спечели, ако това число не е кратно на11. Ако това число се дели на11, вторият играч винаги ще печели.
Игра 3: общ случай
Да приемем, че на масата имаmчипа и всеки ход можете да вземете от1доmчипа (n < m). Печели този, който вземе последния чип. За кой от играчите има печеливша стратегия - за първия или за втория? Какво е? Ако играчът, който е взелпоследният чип, ще загуби, как ще се промени стратегията?
Не става въпрос за една игра, а за група от абстрактни игри. Предишните две игри са специални случаи. Следователно печелившата стратегия за тази игра е общата стратегия, която се прилага към безкраен брой подобни игри. Тази стратегия е формулирана по следния начин. Разделетеmнаn + 1и намерете остатъка от делението. Той ще бъде в диапазона от0доn. Възможни са два случая:
1.Остатъкът от делението е0. В този случай има печеливша стратегия за втория играч, който трябва да остави брой чипове на масата, кратен наn + 1. За да направите това, на всеки ход, ако първият играч вземеρчипа (0ρ< n + 1), вторият играч трябва да вземе
n + 1 - ρжетони. Това число винаги е положително, тъй като се намира между0иn.
2.Остатъкът от делението еr(0 ) В този случай има печеливша стратегия за първия играч. При първия ход той трябва да вземеrчипа, оставяйки брой чипове на масата, който е кратен наn+ 1. Сега той може да действа като втория играч от първия случай. С други думи, ако вторият играч вземеρчипа (0ρ< n + 1), първият играч трябва да вземеn+ 1 - ρ.
Това общо решение се прилага за безкраен брой игри. Можете да го използвате за такава игра: на масата има 2010 чипа, можете да вземете от 1 до 49 чипа на всеки ход. За кой играч има печеливша стратегия? Какво е? Ако променим правилата и този, който вземе последния чип, ще загуби, тогава е достатъчно да отбележим следното: за да спечелите, ще бъде достатъчно да вземете предпоследния чип, оставяйки само един на масата. В такъв случайстратегията няма да се промени, просто трябва да вземете предвид, че броят на чиповете е равен на
. за да спечелите, ще бъде достатъчно да вземете предпоследния чип, оставяйки само един на масата. В този случай стратегията няма да се промени, просто трябва да вземете предвид, че броят на чиповете е
В този случай, ако играчът вземе последния чип и загуби, тогава определението за предимство се променя леко. Стратегията остава същата:разделетеmнаn + 1и определете остатъка от делението.
Но сега имаме нужда от други остатъци от делението. Ако остатъкът е0или от2доn - 1(1 ; n), тогава случай2 е валиден.Съответно, ако остатъкът е1илиn, тогава случай1 е валиден.Всички тези случаи са валидни. описани по-горе, но за тях се добавя една малка подробност: сега трябва да оставите на масата броя чипове, равен наi + 1(iе кратно наn + 1).
Могат да бъдат всички подобни игри, които използват само една група чипове
считани за опростени версии на играта Nim, за които ще пиша в следващия пост.