14
\$\begingroup\$

I'm currently creating a Monopoly game simulator in C++.

I am currently struggling with implementing the auction mechanic for AI players.

How could I implement the bots' participation in auctions? How could I define when the bot should buy and item, or when it shouldn't?

I know for a fact that it should take the color of the property and money into consideration, but could you put me on the right track?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ As a sidenote: This video from the spiffing brit channel deals with the sort of bug you'd encounter if you were to build it wrong (youtube.com/watch?v=N2FywH_2Fik). You can skip to 09:20 approx. Perhaps you can learn from this exploit? Up front: some people hate the way this youtuber presents his content. \$\endgroup\$
    – JustLudo
    Sep 27 at 11:00
  • \$\begingroup\$ Will there be different difficulties? Then you could have something like "easy" who just always bids until the normal purchase would be the same as bidding or something along those lines. The "smarter" you want your AI to get, the harder this will be. A "quick and dirty" thing to do would be creating different AIs with "personalities" (i.e. always bidding, never bidding, only p% of their money etc.) For a proper AI there is a very good answer already. This is just a suggestion to make it "easier" \$\endgroup\$
    – bibleblade
    Sep 27 at 12:02
  • 6
    \$\begingroup\$ The "too long; didn't watch" version of the video posted by @JustLudo: The bug in the AI of that particular Monopoly game is that when the AI estimates property prices during player-player trades, it does not take into account whether or not the property is mortgaged. This can be exploited by mortgaging property, selling it to the AI, letting the AI repay the mortgage, and buying it back for the almost same price. In order to fix this bug, I would change the rating function for the real value of properties accordingly. \$\endgroup\$
    – Philipp
    Sep 27 at 14:02
31
\$\begingroup\$

To determine an auction bid, you need the AI to be able to estimate the value it expects to be able to earn from that property.

First then, we need an estimate for how many rounds the game is likely to last. You could get this by playing a large number of games and calculating the average number of rounds they go for. Or for a more dynamic estimate, compute the average rate of money loss for a losing player at each turn. The estimated turns remaining can then be found by taking the current net worth of all players and subtracting this value for each projected future turn until all but one is reduced to zero. If you don't have the data gathering to support this, you could also just take the average rental cost on the board currently and divide the second-highest net worth by this value as a crude estimate.

Next, it needs to compute how many times an opponent is likely to land on that property in that remaining time. To a first approximation, players land on 1 space per round out of 40 spaces on the board, so we'd expect roughly remainingOpponents * remainingRounds / 40.0 opportunities to collect rent from this property in future. Multiply this by the rent and you have a guess at how much income this property will generate.

At any time this property may also be mortgaged, so add the mortgage value to the expected gain to get our first estimate of its net worth to the AI. (So even a property with negligible future rent prospects may still be worth picking up if we can buy it at/below its mortgage value).

This estimate can now be used as the upper limit for the AI's bid. It should start bidding below that value and above any opponents' bids (you can use your heuristic of choice to choose a starting bid/increment), and stop bidding if the leading bid goes above this threshold. At that point we'd estimate that buying this property would be a net loss by endgame.

We can refine this estimate in various ways:

  • If the AI collects all properties of this colour, or improves this property with houses/hotels in future, the rent may increase.

  • If the AI already owns other properties of this colour, getting this property could increase the rent they can charge at those properties too, or enable improvements via houses/hotels.

  • If the AI is short on cash, it may want to factor in the opportunity cost of spending its liquid funds at auction. You could evaluate the expected value of buying any of the available properties the AI is likely to land on next turn — if the expected value there is greater, cap your bid at what you can spend while still affording this future purchase.

  • You could add in the expected savings in rent that you would otherwise pay in the future if the opponent with the current leading bid were to win. This can also include savings from landing on their *other" properties of the same colour, whose rents may increase if they complete their set with this one, and increase further if they then build houses...

  • You can add an "overspending budget" per lap, equal to the $200 passing GO bonus plus the AI's average rate of earning/spending on rent in a lap (measured from recent laps, or estimated by current property ownership). The AI can over-bid by this amount per lap (or per round if you divide it by the number of rounds per lap), and still stay in the black — still not have a net drain on its coffers. If you spread this over the lap then you'll tend to have leftover budget as you turn the last corner, so you can bid more aggressively on the high-value properties at the tail end of the board.

    If the AI has more cash in hand than it's likely to need to pay rent in the short term, then it can similarly increase this budget.

  • You could run this estimator from each opponents' perspective, and if it has high value to the leading bidder, bid up to a factor of their valuation, to drive up the price they pay or deny them the ability to secure it.

  • If the supply of available properties is dwindling or the AI is behind its opponents in terms of properties in hand, you may want to increase this estimation by a "hunger factor" to guard against the AI being shut out of the property game while waiting for the optimal purchase to come along.

Each of these refinements can make the AI more strategically savvy and might improve numerical results over a large number of games. But they also increase the complexity of the algorithm and might not significantly improve the perceived intelligence of the AI from the players' perspective — overcomplicating this could actually make the AI look less intelligent, if it makes a bidding choice for non-obvious reasons that look to the players like a bug. So exercise judgement in deciding just how nuanced this feature needs to be for your goals guiding this project.

