Quoridor is a board game in which the objective is to move a piece across to the other side. A player can put up fences to block other players from advancing forward. How many possible ways are there to win in this game. Are there optimal strategies? Note that there can be one to four players.
closed as off-topic by user21574, Steven Landsburg, Chris Godsil, Gabriel C. Drummond-Cole, Neil Strickland May 11 '17 at 10:42
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question does not appear to be about research level mathematics within the scope defined in the help center." – Chris Godsil, Gabriel C. Drummond-Cole
The complexity of Quoridor is so high (see http://en.wikipedia.org/wiki/Game_complexity) that of course the game cannot be solved – it is impossible to find a winning strategy. Thus, we cannot determine how many winning strategies are there.
Moreover, as the draw cannot generally be excluded (see http://boardgamegeek.com/thread/447889/draw-possible) it’s not even possible to apply a strategy-stealing argument in order to prove that the first player has a winning strategy. Perhaps, some work could lead to the conclusion that the draw in an ideal game is impossible. This seems much more achievable than finding a winning strategy.
As for your question: “Are there optimal strategies?”, the answer is obviously positive. If there are no winning strategies, the strategy forcing a draw is an optimal one.
Quoridor hasn't received a lot of serious attention, so many basic questions remain wide open.
If you're a beginner then you might want to check out this blog for some basic strategies. As far as I can tell, though, the state of expert human and computer knowledge is still rather low, again because not much effort has been directed at this game.
From a theoretical standpoint, a natural first step would be to prove some kind of hardness result. Showing that Quoridor (with unlimited board size and number of barriers, of course) is EXPTIME-complete, or even NP-hard, would be an interesting result IMO. The game is very geometric so I think it would probably be kind of fun to try to build the appropriate gadgets for a hardness proof.
You have to put some reasonable constraints; the game allows either to add a boundary or to add a fence. Thus, players may move the player token arbitrarily many times before reaching the opposite side.
Is it even reasonable to assume that a player always move in such a way that the shortest path to the opposite edge do not increase?
Although, as others have noted, Quoridor is not solved, my guess is that if it were, the second player would have a winning strategy, rather than the first. The reason is that even though the first player moves first, the second player can force a jump which puts him ahead.
There are two simpler cases which lead me to believe this:
- If neither player places any walls, or only one wall, second player can always win.
- On a 3x3 board with one wall, and a 5x5 board with two walls, the second player can always force a jump and win.
There are two variants of Quoridor (2-player game and 4-player game).
I think we could rephrase your question “How many possible ways are there to win in Quoridor?” as “How many winning strategies are there in Quoridor”. Of course the answer depends which variant we are talking about and whose strategies we analyze. I don’t think we could give precise positive numbers here. Sometimes the answer is “zero”, sometimes “one or more” and sometimes “zero or more” (which is of course trivial and does not tell you anything important).
For a 2-player variant, as Helper noted, we can probably only prove that there’s no winning strategy for the second player. By the way, the very probable conjecture is that there exists a winning strategy for the first player.
If it comes to a 4-player variant, you could prove – by a strategy stealing argument – that a coalition of 3rd and 4th players does not have a winning strategy. Probably we could also prove that it’s a queer game (a game where no player has a winning strategy) by showing that there exist a strategy for a 3-player coalition preventing the player not being in a coalition from winning. It seems possible to prove even something stronger, namely that a 3-player coalition has a winning strategy. Thus, we can perhaps show that the number of winning strategies for a 3-player coalition is greater than or equal to one.