Jump to content
  • Advertisement
Sign in to follow this  
acer3

An expert system for monopoly

This topic is 2809 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Our thesis requires us to create an expert system that would substitute missing players in monopoly.
The AI should be able to base its actions on the probabilities and apply strategies for the game.

What algorithm should we use?
Is the minimax algorithm applicable for monopoly?

Share this post


Link to post
Share on other sites
Advertisement
I've never done anything like it before, but here's what I'd try

First precalculate the long term probabilities of landing on each square, which can be calculated exactly using some linear algebra.
You'll need to precalculate at least two sets of this data: one for when people try to leave jail (early game) and one for when people stay in jail as long as possible (late game).
Remember to factor in chance cards to these probabilities.

Now these long term probabilities can be used to estimate a value for each property, to be used when deciding what to buy and where to build houses.


Finally, you'll probably want to do adjustments based on players positions on the board and how close they are to bankruptcy. Perhaps you could project a turn or two into the future, minmax style.


Other than that, there's not much to the game. It's mostly luck based.

Share this post


Link to post
Share on other sites
Maximization of expected utility.

Pre-calc strengths of various spaces. Assign cost/benefit ratios for each purchase. Add in the values of near-term potential gains (e.g. having 2 of one area is better than having 1 each of 2 areas). In trades, consider the other person's gain/loss compared to their overall position as well as doing the same for your own. That is, you don't want to do something that is moderately good for you if it is REALLY good for them. Likewise, you can be harsh with someone who is in dire straits. Remember to include marginal utility (both increasing and decreasing) as well as straight-up value.

Other than that, I would leave out any die-roll prediction stuff. It is too transient.

This can all be boiled down to a single score for purchasing one property, building on a property, trading for properties, etc. These scores can be compared against other options to select the best option at any one time.

Oh... to answer one of your questions: minmax would fall flat almost immediately because the branching factor is not only huge, it is stochastic based on die rolls. Add in that the person may elect to do the action or not, and you have a big unknown for each ply. That is, while players take turns, it isn't a deterministic change from state to state.

Share this post


Link to post
Share on other sites

Maximization of expected utility.

Pre-calc strengths of various spaces. Assign cost/benefit ratios for each purchase. Add in the values of near-term potential gains (e.g. having 2 of one area is better than having 1 each of 2 areas). In trades, consider the other person's gain/loss compared to their overall position as well as doing the same for your own. That is, you don't want to do something that is moderately good for you if it is REALLY good for them. Likewise, you can be harsh with someone who is in dire straits. Remember to include marginal utility (both increasing and decreasing) as well as straight-up value.

Other than that, I would leave out any die-roll prediction stuff. It is too transient.

This can all be boiled down to a single score for purchasing one property, building on a property, trading for properties, etc. These scores can be compared against other options to select the best option at any one time.

Oh... to answer one of your questions: minmax would fall flat almost immediately because the branching factor is not only huge, it is stochastic based on die rolls. Add in that the person may elect to do the action or not, and you have a big unknown for each ply. That is, while players take turns, it isn't a deterministic change from state to state.


I think dice roll predicition could be useful once all the properties have been bought, because at that point it's just a matter of estimating who is likeliest to encounter gambler's ruin first.

Share this post


Link to post
Share on other sites

I think dice roll predicition could be useful once all the properties have been bought, because at that point it's just a matter of estimating who is likeliest to encounter gambler's ruin first.

But what do you gain by this? Unless you are using it to decide which properties to put that extra house on, it's irrelevant. Also, the spread on 2d6 is subtle enough that moving +/- one result isn't that big of a change. i.e. there isn't that significant of a % difference from 7 to 8 that it is really a deciding factor.

Incidentally, I did a mathematical analysis of the board, and the cost-benefit rates about 15 years ago. The 2nd grouping, (Ontario, Ventor, etc.) is the best grouping to buy by a slim margin.


Share this post


Link to post
Share on other sites
I haven't played Monopoly in many years, and I was never a big fan. My recollection is that you should basically always buy the properties you can and always build up whatever you can. Perhaps this is too simplistic, but I am sure you can come up with a rule-based system that would play roughly correctly using very little time to make decisions. Then you can throw Monte Carlo sampling at the problem, using that policy to simulate future results. I imagine this would result in a strong program, and you don't even need to write an evaluation function.

If you manage to write a good evaluation function (a prediction of the probability that you will win from a given position), you can stop the Monte Carlo simulations after only a few moves and use your evaluation function as the result.

Share this post


Link to post
Share on other sites

I haven't played Monopoly in many years, and I was never a big fan. My recollection is that you should basically always buy the properties you can and always build up whatever you can. Perhaps this is too simplistic, but I am sure you can come up with a rule-based system that would play roughly correctly using very little time to make decisions. Then you can throw Monte Carlo sampling at the problem, using that policy to simulate future results. I imagine this would result in a strong program, and you don't even need to write an evaluation function.

If you manage to write a good evaluation function (a prediction of the probability that you will win from a given position), you can stop the Monte Carlo simulations after only a few moves and use your evaluation function as the result.


Nah... you have to do evaluations because the entire midgame is based on "should I build? If so, on which of my properties? How much do I need to keep on-hand for emergencies (landing on stuff)?" All comparisons and evaluations.

Share this post


Link to post
Share on other sites

But what do you gain by this? Unless you are using it to decide which properties to put that extra house on, it's irrelevant. Also, the spread on 2d6 is subtle enough that moving +/- one result isn't that big of a change. i.e. there isn't that significant of a % difference from 7 to 8 that it is really a deciding factor.

Incidentally, I did a mathematical analysis of the board, and the cost-benefit rates about 15 years ago. The 2nd grouping, (Ontario, Ventor, etc.) is the best grouping to buy by a slim margin.


But the extra information is still better than nothing, though it will only have a significant effect if someone is already very close to losing.

Also, IIRC the reds and oranges are the best properties to have. Purples are the worst by a huge margin.

Share this post


Link to post
Share on other sites

Also, IIRC the reds and oranges are the best properties to have. Purples are the worst by a huge margin.


I do not agree. If you get to have hotels in BOARDWALK AND PARK PLACE you can ruin almost everyone. BALTIC AV. and MEDITERRANEAN are also a must-have because they are cheap to build in and are right after GO, falling in them after collecting GO can easily mine people's moral (along with some strategic mocking lol).

Share this post


Link to post
Share on other sites
But the red properties are the most frequently landed on.

If you rank every property by (probability of landing on)/ (cost), Mediterranean avenue is in last place by nearly an order of magnitude.

Also, another interesting tip is that the third house is the most cost effective improvement.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!