Monday, December 09, 2013

[wgovhyqt] Rex strategies

The objective of misere Hex (rex) is to avoid forming a path between your sides.

Let the bucket capacity of a given position for a given color be the maximum number of consecutive moves of the given color possible before a losing path is necessarily formed.

I strongly suspect bucket capacity is closely related to the minimum distance to a win for the other side in an equivalent position in regular Hex (not misere). Probably min-cut with connected regions of the same color combined into a single node. We need some graph algorithms.

Let the bridge distance of an empty hexagon for a given color be the number of empty hexagon including that one which would need to be colored that color to form a path (thus losing) through the given hexagon.  Playing in a hexagon with bridge distance 1 loses immediately.  If it impossible to form a path through the hexagon (i.e., completely surrounded by the other color) then the bridge distance is infinity.  (Alternatively, the bucket distance?) (There might be a problem if the minimum bridge through a hexagon necessarily forms a different bridge even faster.)

Let the bridge distance vector of a position be a list: the number of hexagons of bridge distance 1, then the number of distance 2, and so forth.

Consider two strategies.  Play the move which leaves a position maximizing the bucket capacity.  Play the move which leaves a position which lexicographically minimizes the bridge distance vector.

Can these evaluation functions be calculated quickly?

How well do these strategies do?  Is Rex too easy, with optimal moves (or even near-optimal) being able to be determined with merely 1-ply search?

No comments :