Комбинаторлық ойындар теориясы: екі ойыншының толық ақпаратты жинағымен кезекті ойындары

Кіріспе

Ойын теориясының екі ойыншы арасындағы тікелей ойындары туралы сала – комбинаторлық ойындар теориясы. Комбинаторлық ойындар теориясы – математика мен теориялық информатиканың бір саласы, көбінесе толық ақпаратты ойындарды зерттейді. Зерттеулер көбінесе екі ойыншыға арналған ойындармен шектеледі, онда ойыншылар белгілі бір жеңіс шартына жету үшін кезекпен белгілі бір қадамдар жасайды. Комбинаторлық ойындар теориясы дәстүрлі түрде кездейсоқ элементтері бар немесе толық емес ақпаратты пайдаланатын ойындарды зерттемейді, керісінше, ойынның жай-күйі мен қолжетімді қадамдар жиыны екі ойыншыға да әрқашан белгілі болатын толық ақпаратты ұсынатын ойындарға басымдық береді. Дегенмен, математикалық әдістердің дамуымен математикалық талдауға болатын ойын түрлері кеңейеді, сондықтан саланың шекарасы үнемі өзгеріп отырады. Ғалымдар әдетте мақаланың басында «ойын» дегенді қалай түсінетінін анықтайды, және бұл анықтамалар көбінесе өзгереді, себебі олар талданатын нақты ойынға байланысты және саланың толық көлемін білдірмейді. Комбинаторлық ойындарға шахмат, шашка және Го сияқты белгілі ойындар кіреді, олар тривиальды емес деп саналады, ал крестики-нолики «шешуге оңай» болғандықтан тривиальды саналады. Кейбір комбинаторлық ойындарда шексіз шахмат сияқты шексіз ойын алаңы болуы мүмкін. Комбинаторлық ойындар теориясында осы және басқа ойындардағы қадамдар ойын ағашы түрінде бейнеленеді. Комбинаторлық ойындарға Судоку сияқты бір ойыншыға арналған комбинаторлық жұмбақтар және Конвейдің «Өмір» ойыны сияқты ойын автоматтары да кіреді (бірақ қатаң анықтама бойынша «ойындар» бірнеше қатысушыны талап етеді, сондықтан «жұмбақ» және «автомат» терминдері қолданылады). Ойын теориясы, жалпы алғанда, кездейсоқ элементтері бар ойындарды, толық емес ақпаратты ойындарды және ойыншылардың бір уақытта қадам жасауы мүмкін болатын ойындарды қамтиды, және олар нақты өмірдегі шешім қабылдау жағдайларын бейнелеуге бейім. Комбинаторлық ойындар теориясы бастапқыда қарапайым комбинаторлық құрылымы бар, бірақ кездейсоқ элементтері бар ойындарды зерттеу үшін әзірленген «дәстүрлі» немесе «экономикалық» ойын теориясынан өзгеше басымдықтарға ие (олар жүйелі қадамдарды қарастырса да, кеңейтілген формадағы ойынды қарастырады). Қысқасы, комбинаторлық ойындар теориясы ойын ағаштарын талдаудың жаңа әдістерін ұсынды, мысалы, сюрреалистік сандарды қолдану, олар екі ойыншыға арналған толық ақпаратты ойындардың кіші класын құрайды. Басқа нақты ойындар бүгінгі таңда толыққанды талдауға мүмкіндік бермейді, бірақ теория Go ойынының соңғы кезеңін талдауда жақында сәттіліктерге қол жеткізді. Комбинаторлық ойындар теориясын нақты бір жағдайға қолдану, екі ойыншының да қадамдарының оңтайлы тізбегін анықтауға бағытталған, осылайша кез келген жағдайдағы оңтайлы қадамды анықтауға мүмкіндік береді. Бірақ іс жүзінде бұл процесс ойын өте қарапайым болмаса, өте қиын. Математиктер мен ғалымдардың зерделеуі мен шешуі үшін қызығушылық тудыратын комбинаторлық «математикалық ойындар» мен ойын-сауық және бәсекелестік ретінде жалпы халықты қызықтыратын комбинаторлық «ойын-сауық» арасын ажырату пайдалы. Дегенмен, көптеген ойындар екі санатқа да жатады. Мысалы, Nim – комбинаторлық ойындар теориясының негізін қалауда маңызды рөл атқарған және алғашқы компьютерлік ойындардың бірі. Крестики-нолики әлі де компьютерлік ғылым студенттеріне ойынның жасанды интеллектін (AI) жобалаудың негізгі принциптерін үйрету үшін қолданылады.

