This topic is for the purpose of discussing #1011: Acmlm's NES Monopoly in 00:30.03

Great job Acmlm, You win the monopoly wars! I am done with this game for now and will most likely never play it again. It will be interesting to see how much lower those 32 can go, if it can go lower at all.

Monopoly gets Dragon Warrior'd. (bonus points to anyone who figures out what these runs have in common) Obvious yes vote now, and... if another Monopoly run is submitted in the next 3 days, I'm going to join DeHackEd in the looney bin.

Great to see computer programs being used for luck manipulation ) Takes away the most annoying part of making a TAS. Could this be the first speedrun known to be optimal?

I think Donkey Kong is known to be optimal

I think if you find a bug, unless you are force-bruting, will make computer programs temporary pointless. But for Monopoly it is probably the fastest but who knows ... ;)

Good job, Acmlm. Voting yes. If it is possible, could you describe how the game's random generator works and how your program works?

I spent the last 1-2 days figuring out the game's randomness completely (different variations and frame timings) by looking at the code and memory viewer, and made a program that simulates it.

Impressive persistence.

Great to see computer programs being used for luck manipulation :) Takes away the most annoying part of making a TAS. Could this be the first speedrun known to be optimal?

Not quite--Acim only used a large random search to find a fast solution, not an exhaustive search specifically designed to find all possible solutions. Until someone finds a way to systematically account for all possible inputs, you can't prove that a speedrun is optimal. A huge, randomized search that uses a specially built simulation is still _extremely_ impressive, though.

Great to see computer programs being used for luck manipulation :) Takes away the most annoying part of making a TAS. Could this be the first speedrun known to be optimal?

Not quite--Acim only used a large random search to find a fast solution, not an exhaustive search specifically designed to find all possible solutions. Until someone finds a way to systematically account for all possible inputs, you can't prove that a speedrun is optimal. A huge, randomized search that uses a specially built simulation is still _extremely_ impressive, though.

Only problem with this is that if a human can deduce exactly what is needed to beat the game, knowing that it is the optimal strategy given one factor (say, luck manip), it would effectively prove that it's optimal (unless you find something stupid like a "cue ending" glitch or whatever) Brute-forcing is far, far harder than this. To the point it's virtually impossible for a long time, unless you want to wait a century (or more) waiting for today's computers to spit out a working, fast-as-possible solution to, say, TLOZ.

Brute-forcing is far, far harder than this. To the point it's virtually impossible for a long time, unless you want to wait a century (or more) waiting for today's computers to spit out a working, fast-as-possible solution to, say, TLOZ.

