A scoring approach to computer opponents that needs balancing

Question

This question is about an approach to computer opponents that I have created and are either currently being used, or are planned to be used, in several computer games.

Background

Last year, when trying to improve a computer opponent for a game called "Minesweeper Flags" (short description: A turn-based multiplayer version of Minesweeper where you have to take more mines than your opponent), I strongly changed the way my algorithms worked. Instead of using an approach like if-else-if-else, I am using a set of "scorers" with specified weights to determine what the best move is.

You might think that for a game like Minesweeper Flags, it's only about making moves that gives you the highest probability of taking a mine, but it's not that simple. Which move the computer will make usually depends on several features for that specific move in the current game state. Examples of features:

• What's the probability of this move scoring a mine?
• What's the probability of revealing anything to my opponent here?

Description of the system

The system basically works like this:

1. "Pre-scorers": Some pre-analysis is done for the current game state (in terms of Minesweeper Flags, this is usually: Calculating all the probabilities)
2. "Scorers": A set of ordinary scorers are asked to determine the score for each possible move, each scorer applies scores according to it's own criteria. The scorers can check the results of the pre-analysis that was made.
3. The scores calculated in the above step is summed together and is set to be the score for a move.
4. The moves are sorted according to their score and ranked so that all moves with the same score gets the same rank.
5. "Post-scorers": The result of the above can be sent to "Post-scorers" that have the possibility to modify the scores of any fields in any way they want, according to the post-scorer's own rules.

When combining a bunch of pre-scorers, scorers (with their weights) and post-scorers, it's becomes what I call a score configuration.

Example result

This is an example of scores having been applied to Minesweeper Flags. This is the map that was scored:

And this is the output of an actual score configuration. It is showing the rank of the possible moves, where 1 is the best rank and has been highlighted in white:

Thanks to having written highly flexible code, this approach to AIs can be inserted into other games as well.

Advantages and disadvantages

Below are some advantages and disadvantages of this system that I can think of myself

Advantages

• It's very easy to create a whole lot of different configurations for AIs.
• It is possible to use with Genetic Algorithms: Each scorer has an associated weight, the weight can become the gene.
• Using some tools, it is possible to check why a specific move was made and which scorers were mainly responsible for that move
• Using tools, it is possible to create a map of the overall score/rank of possible moves (like the screenshot above)
• By applying scores to the way the human plays, it is possible to create an "#AI_Mirror" which tries to make moves that it thinks the human would make

Disadvantages

• It can be extremely difficult to adjust a score configuration "correctly", to make the AI play as good as possible.

Questions

• Is the system I have built here widely known in the AI world? What would it be called in real AI terms?

• Does this approach make sense or is there a different approach that you would recommend?

• What ways are there that could make the process of tweaking a score configuration easier?

Regarding the last question, I am aware of the possibility of using genetic algorithms, I am also mildly aware of SARSA (and I do think my scorers resembles that site's description of features with weights, but from my understanding that's not exactly what I have created here). I think that a problem with SARSA is that you don't know the reward until the game is over, the best move is often a move which doesn't give a reward (a mine) at all. Your current chances of winning depends on both the current score (how many mines you and your opponent have taken) and what the current map looks like.

---

_{This question was originally posted on a now defunct Artificial Intelligence site.
The (Java) code used for this approach has now been posted at Code Review.}

Answer 1

At a stretch it is an expert system (such as fuzzy logic). As you are not running an algorithm to perform feedback onto the decision parameters based on the output, it's not really learning. However, performing feedback is not the only indicator whether an alogirthm is AI. One could argue that if it acts in a way that appears intelligent, that's all that matters - especially when the game is played by a human opponent.

The kind of algorithm you've specified is really a parameterised equation, the kind you'll find in insurance calculations. After each move, the input space changes but the algorithm needs no memory of the previous state, so it treats each move as a new, separate board.

Using Genetic Algorithms

There are two clear options for genetic algorithms:

• Use the parameters for the genome (as you suggested). You will optimise the rules that you have but you're still left with an expert system.
• Use Learning Classifier System (LCS) to choose the rules for you. An LCS is a type of Genetic Algorithm where you encode the rules as well as the parameters. They take longer to converge, and are sensitive to the fitness function. I think the resulting manner of play might be more interesting for it.

Simulated Annealing

Another way to solve the problem is to use Simulated Annealing (SA). Your problem is a bounded input space and you can analytically write a function that finds the best square to pick in any given scenario. Using Simulated Annealing will find a global optimum for your parameters.

On making it too good

I know you want the algorithm to be the best it can be but don't forget that a human is playing against it. There is a tactically perfect way to play these sorts of deterministic games and if the AI player takes it, it would only purely luck that meant that the player wins.

Answer 2

Yes, the technique of assigning scores based on certain aspects of the position is standard in writing AIs to play games. For example, almost all chess programs work by scoring positions based most significantly on the pieces available, with smaller bonuses based on their positions (e.g., pawns protecting each other). They then try to calculate the best available move by using an adversarial search algorithm such as alpha-beta.

Adversarial search might be difficult here because of the large branching factor -- in any position, the legal moves are to mark or reveal any unknown square. On the other hand, it's possible that you can cut down the branching factor a lot by heuristics. For example, marking or revealing a square you know nothing at all about is very rarely going to be the best move. Conversely, if you know the locations of some unmarked mines, marking one of them will presumably be the best move, most of the time. Maintaining a transposition table would also probably help.