Hex: A Strategy Guide | Hacker News Reader

Hex: A Strategy Guide

mseymour.ca

158 pointscreata43 comments

I wrote a hex AI with a couple of friends a few years back based on reinforcement learning.

https://cleeff.github.io/hex/

You move first and the ai might swap meaning that it steals your first move and you swap colors. This enforces you to pick an even opening.

I'm very bad at hex but it still was an awesome experience to observe the ai surpass my performance.

Thanks for making this! As a fellow very bad hex player I have had a lot of fun inevitably losing to the agent.

You might be interested in this - the one time I won, it seemed like a bug? I was playing red and blue could have easily won, but threw the game?

https://i.imgur.com/4uyipte.png if blue goes on the other 6.4 spot blue probably wins, if not red wins. Honestly I was about to give up on the game because the ai plays "mean" as noted in the readme - it always does close out favorable positions but doesn't prioritize the simplest/quickest win. This time I was annoyed at it or something though and playing it out was really surprised at that move it made.

This may or may not be relevant, but it's interesting that the agent rates both the correct move and the move it made at 6.4, maybe that was part of the problem?

On Nintendo Switch, Clubhouse Games includes hex: https://www.nintendo.com/store/products/clubhouse-games-51-w...

(There's a lot of other really fun and interesting games there too BTW - it's been very popular in our family.)

This complements the 2019 book

Hex - The Full Story by Ryan B. Hayward and Bjarne Toft

https://webdocs.cs.ualberta.ca/~hayward/hexbook/hex.html

I have not read it, but it likely complements another Hex strategy book: Hex Strategy: Making the Right Connections by Cameron Browne.

[1]. https://www.google.com/books/edition/Hex_Strategy/tR7XkqeV31...

Man, this brings back memories. In high school I made a version of this game for TI-89 BASIC. One of the first programs I ever released. I even made a silly AI for it just based on some basic heuristics because I had no idea how to make an AI back then. https://www.ticalc.org/archives/files/fileinfo/106/10660.htm...

The site also has a ton of hex puzzles: http://www.mseymour.ca/hex_puzzle/hexpuzzle.html

Those are very nice, and teach you the strategy very intuitively.

I used to play this game quite a lot, back when Six was the strongest AI opponent. Managed to beat it at 11x11, no chance at 8x8. At 13x13 it completely fell apart (but you had to kind of hack the engine to even play at that size, so it might have been buggy). Now I guess the AlphaZero-variants win everything there as elsewhere.

There was a kid from Poland who was insanely good. Maciej Celuch. Don't know what's become of him, but wouldn't be a kid any longer. He was the top player by a mile, won the Little Golem tournaments every year he participated. A bunch of people from the same town in Poland were also really, really good, I guess they had a bit of a community going.

The other place there was a bit of community going was in Oslo, a bunch of guys associated with the defense research institute (FFI). I went to an offline tournament with them once, to my surprise I didn't finish quite last.

I think it's a satisfying game, because it's quite easy to learn to look far ahead. Since the pieces stay put, it's much easier to reason about positions.

M. Seymour's online book is great, too. I've heard good things about Ryan B. Hayward's book. Cameron Browne is a nice guy and has done a lot of other cool work in combinatorial games, but I can't recommend his old Hex book. The tactics advice is not good.

Check this bit of info out, also the entire blog, and also their created games

https://www.nickbentley.games/abstract-strategy-games-online...

Some other games in the immediate family:

Y https://boardgamegeek.com/boardgame/5242/game-y (from 1953)

ConHex https://boardgamegeek.com/boardgame/10989/conhex

Away Across https://boardgamegeek.com/boardgame/30988/away-across (Sid Sackson game from Calculate! - a set of math games)

Lightning https://boardgamegeek.com/boardgame/35528/lightning (from 1892 - possibly the first connection game - https://patents.google.com/patent/US471666A/en?oq=US471666)

Thoughtwave https://boardgamegeek.com/boardgame/2395/thoughtwave (1974) a pipe's style.

Tak https://boardgamegeek.com/boardgame/197405/tak (from The Wise Man's Fear)

Twixt https://boardgamegeek.com/boardgame/949/twixt (1962, when 3M made games)

