How many possible ways are there to win in Quoridor?

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.

-

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?

-

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.

-
Are we supposed to take your claim that "it is impossible to find a winning strategy" as a matter of practicality, rather than as a matheamtically precise statement? After all, since this is a finite game, we can in principle find the optimal strategy for either player by recursion in the game tree. And there seems little reason to think that this method won't eventually be possible (say, in a thousand years from now) with sufficiently fast computers. –  Joel David Hamkins Jun 6 '13 at 17:22
@Joel David Hamkins Of course, I was thinking in practical terms. As Quoridor is more or less as complex as chess, it is impossible to solve it now and in the near future. It would be very optimistic to assume that such games will be solved during our lifetimes even with great technological breakthroughs. Perhaps you are right that it is going to be achievable by the technology “thousand years from now”. The mere fact that Quoridor and chess are solvable in principle is of course a trivial consequence of these games being finite. –  helper Jun 6 '13 at 19:06
As a curiosity related to Joel’s comment, it would be interesting to do some calculations showing how difficult it is to solve chess (and Quoridor) by brute-force. Chess game tree complexity = 10^123 Bremermann's Limit = 1.36 × 10^50 bits per second per kilogram. Mass of the Universe = 10^53 kg Age of the universe = 4.354× 10^17 seconds No. of chess games analyzed by the universe turned into the best computer possible < 10^121 –  Waldemar Jun 7 '13 at 11:30
Waldemar, I guess your estimates assume that we do no pruning at all, but of course, we can substantially prune the game tree, while remaining certain of our analysis, and this might considerably cut down on the complexity. (Also, could you explain the $10^123$ estimate?) –  Joel David Hamkins Jun 14 '13 at 3:02
Joel, first the estimate (10^123). The original source is Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence, p. 171 (link: fragrieu.free.fr/SearchingForSolutions.pdf). A different famous result is known as a Shannon number (en.wikipedia.org/wiki/Shannon_number). Both assume that the game lasts about 40 moves (80 plies). Thus, at least we know they don’t assume the analysis is always continued until a checkmate. The difference between the two is whether the average branching factor is closer to 30 or 35. Of course such estimates are very rough. –  Waldemar Jun 14 '13 at 9:40

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.

-