Wizuriel

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.

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.