\$\endgroup\$
12
  • 4
    \$\begingroup\$ Varying the value of each property above may add character to each AI player, ie having the race car always value trying to finish clumps of real estate highly, and the boot always try to deny other people from finishing theirs. Is important to play test it if you go that route though, to see if it actually makes a perceived difference to the player \$\endgroup\$
    – phflack
    Sep 26 at 23:12
  • 17
    \$\begingroup\$ You might find The Mathematics of Winning Monopoly on YouTube useful. For example, it discusses the probability of landing on each square, which isn't as evenly distributed as you might think. \$\endgroup\$
    – Adam
    Sep 26 at 23:30
  • 2
    \$\begingroup\$ OP could note that calculating expected savings in rent is (to first order) as simple as using remainingPlayers rather than remainingOpponents in the expected income calculation. I.e. accounting for it as paying yourself rent, rather than reducing whatever burn-rate you're using. \$\endgroup\$
    – nitsua60
    Sep 27 at 1:27
  • 1
    \$\begingroup\$ Note that njtsua60's optimization here is correct if all players stand to charge the same rent for the property. Once you start factoring in doubling for having all properties of a colour, or future improvements, then it matters who the rent is being paid to: you (in the context of your owned properties) or the current leading bidder (in the context of their owned properties). So you might still need to use a different rent for the earning vs savings part of that calculation. \$\endgroup\$
    – DMGregory
    Sep 27 at 1:36
  • 4
    \$\begingroup\$ An average monopoly game is about 30 turns per player, so in an average 4-player game, each property will be landed on just 3 times (assuming uniform odds). Property cost is 8-30x times the unimproved rent value, so you'll almost never make your money back with unimproved rent. Figuring out expected return for a single property seems pointless, since it's always a loss - properties are really only valuable when in a set. \$\endgroup\$ Sep 27 at 13:57
17
\$\begingroup\$

DMGregory gave you a lot of ideas on how to value property. However, your starting point should back up a bit:

Design your game engine from the ground up to permit running all-AI games that simply write log information but run without interaction. You can pit a group of AIs against each other, set it to play 1000 games and walk away.

As you're looking at the logic, try different values. How much value do we attach to having another property in the group? Take a group of AIs that are identical except they attach different importance to this, make them play a lot of games. Whatever AI wins the most is probably the best setting.

I would also try to figure out a reasonable range for settings and make the AIs pick a somewhat random value in that range so it plays a bit differently in each game. Being able to 100% predict the AI behavior isn't fun.

\$\endgroup\$
6
  • 6
    \$\begingroup\$ If you already have a runnin readable simulation completed why not go the 3 extra steps and add a machine learning for the betting value. Or just for everything \$\endgroup\$
    – Hobbamok
    Sep 27 at 13:19
  • 1
    \$\begingroup\$ @Hobbamok because while it seems so easy to "just throw ML at it", the reality is that getting that right is still tricky for any non-trivial cases and does by no means guarantee a better outcome. AlphaGo, for example, had an entire AI research company behind it. It wasn't just a case of "here's a neural network, here's the rules of Go - let's roll". \$\endgroup\$
    – Tom
    Sep 29 at 6:21
  • \$\begingroup\$ @Tom Sure, but AlphaGo was trying to beat the best humanity had to offer at an extremely hard game. For monopoly, it should be reasonable to figure out some key factors (price, cash on hand, opposition cash on hand, property id, others of group held, opposition others of group held), and feed that into a ML system. It feels like you should be able to get reasonable answers pretty fast. \$\endgroup\$
    – NPSF3000
    Sep 29 at 18:10
  • \$\begingroup\$ @NPSF3000 for a game like monopoly - relatively low strategic complexity, high randomness - by the time you've figured out all the relevant factors to feed into an ML, it's probably not so hard to just finish writing the algorithm. \$\endgroup\$
    – Tom
    Sep 29 at 20:11
  • 1
    \$\begingroup\$ @NPSF3000 Randomness means you need a very large dataset and since there's AI calculations involved you're not running millions of games in short order. \$\endgroup\$ Sep 30 at 5:11
3
\$\begingroup\$

Something else to consider is that there are situations where a property is much more valuable to a particular player than other players. (e.g. it completes their set). A system would likely involve each AI calculating how much it would be willing to pay for the property. As Monopoly is a perfect information game the same calculation could be run from other players' perspectives to understand how valuable the property is to them. Each player could then have a value for their own 'bidding aggression' (it could be dynamically changed to be higher when winning). The player could then set their own perceived value to:

max(ActualPerceivedValue, BiddingAggression*max(perceived values from other perspectives)).

A bidding aggression of 0.75 for example would mean that the player would bid to up to 75% of what it is predicting the player who wants the property the most will pay. This is good as it forces said opponent to pay more than they might otherwise. If each AI had its own personality parameters and ran the other perspectives with these parameters it would mean the estimations of the opponents strategies would not be perfect and lead to interesting interactions. The bidding aggression could also be set to >1 when strongly winning just to bully weaker players out of being able to buy properties and mount a comeback.

\$\endgroup\$
2
\$\begingroup\$

It's a very rough approximation of an AI, but this video on the Nintendo Entertainment System version of Monopoly might shed some insight. Especially if you can read assembly: https://www.youtube.com/watch?v=lHhdPrD0mUY

\$\endgroup\$
1
  • \$\begingroup\$ This is currently a link-only answer. Please edit this post to include a summary of what you hope a reader will glean from this link, so the information is preserved even if the video is not available in the future or from a particular reader's locale. \$\endgroup\$
    – DMGregory
    Sep 30 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.