Көмескі ойындардың қосындысы және дизъюнктивті қосындысы
Disjunctive sum
Комбинаторлық ойындардағы қосынды – екі ойынды параллель ойнау, кезекпен тек бір ойында ғана жүргізу. Спраг-Граунд теоремасы мен ойын теориясының негізі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Комбинаторлық ойындар математикасында екі ойынның қосындысы немесе дизъюнктивтік қосындысы – екі ойын параллель ойналатын ойын, онда әр ойыншыға кезекпен тек бір ойында ғана жүруге рұқсат етіледі. Қосынды ойын егер екі параллель ойынның екеуінде де жүруге мүмкіндік болмаса аяқталады, сол кезде (қалыпты ойын кезінде) соңғы жүрген ойыншы жеңіске жетеді. Бұл операция кез келген санындағы ойындардың дизъюнктивтік қосындысына дейін кеңейтілуі мүмкін, ойындарды параллель ойнау және кезекпен тек бір ойында жүру арқылы. Бұл операция Спраг-Гранди теоремасында бейтарап ойындар үшін негізгі болып табылады және партизандық ойындар үшін комбинаторлық ойын теориясы саласының дамуына әкелді.
In the mathematics of combinatorial games, the sum or disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. The sum game finishes when there are no moves left in either of the two parallel games, at which point (in normal play) the last player to move wins. This operation may be extended to disjunctive sums of any number of games, again by playing the games in parallel and moving in exactly one of the games per turn. It is the fundamental operation that is used in the Sprague–Grundy theorem for impartial games and which led to the field of combinatorial game theory for partisan games.
Жалпы ойындарға қолдану
Дисъюнктивтік сомалар табиғи түрде өзара әрекеттеспейтін компоненттерге немесе аймақтарға бөлінетін ойындарда туындайды, онда әр ойыншы кезекпен ойнау үшін тек бір компонентті таңдау керек. Мұндай ойындарға Go, Nim, Sprouts, Domineering, Амазондар ойыны және карта бояу ойындары жатады. Мұндай ойындарда әр компонент оның нәтижесіне немесе басқа ойындармен дизъюнктивтік сомасының нәтижесіне әсер етпейтін жеңілдетулер үшін жеке-жеке талдауға болады. Бұл талдау аяқталғаннан кейін компоненттерді екі ойынның дизъюнктивтік сомасын алып, оларды бастапқы ойынмен бірдей нәтижеге ие бір ойынға біріктіру арқылы біріктіруге болады.
Disjunctive sums arise in games that naturally break up into components or regions that do not interact except in that each player in turn must choose just one component to play in. Examples of such games are Go, Nim, Sprouts, Domineering, the Game of the Amazons, and the map coloring games. In such games, each component may be analyzed separately for simplifications that do not affect its outcome or the outcome of its disjunctive sum with other games. Once this analysis has been performed, the components can be combined by taking the disjunctive sum of two games at a time, combining them into a single game with the same outcome as the original game.
Математика
Қосу операциясы формальданды. Бұл коммутативтік және ассоциативтік операция: егер екі ойын біріктірілсе, олардың қандай ретпен біріктірілгеніне қарамастан, нәтиже бірдей болады, ал егер екі ойыннан астам ойын біріктірілсе, нәтиже олардың қалай топтасқанына қарамастан бірдей болады. G ойынының (екі ойыншының рөлін ауыстыру арқылы құрылған ойын) -G терістелуі, дизъюнктивті қосылыстар бойынша қосымша кері шама болып табылады: G + −G ойыны – нөлдік ойын (кім екінші болып ойнаса, сол жеңеді), қарапайым қайталау стратегиясын қолданады, онда екінші ойыншы бірінші ойыншының қимылын екінші ойында қайта-қайта қайталайды. Кез келген екі ойын G және H үшін, H + G + −G ойынының нәтижесі H ойынының өзімен бірдей (бірақ ол қолжетімді қимылдардың кеңірек жиынтығына ие болуы мүмкін). Осы қасиеттерге сүйене отырып, комбинаторлық ойындар класы абельдік топтың құрылымына ие деп есептелуі мүмкін, бірақ элементтер жиынының орнына элементтердің тиісті класы бар (топтар үшін бұл қалыпты жағдай). Ойындардың маңызды бір кіші класы – сюрреалистік сандар деп аталады, олар үшін бұл топты өріске кеңейтетін көбейту операторы бар. Бейтарап, мизерлік ойын режиміндегі ойындар үшін сомалардың ұқсас теориясын дамытуға болады, бірақ олардың қасиеттері азырақ: бұл ойындар коммутативті моноидты құрайды, онда тек бір ғана тривиалды емес инвертибель элемент бар, ол жұлдыз (*) деп аталады және екінші дәрежелі.
The sum operation was formalized by It is a commutative and associative operation: if two games are combined, the outcome is the same regardless of what order they are combined, and if more than two games are combined, the outcome is the same regardless of how they are grouped. The negation −G of a game G (the game formed by trading the roles of the two players) forms an additive inverse under disjunctive sums: the game G + −G is a zero game (won by whoever goes second) using a simple echoing strategy in which the second player repeatedly copies the first player's move in the other game. For any two games G and H, the game H + G + −G has the same outcome as H itself (although it may have a larger set of available moves). Based on these properties, the class of combinatorial games may be thought of as having the structure of an abelian group, although with a proper class of elements rather than (as is more standard for groups) a set of elements. For an important subclass of the games called the surreal numbers, there exists a multiplication operator that extends this group to a field. For impartial misère play games, an analogous theory of sums can be developed, but with fewer of these properties: these games form a commutative monoid with only one nontrivial invertible element, called star (*), of order two.