Difference between revisions of "User:Hexanna"

From HexWiki
Jump to: navigation, search
 
(34 intermediate revisions by 3 users not shown)
Line 5: Line 5:
 
I started learning Hex mid-July of 2021, about 2 weeks before I created my LittleGolem account.
 
I started learning Hex mid-July of 2021, about 2 weeks before I created my LittleGolem account.
  
In the interest of transparency, some people think I'm cheating: [https://littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=828 Bot used in 19x19 Hex championship]. (I claim I'm not, but you don't have to believe me.) It's weirdly discouraging and flattering at the same time. I've been spending less time on Hex and need to take a break from HexWiki, so I'll be slower to respond or work on articles.
+
==katahex/general strategy (draft material)==
  
''Hex is not a game of connection; it is a game of territory, shape, harmony.''
+
Some miscellaneous topics — I've written rough drafts/outlines of a few but they aren't ready to be published. If you have KataHex, you might consider these "select topics" as an advanced study guide for large boards, to explore on your own.
 +
* Common mistake: playing two adjacent stones (of the same color), either in a vacuum or in certain inefficient configurations.
 +
** Closely related to "bad minimaxing". Chances are, if you want to play an adjacent stone and it's not (i) provably optimal, (ii) part of a joseki, or (iii) part of a forcing sequence, you're better off with a bridge move.
 +
* Isosceles triangle pattern - this appears in lots of different josekis. The basic pattern is Red 5/7/9 in https://hexworld.org/board/#19nc1,c2d16b17e17c15b18e14e18d12, where the base of the "isosceles triangle" is perpendicular to your opponent's edge.
 +
