Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Абстрактілі стратегиялық тақта ойыны
абстрактілі стратегиялық ойын
Abstract strategy board game
the abstract strategy game
Хекс (кейде Нэш деп те аталады) – екі ойыншыға арналған абстрактілі стратегиялық тақта ойыны. Ойыншылар алтыбұрышты ұяшықтардан құралған ромб пішіндес тақтаның қарама-қарсы жақтарын байланыстыруға тырысады. Хексті 1942 жылы математик және ақын Пит Хайн ойлап тапты, ал кейін Джон Нэш оны қайта ашып, танымал етті. Әдетте 11×11 өлшемді тақтада ойналады, бірақ 13×13 және 19×19 өлшемдері де танымал. Тақта алтыбұрышты ұяшықтардан, немесе «гекстерден» тұрады. Әр ойыншыға тақтаның қарама-қарсы жақтарының жұбы беріледі, олар бос ұяшықтарға өз түсіндегі тастарды кезекпен қойып, осы жақтарды байланыстыруға тырысады. Қойылған тастарды жылжытуға немесе алып тастауға болмайды. Ойыншы өзінің жақтарын тікелей жанасқан тастар тізбегі арқылы сәтті байланыстырса жеңіске жетеді. Хексте ойын тақтасының топологиясының ерекшелігіне байланысты тең түсу мүмкін емес. Ережелерінің қарапайымдылығына қарамастан, ойын терең стратегия мен өткір тактикаға ие. Сонымен қатар, ойынның Брауэрдің тұрақты нүкте теоремасы, матроидтар және граф байланысымен байланысты терең математикалық негіздері бар. Ойын алғаш рет 1942 жылдың 26 желтоқсанында Данияның Politiken газетінде «Polygon» деген атпен жарияланды. Кейіннен Данияда «Con tac tix» деген атпен тақта ойыны ретінде сатылды, ал Parker Brothers 1952 жылы «Hex» деп аталатын нұсқасын шығарды, бірақ қазіргі таңда олар өндірісте жоқ. Хекс алтыбұрышты торлы қағазға қағаз және қаламмен ойнауға да болады.
Hex (also called Nash) is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash. It is traditionally played on an 11×11 rhombus board, although 13×13 and 19×19 boards are also popular. The board is composed of hexagons called cells or hexes. Each player is assigned a pair of opposite sides of the board, which they must try to connect by alternately placing a stone of their color onto any empty hex. Once placed, the stones are never moved or removed. A player wins when they successfully connect their sides together through a chain of adjacent stones. Draws are impossible in Hex due to the topology of the game board. Despite the simplicity of its rules, the game has deep strategy and sharp tactics. It also has profound mathematical underpinnings related to the Brouwer fixed point theorem, matroids and graph connectivity. The game was first published under the name Polygon in the Danish newspaper Politiken on December 26, 1942. It was later marketed as a board game in Denmark under the name Con tac tix, and Parker Brothers marketed a version of it in 1952 called Hex; they are no longer in production. Hex can also be played with paper and pencil on hexagonally ruled graph paper.
Ойын түрі
Hex – шекті, екі ойыншыға арналған толық ақпаратты ойын және байланыс ойындарының жалпы санатына жататын абстрактілі стратегиялық ойын. Бұл позициялық ойынның бір түрі. Ойын тең түсу мүмкін емес болғандықтан, Данияда «Полигон» деген атпен белгілі болды. Ойын туралы алғашқы жарияланған сипаттама Данияның «Politiken» газетінің 1942 жылғы 26 желтоқсандағы санында Хайн жариялаған мақаласында келтірілген.
Hex is a finite, 2 player perfect information game, and an abstract strategy game that belongs to the general category of connection games. a particular type of positional game. Since the game can never end in a draw, it became known in Denmark under the name Polygon due to an article by Hein in the 26 December 1942 edition of the Danish newspaper Politiken, the first published description of the game, in which he used that name.
Нэштің талабы
Ойынды 1948 немесе 1949 жылы Принстон университетінің математигі Джон Нэш қайта ашты. Мартин Гарднердің мәлімдемесінше, ол 1957 жылғы шілде айындағы «Математикалық ойындар» бағанында Хекс ойыны туралы жазған. Нэштің серіктестері ойынды «Нэш» немесе «Джон» деп атаған, екінші атау ойынды алтыбұрышты ванна бөлмесінің плиткаларында ойнау мүмкіндігін көрсетеді. Гарднер Хайнға жеке хат жазып: «Мен редактормен ақылдастым, және Нашқа сенім артуды жөн көріп шештік. Сіз ойынды басқалардан бұрын ойлап тапқаныңыз сөзсіз. Кейіннен көптеген адамдар осыған ұқсас ойды кейінірек келгенде ойлағанын айтуы мүмкін, бірақ бұл маңызсыз және ешкімге қызық емес».
The game was rediscovered in 1948 or 1949 by the mathematician John Nash at Princeton University. According to Martin Gardner, who featured Hex in his July 1957 Mathematical Games column, Nash's fellow players called the game either Nash or John, with the latter name referring to the fact that the game could be played on hexagonal bathroom tiles. Gardner privately wrote to Hein: "I discussed it with the editor, and we decided that the charitable thing to do was to give Nash the benefit of the doubt. The fact that you invented the game before anyone else is undisputed. Any number of people can come along later and say that they thought of the same thing at some later date, but this means little and nobody really cares."
Шеннонның шақ машинасы
1950 жылы Клод Шеннон мен Э. Ф. Мур аналогты Хекс ойнату машинасы құрастырды, ол негізінен жиектер үшін резисторлармен және төбелер үшін шамдармен жабдықталған кедергілер желісі болды. Жасалатын қадам желідегі белгілі бір анықталған қысым нүктесіне сәйкес келетін. Машина Хексті жақсы ойнады. Кейін ойынды шешуге және Хекс ойнайтын компьютерлік алгоритмдерді жасауға тырысқан зерттеушілер күшті компьютерлік ойыншыларды жасау үшін Шеннонның желісін үлгі етті.
About 1950, Claude Shannon and E. F. Moore constructed an analog Hex playing machine, which was essentially a resistance network with resistors for edges and light bulbs for vertices. The move to be made corresponded to a certain specified saddle point in the network. The machine played a reasonably good game of Hex. Later, researchers attempting to solve the game and develop Hex playing computer algorithms emulated Shannon's network to create strong computer players.
Стратегия
Бірінші ойыншының жеңімпаздық стратегиясын дәлелдеуден белгілі болғандай, алтыбұрыш тақтасында ешқашан шешілмеген күрделі байланыс түрі болуы керек. Ойын, "қауіпсіз байланысқан" деп аталатын қарапайым байланысқа ие кішкентай үлгілер жасаудан және оларды "жол" құрайтын тізбектерге біріктіруден тұрады. Әрі қарай, ойыншылардың бірі тастар мен бос орындардан қауіпсіз байланысқан жолды құрып, жеңіске жетеді. Ойынның соңғы кезеңі, қажет болған жағдайда, жолдағы бос орындарды толтырудан тұрады. "Қауіпсіз байланысқан" үлгі – ойыншының тастары мен бос орындардан құралған, қарсылас қалай ойнаса да, шетімен тігізген тастардың үзілмейтін тізбегіне біріктірілетін құрылым. Мұндай ең қарапайым үлгілердің бірі – көпір, ол бір түсті екі тастан және оларға жанаспайтын екі бос орыннан тұратын ромб тәрізді фигура. Егер қарсылас бір орынға ойнаса, ойыншы екінші орынға ойнайды, осылайша үздіксіз тізбек құрылады. Тастарды жиектерге жалғастыратын қауіпсіз байланысқан үлгілер де бар. Одан әрі, осындай қарапайым үлгілерден құралған, кейбіреулері өте күрделі, көптеген қауіпсіз байланысқан үлгілер бар. Үлгілер мен жолдарды қарсылас толық аяқталмастан бұзуға мүмкіндік бар, сондықтан нақты ойын кезінде тақтаның орналасуы көбінесе жоспарланған немесе жобаланған нәрсеге емес, жапсырма сияқты көрінеді. Ойынның ортаңғы бөлігі – мұндай нашар байланысқан тастар мен үлгілердің желісін құрудан тұрады.
From the proof of a winning strategy for the first player, it is known that the Hex board must have a complex type of connectivity which has never been solved. Play consists of creating small patterns which have a simpler type of connectivity called "safely connected", and joining them into sequences that form a "path". Eventually, one of the players will succeed in forming a safely connected path of stones and spaces between their sides of the board and win. The final stage of the game, if necessary, consists of filling in the empty spaces in the path. A "safely connected" pattern is composed of stones of the player's color and open spaces which can be joined into a chain, an unbroken sequence of edge wise adjacent stones, no matter how the opponent plays. One of the simplest such patterns is the bridge, which consists of a diamond of two stones of the same color and two empty spaces, where the two stones do not touch. If the opponent plays in either space, the player plays in the other, creating a contiguous chain. There are also safely connected patterns which connect stones to edges. There are many more safely connected patterns, some quite complex, built up of simpler ones like those shown. Patterns and paths can be disrupted by the opponent before they are complete, so the configuration of the board during an actual game often looks like a patchwork rather than something planned or designed. The middle part of the game consists of creating a network of such weakly connected stones and patterns
Белгіленуі
"Хекс теоремасы" деп аталатын алтылықтың теңдікпен аяқталмайтынын түсіндіру арқылы өзіңізді сендірудің қиын емес екенін көрсетеді. Яғни, тақта қаншалықты тастармен толтырылса да, әрқашан бір ғана ойыншы өзінің жиектерін байланыстырады. Бұл факт 1942 жылы Пит Хайнгә белгілі болды, ол оны Hex дизайнының шарттарының бірі ретінде Politiken газетіндегі мақаласында атады, бірақ дәлелді жарияламады. Оның алғашқы тұжырымы 1952 жылы жазылған ішкі техникалық есепте кездеседі, онда Нэш «байланыс және қарсыластың жолын кесу – эквивалентті әрекеттер» дейді. Ал 1961 жылы Джон Р. Пирс «Символдар, сигналдар және шу» атты кітабында оған нақты дәлел келтірді. 1979 жылы Дэвид Гейл екі өлшемді Брауэрдің бекітілген нүкте теоремасын дәлелдеу үшін де қолданылатынын, ал жоғары өлшемді нұсқаларының анықтығы жалпы бекітілген нүкте теоремасын дәлелдей алатынын көрсеткен дәлел жариялады. Hex-тің теңдікке келмейтін қасиетін бейресми түрде мынадайша түсіндіруге болады: қызыл жиектің бірінің байланысқан компонентін қарастырыңыз. Егер бұл компонент қарсы жақтанғы қызыл жиекті қамтыса, онда қызыл жеңіске жетеді, әйтпесе, байланысқан компоненттің шекарасындағы көк тастар көкке жеңіс әкелетін жол құрайды. Байланысқан компонент түсінігі дұрыс анықталған, себебі алтыбұрышты торда екі жасуша тек қана жиекте немесе мүлдем жанаспайды; жасушалардың бір нүктеде қиылысуы мүмкін емес.
It is not difficult to convince oneself by exposition, that hex cannot end in a draw, referred to as the "hex theorem". I. e., no matter how the board is filled with stones, there will always be one and only one player who has connected their edges. This fact was known to Piet Hein in 1942, who mentioned it as one of his design criteria for Hex in the original Politiken article. but apparently did not publish the proof. Its first exposition appears in an in house technical report in 1952, in which Nash states that "connection and blocking the opponent are equivalent acts". A more rigorous proof was published by John R. Pierce in his 1961 book Symbols, Signals, and Noise. In 1979, David Gale published a proof which also showed that it can be used to prove the two dimensional Brouwer fixed point theorem, and that the determinacy of higher dimensional variants proves the fixed point theorem in general. An informal proof of the no draw property of Hex can be sketched as follows: consider the connected component of one of the red edges. This component either includes the opposite red edge, in which case Red has a connection, or else it does not, in which case the blue stones along the boundary of the connected component form a winning path for Blue. The concept of a connected component is well defined because in a hexagonal grid, two cells can only meet in an edge or not at all; it is not possible for cells to overlap in a single point.
Бірінші ойыншының жеңісі, бейресми өмір сүру дәлелі
Хекста, алмасу ережесі жоқ кез келген nxn өлшемді тақтада, бірінші ойыншының теориялық жеңіс стратегиясы бар. Бұл фактіні Хайн 1943 жылы өткізген лекциясының жазбаларында атап көрсеткен: «көптеген басқа ойындардан өзгеше, теория бойынша бірінші ойыншы әрқашан жеңе алады, яғни ол барлық мүмкін ойын нұсқаларының соңына дейін көре алса». Осылайша, олар үстелде әрқашан бір артық фигурамен жеңіс стратегиясын қолданады. Бұл артық фигура бірінші ойыншының жеңіс стратегиясын қайталауына кедергі келтіре алмайды, себебі артық фигура ешқашан кемшілік тудырмайды. Демек, бірінші ойыншы жеңе алады. Біз екінші ойыншының жеңіс стратегиясы бар деген жорамалды жоққа шығардық, сондықтан екінші ойыншының жеңіс стратегиясы жоқ деген қорытындыға келдік. Осыған сәйкес, бірінші ойыншының жеңіс стратегиясы болуы тиіс.
In Hex without the swap rule on any board of size nxn, the first player has a theoretical winning strategy. This fact was mentioned by Hein in his notes for a lecture he gave in 1943: "in contrast to most other games, it can be proved that the first player in theory always can win, that is, if she could see to the end of all possible lines of play". In this way they play the winning strategy with one extra piece always on the board. This extra piece cannot interfere with the first player's imitation of the winning strategy, for an extra piece is never a disadvantage. Therefore, the first player can win. Because we have now contradicted our assumption that there is a winning strategy for the second player, we conclude that there is no winning strategy for the second player. Consequently, there must be a winning strategy for the first player.
Есептеу күрделілігі
1976 жылы Шимон Эвен мен Роберт Таржан кездейсоқ графтарда ойналатын жалпыланған «Алтылық» ойынындағы позицияның жеңіс позициясы екенін анықтау PSPACE-толық екенін дәлелдеді. Рейш бұл нәтижені конъюнктивті нормалық формадағы сандық Буль формуласын «Алтылыққа» келтіру арқылы күшейтті. Бұл нәтиже кез келген «Алтылық» позициясын шешу үшін тиімді (тақта өлшеміне қатысты полиномиалдық уақыт) алгоритмнің жоқтығын білдіреді, егер барлық PSPACE проблемалары үшін тиімді алгоритм болмаса. Ал бұл мүмкін емес деп кеңінен есептеледі. Дегенмен, бұл бастапқы позиция үшін (кез келген өлшемдегі тақталарда) немесе белгілі бір өлшемдегі тақтадағы барлық позициялар үшін қарапайым жеңіс стратегиясы болуы мүмкін екенін жоққа шығармайды. 11×11 «Алтылықта» күй кеңістігінің күрделілігі шамамен 2,4×1056, ал шахмат үшін – 4,6×1046. Ойын ағашының күрделілігі шамамен 1098, шахмат үшін – 10123.
In 1976, Shimon Even and Robert Tarjan proved that determining whether a position in a game of generalized Hex played on arbitrary graphs is a winning position is PSPACE complete. A strengthening of this result was proved by Reisch by reducing the quantified Boolean formula problem in conjunctive normal form to Hex. This result means that there is no efficient (polynomial time in board size) algorithm to solve an arbitrary Hex position unless there is an efficient algorithm for all PSPACE problems, which is widely believed not to be the case. However, it doesn't rule out the possibility of a simple winning strategy for the initial position (on boards of arbitrary size), or a simple winning strategy for all positions on a board of a particular size. In 11×11 Hex, the state space complexity is approximately 2.4×1056; versus 4.6×1046 for chess. The game tree complexity is approximately 1098 versus 10123 for chess.
Кіші тақталар үшін есептік стратегиялар
2002 жылы Цзин Янг, Саймон Ляо және Мирек Павалак қайта пайдалануға болатын жергілікті үлгілер жиынтығымен ыдырату әдісін қолдана отырып, 7×7 өлшемді Hex тақталарында бірінші ойыншы үшін нақты жеңіс стратегиясын тапты. Олар 2002 жылы 8×8 тақтадағы топологиялық сәйкес ашылулардың орталық жұбын, ал 2003 жылы 9×9 тақтадағы орталық ашылуды шешу үшін әдісті кеңейтті. 2009 жылы Филип Хендерсон, Бродерик Арнесон және Райан Б. Хейвард компьютерлік іздеу арқылы 8×8 тақтаның талдауын аяқтады, барлық мүмкін ашылуларды шешті. 2013 жылы Якуб Паулевич пен Райан Б. Хейвард 9×9 тақтадағы барлық ашылуларды, сондай-ақ 10×10 тақтадағы бір (ең орталық) ашылу қозғалысын шешті. Гарднер 1957 жылы Scientific American журналындағы бағанында алғаш рет, әлдебір жаңылыспен, қысқа диагональға жасалған кез келген бірінші қозғалыс жеңіске апаратын қозғалыс деп болжағаннан бері, n=9-ға дейінгі барлық шешілген ойын тақталары үшін бұл шындыққа айналды. Бұған қоса, n=2 және n=4 ерекшеліктерін есептемегенде, барлық тақталарда көптеген қосымша жеңіске жеткізетін бірінші қозғалыстар болды; жеңіске жеткізетін бірінші қозғалыстардың саны көбінесе ≥ n²/2 тең.
In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7×7 using a decomposition method with a set of reusable local patterns. They extended the method to weakly solve the center pair of topologically congruent openings on 8×8 boards in 2002 and the center opening on 9×9 boards in 2003. In 2009, Philip Henderson, Broderick Arneson and Ryan B. Hayward completed the analysis of the 8×8 board with a computer search, solving all the possible openings. In 2013, Jakub Pawlewicz and Ryan B. Hayward solved all openings for 9×9 boards, and one (the most central) opening move on the 10×10 board. Since Gardner first postulated in his column in Scientific American in 1957, albeit speciously, that any first play on the short diagonal is a winning play, for all solved game boards up to n=9, that has indeed been the case. In addition, for all boards except n=2 and n=4, there have been numerous additional winning first moves; the number of winning first moves generally is ≥ n²/2.
Нұсқалар
Басқа да ұқсас мақсаттарға қол жеткізуге бағытталған, бірақ құрылысымен ерекшеленетін байланыс ойындарының қатарында Шеннонның ауыстыру ойыны (сонымен қатар Гейл және Бридж Ит деп те аталады) және TwixT бар. Екеуі де белгілі бір дәрежеде ежелгі қытайлық Го ойынымен ұқсас.
Other connection games with similar objectives but different structures include Shannon switching game (also known as Gale and Bridg It) and TwixT. Both of these bear some degree of similarity to the ancient Chinese game of Go.
Төртбұрышты торлар, қағаз және қарындаш
Ойын шахмат, шашка немесе го тақтасы сияқты тікбұрышты торда ойналуы мүмкін, мұнда кеңістіктер (го тақтасындағы қиылыстар сияқты) бір диагональ бойынша, бірақ екіншісі бойынша емес, байланысты болады. Ойынды қағаз бен қарындашпен тікбұрышты нүктелер жиынында немесе екі түрлі түсті қарындашпен сол сияқты ойнауға болады.
The game may be played on a rectangular grid like a chess, checker or go board, by considering that spaces (intersections in the case of go) are connected in one diagonal direction but not the other. The game may be played with paper and pencil on a rectangular array of dots or graph paper in the same way by using two different colored pencils.
Тақтаның өлшемі
Стандартты 11×11 өлшемінен басқа, 13×13 және 19×19 өлшемдері де кең таралған, бұл ойынның ежелгі Го ойынымен байланысты болуының нәтижесі. "А Beautiful Mind" кітабында айтылғандай, Джон Нэш (ойының қалыптасушыларының бірі) 14×14 өлшемін ең тиімді деп саққан.
Popular dimensions other than the standard 11×11 are 13×13 and 19×19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14×14 as the optimal size.
Рекс (қайта қаралған алтылық)
Hex-тің қиын нұсқасы "Rex" деп аталады, онда әр ойыншы қарсыласын тізбек құруға мәжбүрлеуге тырысады. Rex, Hex-ке қарағанда баяу, себебі тең өлшемді бос тақтада жеңіліске ұшыраған ойыншы, бүкіл тақта толығанға дейін жеңілісті кейінге қалдыра алады. Тең емес өлшемді тақталарда, кім бірінші ойнаса да, екі жағы бір-бірінен алыс тұрған ойыншы жеңе алады. Тең өлшемді тақталарда бірінші ойыншы жақтағы ұяшықтардың саны жұп болғанда, ал екінші ойыншы тақ болғанда жеңіске жете алады. Жұп санды тақталарда бірінші ойыншының жеңіске жету мүмкіндіктерінің бірі – өткір бұрышта тас қою. Ол Hex-тен мынада ерекшеленеді: ол алтыбұрышты торда ойналады және үш түрлі пішіннің біреуін жасау арқылы жеңіске жетуге болады.
The misère variant of Hex is called "Rex", in which each player tries to force their opponent to make a chain. Rex is slower than Hex since, on any empty board with equal dimensions, the losing player can delay a loss until the entire board is full. On boards with unequal dimensions, the player whose sides are further apart can win regardless of who plays first. On boards with equal dimensions, the first player can win on a board with an even number of cells per side, and the second player can win on a board with an odd number. On boards with an even number, one of the first player's winning moves is always to place a stone in the acute corner. It differs from Hex in that it is played on a hexagonal grid of hexagons and a win is achieved by forming one of three patterns.
Проекс
Projex — нақты проективті жазықтықта ойналатын Hex ойынының бір түрі, онда ойыншылардың мақсаты — қысқартылмайтын цикл құру. Hex сияқты, тең түсулер болмайды және екі ойыншының да жеңіске жететін байланысы болатын жағдай жоқ.
Projex is a variation of Hex played on a real projective plane, where the players have the goal of creating a noncontractible loop. Like in Hex, there are no ties, and there is no position in which both players have a winning connection.
Қарақалқыт
Dark Hex (фантомдық Hex деп те аталады) – Hex ойынының толық емес ақпаратпен ойналатын нұсқасы. Ойын барысында ойыншылар бір-бірінің тастарын көре алмайды, оларды өздері таба алмаса. Ойын төрешінің қатысуымен өтеді, онда әр ойыншы жасаған жүрістің қарсылас тасқа тиесілігін алдымен тексереді. Осы мәселенің шешілуіне байланысты ойынның әртүрлі нұсқалары пайда болады.
Dark Hex (also known as Phantom Hex) is an imperfect information version of Hex. The players are not exposed to each other's stones at any point in the game unless they discover them first. The game is played in the presence of an umpire where each player first verifies the move if its a collision or not. Based on the continuation of this point the game has different versions.
Жарыс
2016 жылы Бразилия, Чехия, Дания, Франция, Германия, Италия, Нидерланды, Норвегия, Польша, Португалия, Испания, Ұлыбритания және АҚШ елдерінен турнирлер тіркелді. Ең ірі Hex жарыстарының бірі 2013 жылдан бері жыл сайын Париж қаласында Халықаралық математикалық ойындар комитетімен ұйымдастырылады. Hex сондай-ақ Компьютерлік олимпиаданың құрамына кіреді.
As of 2016, there were tournaments reported from Brazil, Czech Republic, Denmark, France, Germany, Italy, Netherlands, Norway, Poland, Portugal, Spain, UK and the US. One of the largest Hex competitions is organized by the International Committee of Mathematical Games in Paris, France, which is annually held since 2013. Hex is also part of the Computer Olympiad.