What are the differences between Monte Carlo and Markov chains techniques?

Question

I want to develop a RISK board game, which will include an AI for computer players. Moreover, I read two articles, this and this, about it, and I realized that I must learn about Monte Carlo simulation and Markov chain techniques. And I thought that I have to use these techniques together, but I guess they are different techniques relevant to calculate probabilities about transition states.

So, could anyone explain what are the important differences and advantages and disadvantages between them?

Finally, which way you will prefer if you would implement an AI for the RISK game?

Here you can find simply determined probabilities about outcomes of a battle in the risk board game, and the brute force algorithm used. There is a tree diagram to which specifies all possible states. Should I use Monte Carlo or Markov chain on this tree?

Answer 1

Firstly I will talk about the Monte Carlo Technique:

Advantages:

• The Monte Carlo technique is best suited to analyze complex and large practical problems when it is not possible to solve them through a mathematical method.

• It is flexible, hence changes in the system variables can be made to select the best solution among the various alternatives.

• In the Monte Carlo simulation, the experiments are carried out with the model without disturbing the system.

• In this technique, the policy decisions can be made much faster by knowing the options well in advance and by reducing the risk of experimenting in the real system.

Disadvantages:

• The simulation does not generate optimal solutions.

• This technique can take a long time to develop a good simulation model.

• In some cases, the models based on this technique can be very expensive.

• This technique requires the decision-maker that provides all information (depending on the model) about the constraints and conditions for examination, as simulation does not give the answers by itself.

Now come to the Markov Chain Technique:

Advantages:

• Markov analysis has the advantage of being an analytical method which means that the reliability parameters for the system are calculated in effect by a formula. 

• This has considerable advantages of speed and accuracy when producing results. 

• Speed is especially useful when investigating many alternative variations of design or exploring a range of sensitivities. In contrast, accuracy is vitally important when investigating small design changes or when the reliability or availability of high integrity systems is being quantified. 

• Markov analysis has a clear advantage over MCS in respect of speed and accuracy since MCS requires longer simulation runs to achieve higher accuracy and, unlike Markov analysis, does not produce an “exact” answer.

Disadvantages:

• As in the case of applying MCS, Markov analysis requires great care during the model building phase since model accuracy is all-important in obtaining valid results. 

• The assumptions implicit in Markov models that are associated with mercilessness and the Exponential distribution to represent times to failure and repair provide additional constraints to those within MCS. 

• Markov models can, therefore, become somewhat contrived if these implicit assumptions do not reflect sufficiently well the characteristics of a system and how it functions in practice. 

In order to gain the benefits of speed and accuracy that it can offer, Markov analysis depends to a greater extent on the experience and judgment of the modeler than MCS. Also, whilst MCS is a safer and more flexible approach, it does not always offer the speed and accuracy that may be required in particular system studies. So, I would recommend the Monte Carlo Technique for building the tree in implementing the AI for your RISK game.