Комбинаторлық ойын теориясындағы стратегия ұрлау аргументі, екінші ойыншының жеңіске кепілді стратегиясы болмауын көрсетеді. Симметриялық ойындарда қолданылады, жеңіс стратегиясын анықтамай-ақ нәтижесін көрсетеді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Комбинациялық ойын теориясында стратегияны ұрлау аргументі – көптеген екі ойыншы ойыны үшін екінші ойыншының кепілді жеңіс стратегиясына ие бола алмайтынын көрсететін жалпы аргумент. Стратегияны ұрлау аргументі кез келген симметриялық ойынға (әрбір ойыншының бірдей нәтижелерге қол жеткізе алатын бірдей мүмкіндіктер жиынтығы бар, сондықтан бірінші ойыншы екінші ойыншының стратегиясын "пайдалана алады") және қосымша қадамның ешқашан зиян келтірмейтін ойынға қолданылады. Стратегияны ұрлау аргументінің маңызды қасиеті – ол бірінші ойыншының нақты стратегияны құрастырмай-ақ ойынды жеңе (немесе тең түсіре) алатынын дәлелдейді. Демек, ол жеңіс стратегиясының бар екенін дәлелдесе де, бұл стратегияның қандай екендігі туралы ешқандай ақпарат бермейді. Аргумент қайшылыққа келу арқылы жұмыс істейді. Екінші ойыншы үшін жеңіс стратегиясы бар деп есептеледі және ол оны пайдаланады. Бірақ, шамамен айтқанда, бірінші ойыншы кездейсоқ қадам жасағаннан кейін – бұл жоғарыда аталған шарттарға сәйкес зиян келтірмейді – сол жеңіс стратегиясын қолдана алады. Нәтижесінде, екі ойыншының да жеңіске жетуіне кепілдік беріледі, бұл абсурд, демек, мұндай стратегия бар деген болжамға қайшы келеді. Стратегияны ұрлауды Джон Нэш 1940 жылдары ойлап тапты, ол гекс ойынының бірінші ойыншының жеңісін көрсету үшін қолданды, себебі бұл ойында тең түсу мүмкін емес. Алайда, Нэш бұл әдісті жарияламады, ал Йозеф Бек оның алғашқы жариялануын Альфред В. Хейлс пен Роберт И. Джуеттке 1963 жылғы «крестики-нолики» туралы мақаласында, онда олар Хейлс-Джуетт теоремасын дәлелдеді, деп санайды. Бұл аргументке қолданылатын ойындардың басқа мысалдары – гомоку сияқты m,n,k ойындары. Чомпы ойынында стратегияны ұрлау бірінші ойыншының кез келген тіктөртбұрышты тақтада (1x1 емес) жеңіс стратегиясына ие екенін көрсетеді. Сильвер монетасы ойынында стратегияны ұрлау бірінші ойыншының «соңғы позициялар» деп аталатын белгілі бір позицияларда жеңе алатынын көрсету үшін қолданылды. Осы мысалдардың барлығында дәлелдеме нақты стратегия туралы ештеңе көрсетпейді.
In combinatorial game theory, the strategy stealing argument is a general argument that shows, for many two player games, that the second player cannot have a guaranteed winning strategy. The strategy stealing argument applies to any symmetric game (one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage. A key property of a strategy stealing argument is that it proves that the first player can win (or possibly draw) the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is. The argument works by obtaining a contradiction. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making an arbitrary first move – which by the conditions above is not a disadvantage – the first player may then also play according to this winning strategy. The result is that both players are guaranteed to win – which is absurd, thus contradicting the assumption that such a strategy exists. Strategy stealing was invented by John Nash in the 1940s to show that the game of hex is always a first player win, as ties are not possible in this game. However, Nash did not publish this method, and József Beck credits its first publication to Alfred W. Hales and Robert I. Jewett, in the 1963 paper on tic tac toe in which they also proved the Hales–Jewett theorem. Other examples of games to which the argument applies include the m,n,k games such as gomoku. In the game of Chomp strategy stealing shows that the first player has a winning strategy in any rectangular board (other than 1x1). In the game of Sylver coinage, strategy stealing has been used to show that the first player can win in certain positions called "enders". In all of these examples the proof reveals nothing about the actual strategy.
Мысал
Стратегияны ұрлау аргументін кез келген өлшемдегі тақта мен жеңіс қатары бар тик-так-то ойыны мысалында қолдануға болады. Ақ немесе Қара ең жақсы ойын көрсетсе жеңіске жете алатыны, немесе екі ойыншы да тең ойнай алатыны әзірге белгісіз. Дегенмен, шахматты зерттегендердің көпшілігі Ақтың алғашқы ходының артықшылық екенін айтады, ал қазіргі заманғы жоғары деңгейдегі ойындардың статистикасы бойынша Ақтың жеңіс көрсеткіші Қарадан шамамен 10% жоғары.
A strategy stealing argument can be used on the example of the game of tic tac toe, for a board and winning rows of any size. It is not currently known whether White or Black can force a win with optimal play, or if both players can force a draw. However, virtually all students of chess consider White's first move to be an advantage and statistics from modern high level games have White's winning percentage about 10% higher than Black's.
Жүре беріңіз
Года өтуге рұқсат етіледі. Бастапқы позиция симметриялық болғанда (бос тақта, екі ойыншының да ұпайлары жоқ), бірінші ойыншы екінші ойыншының жеңіске жететін стратегиясын тек бірінші жүрістен бас тарту арқылы ұрлай алады. Бірақ, 1930 жылдан бері екінші ойыншыға көбінесе бірнеше компенсациялық ұпай беріледі, бұл бастапқы позицияны асимметриялық етеді және стратегия ұрлау аргументі енді қолданылмайды. Ойынның қарапайым стратегиясы – «айна го», онда екінші ойыншы қарсыласы жасаған жүрістерге диагональды түрде қарама-қарсы жүрістер жасайды. Бұл тәсілді басқыш тактикасы, ко-айқас немесе тақтаның орталық нүктесін басып алу үшін күшті бәсекелесу арқылы жеңуге болады.
In Go passing is allowed. When the starting position is symmetrical (empty board, neither player has any points), this means that the first player could steal the second player's winning strategy simply by giving up the first move. Since the 1930s, however, the second player is typically awarded some compensation points, which makes the starting position asymmetrical, and the strategy stealing argument will no longer work. An elementary strategy in the game is "mirror go", where the second player performs moves which are diagonally opposite those of this opponent. This approach may be defeated using ladder tactics, ko fights, or successfully competing for control of the board's central point.
Құрылысшылық
Стратегияны ұрлау аргументі екінші ойыншының кез келген гипотетикалық жеңіс стратегиясынан қайшылық тудырып, екінші ойыншының жеңе алмайтынын көрсетеді. Бұл аргумент, ортаңғы жоқ заңына сәйкес, теңдік мүмкін емес ойындарда кеңінен қолданылады. Дегенмен, ол бірінші ойыншыға нақты стратегияны ұсынбайды, сондықтан оны конструктивті емес деп атайды. Бірақ, позициялар саны көп болғанда, бұл тиімсіз болуы мүмкін. 2019 жылы Грег Бодвин мен Офер Гроссман стратегияны ұрлау аргументтері қолданылған екі түрлі ойында – минималды посет ойыны мен симметриялық Maker-Maker ойынында – жеңіс стратегиясын табу мәселесінің PSPACE қиын екенін дәлездеді.
The strategy stealing argument shows that the second player cannot win, by means of deriving a contradiction from any hypothetical winning strategy for the second player. The argument is commonly employed in games where there can be no draw, by means of the law of the excluded middle. However, it does not provide an explicit strategy for the first player, and because of this it has been called non constructive. However, this might be impractical if the number of positions is large. In 2019, Greg Bodwin and Ofer Grossman proved that the problem of finding a winning strategy is PSPACE hard in two kinds of games in which strategy stealing arguments were used: the minimum poset game and the symmetric Maker Maker game.