(For more - https://boardgamegeek.com/boardgamefamily/7345/mechanism-con... and https://en.wikipedia.org/wiki/Connection_game )

Way back in the day, I wrote an AI to play hex based on the Genetic Algorithm, for which I drew inspiration from Blondie24, a checkers AI. At the time I didn't realize how much broader the search tree for Hex was compared to checkers. The results were disappointing. I had to reduce the board size to get even modest performance.

[1]. https://en.wikipedia.org/wiki/Blondie24

I was interested in this game quite a bit for awhile when I was much younger, but then read an article or something stating that the first player has a strong advantage and that they have a guaranteed route to win simply by virtue of playing first. I'm not sure if this is correct or not but it was my understanding at the time, and it kinda dampened my enthusiasm.

That’s why there’s the “swap” rule.

After which the second player has a guaranteed route to win, but it's much harder to find! Last I checked the game tree was computed up to a 6x7 board, players usually use 13x13

I used to play it quite a bit with a friend back in my student days, on a 12×12 board. We were aware, in principle, that the first player had a winning strategy, but in practice, the advantage to the first player was small enough to hardly be detectable (though we did not compile any statistics on it). Perhaps this only serves to reveal that we weren't terribly good at it, though. We weren't aware of the swap rule at the time.

That's slightly surprising since playing in the middle of the board on your first move is such a large advantage.

Beginner players do seem to think that playing near a black side is a good opening, but it's actually one of the weakest, but playing it "quite a bit" I would suspect you would stumble on playing near the middle by accident if nothing else?

Oh, it took us very little time to figure out to start in the middle. It took us more time to figure out what was the most effective response to that. It is hard to remember now, as I haven’t played the game in decades. But most likely, both of us made just enough mistakes, which the other then exploited, that the initial advantaged drowned in the noise of what followed, if you get my drift.

Yeah we were aware of the swap rule, but it didn't really help our enthusiasm at the time because (1) it seemed then the second player would gain the same advantage, and (2) it seemed to theoretically turn the whole game into one of knowing which opening moves would lead to a guaranteed win, like knowing when to swap, which isn't as interesting.

This was awhile ago though, long before AI solutions to Go and Chess, and what we were reading wasn't that detailed. It seems like the game trees are much harder to know a priori than was our impression at the time, at least for sufficiently large boards. It still makes me wonder but maybe is more complex than I thought.

Seeing it here on HN has kinda rekindled my interest in it.

I will admit in general, these AI approaches to boardgames has kinda changed the way I think about them, from puzzles to think about with a companion to a giant math problem to solve once or so forever for all humankind. It's kinda shifted my interest to the possibility of games where it's harder to develop an AI that could "solve" the game in an algorithmic sense (I was going to say in the sense that there is a program whose probability of winning is equal to or exceeds any other player, but I'm not sure if that's right, because if AI had a 0.5 probability that would be more interesting).

That's only true for very small board sizes where the game can be "solved". Play on a standard 11x11 or 13x13 and even AI has a hard time.

It's true in a technical sense for any size board. But the proof that the first winner has a winning strategy can't easily be put into a practical winning strategy. In rough outline, the proof goes as follows: First, note that the game cannot end in a tie. Next, use standard game theory to conclude that one of the players has a winning strategy (proof by labeling the game tree, starting with the leaf nodes, and working up towards the root). Finally, assume for contradiction that the second player has a winning strategy. If so, deduce the absurd result that the first player has a winning strategy: Place your first piece at a random location, then ignore that piece and follow the second player's winning strategy. If that means placing a piece where your initial piece is already, place a piece in a different random location, and continue. This works because having an extra piece on the board can never hurt you.

I thought this looked familiar so I checked my collection of 2 player abstracts and sure enough I own an octagonal variant called "pathagon". Haven't played it yet. Hard to find people interested in this genre (except for chess and go, grrr).

Is there a 3 player version of hex, and it is as deep?

google is not being my friend today.

Any quick links to play this online against a computer opponent? Looks fun.

Here's one, though the AI is said to be pretty dumb:

https://boardspace.net/english/about_hex.html

Last time I checked there were a couple of mobile games. Looks like these are still available:

https://apps.apple.com/us/app/hex-ai-board-game/id1326484730

https://appadvice.com/app/hex-for-ipad/626696176

I feel like I've missed something. This seems similar to go (yet different in several important ways, of course), which I do know. Is there a relationship?

Both heavily feature stone connectivity. But where connecting your sides with a stone chain is the goal in Hex, connected stones sharing liberties is only used to define capture in Go, and the goal is instead to take the most territory.

I think, if you're familiar with go, this is an uncharitable reading of the question. The victory condition in this game is very directly analogous to a not-uncommon source of (sometimes-game-deciding) violence in go--two nearby weak groups where connection means a decisive victory for whichever player achieves it.

Having not played Hex, I can't say whether it's strategically similar (although just from the first couple of chapters, there are definitely similar concepts of important shapes and ladder breakers).

There was a variant combining Hex and Go which was popular (as these things go) on online abstract games sites a few years ago. Square board, capturing like in Go, but the goal is to connect sides like in Hex.

This game degenerated to "primitive Go" most of the time, because both sides blocking each other is easy on a square board, and at that point it's down to who has the most territory (most free moves to fill in their own areas without being captured.

I've played both on a modest level. I'd say that Hex, at the sizes we typically play at, is a lot like one big Go fight. I find it easier to look far ahead in Hex since pieces are never removed, ladders are (even) more common, and since non-overlapping templates ("miai" in Go) always connect you can build them together into huge parts of the board where you know you can connect.

Thank you for avoiding the straw man I inadvertently invited to. This was indeed how I meant the question.

There aren't really any similarities between the two other than players putting down alternating black and white pieces on a board. There are lots of other games of this kind, like Checkers and Reversi. Hex is in fact unique because it has hexagonal tiles instead of square ones. It is also a very recent invention.

Both Hex and Go place a strong emphasis on forming connected groups of adjacent pieces placed alternately and then never moved -- isn't this a similarity not shared with the other black-and-white-pieces games?

(Even the similar terminology of "stone" and "ladder" seem to hint at a relationship.)

how is it guaranteed that games do not not end in a draw?

The hexagonal diamond board topology is such that an east-west connection can only be prevented by a north-south connection. For more formal proofs, see

https://sites.google.com/site/javhar1/hexcannotendinadraw

Nice diagrams and proofs! This is one of those that can feel obvious, but needs a bit of deep math

If you draw a hex board and try out some connections it will become immediately clear. There can never be a deadlock. No matter how you fill out all the tiles, either the white OR the black sides will connect.

A square arrangement if we allow 8-way connections, we can end up with a cross-connection:

  ox
  xo

If we only allow 4-way connections then a connected line won't permit another line to cross it.

For hex 6-way connections, lets say a place ( ) is where lines cross, but it can only be a single color. How about making a cross connection like the 8-way square: (doesn't work)

    x x x o
   x o o o x
  x o x x x
   o x x x

If you put the constraint that an 'x' set of connections on a square board is not allowed -

  ox
  x.

So that 'o' is prohibited from playing in the empty spot there because 'x' already has a connection - you get the game Crossway - https://boardgamegeek.com/boardgame/30517/crossway // http://superdupergames.org/gameinfo.html?game=cross // http://www.marksteeregames.com/Crossway_rules.pdf

My attempt at intuition: the very act of completely blocking your opponent from making a connection will make a connection for yourself.

Wow. That takes me back.

John Nash independently invented hex in grad school. A sequence of scenes involving hex were cut from the movie "A Beautiful Mind".

The first day that Russell Crowe joined the production, he was occupied with hours of makeup tests for his aging progression. Ron Howard had me meet him during a break, to discuss the hex and go scenes to come. The first dozen of a crew that would be hundreds hadn't met him either, so they hovered nearby as we talked.

To my surprise, Russell asked me what mathematical truths drew Nash to this game. Never underestimate people; I went for it. Rather than explaining the proof Nash liked that the first player could always win, I decided to explain why some player had to win. As I talked, Russell drew me in with fascinated, understanding facial expressions.

When I was done he looked at Ron, "Can you get me the Parker Brothers rules? They're for 8 to 80, I didn't understand a word this guy just said!" Peals of laughter from the room.

Months later we're filming a roomful of grad students playing hex, and Russell doesn't like what the script has him saying. He gets permission to ad lib. "Think of the black stones as water, the white stones as land. Either you can swim across this way, or there's a land bridge that way..."

My longest day shooting, I woke at five, and was an actor in the pen ceremony that evening. Close to 24 hours awake, I found myself nodding off high at a party in Russell's room, everyone singing various national anthems. I learned much later that Russell had been kidded as a child for not knowing the New Zealand anthem. By the party he knew them all. He likes jokes only he gets, jokes with long fuses.

Love this game! and its game theory underpinnings.

That game looks cool

Great! Thanks a lot.

Reply on news.ycombinator.com