Yeah, bruteforcing all possible inputs to play a 30-second movie (1800 frames) means testing (2^8)^1800 different sequences (****), which is precisely 67910599029065024630821659696928156440478833431239810898259887865488\ 82682124358383854697411879171799595276072426960844149236399672422435\ 85171111700341434731511046378380142906153832515518703220889456303770\ 78970231396261499169318373437333482354437574955988983322415743060990\ 50825213585778827024591321949866602257610990048439382865566521433352\ 35957477350939660132505176697163673402203946749680905736175699811066\ 61605022780876364209742244156334092439686640046955717028115708532978\ 09315144580865991543782001705964821619248395562646118954250168465270\ 94863085046134188319597101572502219572973446821826494942338835736438\ 82167059698742843952155455507808940942369730661482143231733076338326\ 87882748377028669349538766791020498279669692300506967355601133325389\ 22667147629488362646624849996076215455013099654267274617322252122678\ 23519493632754762881909418603266412790349657109724822664508743061016\ 60942167298758422797202097817296538495645494051820604910916514815045\ 55088558050236274357091421376495769616948662038130631631995630279379\ 52444371499375682902057525918735280171258627982389034359999206866497\ 02195504211785596382791788315418883902820550611926025209800803718219\ 48647953022427131391906320751749508165834558996833035798785093901242\ 12427759893518304697896406968908133520633754818424137382588589764847\ 79427817459651057206048994621335285624024706531311090554321302589541\ 79988332541368338501340891770257718775658354899071809208031779098544\ 27267385992423381163659338925837104228562202401100879505018411860542\ 89776602345555029837644732838372141044969187528153232465102110333786\ 48763321204425369364830756897879259682155071591419079195293284353786\ 00144888733849174436721182127534675605088165045709641156055785976196\ 59910291871968276903762179718294004327263769282655033523839363977239\ 23076723775414486261108163190604880543653778402040392688375705432163\ 96635678434482765125039931249218548259375150368455776362605126974958\ 69093382488997943863558096027714232055768343919798566850789654087922\ 47430686019869821500724433308778235980518909344793685586336410323574\ 44246483262050566380395595407202633946838443646988859430781734557231\ 31425697432331415105743831634469416635258594239070869410859514402669\ 22797718667081882866211861353395257458578680080958051791638267608627\ 47045887700819213302116514852315931806657414346888500573019118186013\ 72461617106064268740275857405536375347818681564420108737704682738481\ 35181141405518931284600871891794434607444629484202536591293369322112\ 40247029910272322910205112999179146282141292665500065641804630948761\ 29274800466375817689097836017464886057095451720650200493795183561286\ 00743356281256449955064699293143881288939002657901093432292534721008\ 92151914205851519942525099889588386316694416889268025860078514554085\ 89708196087245386556168360921767078530559441373955176144973459517631\ 14959270713422804370201662732023148341128655364347670048197210545176\ 80905630606693334565960860387516510933699725365563198935418557963838\ 73343112733791417577832570254213780513325051519734089410053532106705\ 86198842672664255800640455685153468958309858545053749023687553217935\ 49459408524775257205455473311029085975477894397844836738727955113541\ 97495308964030224591460637169148900309175436847432177444637729148237\ 98783815056576818428054416059710353927480669705061842082283186620196\ 31908151250820550242665313741486602664022526950801610730307544394760\ 19558880758320216997072911139428629257813691404075412540837217276707\ 83703602637285724840858878275401850980576686943666767002231943868408\ 14485849598741593533889612791463793571723510559943369583390718977134\ 78590091089640110283805644281477227438964178878000582323876165890907\ 28326629822365537522718023880789434563418082212232391237743814624987\ 10083177984816242912903374471715719704751434361319950564198022402597\ 42763997537308232826980280702385179923694879249903454253669772615783\ 59046461245950300611502156888809494872775204917088215364663049819719\ 65716664424758375523079768485668460472916133778068418916835049649295\ 97905019964818530955100123685068171696602223780718306565987252530008\ 77727961845362632393041170442417635823952992348265425905660741573806\ 32789067872981821021910801697015314754122341487504024605053180524511\ 71002461906669507020359307490298258129109888367992992876476000213921\ 13322421637646906037145608731875133022649565276098250765941136522019\ 704938186044957157758019297404971319710013640933376 different sequences. Assuming that a thousand million different sequences are tested each second and you have a quantum computer(*) which reduces the number of options to be tested to the squareroot of their actual amount, it will still take about 82579781878965007100103923231985050511715914790279865344545749419260\ 70262675161728233752993296432159712512611896069914713293874863161002\ 55245368666404508763530058311761306889180173355869738602290819072561\ 68663661711028738454908169552459462230269203619930342690843337250572\ 55110967700851040139962899711300721956326012240242656862597205560282\ 41482368747519687589363806162208476657084587720486654700083493748039\ 69552188534741483506534743742823648838872462899632930178171115684672\ 11206635152416848845930284571794369674230369151842295363296279745500\ 97895576970476446207821510270978139524556576060653422525334983476963\ 59958628824789927290705988958584471761613716703524797420402978858165\ 88508420802083281029970177552176992399448375600931560128735513235794\ 90428245440508535219920151345462320246984164102832064238225432842331\ 54196343254507511245119995761413345578582599811218136133085186358669\ 64598140374623812861572923750263566262703040675926866722644235061300\ 43607815844186812129542099972701748213117763662547294191515427556898\ 69931555783783631599544497712888327119244399941037622510321276644332\ 50733348722918213515039587087600531412029789232182148101723386268639\ 31903967903925836771828146008038641758420997602652821186199716973350\ 65315959785742817909769209343190591221038047639112461626066773778050\ 79870667993328437699506771676655440777395455158091988818680570493449\ 82496169703588803881960452473276220977376864063032069322743702564542\ 57606286794611420572392731836845013225665458348706008230992758758274\ 40085794280291546132659193398214449059878381833988311910597622346506\ 21481212769379552848759758448309938539015906681700990100248040064173\ 93894463608691614487215600655773353390911839685915605135217119844555\ 84593212298526474303879182727005311652426216710942866610255353908971\ 87894260188692114502327201166379114066369480499355234626037239508785\ 63326729603670184659988013434895366593210272626047026935073523836514\ 46249128153546554282037234323521695684101916504113496350115467050560\ 46030859457737032757279874646034958580795646804663554257241631419197\ 39357742419515257789571550191920356935302679288651024122951693726810\ 4416745528480614650437950028314796307785258 years to test all options, leap years accommodated (**). If you can somehow drag Earth into extreme near vicinity of the event horizon of a supermassive black hole and perform the calculations somehow elsewhere in the universe, and then return back and pull Earth safe from falling into the event horizon, you could, from the perspective of Earth, reduce the calculation into a few million years. This of course requires that the distance of Earth from the event horizon is in the order of several millimeters... (***) Oops. Maybe I went too far ;) *) Which doesn't yet exist, but is likely reinvented a couple of thousand times while the original program is running. **) sqrt((2^8)^1800) / (10^9 * 86400*(365+1/4-1/100+1/400)) ***) Which would cause tidal and centrifugial forces strong enough that by the time you return, Earth has been rendered into a ring circling the event horizon, assuming that the universe still exists and the black hole hasn't evaporated due to quantum mechanical effects. ****) Of course, you could eliminate combinations which don't seem to affect the game in the long run at all. This would reduce the amount required by the calculations by some (big) factor, but still not far enough to be practical.

