Amazons

My amazons program is coming along nicely. In amazons, the game is over when a player runs out of moves. However, long before the game officially ends, there is usualy a point where the queens are all closed off from each other in separate rooms. At this point, each player simply uses up their moves in their rooms, uncontested. Typically, at the point that all rooms become closed off, you can just count the empty cells in each of the rooms to see who has the most moves left. For instance, black might have 21 moves left and white, 17, in which case black wins by a score of 4.

I want my program to detect the win and score as soon as the rooms have been closed off. The catch? It’s not always as simple as counting all of the empty cells in a room. Some times rooms are defective — which means that they cannot be entirely filled. There may be a section that forces the player to choose one half of the room, at the expense of the other. For instance, moving into the other section and firing an arrow may block access into the rest of the room. Solving rooms in general can be a difficult problem. If one uses a brute force search, it is trivial to solve small rooms. But as the rooms grows in size, the time needed to search grows exponentially. For instance, a room with 12 cells may only take a second to search, and a room with 13 cells might take hours!
For a human, solving the rooms is quite trivial, most of the time.

I want to add some of these smarts to an automatic solver. My plan is to figure out some easy ways to solve the trivial parts of a room, and identify defective areas, which can be analyzed separately. If that turns out to be too difficult, I’ll simply have the program automate what it can, and if it gets stuck, the human players will simply have to play it out themselves. For those who are getting curious, here is a good amazons site.