(Link to video)
  • Recorded with FCEU 0.98.15
  • Luck manipulation
  • Fastest time to get the CPU bankrupt (by last player input)
Yet another improvement, by 16 frames, still using the same strategy. The time is now 00:30.03 (1802 frames) ... almost under 30 seconds, but unless I missed something unexpected, I don't think it's possible to do any better.
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. Then, given the initial random values, it tries all possible timings that lead to victory and only keeps the fastest one ... doing about 500000 re-records worth of work in 15 seconds.
The result was only 10 frames faster than on the last run, but it should be optimal. Then right when I was going to record this run to submit (after finding and testing the best combination), I found another way to manipulate the card order: when entering the player's name, both the amount of letters I enter and the time between each (including End) affect it. Trying different ones until I found a pattern in the results allowed to save 6 more frames.
The delays are now down to this:
  • 7+0 for the card order
  • 0+2+4 to get Community Chest
  • 0+0+4 to visit jail
  • 0 for the CPU to buy Oriental
  • 2+1 to buy St. James
  • 0+0+1 to buy Tennessee
  • 0+1+5 to buy New York
  • 3+2 for the CPU to go bankrupt
Total: 32

Bisqwit: Processing.

TASVideoAgent
They/Them
Moderator
Joined: 8/3/2004
Posts: 14772
Location: 127.0.0.1
This topic is for the purpose of discussing #1011: Acmlm's NES Monopoly in 00:30.03
Player (88)
Joined: 11/14/2005
Posts: 1057
Location: United States
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.
They're off to find the hero of the day...
Banned User
Joined: 12/23/2004
Posts: 1850
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.
Perma-banned
Player (84)
Joined: 2/10/2006
Posts: 113
Location: US
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?
Use the force
Player (88)
Joined: 11/14/2005
Posts: 1057
Location: United States
I think Donkey Kong is known to be optimal
They're off to find the hero of the day...
Active player (410)
Joined: 3/16/2004
Posts: 2623
Location: America, Québec
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 ... ;)
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
Good job, Acmlm. Voting yes. If it is possible, could you describe how the game's random generator works and how your program works?
Post subject: Re: #1011: Acmlm's NES Monopoly in 00:30
Active player, Editor (296)
Joined: 3/8/2004
Posts: 7468
Location: Arzareth
Acmlm wrote:
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.
Player (94)
Joined: 6/25/2005
Posts: 122
Luke wrote:
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.
Banned User
Joined: 12/23/2004
Posts: 1850
trazz wrote:
Luke wrote:
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.
Perma-banned
Active player, Editor (296)
Joined: 3/8/2004
Posts: 7468
Location: Arzareth
Xkeeper wrote:
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.
Joined: 4/16/2004
Posts: 1286
Location: Finland
Too much Stargate SG-1, Bisqwit?
Active player, Editor (296)
Joined: 3/8/2004
Posts: 7468
Location: Arzareth
Kyrsimys wrote:
Too much Stargate SG-1, Bisqwit?
Huh? :P No that didn't have anything to do with Stargate.
Joined: 4/16/2004
Posts: 1286
Location: Finland
Well, it sounded like it could've had, what with the event horizons and black holes and time distortions.
Active player, Editor (296)
Joined: 3/8/2004
Posts: 7468
Location: Arzareth
Kyrsimys wrote:
Well, it sounded like it could've had, what with the event horizons and black holes and time distortions.
$generic_scifi?
Joined: 1/18/2006
Posts: 78
Location: Norway
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
Joined: 11/13/2005
Posts: 1587
I've said it before and I'll say it again: HAHA!! Gotta love this war :) Oh, and great job Acmlm.
Experienced player (527)
Joined: 11/14/2004
Posts: 169
Location: Mirabel, Québec, Canada
FractalFusion wrote:
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.
Joined: 1/23/2006
Posts: 352
Location: Germany
Wouldn't it be more effective to get the formula for the random generator and calculate the optimal solution?
JXQ
Experienced player (749)
Joined: 5/6/2005
Posts: 3132
Looks like Angerfist owes someone some unspecified amount of money :)
Guybrush wrote:
I've said it before and I'll say it again: HAHA!!
LOL
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
Player (88)
Joined: 11/14/2005
Posts: 1057
Location: United States
Sorry to let you down Angerfist. ;)
They're off to find the hero of the day...
Active player (432)
Joined: 4/21/2004
Posts: 3516
Location: Stockholm, Sweden
JXQ wrote:
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 :)
Nitrogenesis wrote:
Guys I come from the DidyKnogRacist communite, and you are all wrong, tihs is the run of the mileniun and everyone who says otherwise dosnt know any bater! I found this run vary ease to masturbate too!!!! Don't fuck with me, I know this game so that mean I'm always right!StupedfackincommunityTASVideoz!!!!!!
Arc wrote:
I enjoyed this movie in which hands firmly gripping a shaft lead to balls deep in multiple holes.
natt wrote:
I don't want to get involved in this discussion, but as a point of fact C# is literally the first goddamn thing on that fucking page you linked did you even fucking read it
Cooljay wrote:
Mayor Haggar and Cody are such nice people for the community. Metro City's hospitals reached an all time new record of incoming patients due to their great efforts :P
Player (246)
Joined: 4/24/2005
Posts: 476
I took your bet.
[URL=http://www.youtube.com/watch?v=IcuV2JdaBYY]Streets of Rage 3 (2 players)[/url]
Skilled player (1399)
Joined: 5/31/2004
Posts: 1821
AngerFist wrote:
Hero, Im sure you will a good TAS for some other great game :)
Ditto
Player (94)
Joined: 6/25/2005
Posts: 122
Bisqwit wrote:
****) 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.