A scoring approach to computer opponents that needs balancing

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:

• "Pre-scorers": Some pre-analysis is done for the current game state (in terms of Minesweeper Flags, this is usually: Calculating all the probabilities)

• "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.

• The scores calculated in the above step is summed together and is set to be the score for a move.

• The moves are sorted according to their score and ranked so that all moves with the same score gets the same rank.

• "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 scor

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.

StackExchange Computer Science Q#21981, answer score: 7