

Hi all,
I am surprised to see so little posted about this game, it seems to have so much depth.
One thing I have been looking into recently is the total amount of possible moves. Somewhere on this forum someone said the gametree for Quoridor is larger than chess. Does anyone know the total amount of possible game states, or how to calculate them?
For example, if you look at a board with no fences then you can calculate the total number of possible game states easily. The board is 9x9 and there are 81 total squares. At any one time, the first pawn will occupy one square. This leaves 80 open squares for the second pawn be on. That would be a total of 81x80= 6480.
Of course the first pawn could be located on any one of the 81 squares, so for each square there are 6480 game states, or 6480x81 = 524,880 game states total (on the open board with no fences).
The fences are going to make this number explode. I've calculated that there are 64+64 = 128 possible fence locations. Once you place the first fence, the total number of possibilities will drop by 4 (3 if the fence is placed in a space touching the edge of the board), but beyond that I didn't venture.
These calculations are all preliminary, just a record of my thinking. I am trying to get a grasp on how one early move will have effects on the later game.

Nick Case
England Epsom Surrey
https://www.facebook.com/amuse.ment.92

Roostaroost wrote: At any one time, the first pawn will occupy one square. This leaves 80 open squares for the second pawn be on. That would be a total of 81x80= 6480.
Of course the first pawn could be located on any one of the 81 squares, so for each square there are 6480 game states, or 6480x81 = 524,880 game states total (on the open board with no fences).
I'm afraid not. The first pawn can only be placed in one of nine squares, the opponant in the opposite nine. Thats 81 perumations for turn 1. After that each pawn can in 2 (corner),3 (side) or 4 directions, or place a fence.
Regardless, I'm struggling to see what this mathematical exercise achieves..



Big Bad Lex wrote: Roostaroost wrote: At any one time, the first pawn will occupy one square. This leaves 80 open squares for the second pawn be on. That would be a total of 81x80= 6480.
Of course the first pawn could be located on any one of the 81 squares, so for each square there are 6480 game states, or 6480x81 = 524,880 game states total (on the open board with no fences).
I'm afraid not. The first pawn can only be placed in one of nine squares, the opponant in the opposite nine. Thats 81 perumations for turn 1. After that each pawn can in 2 (corner),3 (side) or 4 directions, or place a fence. Regardless, I'm struggling to see what this mathematical exercise achieves..
Oh yes, you're right! I framed this poorly.
I am trying to find the total number of game states as a means of thinking about good and bad decisions in the game. For instance, if you place a wall in the middle of the map on your first turn you eliminate certain number of possible game states. This makes your next decision a bit easier. Of course there are far too many possibilities to make this a valuable calculation for a human, but a computer could take on the task. Regardless, I was thinking along these lines hoping to stumble upon some strategic wisdom.



Roostaroost wrote: Hi all,
I am surprised to see so little posted about this game, it seems to have so much depth.
Me too. I really would like to read more about strategy.
Roostaroost wrote: One thing I have been looking into recently is the total amount of possible moves. Somewhere on this forum someone said the gametree for Quoridor is larger than chess. Does anyone know the total amount of possible game states, or how to calculate them?
10^162.
You can see the gametree complexity of Quoridor and other games here: http://en.wikipedia.org/wiki/Game_complexity#Complexities_of...

Russ Williams
Poland Wrocław Dolny Śląsk

Roostaroost wrote: I am trying to find the total number of game states as a means of thinking about good and bad decisions in the game. For instance, if you place a wall in the middle of the map on your first turn you eliminate certain number of possible game states. This makes your next decision a bit easier.
Although it's theoretically interesting, this specific goal makes no sense to me. If you reduce the number of successor game states, that makes it easier for you to look ahead, but also easier for your opponent, so how does that help you strategically? Am I misunderstanding what you mean?



russ wrote: Roostaroost wrote: I am trying to find the total number of game states as a means of thinking about good and bad decisions in the game. For instance, if you place a wall in the middle of the map on your first turn you eliminate certain number of possible game states. This makes your next decision a bit easier. Although it's theoretically interesting, this specific goal makes no sense to me. If you reduce the number of successor game states, that makes it easier for you to look ahead, but also easier for your opponent, so how does that help you strategically? Am I misunderstanding what you mean?
I mean in coming up with strategies for the game in general. This exploration in intended to discover some strategies about Quoridor. When is a wall placement strong or weak? What do you want to do on your first turn? How do you respond to certain moves from your opponent? I began with these questions and started thinking about possibilities, and this led me to ask about the total number of game states.



Big Bad Lex wrote: Roostaroost wrote: At any one time, the first pawn will occupy one square. This leaves 80 open squares for the second pawn be on. That would be a total of 81x80= 6480.
Of course the first pawn could be located on any one of the 81 squares, so for each square there are 6480 game states, or 6480x81 = 524,880 game states total (on the open board with no fences).
I'm afraid not. The first pawn can only be placed in one of nine squares, the opponant in the opposite nine. Thats 81 perumations for turn 1. After that each pawn can in 2 (corner),3 (side) or 4 directions, or place a fence. Regardless, I'm struggling to see what this mathematical exercise achieves..
I had to look at this again, and I think we are both wrong.
According to the rules on the Quoridor website the first player's pawn and the second player's pawn have to start in the center of their base lines.
From here, you can imagine both players moving around the board and not placing any walls (I say more about this below). In this scenario you can see that the first pawn, at any time, can be located on any one of the 81 squares, and the second pawn therefore has the possibility of occupying any one of the other 80 squares. Consider every one of the first pawn's 81 options, and for each of those options the 80 that follow for the second pawn, and this is where I derived the 81x80=6480 possible game states for just 2 pawns on an open board. (I then said to multiply 6480 again by 81, but I think this is just wrong.)
One thing I forgot is that for each pawn there are nine squares that each result in a win when occupied.
Looking just at the first pawn, when it occupies any one of its nine winning squares, then the game is over and the second pawn can not be located on any one of the second pawn's winning squares. So, there have to be a number of possible game states subtracted from the total of 6480. I am going to try and tackle this, but hopefully someone more astute will be interested in this and beat me to it.
Of course I have to explain why I think this calculation is important, and elaborate on what I said above about imagining both players moving around a board and not placing fences.
In this scenario you have each player moving, perhaps progressing towards the goal, or perhaps moving close to the edge. A player moving towards the edge seems to be making a strange (or maybe I should just say bad) decision. You could get something that looks like this:
I think it is safe to say that no game would ever find itself in this position. I think most players will stay towards the center of the board and progress towards their goal, unless of course fences push them outwards. But, now that we have begun thinking about the game this way, it is possible for us to highlight one of the pointless possibilities and see that we never need to consider scenarios like this. That is to say, by thinking too hard about something that doesn't seem to matter, in the least we have highlighted an area of the game that we otherwise might not have considered and labeled it as unnecessary.
I think this approach (counting possibilities) is enlightening. Consider two highly skilled players who like to save their fences, or put another way, they like to respond to how their opponent fences. They don't like to make the first "fence move". Two players in this scenario might actually find themselves in a strange position like this, moving around the board and jockeying for position until they see an advantageous opening.


