Monday, September 22, 2008

(Convex) Hull Lot Of Fun

Start by carefully drawing a square grid that has an odd number of
lines -- and an even number of squares -- on each side.
I suggest about 9 or more lines -- 8 or more squares -- on each side,
for beginners.
I suggest bigger grids with more lines for advanced players.
The game begins with the players (two in number) taking turns drawing
dots, one dot per move, each dot at an empty (no dot there yet)
intersection of grid-lines.
Each player draws some fixed number of dots. I suggest that, if there
are m^2 intersections in the grid (where m is the number of lines on a
side of the grid), then each player draws m^2/6 (approximately) dots,
for m^2/3 total number of dots.
Player 1 moves first, followed by player 2, then player 1, then player
On the first move by player 1, the dot CANNOT go in the center
intersection of the grid.
After the dots are drawn, either player draws line-segments to connect
the dots in the boundary of the convex hull of the dots. (See below
for convex hull definition.) -- The convex hull boundary connects the
same dots that it would connect if the grid happened to have been
perfectly drawn. (So, this game might be a good teaching tool for
learning slopes.)
(By the way: If the player not drawing the line-segments thinks that
the "convex hull's boundary" being drawn is not exactly the true
convex hull boundary, because it is connecting the wrong dots, then
the "convex hull's boundary" can be challenged for accuracy.)
After the first convex hull boundary is drawn, the boundary of the
convex hull of all the dots inside (and not on the edge of) the first
convex hull boundary is drawn.
Then the next convex hull boundary within the previous boundary is
This continues until in the center of the innermost convex hull there
are zero dots, 1 dot, or several dots in a line.
If there are an odd number of dots in the center, then player 1 wins.
If there are an even number of dots in the center, then player 2 wins.
I suggest that players play an even number of rounds, and switch who
is player 1 and who is player 2. Then who wins the most number of
rounds is the winner. (This suggestion is in case there is a bias in
this game towards either player 1 or player 2.)
What is a good strategy for this game?
Convex hull: A convex hull of a set of points in a plane is the
smallest CONVEX polygon that contains all the points. (Convex has
pretty much the intuitive meaning here: There are no concave sections
along the polygon's boundary. Also, ANY point within the polygon can
be connected with ANY other point within the polygon by a straight
line-segment without the line-segment ever leaving the polygon.)
Intuitively: (Following plagiarized from Wikipedia.) Imagine the dots
of the game being pins sticking out of a board. Imagine an elastic
band that stretches around all the pins. Releasing the band, it
contracts around the outermost pins to form the boundary of the convex
By the way, I know that many newsreaders block posts made from Google
(like this post) because of all the spam coming from Google.
The question is, has anyone seen this post? Or is Google blocked by
about everyone now?
Leroy Quet

I feel I should mention in words why I have the rule that the player 1
cannot put a dot at the center intersection of an odd-by-odd grid on
the first move.
Say player 1 places his first dot at the center intersection. Then
player 2 puts her dot anywhere else. Then player 1 needs only to
continue to match player 2's moves so that the finished grid has
rotational symmetry.
Then, either there will be one dot inside the center convex hull at
game's end, or there will be a line of an odd number of dots. Player 1
automatically wins.
It would be advised for player 2 to try to continually keep the grid
from getting symmetric about any point (not necessarily the very
center dot) so that player 1 cannot just reflect player 2's moves
about the point.
If we have an even number of lines on each side of the grid, then
player 2 simply matches player 1's moves so that the grid has
rotational symmetry. Player 2 wins automatically.
I wonder if there are any necessary rule changes that are needed to
prevent easy-wins for one side or the other. (By easy-win, I mean some
strategic move that would ensure a win for a given player.)
Leroy Quet

No comments: