Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Періште мәселесі – Джон Хортон Конвей ұсынған комбинаторлық ойын теориясындағы сұрақ. Ойын көбінесе «періштелер мен шайтандар ойыны» деп аталады. Ойынды екі ойыншы ойнайды: періште және шайтан. Ол шексіз шахмат тақтасында (немесе эквивалентті түрде 2D тордың нүктелерінде) ойналады. Періштеде k күші бар (1-ден жоғары натурал сан), ол ойын басталғанға дейін анықталады. Тақта бос күйде басталады, ал періште бір алаңда орналасқан. Әрбір қадамда періште шахмат патшасының ең көп дегенде k қадамымен жете алатын басқа бос алаңға секіреді, яғни бастапқы алаңнан қашықтық шексіз нормада k-дан аспайды. Шайтан өз кезегінде періштеде жоқ кез келген алаңға кедергі қоя алады. Періште кедергілерден секіріп өте алады, бірақ оларға қона алмайды. Егер періште қозғала алмаса, шайтан жеңеді. Періште шексіз уақыт бойы аман қалу арқылы жеңіске жетеді. Періште мәселесі: жеткілікті күші бар періште жеңе ала ма? Ойыншылардың біреуінің жеңіске жету стратегиясы болуы керек. Егер шайтан жеңіске мәжбүрлей алса, онда ол оны шектеулі қадамдар санымен іске асыра алады. Егер шайтан жеңіске мәжбүрлей алмаса, онда періште әрқашан жеңілістен сақтану үшін бір әрекет жасай алады және оның жеңіске жету стратегиясы әрқашан осындай қадамды таңдау болып табылады. Көбірек абстрактілі түрде, «төлем жиынтығы» (яғни, періште жеңетін барлық ойындар жиынтығы) жабық жиынтық (барлық ойындар жиынтығындағы табиғи топологияда) және мұндай ойындар анықталған деп белгілі. Әрине, кез келген шексіз ойын үшін, егер екінші ойыншының жеңіске жету стратегиясы болмаса, бірінші ойыншы әрқашан екінші ойыншының жеңіске жету стратегиясы жоқ жағдайға әкелетін қадамды таңдай алады, бірақ кейбір ойындарда мәңгі ойнау бірінші ойыншыға жеңіс әкелмейді, сондықтан анықталмаған ойындар болуы мүмкін. Конвей осы мәселенің жалпы шешімі үшін сыйақы ұсынды (жеткілікті күші бар періште үшін жеңіске жету стратегиясы үшін 100 доллар, ал періште күшіне қарамастан шайтан жеңе алатынын дәлелдеу үшін 1000 доллар). Алдымен жоғары өлшемдерде прогресс жасалды. 2006 жылдың соңында, тәуелсіз дәлелдер пайда болған кезде, бастапқы мәселе шешілді, бұл періште жеңе алатынын көрсетті. Боудич 4-күшті періште (яғни k = 4 күші бар періште) жеңе алатынын дәлелдеді, ал Мате және Клостер 2-күшті періште жеңе алатынын дәлелдеді.
The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the angels and devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i. e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely. The angel problem is: can an angel with high enough power win? There must exist a winning strategy for one of the players. If the devil can force a win then it can do so in a finite number of moves. If the devil cannot force a win then there is always an action that the angel can take to avoid losing and a winning strategy for it is always to pick such a move. More abstractly, the "pay off set" (i. e., the set of all plays in which the angel wins) is a closed set (in the natural topology on the set of all plays), and it is known that such games are determined. Of course, for any infinite game, if player 2 doesn't have a winning strategy, player 1 can always pick a move that leads to a position where player 2 doesn't have a winning strategy, but in some games, simply playing forever doesn't confer a win to player 1, so undetermined games may exist. Conway offered a reward for a general solution to this problem ($100 for a winning strategy for an angel of sufficiently high power, and $1000 for a proof that the devil can win irrespective of the angel's power). Progress was made first in higher dimensions. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win. Bowditch proved that a 4 angel (that is, an angel with power k = 4) can win and Máthé and Kloster gave proofs that a 2 angel can win.
Негізгі стратегиялар және олардың жұмыс істемеуінің себептері
Періштеге арналған көптеген интуитивті құтылу стратегияларын жеңуге болады. Мысалы, егер періште жақын блоктардан қашып кетуге тырысса, шайтан үлкен ат тәрізді нысанды алыс солтүстікке қарай жасайды, содан кейін періштеге тұзаққа түсуі үшін періштенің оңтүстігіндегі бір шаршыны қайта-қайта жейді. Егер періште өте алыс орналасқан тұзақтардан қашуға тырысса, шайтан солтүстікке қарай кішкентай ат тәрізді нысан жасап, періштеге алыс оңтүстіктегі шаршыларды жеу арқылы тұзаққа түсуге итермелейді. Періште солтүстікке мүмкіндігінше жылдам қозғалып, кездейсоқ шығысқа немесе батысқа қарай зигзагтар жасау арқылы көзге көрінетін тұзақтардан аулақ болу арқылы жеңіске жете алады деп көрінеді. Бірақ бұл стратегияны жеңуге болады, себебі осы періштенің болашақтағы мүмкін болатын орналасуы конус тәрізді, ал шайтан конустың алыс бөлігінде белгілі бір тәртіппен қабырға тұрғыза алады. Сөйтіп, періште соңғы нүктеге жеткенде, шайтан өтпейтін қабырғаны құрып қояды, ал періште солтүстікке қарай қозғалуға бекінгендіктен, ол мүлдем қозғала алмайды.
Many intuitive escape strategies for the angel can be defeated. For example, if the angel tries to run away from near blocks, the devil can make a giant horseshoe far to the north, then prod the angel into the trap by repeatedly eating the square just to the south of the angel. If the angel tries to avoid traps set very far away, the devil can make a small horseshoe to the north, then prod the angel into the trap by eating the squares far to the south. It seems that the angel should be able to win by moving north as fast as he can, combined with occasional zigzags to the east or west to avoid any obvious traps. This strategy can be defeated by noting that this angel's possible future positions lie in a cone, and the devil can build a wall across the cone in the distance in a certain manner, so that when the angel finally arrives at the distance, the devil has created an impenetrable wall, and since the angel insists on moving north, the angel cannot move at all.
Тағы да шешілмеген сұрақтар
3D кеңістігінде, періште әрқашан y-координатын арттыратыны және шайтан үш жазықтықпен шектелгені ескерілгенде, шайтанның жеңіске жететін стратегиясы бар-жоғы әлі белгісіз.
In 3D, given that the angel always increases its y coordinate, and that the devil is limited to three planes, it is unknown whether the devil has a winning strategy.
Клостердің екі періштеге қарсы қорғанысы
Oddvar Kloster 2 періште проблемасын шешу үшін конструктивті алгоритм тапты. Бұл алгоритм өте қарапайым және сонымен қатар оңтайлы, себебі жоғарыда айтылғандай, шайтанның 1 періштеге қарсы жеңіске жететін стратегиясы бар. Біз періште бастапқы орнының сол жағына тік сызық салып, оны төмен және жоғары қарай жүргіземіз. Бұл сызық періште өтетін жолды көрсетеді, ол шайтанның әр қимылынан кейін жаңартылады және тақтаның шаршыларын «сол жиын» және «оң жиын» деп бөледі. Шаршы бір рет сол жиынға өткеннен кейін, ол ойын соңына дейін сонда қалады, ал періште осы шаршыларға енді қозғалмайды. Шайтан жаңа шаршыны тосқан сайын, біз жолдың барлық мүмкін өзгерістерін іздейміз, яғни оң жиындағы бір немесе бірнеше шаршыларды сол жиынға жылжытамыз. Бірақ мұны тек қана жолдың ұзындығы жылжытылған тосқан шаршылар санының екі есесінен артық болмаса жасаймыз. Осындай шарттарға сай жолдардың ішінде, біз ең көп тосқан шаршыларды сол жиынға жылжытатын жолды таңдаймыз. Содан кейін періште осы жолмен екі қадам басады, алға жылжығанда жолды сол жағында ұстайды (егер шайтан шаршыларды тоспаса, періште солтүстікке шексіз сапар шегер еді). Бұрышты сағат тілімен айналып өткенде періште бір қадамға қозғалмайды, себебі бұрышқа жанасқан екі кесіндінің оң жағындағы шаршысы бірдей болады.
Oddvar Kloster discovered a constructive algorithm to solve the problem with a 2 angel. This algorithm is quite simple and also optimal, since, as noted above, the devil has a winning strategy against a 1 angel. We start out by drawing a vertical line immediately to the left of the angel's starting position, down to and up to This line represents the path the angel will take, which will be updated after each of the devil's moves, and partitions the board's squares into a "left set" and a "right set." Once a square becomes part of the left set, it will remain so for the remainder of the game, and the angel will not make any future moves to any of these squares. Every time the devil blocks off a new square, we search over all possible modifications to the path such that we move one or more squares in the right set which the devil has blocked off into the left set. We will only do this if the path increases in length by no more than twice the number of blocked squares moved into the left set. Of such qualifying paths, we choose one that moves the greatest number of blocked off squares into the left set. The angel then makes two steps along this path, keeping the path to its left when moving in the forward direction (so if the devil were not blocking off squares, the angel would travel north indefinitely). Note that when going clockwise around a corner, the angel will not move for one step, because the two segments touching the corner have the same square to their right.
Матедің екі періштеге қарсы дәлелі
Мате 2005 жылы Мартин Куц да осыған ұқсас дәлел жариялаған.
Máthé A substantially similar proof was published by Martin Kutz in 2005.