From: dboll@vcd.hp.com (David Boll)
Newsgroups: rec.games.abstract
Subject: Hex, Hex FAQ, comments
Date: 3 Apr 1997 16:39:06 GMT

  Hi All

  I'm the author and infrequent maintainer of the Hex FAQ, available on
  my homepage (see .sig below), among many other places.

  I've had various email comments re: Hex that I thought I'd post here,
  in hopes of generating some discussion.

  Re: Hex programs. I've seen several lousy ones, and one decent one,
  available at <insert address here> This decent one plays a mean game
  of 7x7 Hex, and one wonders how portable it would be to 11x11, which makes
  me start to wonder if 11x11 is a bit small for a board size for Hex.
  Perhaps something like 16x16 (I like even board sizes). I was working on
  a Hex program for a while, and it really doesn't look like I'll finish
  it, but I put some notes on my scoring algorithm at the end of this
  post.

  Re: FAQ content: If some of the stronger players on the Hex ladder would
  be interested in discussing some aspect of the game, I'd be 
  interested to include additional material in the FAQ. Some examples
  might be the 5-template, other 4-templates, additional opening theory,
  good moves to offer for the swap option, or ???

  Re: Hex, the game, variations: One email correspondent described Hex
  as being a "knife fight in a phone booth", as opposed to a game with
  broader strategy. Sometimes I find this description fairly apt. I was
  thinking for a bit about some kind of real-valued Hex (I think I
  posted this here ~a year ago), I don't know if this would increase the
  depth of the game. Making the board larger would help also. Any thoughts?

  My scoring function:

  I try to compute the number of additional moves it would take to
  connect a particular edge hex to any hex on the opposite side. I'll 
  then move to the location that maximizes this number for my opponant.
  (Actually I look at not only edge hexes, but also hexes that are
  effectively connected to the edge)

  Here's how I calculate it: I have an array that holds the # of steps
  from (say) the East edge. Hexes on the east edge are 0, as are hexes
  that are connected via a 2,3, or 4-template. Once I populate all the
  zeros, I propogate them as follows:

    * Any empty hex that has a value of N propogates the value (N+1) to
    all neighboring empty hexes, and the 6 2-bridge hexes (provided
    both the hex and the connection is empty) The propagation only
    "sticks" if the neighbor hex isn't already of lower connectivity.

    * A hex occupied by V does no propogation. (My scoring function is
    purely defensive; I've found that adding offense just hurts the
    evaluation)

    * A hex occupied by H that has a value of N propogates the
    value N to neighbors and 2-bridge neighbors.

    Here's an example, using an empty 4x4 board. The #'s are the steps
    necessary to connect each individual hex to the East side, and
    were obtained by propagating the zeros in the manner described above.

	   2 1 1 0
            1 1 0 0
             1 0 0 0
              1 0 0 0

    OK - let's throw in a couple of pieces and try it again:

	    1 1 1 0
	     1 H 0 0
	      1 V 0 0
	       2 1 0 0
    
    Anyway, on more complicated boards it pretty accurately tracks how
    far each hex is from being connected. To select a move for V, I
    choose the one that maximizes H's East-West connectivity; to select
    a move for H, I maximize V's North-South connectivity.

    It plays OK with a 1-ply search. The trouble is there are many ties,
    so I have to do some additional weighting to (for example) encourage
    moving in the center of the board. For some reason, my minimax code
    crashes when I put my scoring function in a 2-ply search, and I 
    haven't yet had the time to track this down.

 

--
  Dave Boll    dboll@hp-vcd.vcd.hp.com
  "The speed of time is one second per second"
  Check out my home page:  http://www.pacifier.com/~dboll/   Lots of
  stuff on Astronomy, recreational mathematics, etc.