** As with all patterns, try to learn/intuit not only when it's efficient to play the pattern, but when it's inefficient to do so. (For instance, in a vacuum, it's inefficient to play two red stones perpendicular and close to the blue edge; you should play at a 30 degree angle instead. This pattern needs neighboring stones to be efficient.)
 +
* Tom's move is useful for connecting, but it leaves several weaknesses and intrusion points if you don't absolutely have to connect.
 +
** Useful starter position with a 2-4 parallel ladder for analysis: https://hexworld.org/board/#19nc1,e6e4d4e3c3d5c7d2f4f5e5g3f3g1f2f1e2e1d3c2b3b2g4h3g2h1
 +
** Obtuse corner opening joseki with a 2-4 parallel ladder: https://hexworld.org/board/#19c1,a19j5d15c17c14c15b17b18a18d14a16d13
 +
* Acute corner joseki continuations. Red 7 is an inaccuracy but this is a common joseki: https://hexworld.org/board/#19nc1,e6e4d4e3d3d5c7f2b7c5b10i2. Study the "continuation" moves Red 11 and Blue 12, and study similar moves in related joseki.
 +
** For example, gain intuition for why Red 13 is the best move in https://hexworld.org/board/#19nc1,d5d4c5c3b4b3e4f2c4d3g3:pb8 (a5/b5 are captured by Red; see [[Theorems_about_templates#The_shape_of_templates]]), why Red 17 is the best move in https://hexworld.org/board/#19nc1,e6e5d6d4c5c4f5g3d5e4h4i2b5b4j3:pc9, and why other moves are weak.
  
==Insights and tidbits from KataHex (hzy's bot)==
+
===a3 opening===
 +
Nowadays, strong players rarely play a3 on the first move because it's similar to c2 (which is already on the losing side on most board sizes), but a bit weaker. There are some subtle differences between a3 and c2, however, and most strategy advice on the a3 opening is outdated.
  
* A couple two-move openings where KataHex's win rate is very close to 50% on 13×13 through 19×19: [https://hexworld.org/board/#13n,c2e9 c2 5-5] and [https://hexworld.org/board/#13n,a3c11 a3 3-3]
+
If Red plays a3, some older strategy guides recommend that Blue respond d6 or e7 if she wants to play in the acute corner. However, KataHex considers this an inaccuracy; even though d6 and e7 are attacking stones in the sense that Blue would win a [[bridge ladder]] towards the acute corner, they don't do a good job blocking Red's edge the way e4 does in an empty corner.
* katahex_model_20220618.bin.gz (I'll call this the "strong" net) appears significantly stronger than the "default" net.
+
 
** From several self-play games, the strong net appears (very approximately) 300±100 Elo stronger on 15×15 and 500±150 Elo stronger on 19×19 when playing with 400-1000 visits/move.
+
If you want to play the acute corner, 5-5, or 4-4 on smaller boards, is a good choice. (There are other options further away from the corner on larger boards.) KataHex and other bots consistently prefer these moves:
** From my tests, the strong net beats the default net >50% of the time when playing as Blue against Red b14 (2-2 obtuse corner) opening on 15×15, and >50% of the time when playing as Blue without swap on 19×19.
+
* https://www.littlegolem.net/jsp/game/game.jsp?gid=2175191&nmove=4
* A 13×13 swap map, with KataHex's self-play Elo estimate of the swap advantage for each opening. Generated using the strong net, with around 30k visits for most moves. For the red hexes, the number corresponds to Blue's Elo advantage if she swaps Red's move; for the blue hexes, the number corresponds to Blue's Elo advantage if she does not swap Red's move. Smaller numbers correspond to fairer openings. Hexes without numbers are unfair openings that confer Blue more than a 300 Elo advantage. For example, the fairest opening is g3 (or g11), which KataHex thinks Blue should swap, leaving Blue with a 51.5% win rate, or 10 Elo.
+
* https://www.littlegolem.net/jsp/game/game.jsp?gid=2033243&nmove=2
** Key takeaways: The "common" human openings c2, k2, a10, a13 are all reasonably fair. g3 has become more popular recently, for good reason. b4 is rarely played, but it seems fair enough to be suitable for even high-level human play.
+
* https://www.littlegolem.net/jsp/game/game.jsp?gid=2018841&nmove=8
<hexboard size="13x13"
+
* https://www.littlegolem.net/jsp/game/game.jsp?gid=1950209&nmove=20
   coords="show"
+
 
   contents="S red:all
+
One reason may be the efficiency of templates [[Edge template IV2e|IV2e]] and [[Fifth_row_edge_templates#V-2-d|V2d]], both of which have a "hole"; the template can be rotated so that the hole coincides with Red's a3 stone. This is explored in more detail below.
              blue:(a1--l1 a2--k2 a3 a11)
+
 
              blue:(b13--m13 c12--m12 m11 m3)
+
It can be useful to realize that a3 is primarily a blocking move (blocking Blue on the left rather than helping Red connect to top), whereas c2 is half blocking and half connecting. To illustrate the point, it's a bad idea for Red to play both c2 and 4-4 obtuse corner on the top edge (in the absence of Blue's blocking stones), because that's too much strength near the top. However, Red could feasibly play both a3 and 4-4 on the top edge.
             E 239:(d3 j11)
+
 
              187:(e3 i11)
+
a3 can combine well with c5. Red's goal is to leave b4/c5 open as options (these are the same hexes used in the a3 escape trick, but of course, a3+c5 can also connect upwards). Blue should also keep an eye on b4 - not to play immediately because it's too close to her own edge - but as the most efficient option for connecting to the left side near the top. Blue would much prefer to connect using b4 (which is a locally efficient move that neutralizes a3's switchback and upwards connecting potential) than b5 (which only slightly weakens a3's potential, forcing Red to play d5 instead of c5), or a 2nd row ladder with b3 (which removes Red's weakness at b1).
              48:(f3 h11)
+
 
              10:(g3 g11)
+
a3 is one of my favorite openings to analyze (I only wish it were more fair as an opening move). Unlike c2 where Blue's best move is typically to tenuki, a3 gives Blue the option to fight in the same acute corner. There is essentially a separate theory of a3 corner joseki.
              68:(h3 f11)
+
 
              185:(i3 e11)
+
I find a3 lines particularly educational because a3 changes the corner just enough to make different moves more efficient. You can learn a lot about how an existing stone influences neighboring stones.
              158:(j3 d11)
+
 
              107:(a13 m1)
+
* d4: https://hexworld.org/board/#14c1,a3d4e4e3
              161:(k2 c12)
+
** Note that Red e4 is near his own edge, but it's adjacent to Blue's stone at d4 and does a good job at blocking it; this is analogous to the joseki https://hexworld.org/board/#14nc1,k10k9, where Blue 2 is often a strong move. Blue e3 is counterintuitive, but it forms [[Fifth_row_edge_templates#V-2-d|template V2d]], which has a hole at Red's a3. In essence, Blue makes Red's a3 stone nearly useless in this line.
              258:(d2 j12)
+
** Red avoids b5 which is a very weak move, because it makes Blue b4 even more efficient: https://hexworld.org/board/#14c1,a3d4b5b4c4d2. This position is practically Blue's dream; Blue makes full use of d4 and the weakness at a3 with [[Edge template IV2e|template IV2e]] (which also has a hole).
              110:(c2 k12)
+
*** This is similar to Red 5 being a blunder in this opening: https://hexworld.org/board/#14nc1,a10d11c12c11b12b11
              184:(b2 l12)
+
* e3 first: https://hexworld.org/board/#14c1,a3e3c4b4d2c3d3c5
               189:(a2 m12)
+
* d3 is bad: https://hexworld.org/board/#14c1,a3d3b4
              207:(a3 m11)
+
* Why is e4 weak? After Red c5!, the normally locally efficient b4 (even though it's globally inefficient, because it's on Blue's 2nd row) is terrible because Red d3 is a bridge cut. Note that a3 primarily is a blocking move, not a connecting one, so d3+a3 is not so much strength near the top that it renders d3 a bad move. https://hexworld.org/board/#14c1,a3e4c5b4d3
              143:(b4 l10)
+
* e5: In some ways, these resemble the low intrusion 5-4 joseki, shifted up one row.
              226:(b11 l3)
+
** https://hexworld.org/board/#14nc1,a3e5c5c6d6d5 Red 5 is optional but actually an acceptable bridge peep, because intruding on the other side of the bridge would be too much strength near the top and almost never a good idea.
              247:(a4 m10)
+
** Red must still avoid b5 for the same reason as before: https://hexworld.org/board/#14nc1,a3e5c5c4b5b4d4f3d3 is very favorable to Blue. Observe that Blue 8 at f3 is more efficient than at e2, because e2 is followed by Red f3 which is a bridge cut
              211:(a6 m8)
+
** https://hexworld.org/board/#14nc1,a3e5c5c4d4c6d6e6d5d7b8c7a7b6a6b5a5a4b4c2c3f3d2 Red peeps the bridge with 7. d6; Blue 8. e6 may be a stronger reply than connecting directly. While this variation represents strong play by both sides, and Red is doing just fine, Blue 20 and the sequence leading up to it is a good illustration of how Blue can play efficiently around Red's a3 stone.
              219:(a7 m7)
+
** https://hexworld.org/board/#14nc1,a3e5c5d4c4c6f5h3 There are too many variations after Blue d4 to list them all. Blue 6 at d3 leads to a fun minimaxing sequence but is perhaps a slight inaccuracy: https://hexworld.org/board/#14nc1,a3e5c5d4c4d3b6d2c3d7
              197:(a8 m6)
+
 
               171:(a9 m5)
+
==Notation for distances==
              158:(a10 m4)
+
When analyzing patterns, it's useful to have a way to express various distances concisely. There are terms like adjacent, bridge, "classic block," but larger distances are hard to describe. Distances like "two hexes away" are ambiguous, does it mean a distance of 2 (like a1 and c1) or two hexes in between (like a1 and d1)? Everyone has their own way of thinking about it. Here's the one I use:
              131:(a11 m3)"
+
* Pretend that the hex grid consists of regular hexagons, and adjacent hexagons' centers have distance 1. (Equivalently, the centers of the hexes form a triangular lattice; pretend these triangles are equilateral with side length 1.)
 +
* It's not hard to show that a "bridge" (like a1 and b2) has length sqrt(3) if you connect the centers, and a "classic block" (like a1 and c2) has length sqrt(7). A fun exercise is to show that the distances between the centers of two hexes is always the square root of an integer. Which integers are possible as squared distances? Answer: [https://oeis.org/A003136 Löschian numbers.]
 +
* The fact that squared distances are integers is notationally convenient. Let Δn denote a ''squared'' distance of n (I like this because it looks nicer than a square root symbol, and a letter like "d" can be confused with a coordinate).
 +
* "Adjacent" is Δ1; "bridge" is Δ3; "classic block" is Δ7; the distance between a1 and c1 is Δ4; "two bridges away" is Δ12.
 +
* Are there collisions? [https://oeis.org/A118886 Yes,] but the first collision is Δ49 (a distance of 7), which is both the distance between a1 and h1, and between a1 and f4. This is large enough that for practical purposes, the notation is unique. (An interesting fact: the first number with a 4-way collision is, coincidentally, [https://oeis.org/A198775 1729] of [https://en.wikipedia.org/wiki/1729_(number)#As_a_Ramanujan_number Ramanujan fame.])
 +
* Here is a mapping of squared distances from the hex marked (*). Most of the time, you only need distances up to Δ16.
 +
<hexboard size="5x9"  
 +
   coords="hide"
 +
   edges="hide"
 +
  visible="area(a1,e5,i1)"
 +
  contents="S a1
 +
             E *:a1 1:b1 3:b2 4:c1 7:c2 9:d1 12:c3 13:d2 16:e1 19:d3 21:e2 25:f1
 +
               27:d4 28:e3 31:f2 36:g1 37:e4 39:f3 43:g2 49:h1
 +
               48:e5 49:f4 52:g3 57:h2 64:i1"
 
   />
 
   />
* Swap map for 19&times;19 generated with the strong net, with around 15k visits for most moves. Includes all fair openings as well as a few selected unfair openings, including the strongest move without swap (e10). I used more visits for the fairest moves: 1000k for e3 (49.5% win rate), 500k for n3 (49.2%), 100k for a15 (52.5%).
+
 
** Key takeaways: The swap map at [[Swap rule#Size 19]] uses [https://pic4.zhimg.com/v2-7287c3a2a4e948da89c3ccad38cea82f_r.jpg data] that is almost certainly from the "weak" net. Compared to the weak net, the strong net notably thinks a19, n3&mdash;p3, and k4&mdash;l4 are stronger. I personally trust the strong net's evaluations more; I think it's dubious that the weak net thought l4 was a very fair opening. The nets disagree on whether e3 is winning or losing, though it's so close to 50% that the difference isn't meaningful.
+
==Why I like the swap rule==
 +
 
 +
# The standard reason: It makes the game much more fair.
 +
# Every Hex player knows "Hex without swap is a first-player win." Add the swap rule, and you get another elegant result for free: "Hex with swap is a second-player win."
 +
# It provides much-needed asymmetry to the opening. The Hex board has two-fold rotational symmetry, and on odd-sized boards without swap, most players will open in the center. The symmetry isn't broken until the second turn!
 +
# The opening stone is especially influential in determining the character of the game. On 19x19, games that open with c2 look quite different from those that open with a10. A lot of cool tactics, like the a3 and a4 switchbacks, only really appear when you add the swap rule. The swap rule greatly expands the variety of plausible positions, and who doesn't like more variety?
 +
# While the second player has a theoretical advantage, the first player has a practical advantage: she can choose what opening to play. Because the opening stone is much more influential than later stones, the first player can pick an opening that she's especially familiar with, or one that her opponent is weak at. It would not be surprising if the first and second player's advantages cancel out among strong humans (on 19x19), and each player wins almost exactly 50% of games.
 +
# Since the swap rule is nonconstructive, it scales up beautifully to larger boards. Even if players have no idea which opening stones are fair, it's virtually certain that fair stones exist, and there should be no qualms about fairness. Contrast this with komi in Go: a fair komi has to be empirically determined for each board size, and there could be disagreements about the komi for various board sizes. (This concern is alleviated with auction komi, but that adds another rule to the game.)
 +
# It's resistant to partial solutions. Let's say that someone miraculously comes up with a constructive proof that the obtuse corner is winning on 19x19. No problem, players will just stop playing obtuse corner and play other opening moves instead.
 +
# It's fun to try to trick players into swapping a weak move or not swapping a deceptively strong move. :)
 +
 
 +
==Second row ladder vs. connecting directly==
 +
 
 +
Pretty contrived, but holding your opponent to a (one-sided) second row ladder instead of letting them connect directly is worth more than getting a second-row escape yourself.
 +
 
 +
I came across this intuition a few times when studying various sequences on large boards, and it seemed surprisingly self-evident (almost like it "has" to be true). I wasn't sure why, so I thought it was a fun exercise to convince myself that it actually makes sense from first principles. Here is an informal argument:
 +
 
 +
* Let x = "holding your opponent to a second row ladder instead of letting them connect directly"
 +
* Let y = "getting a second-row escape yourself"
 +
* To show that x > y, decompose x = m - n, where
 +
* m = "your opponent has a second row ladder"
 +
* n = "your opponent connects directly"
 +
* Also, -y is "your opponent has a second-row escape". Then, x > y is equivalent to m + (-y) > n.
 +
* That is, all else equal, you'd rather allow your opponent a second-row ladder with a second-row escape, than allow your opponent a direct connection. Why is this true? In the first situation (m + (-y)), you have the ability to jump as the defender, and gain territory in exchange for allowing your opponent to connect. On the other hand, if the opponent is connected directly without the need for a ladder escape, you have no such option.
 +
 
 +
Some potential applications of this rule (it's a stretch to say that these are direct implications of the rule, but the rule can help with building intuition):
 +
* Helps explain why Blue 4 is surprisingly strong here: https://hexworld.org/board/#19nc1,e15e17d17b18:pc19d18
 +
* Blue is not afraid of the ladder in the 4-4 3-2 obtuse corner: https://hexworld.org/board/#19nc1,c2d16b17e17c15b18d17c19
 +
* Red is just fine in this line of the obtuse corner opening: https://hexworld.org/board/#19nc1,a19:pd15c17c14e16b17b18a18c15a16b15
 +
 
 +
==Insights and tidbits from KataHex (hzy's bot)==
 +
 
 +
* Swap map for 19&times;19 generated with net 20220618, with around 15k visits for most moves. For the red hexes, the number corresponds to Blue's Elo advantage if she swaps Red's move; for the blue hexes, the number corresponds to Blue's Elo advantage if she does not swap Red's move. Smaller numbers correspond to fairer openings. Includes all fair openings as well as a few selected unfair openings, including the strongest move without swap (e10). I used more visits for the fairest moves: 1000k for e3 (49.5% win rate), 500k for n3 (49.2%), 100k for a15 (52.5%).
  
 
<hexboard size="19x19"
 
<hexboard size="19x19"
Line 66: Line 121:
 
               47:(o3 e17)
 
               47:(o3 e17)
 
               59:(p3 d17)
 
               59:(p3 d17)
 +
              121:(h4 l16)
 
               72:(i4 k16)
 
               72:(i4 k16)
 
               67:(j4 j16)
 
               67:(j4 j16)
 
               81:(k4 i16)
 
               81:(k4 i16)
 
               94:(l4 h16)
 
               94:(l4 h16)
 +
              138:(m4 g16)
 +
              122:(i5 k15)
 +
              108:(j5 j15)
 +
              133:(k5 i15)
 
               69:(q2 c18)
 
               69:(q2 c18)
 +
              163:(p2 d18)
 
               96:(b17 r3)
 
               96:(b17 r3)
 +
              201:(b18 r2)
 
               77:(a2 s18)
 
               77:(a2 s18)
 
               67:(b2 r18)
 
               67:(b2 r18)
 
               56:(c2 q18)
 
               56:(c2 q18)
 +
              146:(d2 p18)
 
               100:(a3 s17)
 
               100:(a3 s17)
 +
              137:(b3 r17)
 +
              157:(c3 q17)
 
               83:(a4 s16)
 
               83:(a4 s16)
 
               73:(b4 r16)
 
               73:(b4 r16)
Line 85: Line 150:
 
               41:(a10 s10)
 
               41:(a10 s10)
 
               81:(a11 s9)
 
               81:(a11 s9)
               81:(a12 s8)
+
               115:(a12 s8)
 
               78:(a13 s7)
 
               78:(a13 s7)
 
               56:(a14 s6)
 
               56:(a14 s6)
Line 95: Line 160:
 
               382:(e10 o10)"
 
               382:(e10 o10)"
 
   />
 
   />
 
* A [https://hexworld.org/board/#19n,a6d16b7c2c8e3c17c16b17b16d9e6e10g15f11h5p4h16o14q3o10 funny opening] where every move is close to KataHex's top choice (within a couple percent). Note KataHex's willingness to play several moves on the a6-b7 diagonal. A similar pattern can be seen from other first-column openings, though it's the most prominent with a6. Humans would do well to take note of the strength of these moves when playing first-column openings (like a10). Twice as funny when Black opens with the a6-equivalent in both acute corners (a6 and s14).
 
  
 
==Random unsolved questions==
 
==Random unsolved questions==
Line 134: Line 197:
 
** The 27&times;27 map looks more reliable. I'm personally very skeptical that moves on Red's 6th row are among the most balanced moves, but there are some interesting (if somewhat noisy) insights to be had still.
 
** The 27&times;27 map looks more reliable. I'm personally very skeptical that moves on Red's 6th row are among the most balanced moves, but there are some interesting (if somewhat noisy) insights to be had still.
  
==Article ideas==
+
==Recursive swap==
 +
Not really a serious suggestion, just for fun. One advantage of "recursive swap" over multi-stone swap is that opening preparation plays a smaller role, because both players have control over the first n stones.
  
* '''Motifs''' &mdash; very loosely related to joseki; small local patterns that occur in the middle of the board, usually representing optimal play from at least one side but not necessarily both sides
+
RECURSIVE_SWAP'[k, depth, color]:
** Motifs have some notion of '''"local efficiency"''' (not to be confused with [[efficiency]]) &mdash; some motifs are, on average, good or bad for a particular player. Strong players anecdotally try to play locally efficient moves on large boards where calculating everything is impractical. It would be useful to have some of these rules of thumb written down. Can be thought of as a generalization of dead/captured cells, where LE(dead cell) = 0, and LE(X) &le; LE(Y) if Y capture-dominates X.
+
  if depth = 0:
** Here are some examples. In the first motif, Red 1 is often a weak move. Blue's best response is usually at a, or sometimes at b or c as part of a minimaxing play. But d is rarely (possibly never) the best move, because Red can respond with a, and Blue's central stone is now a dead stone. So, for any reasonable working definition of "local efficiency" LE, we have LE(d) < LE(a), and LE(b) = LE(c) due to symmetry. KataHex suggests that LE(b) < LE(a).
+
    [color] continues playing as normal.
 +
  else:
 +
    [color] plays a move. [~color] can either
 +
      swap[k], or
 +
      RECURSIVE_SWAP'[k+1, depth-1, ~color]
 +
 +
RECURSIVE_SWAP[n]:
 +
  RECURSIVE_SWAP'[1, n, Red]
  
<hexboard size="5x5"
+
RECURSIVE_SWAP[0]:
  coords="none"
+
  edges="none"
+
  contents="R b3 B c3 R 1:d2 E a:c2 b:b4 c:d3 d:c4"
+
  />
+
  
Sometimes, a player will attempt to minimax by placing two stones adjacent to each other, like the unmarked blue stones below. (This is a common human mistake on 19&times;19; adjacent stones are typically less locally efficient than stones a bridge apart.) Red has several options, such as the adjacent block (*), though a far block is often possible too. It would be enlightening to know, absent other considerations, which block is the most "efficient" for Red, so that on a large board, Red could play this block without thinking too hard. Of course, in general the best move depends on the other stones on the board, and there's no move that strictly dominates another. The best move may even plausibly be to "[[tenuki|play elsewhere]]." Provisionally, KataHex thinks playing at one of A, or the far block at B, is a better first move for Red.
+
Red continues playing as normal.
  
<hexboard size="4x4"
+
RECURSIVE_SWAP[1]:
  coords="none"
+
  edges="none"
+
  contents="B b1 c1 E *:c2 A:(a1 d1) B:a4"
+
  />
+
  
----
+
Red plays a move. Blue can either
 +
* swap, or
 +
* continue playing as normal.
  
Cataloging the simplest of motifs
+
RECURSIVE_SWAP[2]:
  
A. If Blue plays adjacent to Red in the middle of a large board with no nearby stones, a good response for Red is to play adjacent to both stones at one of (*):
+
Red plays a move. Blue can either
 +
* swap, or
 +
* play a move, after which Red can either
 +
** swap2, or
 +
** continue playing as normal.
  
<hexboard size="2x3"
+
RECURSIVE_SWAP[3]:
  coords="none"
+
  edges="none"
+
  contents="R 1:b1 B 2:b2 E *:(a2 c1)"
+
  />
+
  
B. If Blue plays a bridge move away, either of Red's moves at (*) is good.
+
Red plays a move. Blue can either
 +
* swap, or
 +
* play a move, after which Red can either
 +
** swap2, or
 +
** play a move, after which Blue can either
 +
*** swap3, or
 +
*** continue playing as normal.
  
<hexboard size="3x4"
+
===Analysis===
  coords="none"
+
RECURSIVE_SWAP[0] is the same as playing with no swap.
  edges="none"
+
  contents="R 1:c1 B 2:b3 E *:(a2 d2)"
+
  />
+
  
----
+
RECURSIVE_SWAP[1] is the same as playing with the swap rule.
  
regarding your "I think that's fair, ... find it useful." comment on the Cornering talk page:
+
RECURSIVE_SWAP[2]:
 +
* Red shouldn't play a move that's too strong or it'll be swapped.
 +
* If Red plays a weak stone, Blue should try to play a move just strong enough that Red will be indifferent to swap2. (If a "fair" move is half a stone, and Red plays a weak move worth x < 0.5 stones, Blue should play a move worth x + 0.5 stones.)
 +
* Red should try to play a weak move that's also hard for Blue to equalize (so that Red gets a sizable advantage when deciding whether to swap2 or not).
  
I do think a dedicated article for that sort of advice would be good. ​ The title could just be, "Strategic Advice from Katahex", depending on what you were thinking of putting in it.
+
RECURSIVE_SWAP[3]:
 +
* If Red plays a move worth x > 0.5 stones, Blue should swap.
 +
* If Red plays a weak stone worth x < 0.5, Blue should play a move worth less than x + 0.5 (or else Red will swap2). If Blue's move is worth y, then Red should play a move as close to (y - x) + 0.5 as possible, so that Blue's swap3 decision is difficult.
 +
* Red should play a weak move that's hard for Blue to find a tricky reply to (where a "tricky" reply is one that makes it hard for Red to equalize, such that Blue has an easy time deciding whether to swap3 or not).
 +
 
 +
Miscellaneous:
 +
* Infinite recursive swap is (under perfect play) strategically equivalent to Reverse Hex, because each player must try to play a losing move as long as possible, or else their opponent will swap and win.
 +
* On any board size, assuming the opponent has the swap option after the board is completely filled, I believe RECURSIVE_SWAP[n] is a win for Red if n is even, and a win for Blue if n is odd.
 +
** I'm bad at proving things rigorously, but I think this follows from the fact that Reverse Hex is barely a win for the winning side (in that the losing side can delay the loss until the whole board is filled).
 +
 
 +
----
  
[[User:Demer|Demer]] ([[User talk:Demer|talk]]) 17:26, 3 May 2023 (UTC)
+
[[User:Fjan2ej57w|Fjan2ej57w]]'s question 7, "how much space of an empty board would be filled if both sides play optimally":
  
I agree that an article like "Strategic Advice from Katahex" would be very useful. Currently, the wiki has far more information on tactics than on strategy, and most of the strategy advice is from outdated guides. It's probably in the nature of strategy advice that it will sooner or later be outdated, but it would be nice to have more of it, and for it to be more current. [[User:Selinger|Selinger]] ([[User talk:Selinger|talk]]) 17:27, 7 May 2023 (UTC)
+
[https://mathoverflow.net/questions/302821/length-of-optimal-play-in-hex-as-a-function-of-size Stack Overflow answer] for reference. My conjecture is that Hex without swap asymptotically requires Θ(n^2) cells, and more generally, a Demer handicap of Θ(f(n)) stones requires Θ(n^2/f(n)) cells, for all f(n) between Θ(1) and Θ(n). My intuition is that on 1000000&times;1000000 Hex, the first-player advantage is minuscule, and even a handicap of n^(1/2) = 1000 stones, say spaced out evenly across the short diagonal, would require on the order of "1000 columns and 1000000 rows", n^(3/2), to convert to a final connection. Another interesting question is to find a constructive winning strategy with an o(n) (sub-linear) handicap.
  
I started an article: [[Strategic advice from KataHex]]. It's only about half of what I have initially outlined, though I may be too busy to finish the rest in the near future. Any feedback on this format (or the content) would be welcome. [[User:Hexanna|Hexanna]] ([[User talk:Hexanna|talk]]) 00:29, 8 May 2023 (UTC)
+
reply by [[User:Demer|Demer]]: ​ ​ ​ ​ ​ ​ ​ Even one with ​ n/6 - ω(1) ​ handicap would be interesting. ​ ​ ​ (improving on ​ https://webdocs.cs.ualberta.ca/~hayward/papers/handicap.pdf )

Latest revision as of 01:25, 12 October 2024

Openings on 19 x 19

Strategic advice from KataHex

I started learning Hex mid-July of 2021, about 2 weeks before I created my LittleGolem account.

katahex/general strategy (draft material)

Some miscellaneous topics — I've written rough drafts/outlines of a few but they aren't ready to be published. If you have KataHex, you might consider these "select topics" as an advanced study guide for large boards, to explore on your own.

a3 opening

Nowadays, strong players rarely play a3 on the first move because it's similar to c2 (which is already on the losing side on most board sizes), but a bit weaker. There are some subtle differences between a3 and c2, however, and most strategy advice on the a3 opening is outdated.

If Red plays a3, some older strategy guides recommend that Blue respond d6 or e7 if she wants to play in the acute corner. However, KataHex considers this an inaccuracy; even though d6 and e7 are attacking stones in the sense that Blue would win a bridge ladder towards the acute corner, they don't do a good job blocking Red's edge the way e4 does in an empty corner.

If you want to play the acute corner, 5-5, or 4-4 on smaller boards, is a good choice. (There are other options further away from the corner on larger boards.) KataHex and other bots consistently prefer these moves:

One reason may be the efficiency of templates IV2e and V2d, both of which have a "hole"; the template can be rotated so that the hole coincides with Red's a3 stone. This is explored in more detail below.

It can be useful to realize that a3 is primarily a blocking move (blocking Blue on the left rather than helping Red connect to top), whereas c2 is half blocking and half connecting. To illustrate the point, it's a bad idea for Red to play both c2 and 4-4 obtuse corner on the top edge (in the absence of Blue's blocking stones), because that's too much strength near the top. However, Red could feasibly play both a3 and 4-4 on the top edge.

a3 can combine well with c5. Red's goal is to leave b4/c5 open as options (these are the same hexes used in the a3 escape trick, but of course, a3+c5 can also connect upwards). Blue should also keep an eye on b4 - not to play immediately because it's too close to her own edge - but as the most efficient option for connecting to the left side near the top. Blue would much prefer to connect using b4 (which is a locally efficient move that neutralizes a3's switchback and upwards connecting potential) than b5 (which only slightly weakens a3's potential, forcing Red to play d5 instead of c5), or a 2nd row ladder with b3 (which removes Red's weakness at b1).

a3 is one of my favorite openings to analyze (I only wish it were more fair as an opening move). Unlike c2 where Blue's best move is typically to tenuki, a3 gives Blue the option to fight in the same acute corner. There is essentially a separate theory of a3 corner joseki.

I find a3 lines particularly educational because a3 changes the corner just enough to make different moves more efficient. You can learn a lot about how an existing stone influences neighboring stones.

Notation for distances

When analyzing patterns, it's useful to have a way to express various distances concisely. There are terms like adjacent, bridge, "classic block," but larger distances are hard to describe. Distances like "two hexes away" are ambiguous, does it mean a distance of 2 (like a1 and c1) or two hexes in between (like a1 and d1)? Everyone has their own way of thinking about it. Here's the one I use:

  • Pretend that the hex grid consists of regular hexagons, and adjacent hexagons' centers have distance 1. (Equivalently, the centers of the hexes form a triangular lattice; pretend these triangles are equilateral with side length 1.)
  • It's not hard to show that a "bridge" (like a1 and b2) has length sqrt(3) if you connect the centers, and a "classic block" (like a1 and c2) has length sqrt(7). A fun exercise is to show that the distances between the centers of two hexes is always the square root of an integer. Which integers are possible as squared distances? Answer: Löschian numbers.
  • The fact that squared distances are integers is notationally convenient. Let Δn denote a squared distance of n (I like this because it looks nicer than a square root symbol, and a letter like "d" can be confused with a coordinate).
  • "Adjacent" is Δ1; "bridge" is Δ3; "classic block" is Δ7; the distance between a1 and c1 is Δ4; "two bridges away" is Δ12.
  • Are there collisions? Yes, but the first collision is Δ49 (a distance of 7), which is both the distance between a1 and h1, and between a1 and f4. This is large enough that for practical purposes, the notation is unique. (An interesting fact: the first number with a 4-way collision is, coincidentally, 1729 of Ramanujan fame.)
  • Here is a mapping of squared distances from the hex marked (*). Most of the time, you only need distances up to Δ16.
1491625364964371321314357121928395227374948

Why I like the swap rule

  1. The standard reason: It makes the game much more fair.
  2. Every Hex player knows "Hex without swap is a first-player win." Add the swap rule, and you get another elegant result for free: "Hex with swap is a second-player win."
  3. It provides much-needed asymmetry to the opening. The Hex board has two-fold rotational symmetry, and on odd-sized boards without swap, most players will open in the center. The symmetry isn't broken until the second turn!
  4. The opening stone is especially influential in determining the character of the game. On 19x19, games that open with c2 look quite different from those that open with a10. A lot of cool tactics, like the a3 and a4 switchbacks, only really appear when you add the swap rule. The swap rule greatly expands the variety of plausible positions, and who doesn't like more variety?
  5. While the second player has a theoretical advantage, the first player has a practical advantage: she can choose what opening to play. Because the opening stone is much more influential than later stones, the first player can pick an opening that she's especially familiar with, or one that her opponent is weak at. It would not be surprising if the first and second player's advantages cancel out among strong humans (on 19x19), and each player wins almost exactly 50% of games.
  6. Since the swap rule is nonconstructive, it scales up beautifully to larger boards. Even if players have no idea which opening stones are fair, it's virtually certain that fair stones exist, and there should be no qualms about fairness. Contrast this with komi in Go: a fair komi has to be empirically determined for each board size, and there could be disagreements about the komi for various board sizes. (This concern is alleviated with auction komi, but that adds another rule to the game.)
  7. It's resistant to partial solutions. Let's say that someone miraculously comes up with a constructive proof that the obtuse corner is winning on 19x19. No problem, players will just stop playing obtuse corner and play other opening moves instead.
  8. It's fun to try to trick players into swapping a weak move or not swapping a deceptively strong move. :)

Second row ladder vs. connecting directly

Pretty contrived, but holding your opponent to a (one-sided) second row ladder instead of letting them connect directly is worth more than getting a second-row escape yourself.

I came across this intuition a few times when studying various sequences on large boards, and it seemed surprisingly self-evident (almost like it "has" to be true). I wasn't sure why, so I thought it was a fun exercise to convince myself that it actually makes sense from first principles. Here is an informal argument:

  • Let x = "holding your opponent to a second row ladder instead of letting them connect directly"
  • Let y = "getting a second-row escape yourself"
  • To show that x > y, decompose x = m - n, where
  • m = "your opponent has a second row ladder"
  • n = "your opponent connects directly"
  • Also, -y is "your opponent has a second-row escape". Then, x > y is equivalent to m + (-y) > n.
  • That is, all else equal, you'd rather allow your opponent a second-row ladder with a second-row escape, than allow your opponent a direct connection. Why is this true? In the first situation (m + (-y)), you have the ability to jump as the defender, and gain territory in exchange for allowing your opponent to connect. On the other hand, if the opponent is connected directly without the need for a ladder escape, you have no such option.

Some potential applications of this rule (it's a stretch to say that these are direct implications of the rule, but the rule can help with building intuition):

Insights and tidbits from KataHex (hzy's bot)

  • Swap map for 19×19 generated with net 20220618, with around 15k visits for most moves. For the red hexes, the number corresponds to Blue's Elo advantage if she swaps Red's move; for the blue hexes, the number corresponds to Blue's Elo advantage if she does not swap Red's move. Smaller numbers correspond to fairer openings. Includes all fair openings as well as a few selected unfair openings, including the strongest move without swap (e10). I used more visits for the fairest moves: 1000k for e3 (49.5% win rate), 500k for n3 (49.2%), 100k for a15 (52.5%).
abcdefghijklmnopqrs123456789101112131415161718195677675614616369201174100137157653737673849010310449647599611083731217267819413857136122108133179356957813111599814138238241819911513178955693171331081221365713894816772121738311096594764910410390847376733651571371001742016916314656677756

Random unsolved questions

Most of these are very difficult to answer, and I would be happy if even a few were answered in the next few years:

  • Is the obtuse corner always winning on larger board sizes? What about the b4 opening? Let P(n) be the statement that "the obtuse corner is a winning opening in n×n Hex without swap." There are a few possible cases; an interesting exercise is to come up with subjective probabilities of each case being true.
    • A. P(n) is always true. If so, can we prove this?
    • B. P(n) is true for infinitely many n, with finitely many counterexamples. If so, what's the smallest counterexample?
    • C. P(n) is true for infinitely many n, with infinitely many counterexamples. If so, does P(n) hold "almost always," "almost never," or somewhere in between?
    • D. P(n) is true for finitely many n. If so, what's the largest such n?
  • Kriegspiel Hex (Dark Hex), a variant with incomplete information
    • Under optimal mixed strategies, what is Red's win probability on 4×4?
    • For larger boards (say, 19×19), is Red's win probability close to 50%?
      • If so, a swap rule might not be needed for Kriegspiel Hex, which would be neat.
      • If not, imagine a variant where Red's first move is publicly announced to both players, and Blue has the option to swap it. Which initial moves are the fairest now?


replies by Demer:

  • https://zhuanlan.zhihu.com/p/476464087 has percentages, although it doesn't translate these into a guessed swap map and I don't know anything about the bot they came from.
    • ​ It suggests that [on 13x13, g3 is the most balanced opening] and [on 14x14, g3 should not be swapped].
    • On 27x27 without swap, it likes the 4-4 obtuse corner opening slightly more than anything else nearby.
  • As far as I'm aware, even 3×4 Dark Hex has not been solved. ​ (https://content.iospress.com/articles/icga-journal/icg180057 apparently gives "some preliminary results" for that size.)

hexanna:

  • Thank you, this is amazing! From the Google Translate, the bot is an adaptation of KataGo trained on 13×13 and smaller, using transfer learning to train larger nets on top of the 13×13 net for a short period of time. I may edit the swap rule article later with some insights.
    • The results for up to 15×15 look very reliable to me. This is because many of the subtle patterns suggested by other bots, like leela_bot, appear in these swap maps. For example, on 13×13:
      • a1–c1 are stronger than d1; a2–c2 ≥ d2 ≥ e2 in strength; and a similar relation holds for moves on the third row. See Openings on 11 x 11#d2.
      • b4 is weaker than all of its neighbors, because Blue can fit the ziggurat in the corner.
      • j3 is surprisingly weak and i3 is surprisingly strong. Many people were surprised about this when leela_bot's swap map came out, but the result may be more than just random noise.
      • a10 is the weakest of a4–a10, while a5 is the strongest.
      • b10 is stronger than all of its neighbors, because Blue cannot fit the ziggurat in the obtuse corner.
    • That this bot picked up on all these subtleties, and assigns a win percentage close to 100% for most moves on 13×13, suggest to me that it is probably stronger than leela_bot and gzero_bot. I can't know for sure, though.
    • On the other hand, and the author seems to agree, the 37×37 map looks very unreliable. I see percentages as low as 37% but only as high as 54% (for a move like f1, which should almost certainly be a losing move).
    • The 27×27 map looks more reliable. I'm personally very skeptical that moves on Red's 6th row are among the most balanced moves, but there are some interesting (if somewhat noisy) insights to be had still.

Recursive swap

Not really a serious suggestion, just for fun. One advantage of "recursive swap" over multi-stone swap is that opening preparation plays a smaller role, because both players have control over the first n stones.

RECURSIVE_SWAP'[k, depth, color]:
  if depth = 0:
    [color] continues playing as normal.
  else:
    [color] plays a move. [~color] can either
      swap[k], or
      RECURSIVE_SWAP'[k+1, depth-1, ~color]

RECURSIVE_SWAP[n]:
  RECURSIVE_SWAP'[1, n, Red]

RECURSIVE_SWAP[0]:

Red continues playing as normal.

RECURSIVE_SWAP[1]:

Red plays a move. Blue can either

  • swap, or
  • continue playing as normal.

RECURSIVE_SWAP[2]:

Red plays a move. Blue can either

  • swap, or
  • play a move, after which Red can either
    • swap2, or
    • continue playing as normal.

RECURSIVE_SWAP[3]:

Red plays a move. Blue can either

  • swap, or
  • play a move, after which Red can either
    • swap2, or
    • play a move, after which Blue can either
      • swap3, or
      • continue playing as normal.

Analysis

RECURSIVE_SWAP[0] is the same as playing with no swap.

RECURSIVE_SWAP[1] is the same as playing with the swap rule.

RECURSIVE_SWAP[2]:

  • Red shouldn't play a move that's too strong or it'll be swapped.
  • If Red plays a weak stone, Blue should try to play a move just strong enough that Red will be indifferent to swap2. (If a "fair" move is half a stone, and Red plays a weak move worth x < 0.5 stones, Blue should play a move worth x + 0.5 stones.)
  • Red should try to play a weak move that's also hard for Blue to equalize (so that Red gets a sizable advantage when deciding whether to swap2 or not).

RECURSIVE_SWAP[3]:

  • If Red plays a move worth x > 0.5 stones, Blue should swap.
  • If Red plays a weak stone worth x < 0.5, Blue should play a move worth less than x + 0.5 (or else Red will swap2). If Blue's move is worth y, then Red should play a move as close to (y - x) + 0.5 as possible, so that Blue's swap3 decision is difficult.
  • Red should play a weak move that's hard for Blue to find a tricky reply to (where a "tricky" reply is one that makes it hard for Red to equalize, such that Blue has an easy time deciding whether to swap3 or not).

Miscellaneous:

  • Infinite recursive swap is (under perfect play) strategically equivalent to Reverse Hex, because each player must try to play a losing move as long as possible, or else their opponent will swap and win.
  • On any board size, assuming the opponent has the swap option after the board is completely filled, I believe RECURSIVE_SWAP[n] is a win for Red if n is even, and a win for Blue if n is odd.
    • I'm bad at proving things rigorously, but I think this follows from the fact that Reverse Hex is barely a win for the winning side (in that the losing side can delay the loss until the whole board is filled).

Fjan2ej57w's question 7, "how much space of an empty board would be filled if both sides play optimally":

Stack Overflow answer for reference. My conjecture is that Hex without swap asymptotically requires Θ(n^2) cells, and more generally, a Demer handicap of Θ(f(n)) stones requires Θ(n^2/f(n)) cells, for all f(n) between Θ(1) and Θ(n). My intuition is that on 1000000×1000000 Hex, the first-player advantage is minuscule, and even a handicap of n^(1/2) = 1000 stones, say spaced out evenly across the short diagonal, would require on the order of "1000 columns and 1000000 rows", n^(3/2), to convert to a final connection. Another interesting question is to find a constructive winning strategy with an o(n) (sub-linear) handicap.

reply by Demer: ​ ​ ​ ​ ​ ​ ​ Even one with ​ n/6 - ω(1) ​ handicap would be interesting. ​ ​ ​ (improving on ​ https://webdocs.cs.ualberta.ca/~hayward/papers/handicap.pdf )