Combinatorial Regio is a game where two players alternate turns in order to take the last piece. Players use a special board, and the pieces are interconnected. The pieces are laid out in a square formation, and each piece is connected with the ones directly adjacent to it.

To play, a person chooses a piece and takes all the pieces that are connected to it. The person who picks up the last piece(s) is the winner. In any game, the number of pieces that can be picked up start off at 3,4,5 and then are reduced to 1,2 at the end.

Several factors determine the outcome of this type of game. These factors include the size of the board, and the way each player makes his move. The Grundy values of a 4x4 game occur in the pattern of 0,0,0,1,1,1,2,2. If a player always makes the right moves to a safe position, then there is a definite way that they can win.

This paper will demonstrate the game on a standard 4x4 board as well as several differently sized boards. Also, the board will be altered to see whether or not the same pattern continues on a different board. Regio is similar to Nim; however, the board does not allow pieces to be as freely picked up as in Nim.

Combinatorial Games are unique two-person games in which players alternate in moving. Grundy values can be calculated to determine the winner of the game. Sometimes, the winner has already been decided, and that player will win no matter what his opponent does. In other cases, the game allows room for error, and a player who was intended to win may not win at all.

There are very simple rules that apply to most Combinatorial Games. These rules are:

1. There are two players,

2. Both players move alternately,

3. The first player that cannot move anymore loses the game,

4. Both players have the full information on the current game-state, and

5. There are no chance moves- all moves can be calculated to a win or lose position.

Combinatorial Regio, which is an impartial game, satisfies the rules above. An impartial game is where each player always has the same moves available. One of the most famous impartial games is the game of Nim where each player removes pieces from several piles. Regio works in the same fashion as Nim, however, the board on which Regio is played on restricts the positions that can be chosen from.

The board for Regio is laid out a square fashion, and the "pieces" that can be picked up are all interconnected with each other. For example, a typical 4x4 board looks like (picture at left):

To play, players choose one circle and fill all of the circles adjacent to it. A typical move would look like:

Players alternate moves until there are no more circles to fill. The person who makes the last move is declared as the winner.

The game of Regio was originally created by Fabian Maeser and written in the Java programming language.

A directional graph is a set of vertices together with a set of directed edges joining certain pairs of vertices. Such a graph is used to visually show the various moves that can be made from any position. Arrows are drawn to show the only possible moves between each number, and the number zero is the winning number to move to. The directional graph for a 4x4 game of Regio looks like:

Notice how the graph also shows the "safe" and "unsafe" moves within the game. Several rules dictate how safe and unsafe numbers can be determined. These rules are:

1. The winning position (normally zero) belongs to the safe classification
2. Every move from a safe position results in an unsafe position.
3. From each unsafe position, there is a move to a safe position.

For any combinatorial game, the Grundy value can be determined. Grundy values are used to determine safe and unsafe moves that either player can make. A zero represents a safe number, and all other numbers represents an unsafe number. Calculating Grundy values involves starting from zero and working backwards using all possible moves. This process also involves determining the MEX- minimal excludant, or the smallest number left out of the sequence.

When calculated, the Grundy values of a 4x4 Regio are:

First row = # of circles/pieces left

Second row = Grundy value

Because the number sixteen has a zero for its Grundy value, any moves away from it will result in a losing move. So, the first person is almost guaranteed a loss.

However, if the second player does not make a smart move to winning/safe number, then he will also have made a losing move. There is, after all, room for error in Regio. Therefore, the second player will always win if and only if he makes the right moves.

In a 4x4 game of Regio, the second player will win if he makes the right moves. Here’s how the second player can win:

B=Blue=1^st player

R=Red=2^nd player

For the first move, the first player can choose any number of pieces (3,4 or 5 at most). Either way, the first player is moving to an unsafe position. If the first person decides to take 4 pieces, then he has put himself in the 12^th position (figure at right):

Looking at the table, the Grundy value for 12 is 1. Now, for the second player to make a good move, he must move to a safe position. For the second player to move to a safe position, he can take either three or four pieces (nine and eight positions have Grundy values of zero) (figure at right):

This move will have put the second player on a safe position of nine. Now, the first player still does not have a safe move. So let’s say he decides to take three more pieces:

Blue is now left in an unsafe position of six (Grundy value of 2). As before, any move that blue made will be unsafe. For red to win, he must continue to make safe moves. So, now he must take either four or five to reach a safe position (figure at right):

This move places red back into a safe position of two. From here, the game changes because the maximum number of pieces that can be taken is one, and in some cases two. Blue is now forced to take one piece while red gets to take the last piece for the win:

And this is how the second player can always win. In any case, making safe moves will guarantee the win for the second player in a 4x4 game of Regio.

One strategy for playing 4x4 Regio is also to play symmetrically. Playing symmetrically will also help guarantee a win, but playing with safe Grundy values is more definite.

To win at Regio, one must make safe moves all the time as well as follow the game rules. After all possible 3,4,and 5 moves are made, the player must analyze the current game and finish it out with correct moves. In actuality, the game has already decided as to whether or not the first or second player will win, but the players must make good moves in order to keep that theorem straight.

Also, the beginning Grundy value of the game will influence which person will win with best play. If the first value begins with zero, then the second player will win if he always moves to a safe position. If the first value begins with anything except zero, then the first player will win if he makes the right moves.

Boards of larger sizes will have different outcomes determining whether or not the first or second player will win. As usual, players can determine the Grundy value of any sized board to see which player will win with best play. There is also a shortcut to determining the Grundy value of a board of any size- a pattern of values repeat themselves. These values are 0,0,0,1,1,1,2, and 2.

When using these values to calculate positions higher than sixteen, the chart appears as follows:

First row = position

Second row = Grundy value

The above values have been calculated to determine a larger board of 6x6. Looking at the values, it can be determined that the value of a 6x6 Regio game is one. This would mean that safe moves are available to the person who moves first.

Now, if the board is changed (connections cut), then the Grundy values will also change. This is because the number that can be picked up will have also been changed. With less connections between pieces, a selection at first of 3,4,5 may be reduced to something like 1,2, and 3, depending on what exactly is done to the board. For a board that looks like the following:

The only moves will be to take either five or three pieces at first. After several moves, the types of moves can be reduced to taking only one or two at a time. Calculating the Grundy values of a board of this configuration will give you the following:

Fig.

In both games, the concept of picking up a certain number of items is used. Regio restricts the players to choose either 3,4,or 5 pieces until the board is narrowed down to a 1 or 2 piece configuration. Nim is very similar to this; it has a set group of total pieces at first, and a set group of items that can picked up throughout the game.

The piles in Nim are essentially the same idea as the connection of pieces that is taken up in each move in Regio. Also, the Sprague-Grundy Theorem states that every impartial game is equivalent to a Nim-pile of a certain size. Therefore, each move in Regio has a direct correlation to a move in a Nim game.

Eppstein, David. Combinatorial Game Theory. Available: http://www.ics.uci.edu/~eppstein/cgt/. June 25, 1999.

E.R. Berelekemp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays. Academic Press, London, 1982.

Maeser, Fabian. Feeb’s Impartial Games Page. Available: http://nobi.inf.ethz.ch/febi/jgb/cgt_regio/cgt_regio.html. September 22, 1997.