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

Question

I want to develop RISK board game, which will include an AI for computer players. Moreovor, I read two articles, this and this, about it, and I realised that I must learn about Monte Carlo simulation and Markov chains 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 RISK game?

Here you can find simple determined probabilities about outcomes of a battle in 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

Okay, so I skimmed the articles to get a sense of what they were doing. Here is my overview of the terms you asked about:

A Markov Chain is simply a model of how your system moves from state to state. Developing a Markov model from scratch can sometimes be difficult, but once you have one in hand, they're relatively easy to use, and relatively easy to understand. The basic idea is that your game will have certain states associated with it; that as part of the game, you will move from state to state; and, critically, that this movement from state to state happens based on probability and that you know these probabilities.

Once you have that information, you can represent it all as a graph, where nodes are states and arcs between states (labelled with probabilities) are transitions. You can also represent as a matrix that satisfies certain constraints, or several other more exotic data structures.

The short article is actually all about the Markov Chain approach, but-- and this is important-- it is using that approach only as a quick means of estimating what will happen if army A attacks a territory with army B defending it. It's a nice use of the technique, but it is not an AI for Risk, it is merely a module in the AI helping to figure out the likely results of an attack.

Monte Carlo techniques, by contrast, are estimators. Once you have a model of something, whether a Markov model or any other, you often find yourself in the position of wanting to estimate something about it. (Often it happens to be something that you can, if you squint hard enough, put into the form of an integral of something that happens to be very hard to work with in that format.) Monte Carlo techniques just sample randomly and aggregate the results into an estimate of what's going to happen.

Monte Carlo techniques are not, in my opinion, AI techniques. They are a very general purpose technique that happen to be useful for AI, but they are not AI per se. (You can say the same thing about Markov models, but the statement is weaker because Markov models are so extremely useful for planning in AI, that entire philosophies of AI are built around the technique. Markov models are used elsewhere, though, as well.)

So that is what they are. You also asked which one I would use if I had to implement a Risk AI. Well, neither of those is going to be sufficient. Monte Carlo, as I said, is not an AI technique, it's a general math tool. And Markov Models, while they could in theory represent the entirety of a game of Risk, are going to end up being very unwieldy: You would need to represent every state of the game, meaning every possible configuration of armies in territories and every possible configuration of cards in hands, etc. (I am glossing over many details, here: There are a lot of other difficulties with this approach.)

The core of Wolf's thesis is neither the Markov approach nor the Monte Carlo approach, it is actually what he describes as the evaluation function. This is the heart of the AI problem: How to figure out what action is best. The Monte Carlo method in Blatt's paper describes a method to figure out what the expected result of an action is, but that is not the same as figuring out what action is best. Moreover, there's a low key statement in Wolf's thesis about look-ahead being hard to perform in Risk because the game trees become so very large, which is what led him (I think) to focus so much on the evaluation function.

So my real advice would be this: Read up on search-tree approaches, like minimax, alpha-beta pruning and especially expecti-minimax. You can find good treatments of these early in Russell and Norvig, or even on Wikipedia. Try to understand why these techniques work in general, but are cumbersome for Risk. That will lead you to some discussion of board evaluation techniques. Then go back and look at Wolf's thesis, focusing on his action evaluation function. And finally, focus on the way he tries to automatically learn a good evaluation function.

That is a lot of work. But Risk is not an easy game to develop an AI for.

(If you just want to figure out the expected results of a given attack, though, I'd say go for Monte Carlo. It's clean, very intuitive to understand, and very easy to implement. The only difficult-- and it's not a big one-- is making sure you run enough trials to get a good result.)

Answer 2

Markov chains are simply a set of transitions and their probabilities, assuming no memory of past events.

Monte Carlo simulations are repeated samplings of random walks over a set of probabilities.

You can use both together by using a Markov chain to model your probabilities and then a Monte Carlo simulation to examine the expected outcomes.

For Risk I don't think I would use Markov chains because I don't see an advantage. A Monte Carlo analysis of your possible moves could help you come up with a pretty good AI in conjunction with a suitable fitness function.

I know this glossed over a lot but I hope it helped.