Branch of game theory about two player sequential games with perfect information
the theory of combinatorial games

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field. Combinatorial games include well known games such as chess, checkers, and Go, which are regarded as non trivial, and tic tac toe, which is considered trivial, in the sense of being "easy to solve". Some combinatorial games may also have an unbounded playing area, such as infinite chess. In combinatorial game theory, the moves in these and other games are represented as a game tree. Combinatorial games also include one player combinatorial puzzles such as Sudoku, and no player automata, such as Conway's Game of Life, (although in the strictest definition, "games" can be said to require more than one participant, thus the designations of "puzzle" and "automata".) Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real life decision making situations. Combinatorial game theory has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive form game). Essentially, combinatorial game theory has contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two player perfect information games. Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. Applying combinatorial game theory to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is torturously difficult unless the game is very simple. It can be helpful to distinguish between combinatorial "mathgames" of interest primarily to mathematicians and scientists to ponder and solve, and combinatorial "playgames" of interest to the general population as a form of entertainment and competition. However, a number of games fall into both categories. Nim, for instance, is a playgame instrumental in the foundation of combinatorial game theory, and one of the first computerized games. Tic tac toe is still used to teach basic principles of game AI design to computer science students.

Тарих

Комбинациялық ойын теориясы бейтарап ойындар теориясымен байланысты туындады, онда бір ойыншыға қолжетімді кез келген мүмкіндік екінші ойыншыға да қолжетімді болуы керек. Мұндай ойынның бірі – Nim, ол толықтай шешіле алады. Nim – екі ойыншыға арналған бейтарап ойын және қалыпты ойын шартына сәйкес, яғни қимыл жасай алмайтын ойыншы жеңіледі. 1930 жылдары Спрагг–Гранди теоремасы барлық бейтарап ойындар Nim-дегі үймелерге эквивалентті екенін көрсетті, осылайша комбинаторлық деңгейде қарастырылатын ойындарда маңызды біріктірулерге мүмкіндік бар екенін көрсетті, онда егжей-тегжейлі стратегиялар, төлемдерден гөрі маңыздырақ. 1960 жылдары Элвин Р. Берлекамп, Джон Х. Конвей және Ричард К. Гай бірлесіп партиялық ойын теориясын енгізді, онда бір ойыншыға қолжетімді мүмкіндік екеуіне де қолжетімді болуы талабы жеңілдетілді. Олардың нәтижелері 1982 жылы «Математикалық ойындарда жеңіске жету жолдары» кітабында жарияланды. Дегенмен, бұл тақырыпта жарияланған алғашқы жұмыс 1976 жылы Конвейдің «Сандар мен ойындар» кітабы болды, ол ONAG деп те белгілі, және ол сюрреалистік сандар тұжырымдамасын және ойындарға жасалған жалпылауды енгізді. «Сандар мен ойындар» кітабы да Берлекамп, Конвей және Гайдың бірлескен еңбегі болды. Комбинациялық ойындар, әдетте, конвенция бойынша, бір ойыншының екінші ойыншының қозғалыстары таусылғанда жеңіске жететін формаға келтіріледі. Кез келген шекті ойынды, тек екі мүмкін нәтижесі бар, осы конвенцияға сәйкес келетін эквивалентті ойынға түрлендіру оңай. Комбинаторлық ойындар теориясындағы ең маңызды тұжырымдамалардың бірі – екі ойынның қосындысы, яғни ойынның кез келген сәтінде әр ойыншы бір ойында немесе екінші ойында қозғалуға таңдау жасай алады, ал ойыншы қарсыласы екі ойынның бірінде де қозғала алмаса жеңеді. Ойынды осылай біріктіру математикалық құрылымның бай және қуатты болуына алып келеді. Конвей «Сандар мен ойындар» кітабында партиялық ойындар теориясының шабыты Го ойынының соңғы кезеңдеріндегі оның байқауларына негізделгенін, оларды көбінесе досканың әртүрлі бөліктерінде бір-бірінен оқшауланған қарапайым соңғы ойындардың жиынтығына бөлуге болатынын айтты.

Combinatorial game theory arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One such game is Nim, which can be solved completely. Nim is an impartial game for two players, and subject to the normal play condition, which means that a player who cannot move loses. In the 1930s, the Sprague–Grundy theorem showed that all impartial games are equivalent to heaps in Nim, thus showing that major unifications are possible in games considered at a combinatorial level, in which detailed strategies matter, not just pay offs. In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book Winning Ways for your Mathematical Plays in 1982. However, the first work published on the subject was Conway's 1976 book On Numbers and Games, also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was also a fruit of the collaboration between Berlekamp, Conway, and Guy. Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure. Conway stated in On Numbers and Games that the inspiration for the theory of partisan games was based on his observation of the play in Go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

Шолу

Ойын, ең қарапайым түрінде, сол және оң деп аталатын екі ойыншының жасай алатын мүмкін "қимылдарының" тізімі болып табылады. Кез келген қимылдан туындайтын ойын позициясын басқа ойын деп қарастыруға болады. Ойындарды басқа ойындарға қатысты мүмкін қимылдар тұрғысынан қарау идеясы, комбинаторлық ойын теориясында стандартты саналатын ойындардың рекурсивті математикалық анықтамасына әкеледі. Бұл анықтама бойынша, әрбір ойын {L|R} түрінде белгіленеді. L – сол жақ ойыншының қозғала алатын ойын позицияларының жиынтығы, ал R – оң жақ ойыншының қозғала алатын ойын позицияларының жиынтығы; L және R-дегі әрбір позиция сол белгіленуді пайдалана отырып, ойын ретінде анықталады. Мысал ретінде Domineering ойынын алып, төрттік тақтаның он алты шаршысын сол жоғарғы шаршы үшін A1, екінші қатардағы солдан үшінші шаршы үшін C2, және т.б. деп белгілейміз. Мысалы, (D3, D4) вертикальді домино төменгі оң бұрышта орналасқан ойын позициясын білдіреді. Осыдан кейін бастапқы позицияны комбинаторлық ойын теориясының нотациясында былай сипаттауға болады.

