Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Екі ойыншыға арналған абстрактілі үстел ойыны.
Abstract board game for two players
М,n,k ойыны – екі ойыншының m x n тақтаға өз түсінің тастарын кезекпен қоятын абстрактілі үстел ойыны. Көлденең, тік немесе диагональ бойынша бірінші болып өз түсінің k тасын қатар тізеген ойыншы жеңіске жетеді. Осылайша, крестики-нолики – 3,3,3 ойыны, ал еркін стильдегі гомоку – 15,15,5 ойыны. М,n,k ойыны m x n тақтадағы k қатар ойыны деп те аталады. М,n,k ойындары көбінесе математикалық тұрғыдан қызығушылық тудырады. Ойынның теориялық құнын, яғни ең жақсы ойын стратегиясымен ойынның нәтижесін анықтауға тырысады. Бұл ойынды шешу деп аталады.
An m,n,k game is an abstract board game in which two players take turns in placing a stone of their color on an m by n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. Thus, tic tac toe is the 3,3,3 game and free style gomoku is the 15,15,5 game. An m,n,k game is also called a k in a row game on an m by n board. The m,n,k games are mainly of mathematical interest. One seeks to find the game theoretic value, the result of the game with perfect play. This is known as solving the game.
Стратегияны ұрлау аргументі
Комбинаторлық ойын теориясынан стандартты стратегияны ұрлау аргументі ешқандай m,n,k ойынында екінші ойыншының жеңетін стратегиясы болуы мүмкін емес екенін көрсетеді (екінші ойыншының жеңімпаз стратегиясы). Себебі, кез келген позицияда кез келген ойыншыға қосымша тас берілсе, ол ойыншының жеңіс мүмкіндіктерін жақсартады ғана. Стратегияны ұрлау аргументі екінші ойыншының жеңімпаз стратегиясы бар деп есептейді және бірінші ойыншы үшін жеңімпаз стратегияны көрсетеді. Бірінші ойыншы бастапқыда кездейсоқ қимыл жасайды. Содан кейін, ол екінші ойыншы болып есептейді және екінші ойыншының жеңімпаз стратегиясын қабылдайды. Ол бұл стратегияны орындау кезінде, егер стратегия "еркін" алаңға тас қоюды талап етпесе, осылай жалғастыра береді. Егер мұндай жағдай туындаса, ол тағы да кездейсоқ қимыл жасап, екінші ойыншының жеңімпаз стратегиясын бұрынғысынша қолдана береді. Қосымша тас оған зиян келтіре алмайтындықтан, бұл бірінші ойыншы үшін жеңімпаз стратегия болып табылады. Бұл қайшылық бастапқы болжамның жалған екенін көрсетеді, яғни екінші ойыншының жеңімпаз стратегиясы болуы мүмкін емес. Бұл аргумент нақты бір ойынның тең болатынына немесе бірінші ойыншының жеңісіне қатысты ештеңе айтпайды. Сондай-ақ, ол бірінші ойыншыға нақты стратегияны ұсынбайды.
A standard strategy stealing argument from combinatorial game theory shows that in no m,n,k game can there be a strategy that assures that the second player will win (a second player winning strategy). This is because an extra stone given to either player in any position can only improve that player's chances. The strategy stealing argument assumes that the second player has a winning strategy and demonstrates a winning strategy for the first player. The first player makes an arbitrary move, to begin with. After that, the player pretends that they are the second player and adopts the second player's winning strategy. They can do this as long as the strategy doesn't call for placing a stone on the 'arbitrary' square that is already occupied. If this happens, though, they can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt them, this is a winning strategy for the first player. The contradiction implies that the original assumption is false, and the second player cannot have a winning strategy. This argument tells nothing about whether a particular game is a draw or a win for the first player. Also, it does not actually give a strategy for the first player.
Нәтижелерді әр түрлі өлшемді тақталарға қолдану
Пайдалы ұғым – "әлсіз (m,n,k) ойын", онда екінші ойыншының қатарынан k тас қоюы екінші ойыншының жеңісімен ойынды аяқтамайды. Егер әлсіз (m,n,k) тең болса, онда m немесе n-ді кеміту немесе k-ны арттыру да тең ойынға алып келеді. Керісінше, егер әлсіз немесе қалыпты (m,n,k) ойында жеңіс болса, онда одан үлкен әлсіз (m,n,k) ойыны да жеңіс болады. Жұптастыру стратегиясын қолданып теңдікті дәлелдеу, әлсіз нұсқа үшін де, сондай-ақ барлық кіші нұсқалар үшін де теңдікті дәлелдейтінін есте сақтаңыз.
A useful notion is a "weak (m,n,k) game", where k in a row by the second player does not end the game with a second player win. If weak (m,n,k) is a draw, then decreasing m or n, or increasing k will also result in a drawn game. Conversely, if weak or normal (m,n,k) is a win, then any larger weak (m,n,k) is a win. Note that proofs of draws using pairing strategies also prove a draw for the weak version and thus for all smaller versions.
Жалпы нәтижелер
Келесі мәлімдемелер екі ойыншының да оңтайлы стратегия қолданатынын ескере отырып, әлсіз ойынның бірінші ойыншысына қатысты. Егер (m0, n0, k0) тең болса, онда (m0, n0, k) k ≥ k0 болғанда да тең болады, ал (m, n, k0) m ≤ m0 және n ≤ n0 болғанда да тең болады. Сол сияқты, егер (m0, n0, k0) жеңіс болса, онда (m0, n0, k) k ≤ k0 болғанда жеңіс болады, ал (m, n, k0) m ≥ m0 және n ≥ n0 болғанда жеңіс болады. k ≥ 9 теңдікке алып келеді: k = 9 және тақта шексіз болса, екінші ойыншы "жұптастыру стратегиясы" арқылы теңдікке қол жеткізе алады. Шексіз тақтада теңдік – ойынның мінсіз ойынмен мәңгілікке созылуы. Жұптастыру стратегиясы тақтаның барлық шаршыларын жұптарға бөлуді қамтиды, осылайша бірінші ойыншының шаршысына әрқашан ойнайтын екінші ойыншы, бірінші ойыншының бір қатарда k шаршысын жинамайтынына кепілдік береді. Шексіз тақтадағы жұптастыру стратегиясын кез келген шекті тақтаға да қолдануға болады – егер стратегия тақтадан тыс қадам жасауды талап етсе, екінші ойыншы тақта ішінде кездейсоқ қадам жасайды. k ≥ 8 шексіз тақтада теңдікке алып келеді. Бұл стратегияның қандай да бір шекті тақта өлшемдеріне қолданылатыны белгісіз, яғни (m,n,5) m ≤ 8 және n ≤ 8 үшін теңдікке алып келеді. Л. Виктор Аллис компьютерлік іздеу арқылы (15,15,5) Gomoku-ның шектеуші ережелерінің біріне қарамастан жеңіске жететінін көрсетті. (9,6,6) және (7,7,6) екеуі де жұптастыру арқылы теңдікке жетеді.
The following statements refer to the first player in the weak game, assuming that both players use an optimal strategy. If a particular (m0, n0, k0) is a draw, then (m0, n0, k) with k ≥ k0 is a draw, and (m, n, k0) with m ≤ m0 and n ≤ n0 is a draw. Likewise, if (m0, n0, k0) is a win, then (m0, n0, k) with k ≤ k0 is a win, and (m, n, k0) with m ≥ m0 and n ≥ n0 is a win. k ≥ 9 is a draw: when k = 9 and the board is infinite, the second player can draw via a "pairing strategy". A draw on an infinite board means that the game will go on forever with perfect play. A pairing strategy involves dividing all the squares of the board into pairs in such a way that by always playing on the pair of the first player's square, the second player is ensured that the first player cannot get k in a line. A pairing strategy on an infinite board can be applied to any finite board as well – if the strategy calls for making a move outside the board, then the second player makes an arbitrary move inside the board. k ≥ 8 is a draw on an infinite board. It is not clear if this strategy applies to any finite board sizes. which means that (m,n,5) is a draw for m ≤ 8 and n ≤ 8. Computer search by L. Victor Allis has shown that (15,15,5) is a win, even with one of the restrictive rules of Gomoku. (9,6,6) and (7,7,6) are both draws via pairings.