Hello.

I'm attempting to learn programming and web development and for my latest project I'm attempting to program the board game Quoridor. For those that don't know the game; basic idea is Quoridor is played on a 9x9 board, first pawn that reaches the opposite side of the board wins. During your turn you can either move or place a wall (you have 10 walls), each wall blocks 2 squares.

So right now I have the an A* search that lets my AI finding the fastest path and I use the A* search to make sure no wall placed in illegal spots (an illegal wall would completely block a player from being able to reach the end). My problem is trying to do the wall placing AI.

My first attempt was kind of a state machine. After 3 turns (so if both pawns move only they are at the middle of the board) I do a check which pawn is closer to their goal. If the player is closer I try putting a wall on every path of their best route (or the first best route that A* returns, I do check multiple ones but only return the first best one) and put the wall where the players movement is increased the most compared to how it affects the AI. If the AI is closer to the goal than I just get the AI to move.

Now the problem with this is the AI kind of stupidly and quickly runs out of walls, and doesn't place them in the best spot (since It's just going off the best route, the walls don't line up right to really slow the player, its too direct). Also one of the biggest strategies in Quoridor is placing walls defensively so your opponent can't cut off your best path (something I have no idea how to even begin to code).

So I'm now trying to think of a different way of approaching this problem. I'm kind of interested with trying a genetic algorithm / neural network to try and predict moves and act accordingly, but for the life of me I can't think how to condense the data down to even start to do that. So kind of hoping someone can point me in a better direction.

The first thing you should probably do is read what others have published about creating AI for this game. If you Google for "mastering Quoridor", you'll find two papers on the subject. I don't think they are particularly good, but they are a start.

Here's what my plan would be for this game:

• Make your path-finding as fast as possible.
  
• Implement functions to make moves on the board and to undo them.
  
• Implement alpha-beta search using difference of path lengths plus a bit of randomness as the evaluation function.
  

At this point you'll probably have a program that plays OK, at least if you implement the search reasonably well (no bugs, good ordering, hash tables, iterative deepening...). You can then work on improving the evaluation function. I would probably match my program against itself and make a database with the games. You can then use the database to make a model that predicts the result of the game given a position, and use that as evaluation function.

Having known the game for about 30 minutes, the only features of a position that I think would work in an evaluation function are the difference in path lengths and the number of walls left for each player. From a database of games you should be able to determine something like an equivalent number of moves for each number of walls in hand (a table of 10 numbers), so your evaluation function would simply be
// Returns a score that is positive if things are looking good for White
int evaluation(Board const &b) {
static int const table[11] = {0, /* insert reasonable values here*/};
return 100* (b.path_length(Black) - b.path_length(White)) + table[b.walls_left(White)] - table[b.walls_left(Black)];
}

I've never played the game (it seems quite interesting though). But it seems to me your evaluations should break down to:

• Is it more profitable for me to move or to block movement?
  

To know the answer to this, you'll have to find a way to score the possible actions. If it were me, I'd ask myself:

1. How much is forward movement worth?
   
2. How much is lateral movement worth?
   
3. What's my best-case scenario for turns taken to reach the end?
   
4. How much is blocking my opponent worth?
   
5. How will blocking my opponent affect MY path?
   

Then maybe add some weighting and 'personality' to the evaluations:

1. For an offensive player, blocking in the beginning may not be important. But it gets to be VERY important when the opponent starts getting closer to the end (hence the weighting).
   
2. For a defensive player, maybe blocking is worth more in the beginning.
   
3. Blocking a path is worth X. But the more turns it adds to the 'Best-path' makes it more valuable.
   
4. etc.
   

There's a plethora of ways that the AI can take these into account. I agree with IADaveMark though. Adding layers of obfuscation to your AI will not help anything. It may be a good practice in programming and A.I. theory. But for practicality and usability, you won't benefit from them.

-Shadow

[size=2][edit - I should have pre-read this before posting. My grammar was horrible!]

From my experience with other two-player games (checkers, chess, connect 4...) I don't think evaluating moves will make an AI opponent that is challenging enough. Typically you do much better if you evaluate positions and use minimax to search.

I'm not too sure though how to evaluate the position for a minimax tree without it quickly growing out of control / taking forever.

For an easy scenario:


Player green should place the yellow wall, if he doesn't and just moves (following the yellow arrow since that is his closest path to the end) player blue will just place a wall in front of him forcing him to have to backtrack to the one path around that series of walls. In actual gameplay this can get more complex since your best action might be placing several walls trying to make a safe path to the goal instead of moving or trying to block your opponent.


So right now the way I'm (or I was) looking at it would be:
If my path is shorter (using A* and Manhattan distance [with some weight to try and avoid paths right beside 2 walls])
a) see if placing a wall defensively is a good idea (not sure how to do without brute force since the best position in this scenario won't be from the best paths [usually])
b) move

If my path is longer
-find my opponents best path
-for each wall position on their best path try placing a wall and recalculate my best path and opponents
-pick the one that gives the best results.

That scenario would be solved fine with a depth-2 search. If more walls need to be placed, a deeper search might be needed to find that out.

The root of the tree is the diagram, before placing the yellow wall. A depth-2 search consists of all the possible moves by green (including wall placements), with each one of them followed by each possible move by blue (including wall placements). For most of the branches of this tree, blue has a move that is placing a wall blocking the arrow in the diagram, which would result in good evaluations for blue because it increases the distance to goal for green more than it increases it for blue. There will be five moves that don't allow that: blocking the tunnel on the right in four ways (the yellow wall is one of those), or placing a vertical wall along the opening on the left side (adjacent to the arrow on its left). In all those cases, blue cannot immediately block green's path.

EDIT: By the way, the "killer heuristic" would help you sort the moves in such a way that blue would try to block the opening on the left as its first move most of the time, and alpha-beta would allow you to skip looking at other blue moves.

If you can write a program that searches depth 10 or so, it will probably be very hard to beat, even with a simple evaluation function.

Here's a thought... rather than forward searching (which can be a huge potential state space), do it like a planner and search backwards from the goal.

Not really sure how that would reduce the state space, but definitely need to find some way to do that. I followed alvaro's advice and did a Minimax tree with alpha beta pruning and at depth 3+ it is pretty slow on finding the next move. Though looking at the game each position can have something like 130 children :S

Are you pruning the search space using common sense assumptions? For example, taking advantage of left/right reflection symmetry, ignoring illegal wall combinations, ignoring wall combinations which will never improve the situation, etc? And of course there's applying heuristics so you search the more likely options first, e.g. putting a wall behind the opponent is unlikely to help your cause.