This is how the first article ever about Hex begins. It stresses very much the simplicity of the rules and yet the complexity that not even experienced chess players have been able to see through. Hein draws attention to the fact that two lines inside a square each connecting their pair of opposing sides must intersect.
So it must be possible to create a game that challenges two players to connect opposing sides so that only one can succeed. The chess board will not work, as problems will arise as soon as four or more cells meet at one point so at most three cells are allowed to meet. The solution which is most simple and regular is the hexagonal board and all that remains is to choose an appropriate number of cells.
Having explained the simple rules the article goes on to explain three possible relations between two cells: Contact [adjacent], angle [bridge] and across. The two first being secure connections and the third one unsecure. The advice is given that playing around the middle of the board is beneficial but certainly not necessary. An example of good opening play is given [this is, however exactly one of the openings that Cameron Browne shows not to be too good].
Concluding the article is a problem along with the promise that the following days will bring new boards, opening moves and problems. There was a prize for the correct solution to problem 1. They are both shown below. Problem 1: This is the problem that appeared with the first article on Hex on December 26, The task is to place one white marker on the board which makes a white win inevitable.
This day's paragraph shows how a game may begin. We notice a very close opening play resulting in the best position for black with bold numbers. Problem 3: White to move and win. Politiken December 28, New Year's day was the day that Politiken announced the winner of the first competition from December 26 but also made a new one.
The new competition was simply to play a game of Hex, number the moves and send it to Politiken. The best game would be awarded - not stating any criteria. In order to encourage new players the article says that: "Anyone can play Polygon. It is just to hit an empty cell and put one's mark there. It can be done with different talent, yes, but do you know if you do not have that particular ability?
Due to great interest and numerous requests Politiken decided to make pads with Hex boards. They cost only 0,50 Danish crown and contained 50 games ready to play with a pen or pencil. Some days only featured an advertisement for Hex as this one picturing a couple absorbed in playing Hex in an air-raid shelter and a woman from the civil defence telling them that the All-Clear was sounded.
The text in the middle begins: "Yes, one quite forgets one's surroundings - however disturbing they are - when one absorbes oneself in a game of POLYGON. Politiken had made pads with hex boards and sold them through bookstores all over the country. An advertisement from Politiken January 17, A woman from the civil defence sticks his head into an air-raid shelter saying: "Ladies and Gentlemen, the All-Clear was sounded!!
The mathematics department at Princeton University had maybe still has? Games were also a popular means for recreation - especially Chess and Go. John Nash was a graduate student at Princeton in when he reinvented Hex as and example of a game with a winning strategy for the first player. David Gale who was an older student there describes how Nash told him about the game, Gale immediately realising the playability of the game. Gale thus made the first board and donated it to the common room.
In Parker Brothers marketed the game for the first time under the name Hex in the United States. David Gale tells that he received a call from Nash in the mid-fifties who had seen the commercial game and accused him of double crossing, selling the game behind his back. Gale maintains that he didn't, but we can assume that Parker Brothers learnt the game from someone at Princeton.
Martin Gardner wrote a column on Mathematical Games for Scientific American for 30 years between and In he gave an account of Hex in which he tells that Hein is the inventor. This column, together with a book of reprinted columns, made Hex popular and encouraged some research. Gardner was a close friend of Piet Hein and so was able to describe the initial history quite accurately. The column also contains an outline of Nash' proof of the first player win and a mention of some variants of Hex.
Piet Hein was born on December 16, so this year he would have been ! He was from a family of scholars and related to the famous author Karen Blixen. Scientists and artists frequently visited his family and the author Johannes V. Jensen is said to have inspired him to write poetry. Before finishing his studies he went back to Copenhagen to study theoretical physics under Niels Bohr who was also a friend of his family. He did not graduate from The University of Copenhagen either but commenced inventing technical wonders and games, writing poetry and agitating for intercultural understanding and cooperation.
He mainly wrote small poems, in time developing a distinct style, which he called 'grooks'. These are probably what Hein is best known for - in Denmark at least. Hein also contributed to architecture and design.
He is particularly known for his use of the Super Ellipse for a traffic problem in Stockholm as well as a famous table used at the Vietnam conference in Paris His father, John Nash senior was an electrical engineer and provided him with an encyclopedia and gadgets to stimulate his scientific interest.
As a young schoolboy he showed great talent for mathematics and chemistry and for a while actually studied chemistry but changed to mathematics towards the end of his undergraduate study. In at the age of twenty, Nash was accepted into Princeton University as a graduate student of mathematics with very good recommendations. It took Nash only a little more than a year to finish his 27 pages Ph.
After receiving his degree in Nash went to Massachusetts Institute of Technology to teach. Having married and expecting his second son, Nash fell victim to a serious case of schizofrenia forcing him to leave his job and a promising academic career for around 25 years.
His contributions to both game theory and geometry had meanwhile increased in significance and in he was awarded the Nobel prize in economics, sharing with John C. Harsanyi and Reinhard Selten. Nash's mental condition had been improving but the recognition apparently gave him a final push back into the real world.
Nash resumed his research at Princeton and has since been working on a mathematical model for the expansion of the universe as well as game theory and geometry.
As long as a good algorithm does not show up for determining a winning strategy in the general case, there will be a continued effort to improve the tiny knowledge that we have. OHex is building game trees in order to be able to predict outcomes of given board positions. Jing Yang is a computer scientist at University of Manitoba, Canada who has restricted his search to narrow parts of the board. Yang has succeeded in tracking a winning strategy for a specific opening on the 9x9 board.
We already know from Nash's proof that there is a winning strategy and Yang supplies us with one of them. Yang takes advantage of a main property of Hex, namely what he calls 'sudden death'. This notion refers to the fact that quite a lot of moves in Hex are forced, which means that most of the defender's options will result in a quick loss, thus cutting of large branches of the game tree. The approach taken by Yang is a method which consists in decomposing a board position into disjoint groups of cells each constituting a secure connection and in conjunction a winning connection.
The method is closely related to the development of edge templates but also considers the inner board and allows the opponent's piece when necessary. The decomposition method is one that most players apply mentally when playing. Experienced players recognize the simpler structures, simply remember the local winning strategy and thus saves a number of computations.
Yang has so far applied his method to boards of up to 9x9 manually but it definitely has a potential for automation.
The approach is to consider a specific opening and then decomposing the board into two subgames, each connecting the opening piece to a side. In turn, these subgames decompose into subgames of their own. As an example of the decomposition method, I have made a reconstruction of a winning strategy for the opening D3 on the 5x5-board. I shall post this here shortly. Notice how easily one follows the strategy and confirms its validity.
Having examined and solved a number of local patterns it becomes a lot easier to evaluate a board position. It was invented by Piet Hein in and John Nash re-invented the game in Tipping Point Math has a video that explains the rules of the game and proves why the game never ends in a draw.
There is an even stronger result: the first player always has a winning strategy! While the winning strategy is not known, it can be proven that the first player can win for sure, with perfect play. In the rest of the post, I will summarize the rules of the game and then explain how to prove the first player has a winning strategy. MindYourDecisions now has over 1, free articles with no ads thanks to community support!
Help out and get early access to posts with a pledge on Patreon. Two players Red and Blue alternate placing stones on the board. Red owns two opposite sides of the board, say North and South, and Blue owns the other opposite sides, say East and West. The goal is to make a connected path of pieces between the two sides a player owns. The first player to do so wins the game. The board shown below is a win for Red, for example. The red pieces form a continuous chain from the North side to the South side.
Second, highlight all of the edges between a red stone and a blue stone. In other words, imagine the neighboring stone off the board is the same color as the color that owns that side. Third, there will be two highlighted paths, where each path connects two corners of the board, to be proven in a moment. Because each highlighted path connects stones of opposite colors, the color on one of the sides will have a continuous path from one side to the opposite side—this is a victory for that player.
The board shown below is a victory for red. Why must there exist such a highlighted path? Consider the edges where 3 hexagons meet. If all are the same color, there will be no highlighted edges. Otherwise, there will be 2 of one color and 1 of another, resulting in 2 highlighted edges. Furthermore, each corner piece of the board is owned by Red on one side and Blue on the other side.
If a blue stone is placed on a corner, the edge on the Red side is highlighted. If a red stone is placed on a corner, the edge on the Blue side is highlighted.
Each corner always starts with a single highlighted edge. Then, the highlighted edge from the corner has to continue to keep growing in a chain. Each intersection of the hexagons must have 0 or 2 highlighted edges. Since the intersection already has 1 highlighted edge, it cannot have 0 edges. Therefore the intersection must have 2 highlighted edges, which means the chain continues to grow to a connecting highlighted edge. Also the chain cannot self-intersect and loop back—because that would result in 3 highlighted edges, which is not possible.
The chain has to end at some point, and the only possibility is that it ends at another corner which can have only 1 highlighted edge. A Game of Candy Squares. A Sticky Problem. Another Sticky Problem. Dawson's Chess: an Interactive Gizmo.
Dawson's Kayles: an Interactive Gizmo. Nimble: an Interactive Gizmo. Northcott's game An Interactive Gizmo. One Pile: an Interactive Gizmo. Plainim An Interactive Gizmo. Plainim Misere An Interactive Gizmo. Scoring: the simplest of the impartial games. Scoring Misere: an Interactive Gizmo.
0コメント