Кіріспе

Стратегия ойыны – математикалық стратегия ойыны.

Nim – екі ойыншының бөлек-бөлек қалыптардан немесе үйірлерден заттарды кезекпен алып тастау (немесе "нимдеу") ойыны. Әр ойыншы өз кезегінде кем дегенде бір затты алып тастауы керек, ал барлық заттар бір қалыптан немесе үйірден алынған жағдайда, кез келген сандағы затты алып тастауға болады. Ойынның мақсаты – соңғы затты алудан қашу немесе соңғы затты алу болып табылады. Nim – Спраг-Гранди теоремасының негізі, ол кез келген бейтарап ойынды бір қалыпты Nim ойынымен теңестіреді.

Тарих

Нимнің түрлі нұсқалары ежелгі заманнан бері ойналып келеді. Ойынның Қытайда пайда болғаны айтылады – ол қытай ойыны 捡石子 jiǎn shízi, яғни "тас теруге" өте ұқсас, бірақ шығу тегі нақты белгісіз. Ним туралы ең алғашқы еуропалық деректер 16 ғасырдың басына жатады. Оның қазіргі атауын Гарвард университетінің профессоры Чарльз Л. Бутон тапқан, ол 1901 жылы ойынның толық теориясын да жасады, бірақ атаудың шығу тегі толыққанды түсіндірілген жоқ. Оксфорд ағылшын сөздігі атауды неміс тіліндегі "nimm" етістігінен шығарған, ол "алу" деген мағынаны білдіреді. 1939 жылы Нью-Йоркте өткен Дүниежүзілік көрмеде Westinghouse компаниясы "Ним" ойынын ойнайтын Nimatron атты машинаны көрсетті. 1940 жылдың 11 мамырынан 27 қазанына дейін алты айдың ішінде машинаны жеңгендердің саны аз болды; жеңіске жеткендерге "Nim Champ" деп жазылған монета табысталды. Бұл – алғашқы электрондық компьютерлік ойындардың бірі. Ferranti компаниясы 1951 жылы Ұлыбритания фестивалінде көрсетілген "ним" ойнайтын компьютер құрастырды. 1952 жылы W. L. Maxon Corporation компаниясының инженерлері Герберт Коппель, Юджин Грант және Говард Бейлер адамға қарсы ойнап, көбінесе жеңіске жететін машина жасады. Ойыншықтардан құралған "ним" ойын автоматының сипаттамасы да бар. Ним ойыны 1958 жылғы ақпан айында Мартин Гарднердің Scientific American журналындағы "Математикалық ойындар" рубрикасында жарияланды. "Мариенбадтағы өткен жыл" (1961) француз жаңа толқынының фильмінде де нимнің бір түрі ойнатылады және символдық маңызға ие.

Ойын және суреттеу

Nim әдетте misère ойыны ретінде ойналады, онда соңғы затты алған ойыншы жеңіледі. Nim сондай-ақ "қалыпты ойын" ретінде ойналуы мүмкін, онда соңғы затты алған ойыншы жеңіп алады. Қалыпты ойын немесе misère ойыны кезінде, ең болмағанда екі зат бар бір үйінді болғанда, келесі жүріс жасаушы ойыншы оңай жеңе алады. Егер ол екі немесе одан көп зат бар үйіндіден барлық немесе бір затты қалдырса, онда ешқандай үйіндіде бір заттан көп болмайды, сондықтан ойыншылар ойын аяқталғанға дейін кезекпен бір-бірден зат алып отыруға мәжбүр болады. Егер ойыншы нөлдік емес үйінділердің жұп санын қалдырса (қалыпты ойындағыдай), ол соңғы жүріс жасап жеңеді; егер ойыншы үйінділердің тақ санын қалдырса (misère ойынындағыдай), онда екінші ойыншы соңғы жүріс жасап жеңеді. Қалыпты ойын екі ойыншы арасында өтеді және кез келген сандағы үш үйіндімен ойналады. Екі ойыншы кезекпен кез келген үйіндіден кез келген сандағы заттарды алады. Мақсат – соңғы затты алу. Misère ойынында мақсат – қарсыласты соңғы қалған затты алуға мәжбүр ету. Келесі мысал қалыпты ойынды көрсетеді, онда ойдан шығарылған Боб пен Элис ойыншылары үш, төрт және бес заттан бастайды. Heap AHeap BHeap CMove 3 4 5 Ойын басталады 1 4 5 Боб А-дан 2 алады 1 4 2 Элис С-дан 3 алады 1 3 2 Боб B-дан 1 алады 1 2 2 Элис B-дан 1 алады 0 2 2 Боб А үйіндісін толығымен алады, екі 2 қалдырады 0 1 2 Элис B-дан 1 алады 0 1 1 Боб С-дан 1 алады, екі 1 қалдырады. (Misère ойынында ол C-ден 2 алып, (0, 1, 0) қалдырар еді). 0 0 1 Элис B-ден 1 алады 0 0 0 Боб C үйіндісін толығымен алады және жеңіп алады.

