7
$\begingroup$

There is a relatively simple flash game that I enjoy playing -- http://www.gamedesign.jp/flash/chatnoir/chatnoir.html is one version of it, though I've found many -- and it centers around trying to trap a player moving in an 11x11 hexagonal grid. The cat (Player 2) in the linked version of the game is frustratingly non-rational, in that it frequently ignores winning moves, but it seems relatively simple to me and most likely solvable (closer to checkers than chess in terms of numbers of moves and ease of telling if you're "winning" at any given point), but after some casual googling I haven't found any analysis or anything. Does anyone know of any?
To describe the game a little more fully: there's an 11x11 hexagonal grid, with each row offset from the one above and below it, so a non-border hex can move to two spaces in the row below it, two above it, and one on either side. Player 1 starts on the sixth hex of the sixth row, and each turn must choose any of the bordering hexes to move into. Each turn, before Player 1 moves, Player 2 can choose to block a hex, keeping Player 1 from moving into it. Assume that at the beginning of the game, Player 1 can block any six hexes (this is a bit of a departure from the linked game, where a semi-random number of random hexes are blocked, but that seems less interesting and harder to analyze). Player 1 wins if he or she exits the board, and Player 2 wins if Player 1 cannot move (is surrounded by blocked hexes). Who wins, assuming both players play optimally? How many hexes does Player 2 need to block at the beginning of the game to guarantee a win?

$\endgroup$
  • 4
    $\begingroup$ On a rectangular grid (not a hex grid) this is called the Angel Problem. $\endgroup$ – vadim123 May 4 '13 at 2:02
  • 2
    $\begingroup$ You seem to flip the Player numbers halfway through. It looks like the switch happens starting with "Assume that". In your sentence "Assume that" it seems you want Player 2 to block some hexes. If Player 2 gets to choose, she can block all the hexes around Player 1 and the game is over. So I think the number of blocked hexes must be lower or the hexes to block must be random. $\endgroup$ – Ross Millikan May 4 '13 at 2:29
  • $\begingroup$ @RossMillikan-- you're totally right, I did do that! Thanks for the catch. $\endgroup$ – Henry D May 4 '13 at 13:35
  • $\begingroup$ @vadim123 -- I had never heard of the Angel Problem, and from a quick glance at Wikipedia it looks very similar, but not quite identical, since it's played on an infinite board and doesn't have an end goal for the moving player other than survive indefinitely. Thanks though, I had never heard of that before. $\endgroup$ – Henry D May 4 '13 at 13:37
  • $\begingroup$ The infinite board is not essential to the Angel Problem; it can be played on a finite board and the angel wins if it gets off the edge. For the 1-angel, if the board is 32x33 or smaller, the devil will win; if it is larger the angel will win. $\endgroup$ – vadim123 May 4 '13 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.