Talk:Hex (board game)
|WikiProject Board and table games||(Rated B-class, Mid-importance)|
- 1 Move
- 2 Servers
- 3 PSPACE vs. EXPTIME
- 4 Tie games
- 5 Game board graphic
- 6 Brouwer fixed-point theorem
- 7 Examples and more details for Template Section
- 8 Future FA?
- 9 board representations
- 10 Cameron Browne's book
- 11 Nash and Connection games sub-genre
- 12 14x14?
- 13 Go strategy
- 14 First-player strategy
- 15 first proof of PSPACE completeness
- 16 HexWiki a wiki dedicated to Hex
- 17 John Nash apparently did not independently invent Hex
- 18 Shannon switching game/Gale/Bridg-It
- 19 Strategy section
- 20 Theory and proofs: strategy stealing agument
- 21 John Nash said?
- 22 Variants section
- 23 Embellish article with images
- 24 Some history of Hex
OK, I moved this from Hex (game) to here as some anon IP did it by cut and paste. Rather than argue, I just deleted that and moved it properly. This does seem an acceptable place, ie we have Go (board game)... Evercat 21:16, 31 Aug 2003 (UTC)
is there a hex server somewhere on the net?
for example, on [deleted link], they have go, chess, checker, reversi, chinese checker.... and there's lots of go servers around. But never seen a hex server. P0lyglut 07:35, 2003 Nov 27 (UTC)
There are three realtime Hex servers that you might be able to find an opponent on.
A relatively popular server these days is [deleted link] which is based in France. BGA offers grid sizes 6x6, 11x11, 14x14, and 15x15.
Game Center (linked below) may have stronger players. If you start a game table in all three servers, you may be more likely to snag an opponent.
[deleted link] is Spanish. They have a new client which offers odd sizes from 9x9 to 15x15. English menus are available. The board is oriented like a diamond instead of "tipped over" on the other servers. On Wednesdays a real time tournament takes place if there are enough participants.
You can play Hex in real-time on [deleted link]. It supports different board sizes.
--artyomch 04:10, 21 Jun 2008 (UTC)
- See [deleted link] —Kri (talk) 00:19, 22 January 2012 (UTC)
PSPACE vs. EXPTIME
PSPACE and EXPTIME are terms in computational complexity that measure the difficulty of a problem (how long it takes to solve a generic instance of the problem in terms of the size of the input). I added a few sentences to clarify. Basically, it means that we know that generalized chess is at least as hard as generalized hex, but most experts think chess is probably harder. --Ptrillian 22:24, 1 January 2007 (UTC)
Why can the game never end in a tie? It seems plausible, but how does one prove it? pstudier 06:52, 2004 May 27 (UTC)
OK, suppose the game is over, and neither player won. Then the whole board is filled with your stones and your opponents stones, or the game wouldn't be over. Now consider one of your home edges, and all of your stones connected to that edge. That mass of stones doesn't reach your other home edge, or else you would have won. So consider the frontier of that mass of stones. All of the frontier must be either your opponent's stones, or your opponent's edges, because the whole board is filled. That frontier must connect your opponent's two home edges (a topological fact unless the board has holes). But that means he must have won: a contradiction. Therefore the original assumption that the game was a tie is false. This isn't a formal proof, but it may be enough for informal conviction. --Fritzlein 19:44, 28 May 2004 (UTC)
Another way to look at it (more informal than the version Fritzlein gave) is to try to build a tie in an actual board, or think what a tie must be. You'll see quite easily that it is impossible. RBerenguel 09:40, 9 November 2007 (UTC)
The article is underselling Nash's contribution. Nash showed that not only must the game have a winner (which is relatively easy to verify on these space filling games), but that there is a winning strategy for the first player. i.e. if player 1 plays a perfect game he will win. —Preceding unsigned comment added by 22.214.171.124 (talk) 15:09, 12 June 2009 (UTC)
Game board graphic
Is the giant Go board really necessary on this page? This should be describing the game Hex itself, not the way a particular image of a board has been created. --ambience 04:16, 9 Jan 2005 (UTC)
First of all, that was a Hex board, not a Go board. Each internal vertex had six lines radiating from it, not four. The board was a diamond shape, not a rectangle. And did you see the border colors?
I apologize for including my description of how it was made. I apologize if the image was too large to suit you. I could make a smaller image if there is interest. Does anyone besides me think that such an image does indeed describe the game of Hex? Twixter 16:50, 27 Feb 2005
I don't have a problem with the image. It was kind of large when it was horizontal, so I rotated it a while back, but it seems appropriate. If it's still too large you could try specifying a certain pixel width in the article tag. Might make it less jaggy too. DreamGuy 04:44, Feb 28, 2005 (UTC)
DreamGuy, you and I are talking about two different images. I created a POV-ray perspective image of a Hex board. It has been removed. You can see this image in the previous revisions of the Hex (board game) page. I now have a smaller version of the image:
I would be glad to include it on the main page for Hex, without the extraneous discussion I foolishly added the first time. But first, I would like to know if anyone would be interested in it besides me.
And regarding what you did to the other image, I'm sure you meant well, but when two players sit down for a face to face game, they don't orient the board like that. An image serves other purposes than simply fitting on the page well. Some players might like to rotate the board 30 degrees from horizontal, since that is how several servers display it, but not 90 degrees for heaven's sake! That vertical image is disturbing to the eyes of any Hex player. I urge you to rotate it back again.
--Twixter 17:57, 4 Mar 2005 (UTC)
- Hrm, I somehow missed the other one showing up and being removed. Doesn't yours have too many spaces? And the way it looks it could be a square board in perspective. Regarding the orientation of the graphic currently there, it's a top view, not a view from where someone playing would be sitting... players don't hover 5 feet above the board when they play either way, right? DreamGuy 18:59, Mar 4, 2005 (UTC)
How many spaces is too many? It's a 19x19 grid. That's not too many for the 282 players who have enjoyed playing 19x19 on Little Golem. Should I repeat myself? There are six lines radiating from each interior vertex. Perhaps "the way it looks" depends on how closely you look at it. Either you like it or you don't, I guess. No reason is necessary.
Yes, the current graphic is a top view. So are the graphic displays on Little Golem, Kurnik, and all the other Hex servers, both real-time and turn-based. All of them show the board oriented so the long diagonal is either horizontal or 30 degrees off horizontal. That's how the vast majority of Hex games are played these days: on the Internet. These vertically oriented images are, well, disturbing. In my opinion they do not describe the game of Hex, as it is played by so many people, as well as it would if they were rotated back. --Twixter 14:29, 8 Mar 2005 (UTC)
I think we lack a user-box capable graphic, in my user page I just put a hexagon, but it lacks some visual appeal. Does anybody mind adding some kind of Piet Hein problem (the one 3x3 would be dear) to this page? This way we could use it to create an user box. RBerenguel 16:24, 9 November 2007 (UTC)
Brouwer fixed-point theorem
In sect. Theory and Proofs one reads
An important consequence of the determinacy of hex is the Brouwer fixed-point theorem which was shown by David Gale.
I'm not sure I fully understand what is meant, but it is clear that the Brouwer fixed-point theorem is not a consequence of the hex game (and this theorem was not "shown by Gale" but by Brouwer) ; maybe the other way round ? — MFH:Talk 12:20, 24 October 2006 (UTC)
- I had the same question but it checks out; I read through a summary of the results in the cited article (American Mathematical Monthly) on MathSciNet. Gale's proof was certainly not the first nor the most important, but he does show equivalence of the two theorems. The fixed-point theorem in n dimensions requires a different but related n-player game. I've tried to make this clearer in the article. Tracy Hall 17:55, 22 March 2007 (UTC)
Examples and more details for Template Section
I'm a new contributer to wikipedia, so I'm still trying to learn the nuances of what other contributers believe the purpose of wikipedia is. I think it would be a good idea to add examples of some templates (at least 5 or 6 of the smaller ones) along with the analysis to explain why a template is connected. I like one explanation I read (perhaps in Browne's book, I don't recall) of 2-connectedness. The reason a template (or any winning position) works can usually be explained well in terms of being 2-connected. I.e. "if he moves there, then I move here to stay 2-connected." Do others agree that this would be a useful addition? If so, does anyone have ideas about a good way to create the images of the templates. I could probably write up a decent explanation, but it wouldn't do much good without pictures. What do people think? --Ptrillian 21:55, 1 January 2007 (UTC)
Certainly 2-connectedness is a very basic concept which is essential to nearly all Hex strategy. I would prefer not to submit any more images to Wikipedia, but it shouldn't be difficult for someone else to use a Hex tool such as Jhex or Ohex, an image capture tool, and an image editor to show whatever patterns or templates you wish to. Please be sure to verify that your image is your own creation and that you release it to the public domain, when you upload it.--Twixter 02:50, 12 February 2007 (UTC)
I think this article has much room for adding new things. I can imagine tons of different images and mathematical information. I feel that it has the potential to be an FA. Compare with chess, a featured article. Below are the subtopics from the chess article and how a corresponding section could be made for hex.
- Rules - got that.
- History - easy to expand. The current article does not include information about anything past the year 1952, except for the mention of Cameron Browne's Hex Strategy.
- predecessors - Hmm...
- origins - Hmm...
- birth of a sport
- Place in Culture - well... Place in Mathematical Culture?
- Notation for Recording Moves - Easy to add.
- Strategy and Tactics - enough info about this out there, I believe
- fundamentals of strategy - doable.
- fundamentals of tactics - I think templates, ladders, and such belong here.
- opening - easy to add, already have some external links
- middle game
- endgame - I think the closest thing to an endgame in hex is where one player realizes he/she has a winning connection. But I still think it's possible to write a blurb about that.
- chess composition - there are a few problems on HexWiki that are usable
- competitive play
- organization of competitions - mention online playing sites like kurnik, boardspace, littlegolem; mention the ICGA
- Titles and rankings - well... according to HexWiki, "champion" on littlegolem is currently the most prestigious title
- Mathematics and computers - mention programs, algorithms; solutions for the game without the swap-option...
- psychology - nothing.
- Variants - got that
Leon math 18:25, 9 April 2007 (UTC)
- The problem is that there's only a single book ever written on Hex, and it's not by a recognized champion or game authority. Nor is there any magazine where Hex is regularly or even periodically featured. There's no commercial publication of the game (the Parker Brothers and Danish editions are long out of date and unavailable). There's little sponsored competition and no references for exemplary games to illustrate play of the game. The history of the game is largely confined to its invention. It's an exceedingly rare game in play; most of the interest is research related topology, graph theory and combinatorics. Those are arcane topics to go into in a board game article.
- The article as it stands today, after much reoganization, additions, and citations, is barely 'B' class (though it was undeservedly classified 'B' before); the problems remain coverage, citations, and a large chunk of probably original research (though might be able to cite Browne's Hex book). We're a long way from FA, need to focus on getting the basics of a concise scholarly article first. Sbalfour (talk) 18:04, 24 January 2017 (UTC)
That board is just like a go board except with diagonal lines drawn in one of two directions. Does this mean hex can be played with a go board?
Cameron Browne's book
The article said: [Cameron Browne]] wrote a book entitled Hex Strategy: Making the Right Connections, which covers Hex strategy at a greater level of detail than any preceding work. However, some Hex players feel that this book contains many factual errors and advocates questionable strategies.
However, if we check the sources, they say e.g. Players have questioned some of the advice given. This is completely different to his book contains many factual errors and advocates questionable strategies. The other source says basically that there are things Browne does not mention. That is even less support for the wording.
I think there is only one book specifically dealing with Hex strategy, and although it may not be perfect, I'd like to see its name or some way for user to find it via wikipedia (of course one could google "hex book"). --Halladba (talk) 15:38, 18 November 2008 (UTC)
Nash and Connection games sub-genre
Did Hein and Nash invent not only Hex but the entire sub-genre of connection games which require side-to-side connections to win (Hex, Twixt, Gonnect, etc)? —Preceding unsigned comment added by 126.96.36.199 (talk) 07:17, 15 February 2009 (UTC) This mechanism in itself, one gathers, is totally original and unprecedented, but this has never been stated clearly in anything I have read. —Preceding unsigned comment added by 188.8.131.52 (talk) 07:23, 15 February 2009 (UTC)
The claim that Nash thought the winner of Go was determined by chance and not strategy is in serious need of a credible reference; Go is quite obviously a game that involves an enormous amount of strategy - a fact well known among computer programmers and laypersons alike. I will be very surprised if the man who invented game theory held such an obviously fallacious opinion about Go. Failing the addition of a credible citation, this claim (pardon the pun) needs to Go! Spiral5800 (talk) 10:22, 18 February 2011 (UTC)
- Indeed it requires a citation! But note (1) that game theory has little to do wth games like go and hex (which of course doesn't mean that Nash wouldn't be aware that go is a strategy game with perfect information), and (2) go is - unlike hex - so complex, so far outside what any supercomputer could analyse, that among roughly equal players (or players matched with a suitable number of handicap stones), the outcome at the end of a long game has for all practical purposes a substantial element of randomness. I'm not saying the claim in the article is right, or that the claimed claim by Nash is right - but that it might be, in a sense.--Nø (talk) 11:57, 18 February 2011 (UTC)
Who has the winning strategy when the pie rule is used? (My guess would be the second player, since he can "become" the first player if he wants, and he has a winning strategy wherever the first stone is placed for him.) If anyone knows could they add it to the article? — Preceding unsigned comment added by 184.108.40.206 (talk) 21:10, 23 May 2012 (UTC)
- You are correct: the second player can win under the 'pie' rule. The first player can make a move in either of two sets: moves which maintain his winning advantage, and those that do not. If both players play perfectly, and the first player makes a winning move, the second player will swap the board; if the first player makes a losing move, the second player will let him keep it. However, no players are good enough to play perfectly. The real purpose of the rule is to cause the first player to make a weak but plausable move, to equalize the winning changes of (imperfect) players. Sbalfour (talk) 19:45, 20 January 2017 (UTC)
first proof of PSPACE completeness
The first to prove that HEX is PSAPCE complete were Shimon Even and Robert Tarjan. The proof was published in S. Even and R. E. Tarjan. 1976. A Combinatorial Problem Which Is Complete in Polynomial Space. J. ACM 23, 4 (October 1976), 710-719. DOI=10.1145/321978.321989 http://doi.acm.org/10.1145/321978.321989 --220.127.116.11 (talk) 21:20, 15 October 2013 (UTC)
HexWiki a wiki dedicated to Hex
This external link is down:
We currently have some problems with the database. Please come back in a few daysweeks. The provider has been unable to fix his database for the last three months.
- Your promotional link to an external wiki unrelated to Wikipedia has been deleted (apparently), and properly so. Wikipedia is not responsible for that site, and the talk page of this article is not a forum for general discussion of hex or playing hex. It is solely for discussion of content and editing of the article. Sbalfour (talk) 21:53, 24 January 2017 (UTC)
John Nash apparently did not independently invent Hex
If true, a lot of references to Hex across the Internet, not just this page, would need some serious editing. But the above reference is not solid enough for that IMO. If you, dear reader, happen to know more about this, or can afford to access the ICGA journal, 38:2, pp.126-7, any verifiable detail would be appreciated. --Twixter (talk) 08:11, 1 January 2017 (UTC)
Shannon switching game/Gale/Bridg-It
These games aren't really derivatives or variants of Hex; the nature of their connectivity is different (hex is 6-connected, Shannon's game is 4-connected generally) and this gives rise to profound differences in proofs and strategy: the Shannon game is representable as a binary matroid, and is solved. Hex is not a binary matroid; the strategy is very much more complex. I think I'm going to pull Gale/Bridg-It into a separate article, or merge these subsections into the article on the Shannon switching game, which they ARE closely related to, as in synonymous.Sbalfour (talk) 15:33, 15 January 2017 (UTC)
The Strategy section is bare bones, more like an example section, like showing a castled king position or checkmate position in chess. It borders on WP:ORIGINAL RESEARCH. We might be able to cite Cameron Browne's book. But if we go much further, we'll have a WP:GAMEGUIDE. Take a look at historical versions of the TwixT article for what NOT to do. I'm at a loss for how to make this section useful as well as terse and scholarly. In chess, there's openings, endings, combinations and position play. Maybe that'd be a good outline here.Sbalfour (talk) 21:54, 17 January 2017 (UTC)
I've added a bird's eye view description of the strategy, by breaking the objective of the game, to complete a chain between sides, into three steps or phases of the game. I adopted an unfortunate term 2-connectedness for an inherent property characterizing the phases, because that term is already used in the text (borrowed from its usage in the literature) to mean a path between points which contains two open cells. My terminology is original; a similar term by Anshelevich is "virtual connection", i.e. virtual connectedness, though he uses the term only in a local sense as a reduction element in heuristic search. Maybe dual-connected could be substituted to resolve the ambiguity.
Even if the terminology were changed, my argument itself contains an ambiguity born of terseness and simplicity of statement. The connectivity of the open board at the first move is not of the same kind as 2-connectedness: 2-connectedness implies that the player for whom it exists could "pass" if that were permitted by the rules (in practice, he could make a random move) and still win. That is not true on the open board: the first player must make a move from a small set (at least 11 cells on the short diagonal and possibly 25 or more clumped around it) in order to preserve a win. Nor is it exactly 1-connected, where the putative path between points (or edges of he board) requires filling in one cell to join two chains, i.e. the set of cells to be played contains a single cell. 2-connectedness is analogous to the connectivity of the Shannon switching game, wherein the board can be inscribed with two edge-disjoint spanning trees. The connectivity of the open hex board cannot be inscribed with a pair of such trees - the initial part of the game consists of reducing that connectivity to the Shannon-type connectivity. Yet, even that may not be enough for recognition of the 2-connected property: the corresponding edges of the dual trees may not enjoy a simple adjacency propiquinty, but can be remote from each other. Elaborating the stated argument loses something in brevity and elegance for precision. It is in a more general sense true that the hex board contains a property of complex serial connectivity analogous to the binary static connectivity of the Shannon game, which is to be preserved (or broken in the view of he second player). It is also true that that complex connectivity may not be resolved into 2-connectedness during the course of the game, though it almost universally occurs well before a recognized end to the game. It is precisely the nature of this connectivity which is the unsolved aspect of hex; it may be that solution of hex depends on defining how that connectivity can be resolved into 2-connectedness given the alternating turns of play. Sbalfour (talk) 16:18, 24 January 2017 (UTC)
I've replaced the strategy section, in line with similar (brief) sections in other articles. The strategy section is now colloquial rather than formalistic with definitions, etc. The phrasing contains a minimum of game jargon. It is more like a description of game play of interest to a general audience: is the game thoughtful (chess) or casual (yahtzee); how are the board and game pieces used; are there characteristic phases or maneuvers during play; what skills are required? It contains a minimum of game-specific details. Finally, the strategy section is very brief - it doesn't swamp the article presentation space, or distract attention from the rest of the article with glitzy diagrams, tables or illustrative positions from the game. This type of description could comfortably be fitted into a Description or Gameplay section, obviating the need for a separate Strategy section altogether. It should be emphasized that no strategy section is required for GA and except in rare cases (chess is one) for FA. Its presence is an adjunct to a concise but complete scholarly article, not a constituent part of it. If an article would suffer for its deletion, the article and strategy section need to be restructured so all essential information is integrated elsewhere. Sbalfour (talk) 17:29, 28 January 2017 (UTC)
Theory and proofs: strategy stealing agument
The argument has been badly botched. Consider for example the simple statement that if it's been proven that the game can't end in a draw, then one player or the other has a winning strategy. Suppose that the markers are placed on the board alternately by lot. By the time the 121st marker has been placed, one player or the other MUST have won. But neither player has a winning strategy! That is, neither player can FORCE a win. Sheeesh. The argument either needs to be deleted entirely (just say it's been proven that the first player can win), or write that argument in correct prepositional logic.Sbalfour (talk) 23:40, 17 January 2017 (UTC)
I've restored the argument from Gardner's rendition of it in Scientific American. It's still very informal, but considering the informal presentation of the article itself, it'll do for now. Sbalfour (talk) 22:00, 24 January 2017 (UTC)
John Nash said?
If John Nash said or proved something, it must be sourced - a citation to a peer-reviewed professional journal. Otherwise, the statement cannot remain in the article. I'm removing all such unsourced or improperly sourced statements.Sbalfour (talk) 06:05, 18 January 2017 (UTC)
Trying to ref the Variants section, it appears that someone perused the IG Games website and copied all the Hex-like games to here. Easy effort, no scholarship. The list isn't unduely long; the issue is the notability of the items on it. Wikipedia isn't an almanac or gamesite. I propose the following criteria for including/excluding items from the list:
Inclusion criteria (at least one of):
- 1. there is a published book devoted to the game, or at least a whole chapter in a book devoted to the game
- 2. there is at least one paper in a peer-reviewed professional journal devoted exclusively to the game
- 3. there is a commercially published game product
- 4. there's a registered patent, trademark or copyright for the game even if it isn't published
- 5. there's regulated national or international level competition in the game
- 6. there's a wikipedia article for it (somewhat dubious - there's a lot of wiki articles on non-notable things)
- 7. it's listed on the Game Geek website (somewhat dubious)
Exclusion criteria (any single one excludes)
- 1. games that aren't direct descendants of Hex (i.e. Shannon switching game)
- 2. if there are fewer than three online descriptions of the game
- 3. games not structurally similar (i.e. not a maker-breaker positional game, not planar, etc)
Three, possibly four, of the items currently on the list would be excluded applying these criteria. What I suggest for these, is to provide a link in the external links section to gamesite(s) where hex variants can be found for gamers (when THAT section overflows with gaming website links, we'll have a separate issue).
Embellish article with images
The article has only 3 images, and two of them are dubious: the one illustrating a winning chain doesn't look anything like a chain in an actual game, and may be deceiving (the distribution of stones isn't like that, and Hex is seldom played to the state of a complete chain, just as chess is seldom played to checkmate). The picture of hex on a go board doesn't depict a standard or common playing surface (how about a picture of a 1947 Con-Tac-Tix board, or a 1952 Parker Brothers Hex game board and pieces?)
I find it challenging to imagine what the pattern configurations for path, template and especially ladder look like without a picture, and I'm a hex player. It's like trying to play chess blindfold. I also think we need one or more examples of how these patterns are combined into chains. A few 3 or 4 move opening patterns to illustrate potential connection to templates would also be an appropo addition.
It might also be useful to illustrate how the game develops on 2x2 thru 5x5 boards, because the utility of the patterns is immediately apparent there. This gets to be more of a "magazine" type presentation rather than a scholarly one, so need to keep it concise.
It also seems almost essential to illustrate the asymmetry of the pairwise 2-connectivity paradigm with an obtuse position showing how a play in one area of the board may result in a response in another seemingly unrelated area.
Some history of Hex
Sbalfour added a tag noting that statements about the game being popularized in 1942 Danish newspapers, and being manufactured for sale by Piet Hein, really did need some sources. I added a source, from the book "Hex Strategy", about the 1942 newspaper article that first described the game. That book also mentions that Piet Hein marketed the game in 1968, but does not mention any company associated with that marketing, which I think Sbalfour wanted. The book's source for this is a dead Internet link, but that link is still available on Internet archives. That link also fails to mention any company (I wonder if Hein just marketed it himself?). If anyone wants to look at that link to see if there's more information that should be absorbed into this article, it's at: http://web.archive.org/web/20020214224326/http://members.iex.net/~rfinn/gameshlf/abstract/hex/hex.htm . Darrah (talk) 01:43, 26 January 2017 (UTC)
- I just now mailed the company marketing Con-Tac-Tix and other Piet Hein-related products today, . They say it was manufactured back then by a company called Skjøde Knudsen, or more precisely, Th. Skjøde Knudsen, Skjern. (Th. is short for a first name like Thorvald or Thomas; Skjøde Knudsen a family name; and Skjern, Denmark is the town where the company was situated.) With this information, I've googled the following pages:
- So, I have little doubt this is the correct answer, but I don't know if any of these may be considered a valid source. I'll not add anything right now, but knowing the answer may make it eassier to find a source!--Nø (talk) 09:49, 26 January 2017 (UTC)
- Cameron Browne. Hex Strategy: Making the Right Connections. ISBN 1568811179.
- http://maarup.net/thomas/hex/hex3.pdf page 83
- Anshelevich, V. (2000). The Game of Hex: A Hierarchical Approach. Combinatorics Workshop, Berkeley