Too much Stargate SG-1, Bisqwit?

Too much Stargate SG-1, Bisqwit?

Huh? :P No that didn't have anything to do with Stargate.

Well, it sounded like it could've had, what with the event horizons and black holes and time distortions.

Well, it sounded like it could've had, what with the event horizons and black holes and time distortions.

$generic_scifi?

SG-1 is a really good show. You should see it if u have time (about 200 episodes lasting 40 minutes each). Anyways... GOD DAMN! what a awesome monoply war :) gratz again on yet another awesome run

I've said it before and I'll say it again: HAHA!! Gotta love this war :) Oh, and great job Acmlm.

Good job, Acmlm. Voting yes. If it is possible, could you describe how the game's random generator works and how your program works?

http://acmlm.cjb.net:2/emu/nes/fceu/fcs/monopoly2.txt Not 100% complete and the frame timings at the bottom aren't perfect (I fixed them in the program after), but that's most of it. The program works like this:

* Calculate the first roll with no delay (0+0+0), then 0+0+1, 0+0+2, etc. until it gets the dice I want * Calculate the second roll, same thing * Third, 4th, and so on * Once it gets through the whole thing, it counts the total delay and shows what it found * After it goes through all delay combinations for one roll (0+0+0 to x+x+x, 5-10 is good) or the current total delay is higher than the best found, it continues with the previous roll

Then it outputs this:

C:\jf\src\rnd>monopoly 70 19 EE
 0+ 2+ 4,  0+ 0+ 0,  9,  0+ 1,  0+ 3+ 5,  8+ 0+ 0,  1+ 4 =  37
 0+ 2+ 4,  0+ 0+ 0,  9,  0+ 1,  6+ 1+ 0,  3+ 3+ 0,  2+ 3 =  34
 0+ 2+ 4,  0+ 0+ 4,  0,  2+ 1,  0+ 0+ 1,  0+ 1+ 5,  3+ 2 =  25
413491 combinations tested.

Wouldn't it be more effective to get the formula for the random generator and calculate the optimal solution?

Looks like Angerfist owes someone some unspecified amount of money :)

I've said it before and I'll say it again: HAHA!!

LOL

Sorry to let you down Angerfist. ;)

Looks like Angerfist owes someone some unspecified amount of money :)

Funny thing is, I dont remember anyone taking my bet :) Hero, Im sure you will a good TAS for some other great game :)

I took your bet.

Hero, Im sure you will a good TAS for some other great game :)

Ditto

****) Of course, you could eliminate combinations which don't seem to affect the game in the long run at all. This would reduce the amount required by the calculations by some (big) factor, but still not far enough to be practical.

If you could prove that the game was only listening to one button and that the player's input only matters during 50 or less frames, you'd have search space of 2^50. Larger search spaces than 2^50 have been computed using brute force techniques.