So it's been over a whole week since I last posted something interesting, and I bet you've all been thinking "Where's that bugger gone to now huh? Can't this lad keep up any commitments?" Turns out 12 pages of essays is kind of hard. That's beside the point however.
I was thinking a bit about games, and what makes a good game good. In particular, I was thinking about games that you could play anywhere with just pen/paper (like tic-tac-toe, except tic-tac-toe isn't a really good game). In these sorts of games that don't involve any sort of luck (i.e. no dice, no drawing cards or anything) and that are guarenteed to terminate, they seem theoretically solveable, I mean you can just draw up a tree of all possible game-states and just do mini-max on it and it's solved.
What makes a game like this fun to play is if there are so many different possibilities that you can choose from that it's infeasible to actually brute force a solution out of it. Like chess. Except you need chess pieces for chess. What I'm looking for is a game like chess that doesn't need any chess pieces and is simple to explain and play.
A potential candidate could be this 'NoCycle' game I came up with.
Draw \(n\) dots on a page. If \(n\) is big, space them out a little bit.
There are two players, red and blue, who take turns connecting dots with lines. Red goes first, and draws red lines, Blue goes second, and draws blue lines.
Each turn, the player must choose two dots that haven't yet been connected with a line, and connect them.
If a player draws an edge that completes a cycle in the graph, then the game is over. If only one cycle was completed, then the player that completed the cycle wins if the number of their color edges in the cycle is strictly less than the number of edges in the cycle contributed by the opponent. Else the player who completed the cycle loses.
If a player draws an edge that completes multiple cycles, then treat each cycle as it's own individual 'minigame' (e.g. say Red completes three cycles. By looking at the edges in the first cycle and using the previous rule, we can determine whether or not Red won the first cycle or not. Then continue on for all the other cycles) If there are \(n\) cycles in total, then the player who finishes the game must win strictly greater than \(\frac{n}{2}\) cycles to win the game. Else, the player loses. OK that was pretty dumb, you can't end on multiple cycles.
If you try playing this game, it becomes clear that at large \(n\) it is very hard to see what is going on. So some additional rules should probably be introduced for human play (e.g. after a player draws an edge, both players can declare that a cycle has been completed. If neither player declares, they both say 'No Cycle', and even if there was a cycle, the game just continues then both players lose. It's a lose-lose situation.).
Huh... Look at those concentric circles you get when you join up \(n\) vertices on the circumference of a circle... nice.
I'll be back with part 2 soon. Got Putnam soon. Will be fun.