Айырмашылығы - Indistinguishability quotient

Жылы комбинаторлық ойындар теориясы, және әсіресе теориясында бейтарап ойындар жылы қателік ойнау, ажыратылмайтындық Бұл коммутативті моноид жалпылайтын және оқшаулайтын Спраг-Грунди теоремасы нақты ойын ережесі үшін.

Misere-бейтарап ойындардың нақты жағдайында мұндай коммутативті моноидтар белгілі болды misere quotients.

Мысалы: Misere Nim нұсқасы

Делік Nim заттар үйінділерімен әдеттегідей ойналады, бірақ ойын басталған кезде әрбір үйіндіде бір немесе екі зат болуға тыйым салынады. Ішінде қалыпты ойын, ойыншылар кезекпен үйіндіден кез-келген нысанды алып тастайды, ал үйіндіден затты соңғы алған ойыншы ойын жеңімпазы деп жарияланады; Misere ойынында бұл ойыншы ойынның ұтушысы болып табылады.

Қалыпты немесе қате ойын конвенциясы күшіне енгеніне қарамастан нәтиже мұндай позиция міндетті түрде екі түрге жатады:

N
Келесі қозғалатын ойыншы үздік ойында жеңіске жетеді; немесе
P
Алдыңғы қозғалатын ойыншы мәжбүрлі жеңіске ие.

Осы 1-және 2-қадалы Nim ойынының дұрыс емес бөлігі үшін коммутативті моноидты презентацияны әдеттегідей қайта қалпына келтіру арқылы жаза аламыз жіңішке -мультипликативті формаға негізделген шешім, содан кейін оны қате ойын үшін аздап өзгерту.

Қалыпты ойын талдауы

The жіңішке мұндай позициялардың қалыпты ойынында пайда болатын * 0, * 1, * 2 және * 3.

НимберНәтижеСол жіңішке позициялар
P1 өлшемді үйінділердің жұп саны
және 2 өлшемді үйінділердің жұп саны
N1 өлшемді тақтардың тақ саны
және 2 өлшемді үйінділердің жұп саны
N1 өлшемді үйінділердің жұп саны
және 2 өлшемді үйінділердің тақ саны
N1 өлшемді тақтардың тақ саны
және 2 өлшемді үйінділердің тақ саны

Осы төрт ним мәндері сәйкес сәйкес келеді Клейн төрт топтық:

Клейн төрт тобы коммутативпен де анықталады топтық презентация

.

Элементтері ним мәндерімен сәйкестендірудегі сияқты қарастыруға болады осы жеңілдетілген Ним ойынын ойнауда пайда болатын; олар дәл осылай үйлеседі.

Әзірге Клейн төрт тобының бұл ресми енгізілімі 1 және 2 қадалы Nim-ді жіңішке және ним-қосымшаны қолдана отырып талдауға жаңа ешнәрсе қоспады. Оның орнына біз тек теорияны мультипликативті формада қайта құрдық.

Ойынсыз талдау

Мультипликативті форманың артықшылығы - ол тек бір және екі өлшемді үйінділермен ойналған Нимнің қате бағасына ұқсас шешімді жазуға мүмкіндік береді.

Коммутативті енгіземіз моноидты презентация

оның алты элементі

Қате мәнНәтижеОсы сыныптағы позициялар
1N1 өлшемді үйінділердің жұп саны және 2 өлшемді үйінділер жоқ
аP1 өлшемдегі тақ үйінділер саны және 2 көлемдегі үйінділер жоқ
бN1 өлшемді үйінділердің жұп саны және 2 өлшемдегі тақ үйінділер саны
абN1 өлшемдегі тақ үйінді саны және 2 өлшемдегі тақ үйінді саны
P1 өлшемді үйінділердің жұп саны және 2 өлшемді үйінділердің жұп саны (нөлден үлкен)
N1-ші үйінділердің тақ саны және 2-ші үйінділердің жұп саны (нөлден үлкен)

Нимердің дұрыс ойынының шешімін Бутон 1902 жылы толығымен сипаттаған.[1] Осы мақаланың соңғы сөйлемінде Бутон мысер Нимде «қауіпсіз комбинациялар бұрынғыға сәйкес келеді, тек әрқайсысында бір-бірден бар қадалардың тақ саны қазір қауіпсіз болып табылады, яғни P-позиция болып табылады», ал олардың жұп саны қауіпсіз емес [яғни N-позиция]. « Жоғарыдағы бұрыс квота тұжырымдамасы тек бір және екі өлшемді үйінділермен ойнаған Ним жағдайында эквивалентті болып көрінеді.

Ресми анықтама

Айталық - бұл дизъюнктивтік қосындыларға қатысты ақырында жасалатын, объективті комбинаторлық ойындар жиынтығы жабық екі мағынада:

(1) Қоспаларды жабу: Егер және ойындар , содан кейін олардың дизъюнктивті қосындысы сонымен қатар .

(2) Тұқымқуалаушылық: Егер бұл ойын және параметрі болып табылады , содан кейін сонымен қатар .

Әрі қарай, анықтаңыз The ажыратылмайтын сәйкестік Two бұл екі ойынға қатысты және егер ойынның әр таңдауы үшін болса жылы , екі позиция және бірдей нәтижеге қол жеткізіңіз (яғни, екеуі де бірінші ойыншы жеңіске жетеді) , немесе балама түрде екінші ойыншы жеңеді).

Оңай түрде ind барлық дизъюнктивті позициялар қосындыларының жиынтығы бойынша сәйкестік екенін тексереді , және бұл ойынның әдеттегі немесе дұрыс емес ойында болғанына қарамастан дұрыс. Барлық сәйкестік кластарының жиынтығы ажыратылмайтындық.

Егер кәдімгі ойын ретінде ойналады (соңғы ойында жеңетін) бейтарап ойын, содан кейін үйлесімділік сыныптары ойын барысында пайда болатын ним мәндерімен бір-біріне сәйкес келеді (өздері Спраг-Грунди теоремасы ).

Misere ойынында үйлесімділік сыныптары а құрайды коммутативті моноид орнына, және ол қате баға ретінде белгілі болды.

Misere quotients есептеу алгоритмдері

Әр түрлі бейтарап ойындар үшін, әсіресе, ойындар үшін көптеген күрделі және күрделі мисерлік квоенттер есептелген сегіздік ойындар.Белсенді емес ойынның берілген шектеулі жиынтығының моноидты презентациясын есептеудің жалпы мақсаттағы алгоритмін Аарон Н.Сигель ойлап тапқан және сипатталған[2] оның С қосымшасында.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Bouton, C. L. (1901), «Nim, толық математикалық теориясы бар ойын», Математика жылнамалары, 2, 3 (1/4): 35–39, дои:10.2307/1967631, JSTOR  1967631
  2. ^ Пламбек, Тейн Е .; Сигель, Аарон Н., Бейтарап ойындарға арналған қателіктер: қосымша материал, arXiv:0705.2404, Бибкод:2007arXiv0705.2404P

Пламбек, Тейн Э. (2005-07-19). «Бейбіт комбинаториялық ойындарда жабайы табиғатты қолға үйрету» (PDF). INTEGERS: Комбинаторлық сан теориясының электронды журналы (PDF). 5 (G05). Алынған 2010-12-21.

Сигель, Аарон Н. Комбинаторлық ойындар теориясы. 146. Американдық математикалық қоғам 2013. ISBN  9780821851906.

Сыртқы сілтемелер