Difference between revisions of "User:Hexanna"

From HexWiki
Jump to: navigation, search
(conjecture to Fjan2ej57w's question 7)
(remove old stuff)
Line 4: Line 4:
  
 
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.
 
 
''Hex is not a game of connection; it is a game of territory, shape, harmony.''
 
  
 
==Insights and tidbits from KataHex (hzy's bot)==
 
==Insights and tidbits from KataHex (hzy's bot)==
  
* 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]
 
 
* katahex_model_20220618.bin.gz (I'll call this the "strong" net) appears significantly stronger than the "default" net.
 
* 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.
+
* Swap map for 19×19 generated with the strong net, 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%).
** 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.
+
* 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.
+
** 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.
+
<hexboard size="13x13"
+
  coords="show"
+
  contents="S red:all
+
              blue:(a1--l1 a2--k2 a3 a11)
+
              blue:(b13--m13 c12--m12 m11 m3)
+
            E 239:(d3 j11)
+
              187:(e3 i11)
+
              48:(f3 h11)
+
              10:(g3 g11)
+
              68:(h3 f11)
+
              185:(i3 e11)
+
              158:(j3 d11)
+
              107:(a13 m1)
+
              161:(k2 c12)
+
              258:(d2 j12)
+
              110:(c2 k12)
+
              184:(b2 l12)
+
              189:(a2 m12)
+
              207:(a3 m11)
+
              143:(b4 l10)
+
              226:(b11 l3)
+
              247:(a4 m10)
+
              211:(a6 m8)
+
              219:(a7 m7)
+
              197:(a8 m6)
+
              171:(a9 m5)
+
              158:(a10 m4)
+
              131:(a11 m3)"
+
  />
+
* 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.
 
** 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.
  
Line 95: Line 57:
 
               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 153: Line 113:
 
   contents="B b1 c1 E *:c2 A:(a1 d1) B:a4"
 
   contents="B b1 c1 E *:c2 A:(a1 d1) B:a4"
 
   />
 
   />
 
----
 
 
Cataloging the simplest of motifs
 
 
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 (*):
 
 
<hexboard size="2x3"
 
  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.
 
 
<hexboard size="3x4"
 
  coords="none"
 
  edges="none"
 
  contents="R 1:c1 B 2:b3 E *:(a2 d2)"
 
  />
 
 
----
 
 
regarding your "I think that's fair, ... find it useful." comment on the Cornering talk page:
 
 
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.
 
 
[[User:Demer|Demer]] ([[User talk:Demer|talk]]) 17:26, 3 May 2023 (UTC)
 
 
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)
 
 
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)
 
  
 
----
 
----

Revision as of 02:51, 19 April 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.

Insights and tidbits from KataHex (hzy's bot)

  • katahex_model_20220618.bin.gz (I'll call this the "strong" net) appears significantly stronger than the "default" net.
  • Swap map for 19×19 generated with the strong net, 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%).
    • Key takeaways: The swap map at Swap rule#Size 19 uses data that is almost certainly from the "weak" net. Compared to the weak net, the strong net notably thinks a19, n3—p3, and k4—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.
abcdefghijklmnopqrs1234567891011121314151617181956776756691741006537376738490103104496475996110837372678194571361793569578131819981413823824181998113178955693171365794816772738311096594764910410390847376733651001746956677756

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.

Article ideas

  • Motifs — 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
    • Motifs have some notion of "local efficiency" (not to be confused with efficiency) — 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(Y) if Y capture-dominates X.
    • 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).
a1cbd

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×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 "play elsewhere." Provisionally, KataHex thinks playing at one of A, or the far block at B, is a better first move for Red.

AAB

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.