Posted by: Raiun | February 25, 2013

Board Game AI Design

I recently had a short discussion with someone about a board game I’d never heard of called Quoridor. He expressed interest in designing an AI for the game, so I thought I would take a stab at outlining, in a general sense, what an AI might look like for it. I’ll start by describing the basic setup of the game, for those not familiar (and who don’t want to browse the Wikipedia page linked above). Quoridor is played on a 9X9 grid of squares, with 2 or 4 players. Each player has a pawn, and a collection of walls. 20 walls are distributed evenly among the players. The pawns start in the center square of each edge of the board, or opposite each other in a two player game. Each player takes turns either moving their pawn or placing a wall. Pawns can be moved in any of the four directions (no diagonals), and walls can be placed anywhere on the board, as long as it only covers at most two squares, and doesn’t completely close off the ability for the other player’s pawn to reach the other end of the board. I should mention that the goal of the game is to reach the opposite edge of the board first, using your walls to slow the other players and create a path for yourself.

 

The most difficult part of any board game (or any game, really) AI is making it challenging to play against. It’s easy to make an AI that moves somewhat randomly and hope that it somehow manages to present a challenge, but to make an AI that actually surveys the board and makes intelligent decisions is very difficult. When humans play these sorts of games they tend to look into the future, anticipating their opponents future moves and planning out a few possible moves in advance. Ideally, we need to be able to make a computer AI do that as well, because any good strategy involves planning for the future. It’s entirely possible in almost any game to make what appears to be an excellent move, only to have it turn into a disaster the very next turn, or a couple of moves down the road. This turns into a very computationally difficult problem for a computer to handle, because while people are able to visualize the board and quickly narrow down possible moves to moves that make sense, the computer lacks that ability, in traditional computer architectures at least. This is because, inside a computer, everything lacks context. When it boils down to it, a computer is only capable of doing one thing at a time, and only presents the illusion of doing many things at once because it is able to do them VERY quickly. This is called serial processing. The act of looking at a game board (with human eyes) and narrowing down the potential moves is a feat of parallel processing (which, incidentally, the human brain is VERY good at, although we aren’t great at serial processing)

 

Let me clarify a little bit. Imagine a game board, with walls and pawns placed all over the place. At a glance a person can identify where every pawn and wall is located at the same time. Now imagine that instead, you were playing the game from inside a box, with no way to actually look at the game board. Instead, you can ask someone outside of the box what is in a single square of the board, and they write down the square’s contents on a slip of paper and pass it to you. You can keep the scraps of paper to make a single move, but as soon as you’ve made your move, you have to throw them all away and start again. That’s maybe not the best analogy, but it’s a little bit like what being inside a computer is like. Obviously a computer is able to keep track of everything’s location in its memory, but when it comes to actually making decisions, it has to process it each piece at a time, which is very time consuming. This is compounded by the fact that in order to plan several moves in advance, it needs to do the same, very time consuming operation, once for each move it plans. Of course, if it discovers a major flaw in the plan three moves later, it will have to start from scratch. Now you probably understand why Chess games against computer opponents used to take such a long time, although it’s less of an issue now on today’s fast computers. Alright, I think I’ve stressed that enough, now on to The PLAN.

 

What I would do, for a somewhat simple, straightforward, and *hopefully* challenging AI, is keep track of the amount of moves that each player has to make in order to reach the other end of the board, moving along the shortest possible path that currently exists. Then, each time it is the computer player’s turn, here are the steps it would take:

  1. Check if the AI can win by moving its pawn (shortest possible path to the other end of the board = 1), and move it if it can.
  2. Check all possible wall placements. Discard any that are invalid, and discard any that increase the number of moves that it would take for the AI to reach the other end of the board. Keep the rest in a list, and compare each one to discover which move would increase the other player’s moves by the most, and impact the AI’s moves the least. Find whichever one fits that criteria the best and subtract the impact to the AI from the impact to the player, to get a sort of “net impact” that placing the wall would have. If you would lengthen your opponent’s path by 3 and yours by 1, then your net impact is 2. There might be many moves that will have the same net impact, keep them all in a list.
  3. If the net impact is lower (or maybe equal) to the benefit of moving the AI’s piece along its shortest path (which is generally always 1), then move the piece. Basically if you can’t place a wall without hindering yourself more than your opponent, then move instead.
  4. If you didn’t move your pawn, then select one of the wall moves from the list of high impact moves that you kept from earlier. Pretend to make that move. This is where things can get really ugly, because now you have to simulate potential moves that the other player can make. It’s fair to assume that the other player will make the best possible move, so you have to find out what that is (using a similar technique to the previous steps) and then assume they take it. Now plan your next move assuming they have taken their best possible move, or perhaps moves if they have several moves that are equally good. To get a really good plan you should plan a few steps in advance, so you should repeat this several times.. you can see where this becomes time consuming. If you get to the end of your plan without running into any major snags (ie, losing the game, or forcing yourself into a horrible situation) assuming the other player makes their best moves, then take your Pretend move for real.
  5. Wait for the player to make their move. If they make a move according to your plan, continue with it. If not, you have to reevaluate it, because now a move could be available to you that is even better than your original plan. Go back to step 1.

 

That’s it! Easy, right? Well, really I’ve glossed over a number of things here, intentionally. Partly because I’m actually not terribly familiar with the game, partly because of complexity. I’ve kind of assumed that the programmer has access to a sort of “Find best move” or “Find list of best moves” algorithm. In theory that shouldn’t be too difficult, but to make that kind of thing run FAST is a challenge. Similarly, I glossed over the “find shortest path” algorithm which is necessary. I’ve also been assuming that we are creating this using a procedural programming language, which isn’t the best way to make an AI (but it’s what I’m most familiar with). I almost guarantee that this strategy could be improved upon (and probably would need to be improved to pose a real challenge). One thing I thought about was the idea that you might want to plan as many turns in advance as the length of your shortest path, basically plan the exact steps you need to take to win from your current situation. That would make it much easier to take into account the fact that you have a limited number of walls (but might take forever). The worst outcome would be for the AI to use all of their walls early and then have no way to impact the game beyond the first several turns. This is also a reactionary AI because for the first moves it will always behave very similarly, especially if it moves first. That can make it very predictable.

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: