So what do I owe Baxter and Atro? :)

Just a quick note about the brute force discussion. Bisqwit posted some extremely large numbers to explain how long it would take to test every possible input for a game of this length, which looks like it isn't possible and never will be. We assume "never" because we assume that computers will only double in power every 18 months or so because of Moore's Law. To be sure, "general purpose" processors really do only double their performance in general benchmarks every 18 months or so. When someone decides to make a specialized processor, or add specialized instructions, it's often possible to improve upon the performance of a general purpose processor -- on that task -- by dozens of times. Via, for instance, decided to add a dedicated decryption unit to their processors a few years back, making them several times faster at decrypting certain algorithms than AMD and Intel processors at the time, despite significantly lower general purpose performance. Ageia has developed a dedicated "physics processing unit" which they claim will allow 20 times as many objects to be tracked versus a general purpose processor (let's not debate that claim in this thread). Intel has now announced that their next architecture after the Core architecture, which is due in Q3, will be massively multi-core, using dozens of small general purpose cores, with additional dedicated cores for tasks that need the extra power. So... that means that, if someone chooses to create dedicated circuitry for whatever kind of processing this sort of brute force test would need, it's entirely within the realm of possibility that that specific task could be sped up exponentially, or even geometrically, while general performance continues to merely double. I'm not saying that it's likely, or that any of us may live to see the day, but it's at least possible that there will someday be enough processing power to write a program to play a perfect TAS of a game like Monopoly. You might want to freeze yourself while you're waiting for it.

But won't I die of hypothermia?

I realize Bisqwit was just throwing out numbers to prove a point (that brute-forcing a TAS is hard), but really the problem is much more feasible than he suggests. Instead of brute-forcing input, you'd want to brute-force the state of the game. In other words, look at the contents of memory, etc. You'd try each possible input, but only keep track of the unique states that are generated. That way, if there are lots of possible inputs that lead to the same state (an obvious example is, if your input is ignored by the program), not so much redundant computation is done. Perhaps you could even make the search easier by ignoring variables, such as score, that have no impact on whether you beat the game. However, I don't think even this would be feasible for more than ~60 frames in most situations ) Really you need a human to understand the programming of the game. I was wondering if Monopoly is a possible exception--with Acmlm figuring out the random number generator, and an optimal (?) game plan, the run should be provably optimal!

I just found a way to bankrupt the cpu within 9 seconds (the entire movie is only 9 seconds), but it involves a controversial method. If you press Start and select at the same time, an option appears on the board which says "which player am I talking to" if you select the computer players name, you can control thier actions while in the select menu. At this point you can trade all thier cash to player1 and since you are also player1 you can accept the transaction. Afterwards the computer is left with $0 and he must land on a space which costs money, only then will he go bankrupt. Should this method be allowed in a run, or is it considered cheating?

I just found a way to bankrupt the cpu within 9 seconds (the entire movie is only 9 seconds), but it involves a controversial method. If you press Start and select at the same time, an option appears on the board which says "which player am I talking to" if you select the computer players name, you can control thier actions while in the select menu. At this point you can trade all thier cash to player1 and since you are also player1 you can accept the transaction. Afterwards the computer is left with $0 and he must land on a space which costs money, only then will he go bankrupt. Should this method be allowed in a run, or is it considered cheating?

I wouldn't worry about whether or not it was cheating when the previous movie loads every dice roll and stacks the deck of cards. However, the trade-all-the-money away plan certainly lacks style. I like watching TAS movies because they show complete dominance over the game, not because they reveal a hidden "win the game instantly" button.

I just found a way to bankrupt the cpu within 9 seconds (the entire movie is only 9 seconds), but it involves a controversial method. If you press Start and select at the same time, an option appears on the board which says "which player am I talking to" if you select the computer players name, you can control thier actions while in the select menu. At this point you can trade all thier cash to player1 and since you are also player1 you can accept the transaction. Afterwards the computer is left with $0 and he must land on a space which costs money, only then will he go bankrupt. Should this method be allowed in a run, or is it considered cheating?

Haha, I used to do that when I played it on the NES for fun. It made things very boring after a while...one thing I did like, outside of the computer AI was that the chance for rolling any given number and getting any given card is about the same as the board game. Makes this game uber hard to TAS.

I don't think that would be accepted. That's like forcing the CPU to give away all its money, rather than seeing how stupid/unlucky the CPU actually is on its own power. In that regard, Start+Select is almost like a code. On the other hand, I worked out a possible strategy that could bring Monopoly down to 25 seconds. I was inspired by hero's "CPU bankrupt by trading" movie and created a strategy that only trades once, then, after movie end, watches the CPU self-destruct in the next 75 seconds (hint!). It's definitely not what one would think, though (unless you are reading my mind). The only problem (not to a simulator, of course) is that the CPU's last move must be manipulated for 3 rolls. Acmlm, I sent you a PM regarding the strategy. Obviously, I can't do it myself.

