Return to Answer

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

• Alternative adversarial 2 player version: One player is the target, and the other player is seeking the target. Each player can move one square orthogonally or stay still. Walls are added as in the multiplayer game, and the game ends when the seeker moves onto the target's cell. The score of each player is the number of moves the game lasted. Lower score is better for the seeker player, higher score is better for the target player. The target can always see the location of the seeker. The seeker can never see the location of the target. Might also be interesting to allow both players to choose where to place a wall on their turn (in addition to moving). This might open up the possibility of double bluff. Walls would still be prevented from being placed on a cell that doesn't leave a path from seeker to target. Would this be more/less interesting than the multiplayer version? Are they sufficiently distinct to post as separate challenges, or should one be chosen as the one to be posted? Would this adversarial version work best as two KotHs that use each other's answers to judge their own answers (like a cops and robbers challenge) or should all the seeker answers and target answers be posted to one challenge? Alternatively each answer could be required to deal with being either a seeker or a target, but I like the idea of people being able to specialise and build just one or other, without being obliged to write both.

• A player can move to any orthogonally adjacent cell (including staying still).
• A player cannot share a cell with another player.
• A player cannot move onto a wall.
• A player can move onto the target, but will have no way of knowing that this has happened.

Play will continue until no wall can be placed for 10 consecutive turns. The player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many, and in most cases there will be a player on the target cell, meaning only a single winner.

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own cell. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

• A player can move to any of the 4 orthogonally adjacent cells (or stay still).
• A player cannot share a cell with another player.
• A player cannot move onto a wall.
• A player can move onto the target, but will have no way of knowing that this has happened.

Play will continue until no wall can be placed for 10 consecutive attempts (note that attempts only occur with probability 1/7 each turn so this will take more than 10 turns). When play stops the player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many, and in most cases there will be a player on the target cell, meaning only a single winner.

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?