[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[pbmserv-dev] A three-player connection game
Greetings. camb indicated that this list would be a good place for
discussing game theory and working out new games, so I'd like to run out
an idea I had and invite comments and suggestions. This'll be more of a
discussion of the design issues than a description of game rules, even
though I think I have it mostly worked out. I'll ask any topologists in
the crowd to forgive or kindly correct me if I misuse any mathematical
terms as I touch on homology groups and such things; but for the most
part I've tried to keep the explanation simple and accessible.
Since we have a nice elegant connection game projex played on the 2-D real
projective plane, I found myself wondering what sort of game could be played if
we wrap the edges of the usual hex rhombus to get a torus. In this diagram,
capital letters in the grid are the edges of a 6x6 board, and small letters are
their projections to the opposite edge.
v u t s r q v
1- l G H I J K L g
2- m Z . . . . M z
3- n Y . . . . N y
4- o X . . . . O x
5- p W . . . . P w
6- q V U T S R Q v
l g h i j k l
\ \ \ \ \ \
A B C D E F
Note that corners A6 and F1 (L and V) are adjacent, but corners A1 and F6 (G
and Q) are not, though the distance between them is only 2.
On a board like this, there are three simple ways to form a non-trivial loop,
each of minimum length n:
. . x . . . . . . . . . . x . . . .
. . x . . . . . . . . . x . . . . .
. . x . . . . . . . . . . . . . . x
. . x . . . . . . . . . . . . . x .
. . x . . . x x x x x x . . . x . .
. . x . . . . . . . . . . . x . . .
Vert Horz Diag
Any of these three conditions will block both of the other two. So I
(eventually) figured that this could be an interesting connection game for
three players. It's no good though to have three colors of pieces on the
board. If the o and y pieces together form a loop, they're blocking x from
making anything in a different direction, and most likely neither o nor y has
yet won the game alone. It's very easy for a three-color board to reach
stalemate. Instead, we can keep just two colors and use a rule like in
Chameleon: Any player may place a piece of either color on his or her turn.
So you win if either the x's or the o's form a cycle in 'your' direction, even
if it was another player who mistakenly completed the cycle or was forced into
it.
But there's a catch. There are more types of cycles than the simple ones above.
A few more:
. x . . x . . . x x . . . . x x . .
x . . x . . x x . . . . . . . x x .
x . . x . . . . . . x x . . . . x x
. . x . . x . . x x . . x . . . . x
. . x . . x x x . . . . x x . . . .
. x . . x . . . . . x x . x x . . .
Each of these new cycles blocks the other two as well as the original three.
The reason projex is so elegant is that only one class of non-contractible
simple cycle exists on that projective plane, but on a torus there are
infinitely many classes! (On a real torus, anyway. Obviously for a finite
board you'll eventually run out of room. The 6x6 board I've been using
supports 12 different classes before the path starts bumping into itself.)
And each of those cycle classes blocks all of the other ones. Time to get a
bit more mathematical.
Given a cycle, choose any point on the cycle (it doesn't matter where), and as
you traverse it, count the number of times it crosses each edge:
Let x = (# of times the path hits the right edge and appears at the left)
- (# of times it hits left and appears at right),
Let y = (# of times it hits the top and appears at the bottom)
- (# of times it hits the bottom and appears at the top).
The ordered pair (x,y) will describe the topological class of the cycle in
question. Note that (-x,-y) describes the same class as (x,y), since if we
traverse the cycle in the opposite order, x and y will both change sign. If
both x and y are 0, then the cycle is equivalent to the boring local loop and
it hasn't blocked any other winning cycles, no matter how much it winds around
and crosses edges. Finally, x and y will always be relatively prime, or at
least if we got the pair (k*a, k*b) where k>1, then the path must intersect
itself and also form a path whose pair is (a,b). (For these purposes, I'll
define 0 to be relatively prime only to +-1.)
So the first simple examples above give pairs of Vert=(0,1), Horz=(1,0),
Diag=(1,1), and the next set are (1,2), (2,1), and (1,-1) respectively. The
allowed positions can be plotted on a Cartesian graph with the axes tilted so
that paths of equal difficulty are at equal distances from the origin:
y ^
\
. * . * . . = no new cycle, x and y not relatively prime
* . * * . * * = non-trivial cycle
. * . * . * . O = origin
* * * * * * * *
. . . * O * . . . -> x
* * * * * * * *
. * . * . * .
* . * * . *
. * . * .
The 36 asterisks show the first 18 cycles (remember, (x,y) and (-x,-y) are the
same cycle). I suspect this is far more complicated than any real game would
reasonably get, unless on a really huge board, but it's good to be complete.
As you may have suspected for some time, the cycles come in triples of equal
difficulty, so all we have to do to keep the game fair is distribute them
evenly among three players. I see two obvious ways to do it:
Sextant Method Parity Method
y ^ y ^
\ \
. V . V . . H . H .
H . V V . D D . D V . V
. H . V . D . . H . H . H .
H H H V D D D D D V D V D V D V
. . . H O H . . . -> x . . . H O H . . . -> x
D D D D V H H H V D V D V D V H
. D . V . H . . H . H . H .
D . V V . H V . V D . D
. V . V . . H . H .
V: x=0 or V: x even
y and (y-x) have same sign H: y even
H: y=0 or D: x and y both odd
x and y have opposite signs
D: x-y=0 or
x and (x-y) have same sign
In the sextant method, each player gets two opposite sextants of the tilted
graph. (I chose them so that the player we called Vert gets the (1,2) loop,
which is the one drawn in the second set above that looks purely vertical.)
Describing just which loops belong to which player is a bit complicated and
maybe hard to remember during play, but it has the advantage that a player's
goals are all more or less in the same direction.
The parity method is very simply stated. In fact, we could take out the sign
conventions from the definitions of x and y. ("Horz wins if the first cycle
made crosses the top/bottom edge an even number of times, including zero.")
But it gives me a foreboding of pathological gameplay: If Horz feels he's going
to be blocked from a horizontal connection class, his next recourse is to build
_perpendicular_ to that on the purely vertical (1,2) loop. Not that
pathological gameplay always discourages pbmserv players.
The only way to block a given loop class completely is to form a loop of a
different class using the other color. So at least one player will always
win. This brings up another catch though, because it's possible for more than
one win condition to be satisfied on the same move.
1- x . x . . .
2- x x . . . .
3- . x x x . .
4- . . . . x x
5- x . x . . x
6- x . x . . .
\ \ \ \ \ \
A B C D E F
There is no loop yet, but C4x forms a (0,1) loop, D5x forms a (1,0) loop, and
E3x forms a (1,-1) loop. Using the sextant method, that's two that would win
for Horz and one for Vert. Using the parity method, it's one potential loop
for each player. But if anybody plays D4x (perhaps the other positions are
blocked with o pieces), all those loops get formed. I'm inclined to declare
anybody who plays in such a position the winner. (A computer implementation
would have to watch out for similar situations that involve a local loop and
two identical loops and have a clear winner.) The parity method ensures that
every time this situation comes up, each player was involved anyway. Even
with the sextant method, Diag in the above example could claim a long path in
his/her sextant if it's allowed to use some of the same pieces more than once.
The sort of double-loop creation I was just discussing is essentially the
equivalent on the torus to the cross formation of Jade. And you could actually
play Jade on a torus with two players, but that's not as radically different as
what I've been describing.
It occurred to me to consider opening and equalization issues, but I think most
problems are cancelled out by the combination of piece-sharing like Chameleon
and the fact that two players can team up on anybody who takes a clear lead
early on. One thing worth noting is that before any pieces are on the board,
every location is equivalent (by translation), so we might as well say there's
an x in the center before anybody moves.
I'd normally be interested in implementing this myself, but I don't really have
the time this month to take on some programming. In fact, I really shouldn't
have spent all this time writing this up.
So, I think that's it. Anything I missed? Anybody going to demand proofs for
my mathematical claims wedged in everywhere? Anybody want to try it out?
--
Andrew Schepler
pbmserv ID: schep
P. S. Your homework assignment (2 stars): Invent a connection game on the
Klein bottle.