What is Grod?

It's a game with a grid and some rods. You can play it by choosing GAME above. The game was invented by a friend of mine so you have probably not seen it before. It is a two-player, deterministic, finite, zero-sum game with perfect information. Other games in the same category are Gomoku, Checkers, Go, and Chess. If you play Nim, another game in the same category you will soon see 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(k)

P(1)  and  P(k-1)   P(k)                P(16)

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. The previous sentences are now obsolete The best players in either chess or Go are nowadays easy prey for the best algorithms on a modern computer.

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. Game in the menu leads to the game of Grod. The code written in Javascript uses two non-standard fonts for reasons of style. These fonts, Snell and Chalkboard can be downloaded from the Info & Downloads section. 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.