Жеңімпаздық позициялар

Ним ойынында жеңіске жетудің практикалық стратегиясы – қарсыласты келесі позициялардың біріне жеткізу, содан кейін әрбір кезегінде кішірек позициялардың бірін жасау мүмкіндігін қамтамасыз ету. Тек соңғы қадам ғана мизер және нормалды ойын арасындағы айырмашылықты құрайды. 2 қазандық3 қазандық4 қазандық1 1 *1 1 1 **1 1 1 1 *2 21 2 31 1 n3 31 4 51 2 4 74 41 6 71 2 5 65 51 8 91 3 4 66 6 2 4 61 3 5 77 72 5 72 3 4 58 83 4 72 3 6 79 93 5 62 3 8 9n n4 8 124 5 6 74 9 134 5 8 95 8 13n n m m5 9 12n n n n * Тек нормалды ойын үшін қолданылады. ** Тек мизер ойыны үшін қолданылады. Жалпылау үшін n және m кез келген 0-ден жоғары мән болуы мүмкін, және олар бірдей болуы мүмкін.

100 ойын

Осыған ұқсас нұсқасы "100 ойын": Екі ойыншы 0-ден бастайды және кезекпен 1-ден 10-ға дейінгі санды қосады. 100-ге жеткен ойыншы жеңіп шығады. Жеңіс стратегиясы – сандар тізбегіндегі келесі санға жету (мысалы, 01, 12, 23, 34) және осы тізбектегі барлық сандар арқылы секіріп, ойынды бақылау. Егер ойыншы 89-ға жетсе, қарсыласы тек 90-нан 99-ға дейінгі сандарды таңдай алады, ал келесі мүмкін жауап әрқашан 100 болады.

Көптік үйір ереже

Nim-нің тағы бір түрінде, бір үйіндіден кез келген сандағы заттарды алып тастаудан басқа, әрбір үйіндіден бірдей сандағы заттарды алып тастауға да рұқсат етіледі.

Грандидің ойыны

Гранди ойынында, нимнің тағы бір түрі, бірнеше зат бастапқы қалыпқа орналастырылады және екі ойыншы кезекпен қалыпты екі бос емес, әртүрлі өлшемдегі қалыптарға бөледі. Мысалы, алты затты 5+1 немесе 4+2 қалыптарына бөлуге болады, бірақ 3+3 емес. Гранди ойыны мизерлік немесе стандартты режимде ойналуы мүмкін.

Ашкөз нөмін

