Math: TRON Light Cycle Optimal Strategy
Has anyone done research about the opitmal strategy for the TRON's light cycle?
We assume it as a perfect-info mathematical game, on a n×n square grid. Suppose the cycles are red and blue. Red moves first. Each turn, the player moves one square edge. The first player that doesn't have legal move loses. Also, we suppose it's a board game, and both players knows the other's position exactly at all times. We also for now assume that the starting position is at the opposite corners of the board.
- 2×2. Second player win.
- 3×3. First player win.
- 4×4. Second player win.
- 5×5. First player win.
The pattern seems clear. On Odd boards (where there's a center spot), first player win. On even boards, second player win.
Now, if we assume that the starting position is on the opposite of the same edge, the situation is the same. If we assume they start on the middle of the opposite edges, the situation remains the same too (when the edge is even, we assume they start at opposite nearest edge-center).
So, it looks like game isn't mathematically interesting.
Making the Game Mathematically Interesting
But what about on boards of various regular tilings?
After a quick look, it seems the analysis is pretty much the same. Whoever can get to the center wins, and if there is no center, second player always win.
Now, what are some ways to make the game interesting, or introduce some handicap rules, so it's more mathematically complex?
On a Flat Torus
What if it's played on a Flat torus?
If we start with n×n torus (that is, square torus), i think the situation is the same. When n is even, you can think of this as both player's light cycle having the same speed and start at the same time. Each want to maximize his area. When they meet head to head, both have no choice but turn 90° and race side by side, and when they both traced a circle, then turn back and race to the other side, and repeat. Eventually, the situation is the same as n×n bounded square. The first player will first run out of space.
If n is odd in a n×n torus, then first player wins.
Now, what about a m×n torus, where m is “n+1”? …
Other topogicaly variation worth thinking about are m×n Moebius Strip or Klein Bottle or projective plane the Cross-Cap.
Am guessing that they all does not matter because player's moves are local, so topology of the space doesn't matter.
So, to make it interesting, perhaps each player can have 2 cycles, placed across 2 opposite positions in a space. Each turn, he can move one of his cycle by 1 unit.
Own Wall Can be Passed?
Now, let's go back to the original bounded square on a n×n grid. What if, one can pass his own walls? This would force the game into a draw, because a player can just draw a small square and keep running inside it.
Perhaps at each turn, the player can delete one spot. (the second player should be the first allowed to do this) Or, pick a spot that only he can still pass (For example, mark a spot of his own color). This can be thought of as throwing a bomb.
PS If you like to play light cycle, there are 2 very nice free ones:
I think a very promising rule is to introduce random walls, or maze. The start position of each player will also be random.
Google Programing AI Challenge: Tron Light Cycle
Discovered that Google actually has a programing AI Challenge. It's a contest for programers to write program that fight each other in a game as a bot. And, one of their game is Tron Light Cycle. Here's the site:
[a1k0n : Andy Sloane's weblog http://www.a1k0n.net/2010/03/04/google-ai-postmortem.html ]
- TRON Operating System
- μTRON Keyboard Review
- Emacs eshell Featured in Movie TRON
- Go Board Game on Hexagonal and Triangular Grids
- Bird Flight V Formation As Geometry Problem Of Max Visual Contact
- Modeling Math Problem Into a Question in Formal Language
- Knitting, Chinese Knots, Braid Theory
- Maze and Math in Video Games
- Juggling: Orbits in Siteswap Notation