It's a game with a grid and some rods. The game was invented by a friend of mine
so you have probably not seen it before. To be more specific; it's a two-player,
deterministic, finite, zero-sum game with perfect information.
Other games in the same category are tic-tac-toe, Gomoku, Checkers, Go, and chess.
If you play Nim, another game in the same category you will soon find out why
they are called deterministic.
There is quite a span in complexity between Nim and chess even though they are
basically the same type of game. Grod is interesting because it's the first
step in a chain from being trivial to becoming more sophisticated.
Grod is played on a 4 x 4 grid with rods of length 1, 2, and 3.
Players take turn inserting rods from the sides.
Rods of length one can be inserted from the top.
The person that is forced to put the last rod in looses the game.
It is quite entertaining and all you need is paper and pencil.
If both participants play optimally then every pattern on the grid can be
categorized as a winning or loosing position. A pattern P is composed of the free positions.
Let P(n) mean that all patterns with n or fewer free positions have been categorized.
Proof of determinism by induction:
If there is only one free position left then it is a loosing pattern. P(1)
Assume P(k-1), that all patterns with less than k free positions
have been categorized as winning or loosing.
Given a situation with k free positions, every move will lead to
a pattern that has been categorized as either winning or loosing, for the opponent.
If a loosing pattern exist, make this move. The original pattern was a winning pattern.
The alternative is that all moves lead to winning patterns for the opponent. The
original pattern was a loosing one. As a consequence every pattern with k free positions
can be categorized as either loosing or winning. We get P(k-1)
P(1) and P(k-1)
The starting position with 16 free positions is categorized and must be either a
loosing or a winning pattern. The outcome is given if both players are optimal.
The same type of proof could be applied to chess. The starting step would be
checkmate positions, win or loose. In the next step you could categorize those
positions where all possible moves lead to previously categorized positions.
Since the total number of positions is finite this process will stop after a
finite number of steps. If any positions remain uncategorized, these could be
considered as draws. So chess is a trivial game. For optimal players the outcome
is always given from the start. They would just pick the proper move from a
gigantic database. This is of course only a theoretical possibility.
Even the best chess playing programs have a very hard time to beat the best human
players and for the game of Go the best programs are not even close to beating
a skilled human player. The vast number of reasonable alternatives at each
move makes the search space prohibitively large.
Is the empty grid in Grod a win or loose position? Provided you made the right
choice of starting or not, is it possible to memorize the database so that you
could be sure of winning? The surprising answer is yes and it's not very
difficult either. The solution is given in the winning section. Reading this
will spoil the game so play the game before you read. If you want to
impress someone, learn how to win and introduce the game. To unspoil the game
just increase the grid to 5 x 5. Your mission should you accept it, is to analyze
the 5 x 5 Grod game. Is the start position win or loose? Is it possible to
master it? Another project could be to make a program that makes it possible
to play person to person between connected computers.