Greedy nim – ойыншылардың тек ең үлкен үймеден тастарды таңдауға шектеу қойылған түрі. Бұл шекті бейтарап ойын. Greedy nim misère-дің ережелері greedy nim-нің ережелерімен бірдей, бірақ соңғы қозғалыс жасай алатын ойыншы ұтылады. Ең үлкен үймедегі тастардың саны m, ал екінші ең үлкен үймедегі тастардың саны n болсын. pm – m тасы бар үймелердің саны, pn – n тасы бар үймелердің саны болсын. Онда pm жұп болғандағы ойын позициялары P-позициялар болады деген теорема бар. Егер pm 1-ден үлкен болса, осы үймеден барлық тастарды алып тастау арқылы pm-ді 1-ге кемітуге болады, сонда жаңа pm жұп санға тең болады. Егер pm = 1 (яғни ең үлкен үйінді бірегей болса), екі жағдай қарастырылады: егер pn тақ болса, ең үлкен үйіндінің мөлшері n-ге дейін азаяды (сонда жаңа pm жұп болады). Егер pn жұп болса, ең үлкен үйінді толығымен алынып тасталады, ең үлкен үйінділердің жұп саны қалады. Осылайша, pm жұп болатын күйге өтуге болады. Керісінше, егер pm жұп болса, егер қандай да бір қозғалыс мүмкін болса (pm ≠ 0), онда ол ойынды pm тақ болатын күйге жеткізуі керек. Ойынның соңғы позициясы жұп (pm = 0). Демек, pm жұп болатын ойынның кез келген позициясы P-позиция болуы керек.

Индекс- k nim

Көп үйінді nim-нің жалпылануын 1910 жылы талдаған Э. Х. Мур "nim" немесе "индекс k" nim деп атады. Индекс k nim-де бір ғана үйіндіден нысандарды алып тастаудың орнына ойыншылар кем дегенде бір, бірақ k түрлі үйінділерден нысандарды алып тастай алады. Әр үйіндіден алынып тасталатын элементтердің саны кездейсоқ немесе жоғарыда көрсетілген "азайту ойынында" сияқты ең көп r элементтермен шектелуі мүмкін. Жеңімпаз стратегиясы мынадай: Кәдімгі көп үйінді nim-дегідей, үйінділердің мөлшерінің (немесе үйінділер мөлшерінің r + 1 модулі) екілік түрі қарастырылады. Кәдімгі nim-де әрбір екілік санның XOR қосындысы (немесе 2 модулі бойынша қосындысы) құрастырылады, ал жеңімпаз стратегиясы – әрбір XOR қосындысын нөлге келтіру. Индекс k nim-ге жасалған жалпылауда, әрбір екілік санның қосындысы k + 1 модулі бойынша есептеледі. Тағы да жеңімпаз стратегиясы – осы қосынды әрбір сан үшін нөлге тең болатындай етіп жүргізу. Расында, осылай есептелген мән соңғы позиция үшін нөлге тең, ал осы мән нөлге тең үйінділердің конфигурациясы берілгенде, ең көп дегенде k үйіндіні өзгерту мәнді нөлден өзгеше етеді. Керісінше, нөлдік емес мәнді конфигурация берілген жағдайда, ең көп дегенде k үйіндіден мұқият таңдап алып, мәнді нөлге келтіруге болады.

Құрылыс

Құрылыс Nim — екі ойыншының алдымен Nim ойынын құрастыратын Nim ойынының түрі. Ойыншыларға n тас және s бос үйінді берілген. Олар кезектесіп, өздері таңдаған үйіндіге дәл бір тас қояды. Барлық тастар орналастырылғаннан кейін, келесі кезектегі ойыншыдан бастап Nim ойыны басталады. Бұл ойын BN(n, s) деп белгіленеді.

Жоғары өлшемді нм

n d nim тақтада ойналады, онда кез келген қатардан кез келген сандағы тізбектес тастар алынып тасталуы мүмкін. Бастапқы позиция әдетте толық тақта, бірақ басқа нұсқалар да қабылданды.

График

Басталу тақтасы – байланысқан емес граф, ал ойыншылар қатар орналасқан төбелерін кезекпен жояды.

Конфеталық

Candy nim – ойыншылардың бір уақытта екі мақсатқа қол жеткізуге тырысатын, дәстүрлі nim ойынының бір түрі: соңғы затты (осы жағдайда, конфета) алып қалу және ойын аяқталғанда ең көп конфета жинау.