I want to create a computer player for a 2-player board game, but I don't know how to represent or to approach the problem. I would like to know what game features and topics you think are relevant. Game: The Crossing o The board is a 13x13 matrix o Player 1 and Player 2 take turn to place their pieces on empty cells o Player 1 can place at most 4 consecutive horizontal pieces each turn o Player 2 can place at most 4 consecutive vertical pieces each turn o Player 1 wins if its pieces form a path from left edge to right edge o Player 2 wins if its pieces form a path from top edge to bottom edge [ Sample game runs with red going first (image) ] What do you think? - Thanks

Well basically it looks like you have two choices on every move: build or block. Look for the shortest route to complete a path for both teams. If the other team is doing better, you need to block if you can; select the blocking move which improves your own path by the most. If you are winning, place a piece on your shortest path – preferably covering the place where you would block if you were the opponent.

A more traditional approach is to write an evaluation function (something that looks at a board and returns a number, roughly indicating how happy red is with the situation, with 0 meaning it looks like a draw). You then write a minimax searcher with a few common improvements (alpha-beta prunning, transposition tables, iterative deepening, perhaps some form of quiescence search...) and you should have a very strong opponent.

There is a lot of information out there on how to make a strong chess program, a lot of which will apply to your game too.

For the evaluation function, you can do something like finding the shortest path for each side (like in Bob's suggestion). Other much crazier alternatives include:
(1) computing how much current could go through a mesh of resistors that looks like the board,
(2) playing a few thousand games at random from the position given (yes, both players move totally randomly) and use the average result as the evaluation.

I believe (1) was first used for the game called hex. (2) and other types of Monte Carlo search are common these days in computer go.

How do you find one shortest path for one color given the current board?

Quote: Original post by Wai
How do you find one shortest path for one color given the current board?

Some modification of Dijkstra's algorithm or A* will probably do. I have to think of the details, but you are basically trying to find a path from the top of the board to the bottom of the board where moving over red squares is free, moving over empty space costs you moves and moving over blue squares is forbidden.

I think you need to use Dijkstra (i.e. heuristic = 0) because you don't know if you're one move from the end anywhere. Well, I think you should have a heuristic which is smaller for tiles near the top, but always less than 1, to ensure a quick solution in simple cases, but it won't always get the path.

For the vertical player (red):

Starting at the bottom, all tiles which are currently connected get set to a value of 0. Then, repeat:

For each column, find the highest point where you can start a move with the current lowest node value. Draw upwards for 4 squares or the most squares you can place before hitting a blue, and set their node value to 1 more than the parent node (unless it is already set to that or something lower). If placing this move causes some existing pieces to be touching, treat them all as zero cost nodes and add them to the path. This is the A* or Dijkstra process but with the additional step of adding existing pieces to the path when you touch them.

I know what you mean and I will be doing some tests.

- Thanks

[ Crossing (Flash) ]

Use the arrow keys to move the crosshair.
Hit SHIFT to melt soft ice.

One thing you can use the pathfinding for is to find out if any given potential endpoint has a chance of eventually connecting to the otherside. There is no point in building into a place that is a dead end. Similarly, you can also rate the squares as being the ones that can make it to the other side with the least amount of fuss.

therefore, you can use A* not from the points that you are at, but from every point you are not at. Use the resulting distance values to rank the squares on preferability. Then, do the same from your potential starting locations (i.e. ends of your current threads). You do some quick addition to determine the best combination of HERE -> TARGET -> EDGE. That's your list of offensive moves ranked accordingly.

In typical MinMax fashion, you can do the same for the other player... therefore generating both an "urgency" utility for blocking and also determining through what corridors his best path is. You don't have to block directly... just make life more difficult for him. Rank those squares highly for defense.

Combine the offensive and defensive lists in such a way that the defensive weight is based on the urgency of how close he is to winning.

Select the best move from the combined lists.

Hi, I think that is what I have done:

I compute the minimum distance from a cell to each edge.
Then I add the distances to opposite edges to get an approximate
number of moves required to connect across. Then I scored each
cell by the moves it take to connect top and bottom, and also
left and right. The AI places blocks at a cell with lowest score.

The current algorithm does not simulate or evaluate future boards.