One of the games Ludus has used in their national tournaments is Slimetrail. This game is simple enough that it can be played by a wide age range, but there are many complicated strategies that can be used by more advanced players.
Slimetrail is played on a connected graph, with one vertex colored Blue, another colored Red, and a third vertex with a moveable piece or token which will create the trail of slime. The two players alternate turns moving the token one space, then marking the previous space (where the token was) a third color (usually green). The token can never be moved back to one of these "slimed" spaces.
A player wins when the token is moved onto the space of their color. Since we want to make sure that one player can still win, it's not allowed to move the token to a space where it can't reach at least one of the two goals.
In all the examples I've seen, Slimetrail is played on a grid, with adjacencies in all 8 directions. Apparently, it's also played on hex grids.
I wrote a playable version using Javascript. My auto-AI players are terrible at this game, but you can still try it out. In order to make this strictly-combinatorial (the last player wins) I altered the rules slightly so that you can't move to your opponent's goal space.
(Edit: the link to the game didn't auto-clickableify, so I added a clickable link.)
Red, Yellow, and Green Hats
17 hours ago
Bonus comment: This game is very similar to undirected vertex Geography, with a different---and partisan---ending condition. Can the polynomial-time solution to undirected vertex Geography be used to solve this? More importantly (not really) should this be listed as a variant in the ruleset table?
ReplyDeleteSince we can check for connectivity of the graph in polynomial time (right?), and the connectivity we care about ("Is (red and snail) or (blue and snail) in the same component?") is even easier to check, then shouldn't this also be polynomial?
ReplyDeleteYes, that is a solution we can use to see if the game is still in a legal position. Undirected-Vertex Geography has a polynomial solution to determine the outcome class, not just the legality of the board state.
ReplyDeleteAh
ReplyDeleteExcellent and very exciting site. Love to watch. Keep Rocking.
ReplyDeletealiza sheikh