The Genius, by A Skymin’s Mind #7

Monorail

Used as Death Match of Season 3, Round 10 and Season 4, Round 6. (Discussion of S4E6 in particular will come later.)

Rules

The objective is to be the one that completes a train track, or to be the one that declares it’s impossible (correctly).

There are 18 square tiles used in the game. Two of them show straight tracks, the station tiles, which are already placed on the grid; the remaining 16 tiles can be made to show a straight track or a bend track, which are to be placed. Players place tiles so that sides match (a track leading to a non-track side is not permitted; think of tile-based games (such as Dominoes or Carcassonne, where sides of tiles must match). A player may place one to three tiles at once, but all of them must be played in a straight line contiguously (think of Scrabble, where you cannot place your tiles separated, only that it’s even more strict; the tiles must be contiguous, not separated by already existing tiles). However, the track itself doesn’t need to be connected; as long as the tiles placed are connected, it’s fine.

The person who places the last tile, completing the track using all tiles already placed, wins. However, a player can also declare that it’s impossible to complete the track, in which the opponent must either complete it (for a win to the non-challenger) or resign (for a win to the challenger).

Also see this video from the Facebook page, which is unfortunately in Korean, but gives illustrations.

Discussion

I wrote up an introduction to combinatorial game theory, which is used in this discussion, if you’re not familiar with it before.

First, since in all cases moves are available to both players, this is an impartial game and so Sprague-Grundy theorem declares that it has a Grundy value (aka nim-value, nimber). This makes it possible to analyze the game by finding nimbers.

Sprague-Grundy theorem requires the game to have the normal play convention (player that cannot move loses). For the purpose of this game, it’s easy to decide whether a track can still be completed or not; if it’s not, the current player can declare so for a victory. It’s easier to interpret this as “making a move that makes the track impossible to complete is an illegal move”, so that in case there is an impossible track, the previous player must have made an illegal move; if they indeed didn’t have any legal move, they have lost by that point for having no legal move. This makes the game to satisfy the normal play convention.

Now, this should be solvable by bruteforcing the way, but I’m too lazy to code or let enough computer-hours to do the job. Instead, I will provide one move that I’ve analyzed, which is losing for the first player but the forced win is so deep that there are only two winning moves, both hard to find, and any other move (about 100+ moves exist in any position) loses. The station is marked in orange and the move I suggest is marked in green; the only two winning moves are those in red (both playing one tile).

Monorail - A hard move to counter

Monorail – A hard move to counter

The first reason is that the only possible track involving these tiles is the following:

Monorail - Only way to complete

Monorail – Only way to complete

This can be proven, but it’s a good puzzle nevertheless. (Aka I’m too lazy; you go figure it out yourself.)

Now, with all orientation of tiles fixed, the game suddenly becomes a completely new face: You may put one to three tiles in a contiguous straight line over the red tiles (still with connectivity to the rest of the board), where the last person to place a tile wins. This is way simpler to analyze, especially armed with Sprague-Grundy theorem. We can prove that the left L-shaped part has nimber *6, and the right d-shaped part has nimber *7. Thus, by using Nim strategy, the second player must play in the right part to reduce its nimber to *6. As it turns out, only the two moves above have this property; the rest doesn’t make the nimber *6, and thus the first player wins by moving on the left part appropriately. (Or if the second player plays in the left part, the first player can play in the right part to equalize the nimbers.)

With human players (and hence possible to make mistakes, especially those as deep as above), that move is a strong one even if losing. I haven’t found a winning first player move—indeed, I’m not even sure whether this is first-player or second-player win—but first player has a major advantage as they can force a major part of the track, if not completely, so that the second player must think carefully. On the other hand, once the track is completely determined, the game becomes simpler to analyze as above, so one must be careful of this if the opponent is aware of the strategy.

Advertisements

12 thoughts on “The Genius, by A Skymin’s Mind #7

    • If there is, I haven’t found any, but Hyunmin’s position at 1:23 is clearly losing. The track is completely determined; he has an L-part at the left and two dominoes at top-middle and bottom-rightish. The two dominoes cancel each other since they have the same shape (if one plays in one, the other plays in the other; also their nimbers are both *2, adding up to *0), and the L-part has nimber *4 which is not zero, so the player to move (Jinho) wins. Playing either a single piece at the top of the L (leaving a smaller L of three squares) or two pieces in the middle of the L (breaking it into two single squares) would have won for Jinho. His next move was an error though, giving Hyunmin the win (due to two identical regions always winning for second player; see above).

      As for after Hyunmin’s first move, I haven’t completely analyzed that yet, but the track is already completely determined so one can try doing the same as in this post.

      Reply
      • “The two dominoes cancel each other since they have the same shape” – I thought they do not cancel each other out, because in this portion, there are 2 (2 double-tile), 3 (2 single-tile + 1 double-tile) or 4 (4 single-tile) moves instead of just 2 double-tile moves, right? Since Hyunmin plays after Jinho, he could have gone for 3 moves instead of 2 or 4.

        “Playing either a single piece at the top of the L (leaving a smaller L of three squares) or two pieces in the middle of the L (breaking it into two single squares) would have won for Jinho.”
        Wouldn’t this will depend on how the above dominoes play out as well? Hyunmin could have broken up one of the dominoes to create an extra move so he gets to place the last tile regardless.

        Sorry, I’m not that good at such puzzles, but just curious at the possibilities of how Hyunmin as the last to go could have manipulated the no of tiles that can be put from a reactive position.

        Reply
        • They do. Whoever is winning shouldn’t play on either of the dominoes; if the opponent plays on one, they can mirror the move, making sure that the two dominoes contribute an even number of moves. Hyunmin cannot force the dominoes to be spent in three moves, only if Jinho made a mistake.

          And yes, the L also works because the dominoes cancel each other.

          Yes, combinatorial game theory isn’t a simple thing. I think I shouldn’t have begun the post with “by Sprague-Grundy theorem”…

          Reply
  1. Pingback: Introduction to Combinatorial Game Theory, Part 1 | Chaos at the Sky

  2. I wonder if any of the S4 players could have found this? I know Yoohyun knows English, Kyunghoon went to school in the US so surely he does as well, there are probably others…

    Reply
    • Even if they found this, the big problem is learning combinatorial game theory. I don’t think any of them knows this; Yoohyun should know game theory by virtue of being a poker player, but combinatorial game theory is not quite the same thing. (Also, I’m pretty sure Hyunmin should know English too, if he’s a student in KAIST. English isn’t that uncommon in Korea.)

      Reply
  3. Someone mentioned on a podcast, and it turns out that if you look closely Kyunghoon actually did at least think about your move:

    Apparently he decided that his was better, although they seem about equal to me.

    Reply
    • Achievement unlocked: Affect one The Genius player’s thoughts

      Let’s just hope Kyunghoon actually got the idea from this.

      Meanwhile, both moves are losing, so they are equal against a perfect opponent. I guess his is better because the analysis is harder (the layout isn’t fixed, so there are many more moves, so it’s hard to compute the winning move for the opponent), while on the other hand mine is better because the analysis is simpler (if the opponent doesn’t play a winning move, you can find the winning move easier)…

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s