Стандартты Cross Cram ойынында ойыншылар кезегімен ойнайды, бірақ бұл кезектесу ойын күйлерінде кодталғаннан гөрі, комбинаторлық ойын теориясының анықтамалары арқылы түсіндіріледі. Жоғарыдағы ойын екі ойыншының біреуі үшін тек бір ғана қимыл қалғанын көрсетеді, және егер ойыншы сол қимылды жасаса, жеңіске жетеді. (Диаграммадан маңызсыз ашық шаршы C3 алынып тасталды.) Әр ойыншының қимыл тізіміндегі {|} (қимылдан кейін қалған жалғыз шаршыға сәйкес) нөлдік ойын деп аталады, және оны 0 деп қысқартуға болады. Нөлдік ойында екі ойыншының да жарамды қимылы жоқ; демек, нөлдік ойын пайда болған кезде кезегі келетін ойыншы автоматты түрде жеңіледі. Жоғарыдағы диаграммадағы ойынның түрі де қарапайым атауға ие; ол жұлдыз ойыны деп аталады, және оны ∗ деп қысқартуға болады. Жұлдыз ойынындағы жалғыз жарамды қимыл нөлдік ойынға әкеледі, яғни жұлдыз ойынында кімнің кезегі келсе, ол автоматты түрде жеңіске жетеді. Domineering ойынында кездеспейтін ойынның қосымша түрі – циклдік ойын, онда солға немесе оңға дұрыс қимыл жасау, сол қимыл бастапқы ойынға қайта оралуы мүмкін. Мысалы, шашкада бір фигура ханшайым болғанда циклдік болады, себебі ол екі немесе одан да көп шаршы арасында шексіз айналып жүреді. Мұндай қимылдары жоқ ойын циклсіз деп аталады.

Жұлдыз

Жұлдыз, немесе {0|0} деп жазылады, бірінші ойыншының жеңісін білдіреді, себебі кез келген ойыншы (ойынды бірінші қозғаған жағдайда) нөлдік ойынға өтуге міндетті, демек жеңіске жетеді. Жұлдыз + Жұлдыз = 0, өйткені бірінші ойыншы жұлдыздың бір данасын 0-ге айналдыруы керек, ал екінші ойыншы жұлдыздың екінші данасын да 0-ге айналдыруға мәжбүр болады; осы кезде бірінші ойыншы жеңіледі, себебі 0 + 0 қозғалысқа мүмкіндік бермейді. Жұлдыз оң немесе теріс емес; ол және бірінші ойыншының жеңіске жететін барлық басқа ойындар (ойыншының қай жағында болғанына қарамастан) 0-ге шатасқан немесе байланысты деп есептеледі; символдық түрде біз жұлдыз || 0 деп жазамыз.

"Жылы" ойындар

{1|−1} ойынын қарастырайық. Бұл ойындағы екі мүмкіндік те оны жасаған ойыншыға пайдалы; сондықтан бұл ойын "қызды" деп аталады; ол -1-ден кішкенерей саннан үлкен, 1-ден үлкен саннан кішкенерей, ал аралықтағы кез келген санмен шатасқан. Ол ±1 деп жазылады. Оны сандарға қосуға немесе оң сандарға көбейтуге болады, нәтиже күтілгендей болады; мысалы, 4 ± 1 = {5|3}.

Қаңқалар

Бейтарап ойын — ойынның кез келген позициясында екі ойыншыға да бірдей мүмкіндіктер ашық болатын ойын. Мысалы, Nim бейтарап ойын, себебі бір ойыншы алып тастай алатын кез келген затты екінші ойыншы да алып тастай алады. Дегенмен, домино ойыны бейтарап емес, өйткені бір ойыншы көлденең доминоларды, ал екіншісі тік доминоларды қояды. Сол сияқты, шашки де бейтарап емес, себебі ойыншылардың әртүрлі түсті фигуралары болады. Кез келген реттік сан үшін, Nim ойынын жалпылайтын бейтарап ойынды анықтауға болады, онда әрбір қадамда ойыншылардың бірі санды кез келген кіші реттік санмен алмастыра алады; осылай анықталған ойындар нимберлер деп аталады. Спраг–Гранди теоремасы әрбір бейтарап ойын нимберге эквивалентті екенін көрсетеді. "Ең кіші" нимберлер — ординалдардың стандартты реті бойынша ең қарапайым және ең төменгі сандар — 0 және ∗ болып табылады.