Thats awsome FractalFusion, 25 seconds is great. Your strategy intrigues me though. The most you can obtain in a single trade is $930, which means you some how found a way for the computer to lose $570 within three (or four) dice rolls. Good luck with getting the final turn manipulated, I would love to see this game drop below 30 seconds. Edit: I couldn't figure out what your strategy is FractalFusion, but in the process of thinking I discovered a legitimate way to beat the current record. It involves the trading process but only requires one trade as well. I don't think my method would be 25 seconds though, more likely 28-29 seconds.

Is trading a good idea. No. Seriously, a movie doing that won't amaze me.

Yes the movie would be less entertaining with trading in it, but there is still alot of luck manipulation which makes it impossible to duplicate on a console. I dont really intend on running this game anymore, I just want to give ideas to people who are still trying.

Computer opponents vary in their ability to handle money. Ollie is the worst. I just tested and if you mortage all 3 orange properties, he will trade all $1500 for them and then go bankrupt on the interest. That means just buying the 3 properties, minimizing ollie's first turn, then make 1 trade, then watching him self-destruct. Of course you could optimize that and ask for the minimum amount to make him go bankrupt (which would be slightly less than the 1500)

I just tested and he will in fact trade $1440 for a mortaged mediterranean & boardwalk when he owns baltic. the problem is that it won't bankrupt him since he is required only to pay the interest which adds up to $23 and he can mortgage baltic for $30.

My strategy (which I sent to Acmlm and I think he received), was quite different. The CPU and I take light blue properties: H: 2+4 Oriental C: 2+6 Vermont H: 1+2 Connecticut However, the trading is very different. Instead of trading as much as possible from the CPU, I give him a monopoly for $201. Why not max $? First, it's faster that way :) Second, a little trick I remember is that a player can have 4 houses each on a first street monopoly and nothing else, hit Community Chest repairs, and go bankrupt. Thus, I let the CPU build its houses and hotels. The CPU buys a second street property, then hits Chance repairs, losing its hotels, then hits Comm. Chest repairs, done. By the way, this doesn't work on all CPU characters since some go into trade mode almost instantly after buying Vermont. And that's three rolls to manipulate. I never realized though that CPU Ollie gives up all money for a monopoly, though.

Fractal I had the exact same idea, but after running the numbers through my head a few times, I dont think it is possible (if I understand your idea correctly). Here is why: From vermont avenue the CPU needs to roll doubles just to take a second turn. It is 9 spaces to community chest which would mean he would not be able to roll again. Not only that, but with 12 houses at $40 dollars a pop for the comunity chest repair card, he would owe $480. He would be able to mortgage all his houses for $300, and the 3 blue properties for $160. If he was allowed to purchase a second street property, he could mortgage that and easily pay off the extra $20 owed.

I haven't tried FractalFusion's yet, but it seemed like it'd work ... the CPU would buy one of the orange properties before landing on Chance and Community Chest, then would be missing $7 to pay for repairs. I tested the one where Ollie trades all his money away, it's about half a second slower than this submission (setting the money to trade takes too long), but at least it ends about 10 seconds faster.

Sorry for not making it clear, but the Chance repair would force CPU to mortgage both second street property and lose hotels. I also forgot to mention mortgaging Oriental and Connecticut before trading, since it seems faster than raising the trade money.

Oh ok that makes sense, very nice strategy FractalFusion! This would definitly bring the input time to around 25 seconds. Edit: I recorded a very unoptimized run using an easy new trade strategy and got a movie 28 seconds in length. It is likely that FractalFusion's method will yield a shorter movie, if not I may clean this one up and submit it.

This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [520] NES Monopoly by Acmlm in 00:30.03

This is a very impressive feat of engineering. Though Bisqwit's comment is a little exagerrated. There are always optimizations you can do to a brute force search to prune the branching factor considerably. At least if you can think of a meaningful lower-bound heuristic.

Whoa very nice. I would have never guessed 4 seconds to be dropped and here you guys are still talking about dropping even more time!

That was really really fast. I loved it.

I wouldn't mind seeing a movie where the player bankrupts the maximum number of computer opponents (rather than just one). Any thoughts?

I wouldn't mind seeing a movie where the player bankrupts the maximum number of computer opponents (rather than just one). Any thoughts?

I would prefer to watch that instead myself. Seeing three computer opponents going bankrupt in 2 minutes would be hilarious.