home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / info / hypercon.trl < prev    next >
Encoding:
Internet Message Format  |  1993-06-20  |  12.2 KB
  1. From: wft@math.canterbury.ac.nz (Bill Taylor)
  2. Subject: Hypercontrol of the board.
  3.  
  4. This is actually a followup to "how to kill all enemy groups with non-play?"
  5. by  John Tromp (tromp@cwi.nl),  which appeared recently in rec.games.go  .
  6.  
  7. Some time ago I looked at this matter of "hypercontrol" of a board.
  8.                                           ~~~~~~~~~~~~
  9. That is, on an (n x n) board, what is the smallest k such that...
  10.  
  11. 1) Black can play k stones in some appropriate pattern;
  12. 2) White may play any number of legal moves in succession
  13.                 (no suicide positions allowed of course);
  14. 3) Black can then kill all the white stones, with normal play.
  15.  
  16. The situation described by (1-3) gives Black "hypercontrol" of the
  17. board at the end of phase 1.
  18. For board sizes of n from 2 through to 9 I got the following minima for k;
  19.  
  20. n : 2  3  4  5  6  7  8  9
  21. k : 2  3  6  8 12 17 22 28   This last one agrees with John Tromp's,
  22.                              though I have not seen his solution.
  23. I'm reasonably confident of the solutions up to n = 7, but not beyond.
  24. The patterns for n = 2,3 and 5 are unique, but there are many variations
  25. otherwise.  Here are some of the minimal patterns. I'd welcome improvements.
  26.  
  27.  
  28. n=2  . X        n=3  . X .      n=4   . X . .      . X . .
  29.      X .             . X .            X . X .      . X . .
  30.                      . X .            . X . X      X X X X
  31.                                       . . X .      . . . .
  32.  
  33.  
  34. n=5  . X . . .      n=6   . X . . . .      n=7   . X . . . X .
  35.      X . X . .            X . X . . .            . X . . . X .
  36.      . X . X .            . X . X X .            . X . . . X .
  37.      . . X . X            . . X . X .            . X X X X X .
  38.      . . . X .            . . X X . X            . X . . . X .
  39.                           . . . . X .            . X . . . X .
  40.                                                  . X . . . X .
  41.  
  42. n=8                                    n=9
  43.           . . X . . X . .                 . X . . . . . . .
  44.           . X X . . X X .                 . X X X X X X X .
  45.           . . X . . X . .                 . X . . . . . . .
  46.           . . X . . X . .                 . X . . . . . . .
  47.           . . X . . X . .                 X X X X X X X X .
  48.           . . X X X X . .                 . X . . . . . . .
  49.           . X X . . X X .                 . X . . . . . . .
  50.           . . X . . X . .                 . X X X X X X X .
  51.                                           . X . . . . . . .
  52.  
  53.  
  54.                                                         2
  55. It's interesting to note that minimum(k) appears to be n /3 (or just over).
  56.  
  57. Perhaps this shouldn't be surprising, as apparently black can gain
  58. hypercontrol of an infinite (or just enormous) board, with just over one third
  59. of the points occupied, with the pattern
  60.  
  61. . . . . . . . . . . . . . . . .
  62. X X X X X X X X X X X X X X X X
  63. . . . . . X . . . . . . . . . .
  64. . . . . . X . . . . . . . . . .
  65. X X X X X X X X X X X X X X X X
  66. . . . . . . . . . . . . . . . .
  67. . . . . . . . . . . . . . . . .
  68. X X X X X X X X X X X X X X X X
  69. . . . . . X . . . . . . . . . .
  70. . . . . . X . . . . . . . . . .
  71. X X X X X X X X X X X X X X X X
  72. . . . . . . . . . . . . . . . .
  73.  
  74. with the lines extended indefinitely left and right, and repeated above
  75. and below. This pattern appears to be 'minimal' for the infinite board.
  76.  
  77. Further comments would be most appreciated.
  78.  
  79.  
  80.  
  81. From: hansm@cs.kun.nl (Hans Mulder)
  82. Subject: Re: Hypercontrol of the board.
  83.  
  84. How about:
  85.  
  86. n=7  . . . . . . .   n=8  . . . . . . . .   n=9  . . . . . . . . .
  87.      . X . . . X .        . X X . . X X .        . X X X . . X X .
  88.      . X . . . X .        . . X . X X . .        . . . X X . X . .
  89.      . X X X X X .        . . X X . X X .        . . . X . X X . .
  90.      . X . X . X .        . . X . X X . .        . X X X X . X X .
  91.      . X X . X X .        . . X X . X . .        . . . X . X X . .
  92.      . . . . . . .        . X X . . X X .        . . . X . . X . .
  93.                           . . . . . . . .        . X X X . . X X .
  94.                                                  . . . . . . . . .
  95.  
  96. Using 16, 21 and 27 stones, respectively.
  97.  
  98. The Dutch national record for n=19 is 120, by Ger Hungerink (3-dan) in
  99. Go magazine 15/4, page 42:
  100.  
  101. n=19  . . . . . . . . . X . X . . . . . . .
  102.       . X X X X X X X X X X . X . . X . . .
  103.       . X . . X . . X . . X X X X X X X X .
  104.       . X . . X . . X . . X . . X . . X . .
  105.       . X . . X . . X . . X . . X . . X . .
  106.       . X . . X . . X . . X . . X . . X X .
  107.       . X . . X . . X . . X . . X . . X . .
  108.       . X . . X . . X . . X . . X . . X . .
  109.       . X . . X . . X . . X . . X . . X X .
  110.       . X . . X . . X . . X . . X . . X . .
  111.       . X . . X . . X . . X . . X . . X . .
  112.       . X . . X . . X . . X . . X . . X X .
  113.       . X . . X . . X . . X . . X . . X . .
  114.       . X . . X . . X . . X . . X . . X . .
  115.       . X . . X . . X . . X . . X . . X X .
  116.       . X . . X . . X . . X . . X . . X . .
  117.       . X . . X . . X . . X . . X . . X . .
  118.       . X . . X . . X . . X . . X . . X X .
  119.       . . . . . . . . . . . . . . . . . . .
  120.  
  121.  
  122.  
  123. From: t68@nikhefh.nikhef.nl (Jos Vermaseren)
  124.  
  125. I am sorry to say this, but none of the above is hypercontrol:
  126.  
  127. n=7  . O O O O O .
  128.      O X . . . X O
  129.      O X . . . X O
  130.      O X X X X X O
  131.      O X . X . X O
  132.      O X X . X X O
  133.      . O O O O O .
  134.  
  135. and white lives. You will have to add a stone on the edge, like in the
  136. 19*19 example
  137.  
  138.  
  139. n=7
  140.  . X . . . . .
  141.  X . X . . X .
  142.  . X . X . X .
  143.  . . X . X X .
  144.  . . . X . X .
  145.  . X X X X . .
  146.  . . . . . . .
  147.  
  148. This is a solution of 16. Haven't found a better one for 8 yet though.
  149.  
  150. From: tromp@cwi.nl (John Tromp)
  151. Subject: Re: Hypercontrol of the board.
  152.  
  153. The following position with only 26 stones almost solves the problem
  154. (white can still form a `double-headed dragon', as it seems to be called):
  155.  
  156. . . . . . . . . .
  157. . X X X X X X X .
  158. . . . . . . . X .
  159. . . . . . . . X .
  160. . X X X X X X X .
  161. . . . . . X . X .
  162. . . . . X . X . .
  163. . X X X X X X . .
  164. . . . . . . . . .
  165.  
  166. But adding another stone appropriately on the edge prevents this,
  167. which brings the 9x9 record down to 27.
  168.  
  169. Another formation achieving this bound, inspired by Ger Hungerink:
  170.  
  171. . . . . . . . . .
  172. . X X X X X X X .
  173. . . . . . . . X .
  174. . . . . . . . X X
  175. . X X X X X X X .
  176. . . . . . . X . X
  177. . . . . . . X X .
  178. . X X X X X X . .
  179. . . . . . . . . .
  180.  
  181.  
  182.  
  183. From: wft@math.canterbury.ac.nz (Bill Taylor)
  184. Subject: HYPERCONTROL : summary and extension.
  185.  
  186. FIRSTLY, thanks to all who responded to the initial posting on
  187. this topic. I'm glad so many were interested. I saw replies from...
  188.  
  189. tromp@cwi.nl (John Tromp)
  190. hansm@cs.kun.nl (Hans Mulder)
  191. Klaus Reinhardt <reinhard@orchidee.informatik.uni-stuttgart.de>
  192. t68@nikhefh.nikhef.nl (Jos Vermaseren)
  193.  
  194. ..and others (that don't seem to be in my file); apologies for omissions.
  195.  
  196. SECONDLY, a correction to my original posting. Although no-one picked
  197. it up, I incorrectly stated...
  198.  
  199. >The patterns for n = 2,3 and 5 are unique,
  200. >
  201. >n=2  . X        n=3  . X .
  202. >     X .             . X .
  203. >                     . X .
  204. >
  205. >
  206. >n=5  . X . . .
  207. >     X . X . .
  208. >     . X . X .
  209. >     . . X . X
  210. >     . . . X .
  211.  
  212. This was correct for 2 & 3, but not for 5; where there are at least two
  213. other patterns with 8 stones. Those (like me) interested in such things
  214. might like to try to find them.
  215. -------------------------------
  216.  
  217. SUMMARY: the minimal numbers for hypercontrol of square boards seem to be
  218. ~~~~~~~
  219. width:  2  3  4  5  6  7  8  9  13  19
  220. number: 2  3  6  8 12 16 21 27  56 120
  221.  
  222. ------
  223.  
  224. EXTENSION. The above table is just the main diagonal of a table for minimal
  225. ~~~~~~~~~  hypercontrol numbers for rectangular boards.
  226.  
  227. RECTANGULAR BOARDS: these do not get much attention from go players, but
  228. they are of considerable interest for those who delve into optimal
  229. small-board play, hypercontrol, and similar matters.
  230.  
  231. For (m x n) boards, the minimal numbers for hypercontrol seem to be...
  232.  
  233.      n = 1  2  3  4  5  6  7  8  9 10 11 ...         general term
  234. -------------------------------------------------------------------------------
  235. m = 1 |  *  *  1  2  2  3  3  4  4  5  5 ...           [n/2]        n >= 3
  236.     2 |     2  2  4  4  5  6  6  7  8  9 ...          [6n/7]        n >= 5
  237.     3 |        3  4  5  6  7  8  9 10 11 ...             n
  238.     4 |           6  7  8  9 11 12 13 15 ...          [4n/3]        n >= 5
  239.     5 |              8 10 12 13 15 17 18 ...   \
  240.     6 |                12 14 16 18 20 22 ...    |
  241.     7 |                   16 19 21 23 26 ...    |
  242.     8 |                      21 24 27 29 ...     >    [mn/3]      m,n >= 5
  243.     9 |                         27 30 33 ...    |
  244.    10 |                            33 37 ...    |
  245.    11 |                               40 ...   /
  246.    12 |
  247.  
  248. So; for m,n >= 3 , the general term is [mn/3],     { using [x] for floor(x) }.
  249.     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  250. (The sole exception being at 4x4).
  251.  
  252. The rows for n=1 and n=2 are quite different from the rest.    ( Indeed `go' on
  253. 1xn and 2xn boards is quite unlike regular go, as small-board analyzers will know;
  254. especially (1xn) go, where it is almost suicidal EVER to play on an end-point ! )
  255.  
  256. -------------
  257. m=1 has unique patterns like   . X . X . X .  and    . X . X X . X .
  258. ------------
  259. m=2 has patterns with limiting density 3/7 ;
  260.  
  261. a typical case being 2x24 :     . . X X . X . . . X X . X . . . X X . X X X . .
  262.                                 . . X . X X . . . X . X X . . . X . X X . . . .
  263. which type serves down to n=7.
  264.  
  265. and              X . X .       . . X . X      . . X . X .
  266. n=4,5,6 have     . X X .       . . X X .      . . X X . X
  267. --------------
  268. The minimal patterns for m=3 are trivial, like   . . . . .
  269.                                                  X X X X X
  270. -------------                                    . . . . .
  271.  
  272. The minimal patterns for m=4 are of 3 types, depending on (n mod 3);
  273.  
  274.  4x11   . X X . . . . . . . .
  275.         X . X . X . . X . . .
  276.         . X X X X X X X X X .
  277.         . . . . . . . . . . .
  278.  
  279.  4x12   . X X . . . . . . . . .
  280.         X . X . . X . . X . . .
  281.         . X X X X X X X X X X .
  282.         . . . . . . . . . . . .
  283.  
  284.  4x13   . . X . X . . . . . . . .
  285.         . X X X . X . . X . . X .
  286.         . . . X X X X X X X X X .
  287.         . . . . . . . . . . . . .
  288.  
  289. These patterns serve right down to n=5.
  290. -------------
  291.  
  292. For m,n >= 5 , there are 4 typical patterns (which cover all cases).
  293.  
  294. A: m=3k
  295. B: m=3k+1   n=3j+1
  296. C: m=3k+1   n=3j+2
  297. D: m=3k+2   n=3j+2
  298.  
  299. The patterns for these are based on those by Klaus Reinhardt and Ger Hungerink.
  300.  
  301. A: 9x11     . . . . . . . . . . .     B: 10x10   . . . . . . . . . .
  302.             . . X X X X X X X X .                . . X . . X . . X .
  303.             . . X . . . . . . . .                . . X X X X X X X .
  304.             X X X . . . . . . . .                . X X . . . . . . .
  305.             X . X X X X X X X X .                X . X . . . . . . .
  306.             . X . . . . . . . . .                . X X X X X X X X .
  307.             X X . . . . . . . . .                X X . . . . . . . .
  308.             . X X X X X X X X X .                . X . . . . . . . .
  309.             . . . . . . . . . . .                . X X X X X X X X .
  310.                                                  . . . . . . . . . .
  311.  
  312.  
  313. C: 10x11    . . . . . . . . . . .     D: 11x11
  314.             . . . X . . X . . X .                . X . . . . . . . . .
  315.             . X X X X X X X X X .                X . X X . . X . . X .
  316.             X . X . . . . . . . .                . X . X X X X X X X .
  317.             . X X . . . . . . . .                . . X X . . . . . . .
  318.             X X X X X X X X X X .                . . X . . . . . . . .
  319.             . X . . . . . . . . .                . X X X X X X X X X .
  320.             . X . . . . . . . . .                . . X . . . . . . . .
  321.             . X X X X X X X X X .                . . X . . . . . . . .
  322.             . . . . . . . . . . .                . X X X X X X X X X .
  323.                                                  . . . X . . X . . X .
  324. All of these can clearly be simply extended by   . . . . . . . . . . .
  325. threes, in either dimension; and can be similarly
  326. reduced down as far as the case 5x5 .
  327. ------------------------------------------
  328.  
  329. Well; there it all is.   Probably no-one else is interested.
  330.  
  331. The above diagrams show that the numbers given in the table are at least
  332. correct upper bounds. They do not, of course, provide a proof that the
  333. table is exactly right.
  334.  
  335. If anyone can find patterns of hypercontrol that use fewer stones than
  336. given in the table, I will be very delighted.
  337.  
  338. Have fun.
  339. ------------------
  340. Bill Taylor.            wft@math.canterbury.ac.nz
  341.  
  342.