Unused Cycles

August 3, 2008

The Gordon Game

Filed under: Mathematics — Tags: , — Kevin @ 11:30 pm

The Gordon game is a game to be played by two people who know a bit about group theory (and by a bit, it’ll suffice to read my introduction to group theory). I found of the game in the book “Adventures in Group Theory: Rubik’s Cube, Merlin’s Magic and Other Mathematical Toys” by David Joyner.

According to the book, the rules are as follows. Take two copies of a set corresponding to the group (G,\ast) and call one M and the other P. The rules are then as follows:

  1. Player one chooses an element p_1 from the group P and m_1 from M. These can be any element he chooses, and once they are chosen they are removed from the sets P and M
  2. The next player chooses an element m_{i+1} and p_{i+1} such that p_{i+1}=m_{i+1}p_{i}. Both elements are removed from their respective sets.
  3. Repeat the previous step. The first player that cannot move loses.

I’ve written a program in C++ that will compile under GCC. The group used here is \mathbb{Z}/7\mathbb{Z}, that is, the integers modulo 7. You can download it here, although this link may change after I graduate. I wrote it hastily, so it’s not commented well and it probably has bugs. To compile, use the command

g++ gordon.cpp -o gordon

I can compile it fine on OpenSUSE 11.0. There’s no AI yet, so it simply switches between two human players. In the future, I may add support for user-defined groups and possibly some rudimentary AI.


UPDATE: I updated the program a little bit so that you can make your own groups. As a result, you’ll now need to download the default file, z7z.grp, if you  want to be able to run the program.

To make your own groups, follow this recipe:

  1. On the first line, list all of the group elements separated by a space and followed by an exclamation mark.
  2. Now just list the multiplication table, with a space between columns and a new line between rows.

For example, the group \mathbb{Z}/7\mathbb{Z} looks like this:

0 1 2 3 4 5 6 !
0 1 2 3 4 5 6
1 2 3 4 5 6 0
2 3 4 5 6 0 1
3 4 5 6 0 1 2
4 5 6 0 1 2 3
5 6 0 1 2 3 4
6 0 1 2 3 4 5

To use your new group, pass it on as a command line argument, i.e. run

./gordon mygroup.grp

That’s it! Try it with a complicated group, for example a large order dihedral group.


Create a free website or blog at WordPress.com.