1
$\begingroup$

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These tiles connect together to make paths.

At the start of the game there are 8 pieces belonging to 8 players which begin at random points on the edge of the board and players take turns placing tiles in any orientation they desire. The pieces then move along the newly created paths to the end and players must place tiles so that their piece moves. Pieces are removed if they collide with one another or move off the edge of the board. ( http://en.wikipedia.org/wiki/Tsuro )

What is the probability that, with a randomly generated tileset, all pieces can survive 'til the end. I.e. that they're all clustered around the empty square? All players can see the entire tileset so they can play "perfectly". The original game is for a specific tile set and a $6 \times 6$ grid but I'm more interested in the general game.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I would not be surprised if the probability was near the probabilty for a random matching between the points of a given set forming a special submatching. For a board holding k by k many tiles, this is the ratio of matchings from 8 points to a set of 8k points divided by all matchings on 8(k+1) points. This ratio seems close to 1: I get $2^8(8k)!(4k+4)!$ in the numerator and $(8k+8)!(4k-4)!$ in the denominator. This doesn't answer the question in case of perfect play, but it does suggest in cooperative play that it is likely to acheive the goal of noone moving from outer edge to outer edge after the graph is built, even though the 8 outer points for the special matching have been chosen in advance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In fact, here is a start at a cooperative play strategy: Match up the 8(k-1) points first, then arrange for a special matching among the remaining. In actual competitive play of the game, I imagine it is easy to knock others or yourself off, so that all 8 players surviving has a likelihood much smaller than 1 over (8k choose 8). $\endgroup$
    – The Masked Avenger
    May 4, 2015 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.