Post by Bobo_the_King

Posted: 12/22/2013 3:10 AM
(Edited: 8/10/2015 8:04 AM)

Post subject: Brute-force script for short, well-defined goals

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

For an updated version of my script that works in BizHawk, click here. To see an example of how to use my script, scroll down to the second post or just click here. The topic of brute-force completing even a short task in a game comes up every now and then. The conclusion is inevitably that brute-force searches are infeasible for even short segments under heavy restrictions. (Emulating 30 frames using only one button would take one billion iterations.) Wait, where are you going? Come back! I swear I'm not wasting your time! Hear me out! What always struck me as unreasonable about previous discussions of brute-force solutions is that they assumed the most naive restrictions about the input. For example, truly random input (or exhaustive search through all input combination) would include absurd combinations where a button is pressed and released many times to no great effect. For example, in Super Mario Bros., if all we want is for Mario to run right, we want to hold right, not press and release it over and over again. In an ideal situation, the user wants to complete some short task using a few buttons and they already have a decent idea of what buttons they want to press and when. That's where my script comes in. Purpose: To brute-force a short section of the game in which the goal is well-defined and the user has a decent idea of what buttons they want to press and when to press them to achieve that goal. This severely cuts down on the parameter space, so it isn't really brute-forcing, but it does exhaustively run through all possible timings within the ranges specified by the user. The script: Download BruteForce.lua

Language: lua
-- * * * PARAMETERS * * *
-- By default, ThisAddress just returns the value of a single address.  However, you can have it return any function of any number of addresses.
local function ThisAddress()
	return memory.readbyte()   --Input the address you're interested in here.
end

IWant=ThisAddress
ToBe=''	--{'minimized','maximized','equal to','less than','greater than','at least','at most'}
-- If ToBe in {'minimized','maximized'}...
	AndTheBestIveDoneIs=   --Input a value of that address that you think this script can beat.
	InThisManyFrames=   --How many frames should each iteration run for?  The script will check for success after this many frames.
-- Elseif ToBe in {'equal to','less than','greater than','at least','at most'}
	ThisValue=   --Input the value that you'd like to compare the address to.
	AndTheFastestIveDoneItIs=   --Input a number of frames that you think the script can beat.

UsingTheseButtons={{}}   --Input the buttons you'd like to use.  Each element of UsingTheseButtons is a table.  The first entry is the player, the second is the button, the third is 'on' or 'off' depending on whether you'd like to press or release the button, and the fourth is the interval (absolute or relative) over which you'd like the script to check.  See my comment at the bottom of this script for examples of how to enter it.

-- * * * FUNCTIONS * * *
local function tablecopy(t1)
	local t2={}
	if not(type(t1)=='table') then
		t2=t1
		return t2
	end
	for k,v in pairs(t1) do
		if type(v)=='table' then
			t2[k]=tablecopy(v)
		else
			t2[k]=v
		end
	end
	return t2
end

-- Takes a character code (from a string) and returns true if it corresponds to a numeral.
local function isnumeral(charcode)
	return (charcode>=0x30 and charcode<=0x39)
end

-- Extracts the first number from a string.  For example, running this function on the string "event48blah19" will return 48.
local function getnumber(str)
	local numstart=nil
	local numend=nil
	for i=1,string.len(str) do
		if isnumeral(string.byte(str,i)) then
			if not(numstart) then
				numstart=i
				numend=numstart
				local j=i+1
				while isnumeral(string.byte(str,j)) do
					numend=j
					j=j+1
				end
			end
		end
	end
	if not(numstart) then
		error('No number found!')
	end
	
	local valuetext=string.sub(str,numstart,numend)
	local value = tonumber(valuetext)
	return value
end

-- Parses one of the bounds in an interval, returning the frame value.  You would run this function on, say, "(event2+10," to return index[2]+10+1.
-- It isn't necessary to type "event", "start", or "finish" in full, it just looks for the first match.  Watch out, though, because parsebound('[safe+2,') will return index[2]+2, not 2.
local function parsebound(str,index,maxframes)
	local value=-1
	if string.find(str,'e') then	--Bound defined relative to event.
		value=index[getnumber(str)]
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	elseif string.find(str,'f') then	--Bound defined relative to finish.
		value=maxframes
		local minus=string.find(str,'-')
		if minus then
			local minusthis=string.sub(str,minus)
			value=value+getnumber(minusthis)
		end
	elseif string.find(str,'s') then	--Bound defined relative to start.  Note that because of the elseif statement above, this won't be triggered by "finiSh".
		value=0
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	else	--Bound defined by number.  "+" not allowed!
		value=getnumber(str)
	end
	if string.sub(str,1,1)=='(' then
		value=value+1
	end
	if string.sub(str,-1)==')' then
		value=value-1
	end
	return value
end

-- Parses interval notation into start and finish times.
local function parseinterval(UsingTheseButtons,index,depth,maxframes)
	interval = UsingTheseButtons[depth][4]
	if type(interval)=='number' then	--If interval is just a number, then low and high are both equal to that number.
		low=interval
		high=interval
	elseif string.sub(interval,1,1)=='[' or string.sub(interval,1,1)=='(' then	--The interval is explicitly defined in this case.
		local comma=string.find(interval,',')
		if not comma then
			error('Expected comma to define interval.')
		else
			local lowerbound=string.sub(interval,1,comma)
			local upperbound=string.sub(interval,comma)
			low=parsebound(lowerbound,index,maxframes)
			high=parsebound(upperbound,index,maxframes)
		end
	else	--If no interval is explicitly defined, then the interval is taken to be implicit and both low and high are set equal to the output of parsebound acting on interval in its entirety.
		low=parsebound(interval,index,maxframes)
		high=low
	end

	--This is a little forgiving to the user.  Perhaps their interval was defined improperly, such that the lower bound surpassed the upper bound.
	if high<low then
		high=low
	end
	return low,high
end

-- Compares IWant with Value according to function specified by ToBe
local function check(IWant,ToBe,Value)
	if not(Value) then return nil end
	if ToBe=='minimized' then
		return (IWant()<Value)
	elseif ToBe=='maximized' then
		return (IWant()>Value)
	elseif ToBe=='equal to' then
		return (IWant()==Value)
	elseif ToBe=='less than' then
		return (IWant()<Value)
	elseif ToBe=='greater than' then
		return (IWant()>Value)
	elseif ToBe=='at least' then
		return (IWant()>=Value)
	elseif ToBe=='at most' then
		return (IWant()<=Value)
	else
		error('Invalid string for ToBe.')
	end
end

-- IWant refers only to the current frame, which isn't useful when checking nodes with branches.  Therefore, this function directly compares an old value with a new value, based on ToBe.
local function check2(newvalue,ToBe,oldvalue)
	if not(newvalue) then return nil end
	if ToBe=='minimized' then
		return (newvalue<oldvalue)
	elseif ToBe=='maximized' then
		return (newvalue>oldvalue)
	elseif ToBe=='equal to' then
		return (newvalue==oldvalue)
	elseif ToBe=='less than' then
		return (newvalue<oldvalue)
	elseif ToBe=='greater than' then
		return (newvalue>oldvalue)
	elseif ToBe=='at least' then
		return (newvalue>=oldvalue)
	elseif ToBe=='at most' then
		return (newvalue<=oldvalue)
	else
		error('Invalid string for ToBe.')
	end
end

-- Executes the actual button presses and checks if it is superior to previous attempts.
-- The output of this function depends on the string in ToBe.  If the string is "minimized" or "maximized", it returns the value.  If the string is something else, it returns the number of frames.
-- If it doesn't beat the current record, the output is nil.
local function attempt(presses,IWant,ToBe,Value,maxframes)
	
	if ToBe=='maximized' or ToBe=='minimized' then
		for frame=0,#presses do
			for player=1,2 do
				joypad.set(player,presses[frame][player])
			end
			emu.frameadvance()
		end
		if check(IWant,ToBe,Value) then
			return IWant()
		end
	else
		for frame=0,#presses do
			if frame<maxframes then
				if check(IWant,ToBe,Value) then
					return frame
				end
			end
			for player=1,2 do
				joypad.set(player,presses[frame][player])
			end
			emu.frameadvance()
		end
	end
	return nil
end

-- Presses the buttons prescribed by UsingTheseButtons and index.
-- presses[frame][player][button].
local function pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state)
	local presses={}
	for frame=0,maxframes do
		presses[frame]={}
		for player=1,2 do	--Edit the number of players here.
			presses[frame][player]={}
		end
		for i=1,#index do
			if frame>=index[i] then
				local OnOrOff = (UsingTheseButtons[i][3]=='on')	--Set button if "on", reset otherwise.
				presses[frame][UsingTheseButtons[i][1]][UsingTheseButtons[i][2]]=OnOrOff
			end
		end
	end
	output=attempt(presses,IWant,ToBe,Value,maxframes)
	savestate.load(state)
	return presses,output
end

--
local function DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state)
	depth=depth+1
	local bestpresses,attemptframes,attemptValue,presses
	low,high=parseinterval(UsingTheseButtons,index,depth,maxframes)
	if depth==#UsingTheseButtons then
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state)
				if attemptValue then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state)
				if attemptframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	else
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state)
				if check2(attemptValue,ToBe,Value) then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state)
				if attemptframes<maxframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		return bestpresses,Value
	else
		return bestpresses,maxframes
	end
end

-- * * * BASE CODE * * *
if ToBe == 'minimized' or ToBe == 'maximized' then
	Value=AndTheBestIveDoneIs
	maxframes=InThisManyFrames
else
	Value=ThisValue
	maxframes=AndTheFastestIveDoneItIs
end
depth=0
index={}
state1=savestate.create()
savestate.save(state1)
presses,best=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state1)
if presses then
	for frame=0,#presses do
		print('Frame: '..frame)
		print('Buttons: ',presses[frame][1])
		for player=1,2 do
			joypad.set(player,presses[frame][player])
		end
		emu.frameadvance()
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		print('Best value: ' .. best)
	else
		print('Fewest frames: ' .. best)
	end
else
	print('No improvement found!')
end
emu.pause()

--[[
UsingTheseButtons has elements with the structure
{player,button,'on'/'off',timing}
where timing is a string based solely on PREVIOUS events in the UsingTheseButtons vector as well as the start frame (0) and end frame (InThisManyFrames/AndTheFastestIveDoneItIs).  Examples of timing:
'[start,finish]'		-- Test all frames.
'[start,37]'			-- Test all frames from start to frame 37, inclusive.
'(start,37)'			-- Test all frames from start to frame 37, exclusive.
'[15,37]'				-- Any frame from 15 to 37, inclusive.
'[event 2,finish]'		-- Any frame after event 2 has begun, where event 2 is the second element of the UsingTheseButtons vector.  This can be used to force, for example, shooting only after jumping.
'[event 2+37,finish]'	-- No, that doesn't mean event 39.  It means wait at least 37 frames after event 2 has finished.
('[event 2-37,finish]')	-- I'm not sure I want to program this, since each event's timing is supposed to depend on PRIOR events.  It should always be possible to put them in order.

In total, the UsingTheseButtons table might look like this:
UsingTheseButtons={{1,'A','on','[start,finish]'},
				   {1,'A','off','(event 1, finish]'},
				   {1,'right','on','[37,60]'},
				   {1,'up','on','[event 3+2,event 3+2]'},
				   {1,'right','off','[40,finish]'}
				   }
				   
which means try pressing A on any frame, hold it for any interval (release A any time AFTER pressing it), hold right beginning sometime between frames 37 and 60, 
hold up beginning exactly 2 frames after holding right, and release right sometime between frame 40 and the end of input.  Up will be held until the end of input.

Later events override conflicting earlier events.  Generally, it's a good idea to define the timing of 'off' commands with respect to their earlier 'on' counterparts.
]]--

How to use it: I'll post an example of this script's use after I'm finished writing this post. Here is a formal description of how to use the script. Focus your attention on the uppermost section of the script, in the section labeled "PARAMETERS". Everything you input will be there. 1) Decide what constitutes "success". What addresses are involved? If there is just one address you're interested in, put it in the memory.readbyte() function on line 4. If you're interested in some function of more than one memory address, you'll need to rewrite the entire ThisAddress function. 2) What do you want to do with the value you programmed? Do you want it to be maximized or minimized? Do you want it to be equal to, greater than, less than, at least, or at most some value? Pick one of those options and put that corresponding string on line 8, variable ToBe. 3) Suppose you want to minimize or maximize the value. Then the script needs a benchmark from which to start, as well as a number of frames after which to check. These are defined on lines 10 and 11 as variables AndTheBestIveDoneIs and AfterThisManyFrames. (Note that AndTheBestIveDoneIs is largely irrelevant, since the script will keep trying inputs and replacing its value as it runs.) You can then make ThisValue and AndTheFastestIveDoneItIs whatever values you want; those variables will not be used. 4) Suppose instead you want to compare the address with some predetermined value. Input the value you wish to compare it with on line 13 as ThisValue. The script needs to know how long it will have to run for, so input the number of frames at which to check on line 14 as AndTheFastestIveDoneItIs. Since you aren't minimizing or maximizing the address, you can make AndTheBestIveDoneIs and AfterThisManyFrames on lines 10 and 11 whatever you want. Their values will not be used. 5) Finally, here's the hard part. You need to tell the script what buttons to use. That's done on line 16 under table UsingTheseButtons. Each element is another table with four elements. The first element is the player number. The second is the button (as a string) to press/release. The third is either 'on' or 'off', specifying that the button is to be pressed or released respectively. The last element is tricky. It uses mathematical interval notation. You need to specify the interval over which the button might be pressed or released. This can be done absolutely (relative to 'start'=0 frames) or relatively (relative to any prior event). For relative timings, type "event", followed by a number. The number specifies which element of UsingTheseButtons the timing is relative to. For example, if we enter '[event2+8,event3+12]', that means the button is pressed/released no sooner than 8 frames after the second button is pressed/released and no later than 12 frames after the third button is pressed/released. For an example of how all of these are entered, see the comment at the bottom of my script. Briefly reflect on all the values you entered. It's supposed to be easy to interpret in plain English. We entered either, "I want this address (_____) to be {minimized/maximized} and the best I've done is ______ in ______ frames using these buttons: _____," or, "I want this address (_____) to be {equal to/less than/greater than/at least/at most} ______ and the fastest I've done it is _____ frames using these buttons: _____." Make sense? Now save the script and run it during the relevant part of the game. The script will run through all iterations consistent with the bounds you gave it. When it is done, it will execute the button presses that gave it the best result and output those presses to the Lua console for your convenience. Possible improvements: Very few, I'm proud to say! This script already does just about everything I want it to. As usual, my coding is sloppy and could probably be much more concise. I would like to combine the check and check2 functions into one function and I would also like to allow the user to input the address they're interested in directly into the definition of IWant (both of these changes should be easy). I also should expand the script to allow for three or four player games. This is a very powerful script, so if you think that it's not up to some task, it's probably because you haven't yet figured out how to use it to its full potential. Nevertheless, if you have any suggestions, please let me know. Finally, I'd like to thank FatRatKnight for helping me debug the script when it was almost finished.

Posted: 12/22/2013 3:11 AM
(Edited: 8/10/2015 8:11 AM)

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

This post has been updated on August 10th, 2015 to incorporate BizHawk instead of FCEUX. Almost everything is identical. The save file has been updated. The only major difference to look out for is that directional buttons in FCEUX are uncapitalized ("up", "down", "left", "right"), while in BizHawk they are capitalized ("Up", "Down", "Left", "Right"). As a demonstration of my script, I will use a simple example that you should already be familiar with. We're going to pretend that we don't know how to execute a walljump in Super Mario Bros. and we'll have the script execute one for us. Before we begin, I need to point out that I'm using FCEUX. That's important because FCEUX does not execute Lua scripts until the frame after they are loaded. That means even though my state starts at frame 4036, the Lua script will begin executing on the next frame, 4037. Because the framecount is important to the script, I have to be careful to measure all of those frames relative to 4037. You'll see what I mean in a bit. I haven't checked other emulators to see if Lua scripts execute on the frame they're loaded, but you would be wise to check it yourself before using my script. [Note: I just realized that because of how movies are timed, the movie I uploaded resets the frame count to 0. This doesn't change what I said above, except for the numbers I used.] The savestate (compatible with BizHawk) I will be using can be found here. (The old file, compatible with FCEUX can be found here. In both cases, it's saved as a movie file because apparently we don't have a way of exchanging savestates. Just open the movie and immediately stop it.) As you can see, we're at the end of world 1-1 with a nice wall to our left. Let's jump up it, pretending we can't do it by trial and error ourselves. First, we'll need to consider how to define success at the walljump. One relevant RAM address is Mario's y value, stored at 0x00CE. A quick inspection shows that this value decreases as the height of Mario's jump increases. Furthermore, by executing a single running jump, its value reaches a minimum of 93. (Note: the highest Mario can reach from a standing jump is 110. I completed much of this example with 110 as my value before realizing that 93 was the one I should use. Be careful!) Let's define a successful walljump as a series of inputs such that address 00CE is minimized and is less than 93. (We could also define it to be any jump where 00CE is less than 93. This will slightly alter the results because the script will look for the quickest walljump, not the highest walljump.) Our goal is well-defined, so we can enter the first few lines of our program. We're interested in Mario's y position, so we'll insert the value 0x00CE into the ThisAddress function:

Language: lua
local function ThisAddress()
	return memory.readbyte(0x00CE)
end

We want to minimize its value, so we'll set ToBe like so:

Language: lua
ToBe='minimized'

And we want to the height of the jump to be at least 93 (setting this value higher will not affect the output of the script):

Language: lua
     AndTheBestIveDoneIs=93

Now we need to know how many frames must pass before checking the result. This is nontrivial, so I'll just do a back-of-the-envelope calculation. It takes about 30 frames for Mario to reach his peak height. If two jumps are fully executed, that would be about 60 frames. Let's tack on another 30 frames in case Mario needs a running start. That means we need to change the script like so:

Language: lua
     InThisManyFrames=90

Because this is a minimization/maximization problem, the values of ThisValue and AndTheFastestIveDoneItIs are irrelevant. Let's take a moment to read back the contents of what we put in. In plain English, it should now read, "I want this address (00CE) to be minimized and the best I've done is 93 in 90 frames." Sounds good! Now for the hard part. We need to establish the pattern of the button presses. We're only using one player, so the first element of each element of UsingTheseButtons will be 1. That simplifies it a bit. It seems like it would be a good idea to have Mario run left immediately. Therefore, our first two events are quite simple:

Language: lua
UsingTheseButtons[1]={1,'Left','on','start'}
UsingTheseButtons[2]={1,'B','on','start'}

which tells the script to hold left and B at the start of the script's execution, with no exceptions. (The last element of each, 'start', could be equivalently replaced with 's', '[start,start]', 0, '0', 'start+0', or any number of other strings, including almost absurd ones like 'sasquatch'.) Now what? We want Mario to begin his jump at some later frame. By doing a quick test, we can determine that he needs at least a little running start or else he will fall short of the wall. After a few trials, we find that Mario needs about 20 frames of running before beginning his jump. Furthermore, we can see that if we jump too late (after 30 frames), we hit the wall as we're going up. Therefore, we want to press A somewhere between 20 and 30 frames after the start. I'll modify those bounds to 18 and 32 frames so that there's a little forgiveness in case my estimates were off. This comes at the expense of making the program run 1.4 times longer. Here's what the third event will be:

Language: lua
UsingTheseButtons[3]={1,'A','on','[18,32]'}

How long do we want to hold A for? It takes about 30 frames to reach the maximum height of the jump, so it doesn't make sense to hold it longer than that. On the other hand, we want at least a moderately high jump, so let's hold A for at least 20 frames. Note that both of these bounds are written with respect to when we started holding A. Our next event is:

Language: lua
UsingTheseButtons[4]={1,'A','off','[event3+18,event3+30]'}

Here, event3 refers to UsingTheseButtons[3]. We release A between 18 and 30 frames after it was first pressed. Finally, we need to press A again to execute the walljump itself. By running right, we find that we hit the wall at around frame 4096, 59 frames after the Lua script begins executing. Let's press A a second time either on that frame or one of the subsequent three frames, like so:

Language: lua
UsingTheseButtons[5]={1,'A','on','[59,63)'}

Note the close parenthesis there. Like interval notation in mathematics, it means exclude 63 from the interval. That means we'll be pressing A on frames 59, 60, 61, and 62. After entering all of this, the top of our script should read:

Language: lua
local function ThisAddress()
	return memory.readbyte(0x00CE)
end

IWant=ThisAddress
ToBe='minimized'	
	AndTheBestIveDoneIs=93
	InThisManyFrames=90
	ThisValue=0
	AndTheFastestIveDoneItIs=0

UsingTheseButtons={{1,'Left','on','start'},
                   {1,'B','on','start'},
                   {1,'A','on','[18,32]'},
                   {1,'A','off','[event3+18,event3+30]'},
                   {1,'A','on','[59,63)'}
                  }

Based on all the intervals we input, how many iterations will this script run through? The first two events don't contribute any iterations because they always execute at a fixed time. Event 3 runs over 15 possibilities, event 4 runs over 13 possibilities, and event 5 runs over 4 possibilities. Therefore, the number of iterations will be 1*1*15*13*4 = 780 iterations. At 90 frames per iteration (one-and-a-half seconds at 100% speed), it will take about 20 minutes to run through all iterations. Of course, you'll want to go through at turbo speed, so it will actually take just a minute or two to finish. Now run the script! You'll see Mario run to the wall and jump over and over again. If you look carefully, you'll notice that each time, his motion is subtly different as the script runs through all the possibilities you gave it. Eventually, he'll successfully execute the walljump! After all iterations are complete, it executes the button presses that produced the best results (in this case, Mario reaches a height of 13 after 90 frames). *Whew!* You may be asking yourself at this point, "Was all of this effort worth it?" For a well-documented trick like walljumping in Super Mario Bros., no, of course it isn't. But suppose you don't know that walljumping is possible. For example, walljumps were discovered in Yoshi's Island when NxCy and Baxter were already well into their TAS. They had to go back and redo much of their run to incorporate the new trick. If they had my script as well as a notion that walljumping might be possible given the right timings, they could have executed my script and seen in a matter of minutes how to perform a walljump. But that's just the tip of the iceberg. Any goal that is well-defined by the RAM and does not rely on too many button presses with loose restrictions can be thoroughly and exhaustively optimized for the input paramters. The sky's the limit! This script is about as powerful as what you put into it. For those of you who would like to execute the script on the savestate without editing it yourself, here it is in its entirety:

Language: lua
-- * * * PARAMETERS * * *
-- By default, ThisAddress just returns the value of a single address.  However, you can have it return any function of any number of addresses.
local function ThisAddress()
	return memory.readbyte(0xCE)
end

IWant=ThisAddress
ToBe='minimized'  --{'minimized','maximized','equal to','less than','greater than','at least','at most'}
-- If ToBe in {'minimized','maximized'}...
  AndTheBestIveDoneIs=93
  InThisManyFrames=90
-- Elseif ToBe in {'equal to','less than','greater than','at least','at most'}
  ThisValue=0
  AndTheFastestIveDoneItIs=0    --frames

UsingTheseButtons={{1,'Left','on','start'},
           {1,'B','on','start'},
           {1,'A','on','[18,32]'},
           {1,'A','off','[event3+18,event3+30]'},
           {1,'A','on','[59,63)'}
          }

-- * * * FUNCTIONS * * *
local function tablecopy(t1)
	local t2={}
	if not(type(t1)=='table') then
		t2=t1
		return t2
	end
	for k,v in pairs(t1) do
		if type(v)=='table' then
			t2[k]=tablecopy(v)
		else
			t2[k]=v
		end
	end
	return t2
end

local function getframeadvancefunction()
	if FCEU or bizstring then
		return emu.frameadvance
	elseif gens then
		return gens.emulateframeinvisible
	else
		print("Unrecognized emulator.")
	end
end

local function jpset(player, buttons)
	if FCEU or gens then
		joypad.set(player, buttons)
	elseif bizstring then	-- BizHawk's joypad.set convention is "backwards".  WTF, BizHawk?
		joypad.set(buttons,player)
	else
		print("Unrecognized emulator.")
	end
end

-- Takes a character code (from a string) and returns true if it corresponds to a numeral.
local function isnumeral(charcode)
	return (charcode>=0x30 and charcode<=0x39)
end

-- Extracts the first number from a string.  For example, running this function on the string "event48blah19" will return 48.
local function getnumber(str)
	local numstart=nil
	local numend=nil
	for i=1,string.len(str) do
		if isnumeral(string.byte(str,i)) then
			if not(numstart) then
				numstart=i
				numend=numstart
				local j=i+1
				while isnumeral(string.byte(str,j)) do
					numend=j
					j=j+1
				end
			end
		end
	end
	if not(numstart) then
		error('No number found!')
	end
	
	local valuetext=string.sub(str,numstart,numend)
	local value = tonumber(valuetext)
	return value
end

-- Parses one of the bounds in an interval, returning the frame value.  You would run this function on, say, "(event2+10," to return index[2]+10+1.
-- It isn't necessary to type "event", "start", or "finish" in full, it just looks for the first match.  Watch out, though, because parsebound('[safe+2,') will return index[2]+2, not 2.
local function parsebound(str,index,maxframes)
	local value=-1
	if string.find(str,'e') then	--Bound defined relative to event.
		value=index[getnumber(str)]
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	elseif string.find(str,'f') then	--Bound defined relative to finish.
		value=maxframes
		local minus=string.find(str,'-')
		if minus then
			local minusthis=string.sub(str,minus)
			value=value+getnumber(minusthis)
		end
	elseif string.find(str,'s') then	--Bound defined relative to start.  Note that because of the elseif statement above, this won't be triggered by "finiSh".
		value=0
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	else	--Bound defined by number.  "+" not allowed!
		value=getnumber(str)
	end
	if string.sub(str,1,1)=='(' then
		value=value+1
	end
	if string.sub(str,-1)==')' then
		value=value-1
	end
	return value
end

-- Parses interval notation into start and finish times.
local function parseinterval(UsingTheseButtons,index,depth,maxframes)
	interval = UsingTheseButtons[depth][4]
	if type(interval)=='number' then	--If interval is just a number, then low and high are both equal to that number.
		low=interval
		high=interval
	elseif string.sub(interval,1,1)=='[' or string.sub(interval,1,1)=='(' then	--The interval is explicitly defined in this case.
		local comma=string.find(interval,',')
		if not comma then
			error('Expected comma to define interval.')
		else
			local lowerbound=string.sub(interval,1,comma)
			local upperbound=string.sub(interval,comma)
			low=parsebound(lowerbound,index,maxframes)
			high=parsebound(upperbound,index,maxframes)
		end
	else	--If no interval is explicitly defined, then the interval is taken to be implicit and both low and high are set equal to the output of parsebound acting on interval in its entirety.
		low=parsebound(interval,index,maxframes)
		high=low
	end

	--This is a little forgiving to the user.  Perhaps their interval was defined improperly, such that the lower bound surpassed the upper bound.
	if high<low then
		high=low
	end
	return low,high
end

-- Compares IWant with Value according to function specified by ToBe
local function check(IWant,ToBe,Value)
	if not(Value) then return nil end
	if ToBe=='minimized' then
		return (IWant()<Value)
	elseif ToBe=='maximized' then
		return (IWant()>Value)
	elseif ToBe=='equal to' then
		return (IWant()==Value)
	elseif ToBe=='less than' then
		return (IWant()<Value)
	elseif ToBe=='greater than' then
		return (IWant()>Value)
	elseif ToBe=='at least' then
		return (IWant()>=Value)
	elseif ToBe=='at most' then
		return (IWant()<=Value)
	else
		error('Invalid string for ToBe.')
	end
end

-- IWant refers only to the current frame, which isn't useful when checking nodes with branches.  Therefore, this function directly compares an old value with a new value, based on ToBe.
local function check2(newvalue,ToBe,oldvalue)
	if not(newvalue) then return nil end
	if ToBe=='minimized' then
		return (newvalue<oldvalue)
	elseif ToBe=='maximized' then
		return (newvalue>oldvalue)
	elseif ToBe=='equal to' then
		return (newvalue==oldvalue)
	elseif ToBe=='less than' then
		return (newvalue<oldvalue)
	elseif ToBe=='greater than' then
		return (newvalue>oldvalue)
	elseif ToBe=='at least' then
		return (newvalue>=oldvalue)
	elseif ToBe=='at most' then
		return (newvalue<=oldvalue)
	else
		error('Invalid string for ToBe.')
	end
end

-- Executes the actual button presses and checks if it is superior to previous attempts.
-- The output of this function depends on the string in ToBe.  If the string is "minimized" or "maximized", it returns the value.  If the string is something else, it returns the number of frames.
-- If it doesn't beat the current record, the output is nil.
local function attempt(presses,IWant,ToBe,Value,maxframes,frameadvance)

	if ToBe=='maximized' or ToBe=='minimized' then
		for frame=0,#presses do
			for player=1,2 do
				--Edited for BizHawk support.  Try to come up with a solution for all emulators.
				jpset(player, presses[frame][player])
			end
			frameadvance()
		end
		if check(IWant,ToBe,Value) then
			return IWant()
		end
	else
		for frame=0,#presses do
			if frame<maxframes then
				if check(IWant,ToBe,Value) then
					return frame
				end
			end
			for player=1,2 do
				jpset(player, presses[frame][player])
			end
			frameadvance()
		end
	end
	return nil
end

-- Uses UsingTheseButtons and index to construct a table of button presses, then passes that table to the attempt function to execute them.
-- presses[frame][player][button].
local function pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
	local presses={}
	for frame=0,maxframes do
		presses[frame]={}
		for player=1,2 do	--Edit the number of players here.
			presses[frame][player]={}
		end
		for i=1,#index do
			if frame>=index[i] then
				local OnOrOff = (UsingTheseButtons[i][3]=='on')	--Set button if "on", reset otherwise.
				presses[frame][UsingTheseButtons[i][1]][UsingTheseButtons[i][2]]=OnOrOff
			end
		end
	end
	output=attempt(presses,IWant,ToBe,Value,maxframes,frameadvance)
	savestate.load(state)
	return presses,output
end

--
local function DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
	depth=depth+1
	local bestpresses,attemptframes,attemptValue,presses
	low,high=parseinterval(UsingTheseButtons,index,depth,maxframes)
	if depth==#UsingTheseButtons then
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
				if attemptValue then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
				if attemptframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	else
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
				if check2(attemptValue,ToBe,Value) then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
				if attemptframes<maxframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		return bestpresses,Value
	else
		return bestpresses,maxframes
	end
end

-- * * * BASE CODE * * *
if ToBe == 'minimized' or ToBe == 'maximized' then
	Value=AndTheBestIveDoneIs
	maxframes=InThisManyFrames
else
	Value=ThisValue
	maxframes=AndTheFastestIveDoneItIs
end
frameadvance=getframeadvancefunction()
depth=0
index={}
if bizstring then
	state1="state1"
else
	state1=savestate.create()
end
savestate.save(state1)
presses,best=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state1,frameadvance)
if presses then
	for frame=0,#presses do
		print('Frame: '..frame)
		for player=1,2 do
			print('Player ' .. player .. ' buttons: ',presses[frame][player])
			jpset(player, presses[frame][player])
		end
		frameadvance()
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		print('Best value: ' .. best)
	else
		print('Fewest frames: ' .. best)
	end
else
	print('No improvement found!')
end
if FCEU or gens then
	emu.pause()
elseif bizstring then
	client.pause()
end

--This function works.  It will serve as a template for the final function.
--[=[
local function DFS(G,index,depth)
	depth=depth+1
	if G[depth][1] == 'abs' then
		low=G[depth][2]
		high=G[depth][3]
	elseif G[depth][1] == 'rel' then
		low=index[G[depth][2]] + G[depth][3]
		high=index[G[depth][2]] + G[depth][4]
	end
	if depth==#G then
		for i=low,high do
			index[depth]=i
			for j=1,#index do
				print(index[j])
			end
			print('Next!')
		end
	else
		for i=low,high do
			index[depth]=i
			DFS(G,index,depth)
		end
	end
end

G={{'abs',0,5},{'rel',1,6,16},{'rel',2,8,20}}
--G={{'abs',0,1},{'rel',1,10,11},{'rel',2,100,101}}
depth=0
index={}
DFS(G,index,depth)
]=]--

--[[
{{,,'[start,start+20]'},
 {,,'[event1,event1+5]'},
 {,,'[event2+10,event2+20]'}}
for i=0,20 do
	for j=i,i+5 do
		for k=j+10,j+20 do
		
		end
	end
end

index={}
function makeloops(events,index,depth)
	if depth==#events then
		for 
	else
		depth=depth+1
	end
end

Wikipedia pseudocode:
procedure DFS(G,v):
	label v as discovered
	for all edges from v to w in G.adjacentEdges(v) do
		if vertex w is not labeled as discovered then
			recursively call DFS(G,w)
]]--

--[[
UsingTheseButtons has elements with the structure
{player,button,'on'/'off',timing}
where timing is a string based solely on PREVIOUS events in the UsingTheseButtons vector as well as the start frame (0) and end frame (InThisManyFrames/AndTheFastestIveDoneItIs).  Examples of timing:
'[start,finish]'		-- Test all frames.
'[start,37]'			-- Test all frames from start to frame 37, inclusive.
'(start,37)'			-- Test all frames from start to frame 37, exclusive.
'[15,37]'				-- Any frame from 15 to 37, inclusive.
'[event 2,finish]'		-- Any frame after event 2 has begun, where event 2 is the second element of the UsingTheseButtons vector.  This can be used to force, for example, shooting only after jumping.
'[event 2+37,finish]'	-- No, that doesn't mean event 39.  It means wait at least 37 frames after event 2 has finished.
('[event 2-37,finish]')	-- I'm not sure I want to program this, since each event's timing is supposed to depend on PRIOR events.  It should always be possible to put them in order.

In total, the UsingTheseButtons table might look like this:
UsingTheseButtons={{1,'A','on','[start,finish]'},
				   {1,'A','off','(event 1, finish]'},
				   {1,'right','on','[37,60]'},
				   {1,'up','on','[event 3+2,event 3+2]'},
				   {1,'right','off','[40,finish]'}
				   }
				   
which means try pressing A on any frame, hold it for any interval (release A any time AFTER pressing it), hold right beginning sometime between frames 37 and 60, 
hold up beginning exactly 2 frames after holding right, and release right sometime between frame 40 and the end of input.  Up will be held until the end of input.

Later events override conflicting earlier events.  Generally, it's a good idea to define the timing of 'off' commands with respect to their earlier 'on' counterparts.
]]--

Posted: 12/22/2013 8:39 AM

Quote

BadPotato

Joined: 1/26/2009
Posts: 558
Location: Canada - Québec

Bobo the King wrote:

Therefore, the number of iterations will be 1*1*15*13*4 = 780 iterations. At 90 frames per iteration (one-and-a-half seconds at 100% speed), it will take about 20 minutes to run through all iterations. Of course, you'll want to go through at turbo speed, so it will actually take just a minute or two to finish.

For a generic script(that require precise pattern of button press&goals) running on the NES, the time spent on bruteforcing seem fairly reasonable! At some point, I guess the higher the "InThisManyFrames" value is, the more pattern should be described to keep the script "short" enough. So as a small suggestion for improving the script, I'll suggest to calculate right at beginning what is the maximum exhaustion attempt number and print it on the screen, in order to get a general idea of how long we should wait.

For example, walljumps were discovered in Yoshi's Island when NxCy and Baxter were already well into their TAS. They had to go back and redo much of their run to incorporate the new trick. If they had my script as well as a notion that walljumping might be possible given the right timings, they could have executed my script and seen in a matter of minutes how to perform a walljump.

Since walljump are kinda a common trick on platform game and they're likely to require very few changes for pattern provided... maybe it could be possible to make a library of pattern/common tricks for games. Some common idea that I could think: -Walljump over a fence. -Zip through the wall. -Hit a boss when you have to for invincibility gap to end. -Get a random item drop after a specific task. -Pass text on the right frame when you have to wait for unskippable dialog text. -Get the best angle for a specific task in 3D games. ...etc I'm sure there're plenty of common patterns that could inspire other people to make their own implementation for their own game. However in the end, I guess it's best to keep in mind that quite often, it's better for the TASer to just make their own custom bot for flexibility purpose. In any case, right now when I'm trying to run the script, there is a couple of errors. So far, I think you forgot to post the DepthFirstSearch function, or maybe I missed something?

Posted: 12/22/2013 2:24 PM

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

BadPotato wrote:

In any case, right now when I'm trying to run the script, there is a couple of errors. So far, I think you forgot to post the DepthFirstSearch function, or maybe I missed something?

Ugh, how embarrassing! I shouldn't have gone to sleep immediately after posting my script! It turns out that having HTML enabled was causing a large section of my script (between two inequalities) to be deleted. I've disabled HTML in my two posts and modified the script accordingly. I'll try to incorporate your suggestion later today. My first thought was that it should be easy, but on further thought, the intervals are not necessarily of fixed length, which makes the combinatorics much more difficult. I'll think about it.

Posted: 12/22/2013 4:26 PM

Quote

r57shell

Player (99)

Joined: 12/12/2013
Posts: 380
Location: Russia

Is this script able to make right positioning? I want X to be in range [0,2] as fast as possible, and keys: C,Left,Right press/release in any time. Something like that... I don't see how to configure it out. EDIT: you always run whole input from start. You can make savestates (in memory) at events.

Posted: 12/22/2013 8:56 PM

Quote

r57shell

Player (99)

Joined: 12/12/2013
Posts: 380
Location: Russia

TASK: you stay in position X. You have jump, and walk. Both has different accelerations by X. Time in jump differs by C time pressed after jump. Needs to set X at range[a,b]. After this, I can make zip through wall. (Or want to test).

Posted: 12/22/2013 10:40 PM

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

r57shell wrote:

TASK: you stay in position X. You have jump, and walk. Both has different accelerations by X. Time in jump differs by C time pressed after jump. Needs to set X at range[a,b]. After this, I can make zip through wall. (Or want to test).

I edited my post above to show how you would test for a range of values using my current script. I hope that helps! If not, I think I need more information about the game you're testing.

Posted: 12/23/2013 1:31 AM

Quote

r57shell

Player (99)

Joined: 12/12/2013
Posts: 380
Location: Russia

Problem is that I don't know how many times I need to press and release Left and Right buttons. Nevermind, it will brute for centuries.

Posted: 12/25/2013 7:44 AM

Quote

Personman

Other

Joined: 4/20/2008
Posts: 466

While I'm not in a position to be using this myself right now, I hope I am someday, and regardless, I want to thank you deeply for doing this work! This kind of thing is exactly what we need more of, and I can see some very exciting tools being growing out of it - not that it's not exciting enough already! I hope word spreads quickly, and people are able to adopt this new methodology soon & successfully!

A warb degombs the brangy. Your gitch zanks and leils the warb.

Posted: 4/25/2015 12:23 AM

Quote

ventuz

He/Him

Player (127)

Joined: 10/4/2004
Posts: 940

Update for BizHawk please? Error: LuaInterface.LuaScriptException: [string "main"]:291: attempt to call field 'create' (a nil value)

Posted: 8/7/2015 5:16 AM

Quote

Really_Tall

She/Her

Editor, Player (222)

Joined: 9/29/2014
Posts: 123
Location: Scotland

ventuz wrote:

Update for BizHawk please? Error: LuaInterface.LuaScriptException: [string "main"]:291: attempt to call field 'create' (a nil value)

YouTube: https://www.youtube.com/Really_Tall Twitter: https://twitter.com/Really_Tall Discord: Really_Tall

Posted: 8/7/2015 8:17 PM

Quote

Warepire

He/Him

Editor

Joined: 3/2/2010
Posts: 2178
Location: A little to the left of nowhere (Sweden)

http://tasvideos.org/Bizhawk/LuaFunctions.html Begin with changing the savestate calls. Instead of create, assign state1 to for example 1 (or any other number in the range 0-9) And instead of .save / .load, use .saveslot / .loadslot It should also be possible to give state1 a full path as a string, then .save / .load shall not be replaced. With this solution, ensure that you have the necessary rights to create files in that path. And as stuff breaks, keep making comparisons between the script, error message, and the Lua doc making corrections to the script. And before you know it, the script is ported.

Posted: 8/7/2015 9:22 PM

Quote

moozooh

Senior Moderator

Joined: 8/4/2005
Posts: 5783
Location: Away

I'd love to give it a try someday soon. (Man, I wish I could offload bruting on my GPU...)

Posted: 8/7/2015 10:17 PM

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

Several users wrote:

Update this script for BizHawk, plz?

Errr... wow. First of all, I'm sorry I missed the bump to this thread back in April. I was a little busy at the time and it must have slipped past me. But I'm supremely flattered that users remain interested in this script. I seriously had no idea that anyone cared at this point. I'll work on it in the near future, following Warepire's suggestions, and submit an official updated version. I may also take the time to consider further changes to the script, including making an iterator function, which I've never done in Lua. By the way, I recently thought about using this script on that Mario 64 glitch in Tick Tock Clock. It might be an easy way to collect the $1000 bounty. The problems are that I haven't touched the script in ages, I don't have the Mario 64 ROM, and the script isn't set up for N64 games. Even so, I thought I would throw that out there if anyone else would like to collect on the bounty.

Posted: 8/8/2015 6:25 AM

Quote

Really_Tall

She/Her

Editor, Player (222)

Joined: 9/29/2014
Posts: 123
Location: Scotland

Bobo the King wrote:

By the way, I recently thought about using this script on that Mario 64 glitch in Tick Tock Clock. It might be an easy way to collect the $1000 bounty. The problems are that I haven't touched the script in ages, I don't have the Mario 64 ROM, and the script isn't set up for N64 games. Even so, I thought I would throw that out there if anyone else would like to collect on the bounty.

Yeah, when I saw the bounty I remembered reading about this script, and thought it might to do the job.

YouTube: https://www.youtube.com/Really_Tall Twitter: https://twitter.com/Really_Tall Discord: Really_Tall

Posted: 8/9/2015 6:43 PM

Quote

CoolKirby

Editor, Experienced player (530)

Joined: 11/8/2010
Posts: 4056

Bobo the King wrote:

But I'm supremely flattered that users remain interested in this script. I seriously had no idea that anyone cared at this point.

I meant to post this a few days ago, but I wanted to chime in and say thank you so much for the script! I've found it highly useful in optimizing an NES TAS I'm working on. In one instance of 2221 iterations (less than a half hour!) of aiming for a certain value, it did 6 frames better than I could do by hand. I hope to be able to use this for future projects too (especially once the BizHawk port is out).

Posted: 8/10/2015 8:02 AM
(Edited: 8/10/2015 8:16 AM)

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

Here is an updated version of my script. I've tested it in both FCEUX and BizHawk and it remains compatible in both. I'm concerned that it's rather bloated and inefficient. I can actually think of one glaring inefficiency. It should create savestates at intermediate points to cut down on execution time. For example, there's no need to re-execute all of the button-presses from the start if nothing has changed in the first frames. I know more or less how to fix this, but I'm a bit burned out at the moment. Anyway, enjoy! Download bruteforce.lua

Language: lua
-- * * * PARAMETERS * * *
-- By default, ThisAddress just returns the value of a single address.  However, you can have it return any function of any number of addresses.
local function ThisAddress()
	return memory.readbyte()
end

IWant=ThisAddress
ToBe=''  --{'minimized','maximized','equal to','less than','greater than','at least','at most'}
-- If ToBe in {'minimized','maximized'}...
  AndTheBestIveDoneIs=
  InThisManyFrames=
-- Elseif ToBe in {'equal to','less than','greater than','at least','at most'}
  ThisValue=
  AndTheFastestIveDoneItIs=--   frames

UsingTheseButtons={{}}

-- * * * FUNCTIONS * * *
local function tablecopy(t1)
	local t2={}
	if not(type(t1)=='table') then
		t2=t1
		return t2
	end
	for k,v in pairs(t1) do
		if type(v)=='table' then
			t2[k]=tablecopy(v)
		else
			t2[k]=v
		end
	end
	return t2
end

local function getframeadvancefunction()
	if FCEU or bizstring then
		return emu.frameadvance
	elseif gens then
		return gens.emulateframeinvisible
	else
		print("Unrecognized emulator.")
	end
end

local function jpset(player, buttons)
	if FCEU or gens then
		joypad.set(player, buttons)
	elseif bizstring then	-- BizHawk's joypad.set convention is "backwards".  WTF, BizHawk?
		joypad.set(buttons,player)
	else
		print("Unrecognized emulator.")
	end
end

-- Takes a character code (from a string) and returns true if it corresponds to a numeral.
local function isnumeral(charcode)
	return (charcode>=0x30 and charcode<=0x39)
end

-- Extracts the first number from a string.  For example, running this function on the string "event48blah19" will return 48.
local function getnumber(str)
	local numstart=nil
	local numend=nil
	for i=1,string.len(str) do
		if isnumeral(string.byte(str,i)) then
			if not(numstart) then
				numstart=i
				numend=numstart
				local j=i+1
				while isnumeral(string.byte(str,j)) do
					numend=j
					j=j+1
				end
			end
		end
	end
	if not(numstart) then
		error('No number found!')
	end
	
	local valuetext=string.sub(str,numstart,numend)
	local value = tonumber(valuetext)
	return value
end

-- Parses one of the bounds in an interval, returning the frame value.  You would run this function on, say, "(event2+10," to return index[2]+10+1.
-- It isn't necessary to type "event", "start", or "finish" in full, it just looks for the first match.  Watch out, though, because parsebound('[safe+2,') will return index[2]+2, not 2.
local function parsebound(str,index,maxframes)
	local value=-1
	if string.find(str,'e') then	--Bound defined relative to event.
		value=index[getnumber(str)]
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	elseif string.find(str,'f') then	--Bound defined relative to finish.
		value=maxframes
		local minus=string.find(str,'-')
		if minus then
			local minusthis=string.sub(str,minus)
			value=value+getnumber(minusthis)
		end
	elseif string.find(str,'s') then	--Bound defined relative to start.  Note that because of the elseif statement above, this won't be triggered by "finiSh".
		value=0
		local plus=string.find(str,'+')
		if plus then
			local plusthis=string.sub(str,plus)
			value=value+getnumber(plusthis)
		end
	else	--Bound defined by number.  "+" not allowed!
		value=getnumber(str)
	end
	if string.sub(str,1,1)=='(' then
		value=value+1
	end
	if string.sub(str,-1)==')' then
		value=value-1
	end
	return value
end

-- Parses interval notation into start and finish times.
local function parseinterval(UsingTheseButtons,index,depth,maxframes)
	interval = UsingTheseButtons[depth][4]
	if type(interval)=='number' then	--If interval is just a number, then low and high are both equal to that number.
		low=interval
		high=interval
	elseif string.sub(interval,1,1)=='[' or string.sub(interval,1,1)=='(' then	--The interval is explicitly defined in this case.
		local comma=string.find(interval,',')
		if not comma then
			error('Expected comma to define interval.')
		else
			local lowerbound=string.sub(interval,1,comma)
			local upperbound=string.sub(interval,comma)
			low=parsebound(lowerbound,index,maxframes)
			high=parsebound(upperbound,index,maxframes)
		end
	else	--If no interval is explicitly defined, then the interval is taken to be implicit and both low and high are set equal to the output of parsebound acting on interval in its entirety.
		low=parsebound(interval,index,maxframes)
		high=low
	end

	--This is a little forgiving to the user.  Perhaps their interval was defined improperly, such that the lower bound surpassed the upper bound.
	if high<low then
		high=low
	end
	return low,high
end

-- Compares IWant with Value according to function specified by ToBe
local function check(IWant,ToBe,Value)
	if not(Value) then return nil end
	if ToBe=='minimized' then
		return (IWant()<Value)
	elseif ToBe=='maximized' then
		return (IWant()>Value)
	elseif ToBe=='equal to' then
		return (IWant()==Value)
	elseif ToBe=='less than' then
		return (IWant()<Value)
	elseif ToBe=='greater than' then
		return (IWant()>Value)
	elseif ToBe=='at least' then
		return (IWant()>=Value)
	elseif ToBe=='at most' then
		return (IWant()<=Value)
	else
		error('Invalid string for ToBe.')
	end
end

-- IWant refers only to the current frame, which isn't useful when checking nodes with branches.  Therefore, this function directly compares an old value with a new value, based on ToBe.
local function check2(newvalue,ToBe,oldvalue)
	if not(newvalue) then return nil end
	if ToBe=='minimized' then
		return (newvalue<oldvalue)
	elseif ToBe=='maximized' then
		return (newvalue>oldvalue)
	elseif ToBe=='equal to' then
		return (newvalue==oldvalue)
	elseif ToBe=='less than' then
		return (newvalue<oldvalue)
	elseif ToBe=='greater than' then
		return (newvalue>oldvalue)
	elseif ToBe=='at least' then
		return (newvalue>=oldvalue)
	elseif ToBe=='at most' then
		return (newvalue<=oldvalue)
	else
		error('Invalid string for ToBe.')
	end
end

-- Executes the actual button presses and checks if it is superior to previous attempts.
-- The output of this function depends on the string in ToBe.  If the string is "minimized" or "maximized", it returns the value.  If the string is something else, it returns the number of frames.
-- If it doesn't beat the current record, the output is nil.
local function attempt(presses,IWant,ToBe,Value,maxframes,frameadvance)

	if ToBe=='maximized' or ToBe=='minimized' then
		for frame=0,#presses do
			for player=1,2 do
				--Edited for BizHawk support.  Try to come up with a solution for all emulators.
				jpset(player, presses[frame][player])
			end
			frameadvance()
		end
		if check(IWant,ToBe,Value) then
			return IWant()
		end
	else
		for frame=0,#presses do
			if frame<maxframes then
				if check(IWant,ToBe,Value) then
					return frame
				end
			end
			for player=1,2 do
				jpset(player, presses[frame][player])
			end
			frameadvance()
		end
	end
	return nil
end

-- Uses UsingTheseButtons and index to construct a table of button presses, then passes that table to the attempt function to execute them.
-- presses[frame][player][button].
local function pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
	local presses={}
	for frame=0,maxframes do
		presses[frame]={}
		for player=1,2 do	--Edit the number of players here.
			presses[frame][player]={}
		end
		for i=1,#index do
			if frame>=index[i] then
				local OnOrOff = (UsingTheseButtons[i][3]=='on')	--Set button if "on", reset otherwise.
				presses[frame][UsingTheseButtons[i][1]][UsingTheseButtons[i][2]]=OnOrOff
			end
		end
	end
	output=attempt(presses,IWant,ToBe,Value,maxframes,frameadvance)
	savestate.load(state)
	return presses,output
end

--
local function DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
	depth=depth+1
	local bestpresses,attemptframes,attemptValue,presses
	low,high=parseinterval(UsingTheseButtons,index,depth,maxframes)
	if depth==#UsingTheseButtons then
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
				if attemptValue then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=pressbuttons(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,state,frameadvance)
				if attemptframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	else
		for i=low,high do
			--if i>maxframes then return end	--Any input after maxframes is irrelevant and shouldn't be checked.
			index[depth]=i
			if ToBe=='minimized' or ToBe=='maximized' then
				presses,attemptValue=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
				if check2(attemptValue,ToBe,Value) then
					Value=attemptValue
					bestpresses=tablecopy(presses)
				end
			else
				presses,attemptframes=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state,frameadvance)
				if attemptframes<maxframes then
					maxframes=attemptframes
					bestpresses=tablecopy(presses)
				end
			end
		end
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		return bestpresses,Value
	else
		return bestpresses,maxframes
	end
end

-- * * * BASE CODE * * *
if ToBe == 'minimized' or ToBe == 'maximized' then
	Value=AndTheBestIveDoneIs
	maxframes=InThisManyFrames
else
	Value=ThisValue
	maxframes=AndTheFastestIveDoneItIs
end
frameadvance=getframeadvancefunction()
depth=0
index={}
if bizstring then
	state1="state1"
else
	state1=savestate.create()
end
savestate.save(state1)
presses,best=DepthFirstSearch(IWant,ToBe,Value,maxframes,UsingTheseButtons,index,depth,state1,frameadvance)
if presses then
	for frame=0,#presses do
		print('Frame: '..frame)
		for player=1,2 do
			print('Player ' .. player .. ' buttons: ',presses[frame][player])
			jpset(player, presses[frame][player])
		end
		frameadvance()
	end
	if ToBe=='minimized' or ToBe=='maximized' then
		print('Best value: ' .. best)
	else
		print('Fewest frames: ' .. best)
	end
else
	print('No improvement found!')
end
if FCEU or gens then
	emu.pause()
elseif bizstring then
	client.pause()
end

--This function works.  It will serve as a template for the final function.
--[=[
local function DFS(G,index,depth)
	depth=depth+1
	if G[depth][1] == 'abs' then
		low=G[depth][2]
		high=G[depth][3]
	elseif G[depth][1] == 'rel' then
		low=index[G[depth][2]] + G[depth][3]
		high=index[G[depth][2]] + G[depth][4]
	end
	if depth==#G then
		for i=low,high do
			index[depth]=i
			for j=1,#index do
				print(index[j])
			end
			print('Next!')
		end
	else
		for i=low,high do
			index[depth]=i
			DFS(G,index,depth)
		end
	end
end

G={{'abs',0,5},{'rel',1,6,16},{'rel',2,8,20}}
--G={{'abs',0,1},{'rel',1,10,11},{'rel',2,100,101}}
depth=0
index={}
DFS(G,index,depth)
]=]--

--[[
{{,,'[start,start+20]'},
 {,,'[event1,event1+5]'},
 {,,'[event2+10,event2+20]'}}
for i=0,20 do
	for j=i,i+5 do
		for k=j+10,j+20 do
		
		end
	end
end

index={}
function makeloops(events,index,depth)
	if depth==#events then
		for 
	else
		depth=depth+1
	end
end

Wikipedia pseudocode:
procedure DFS(G,v):
	label v as discovered
	for all edges from v to w in G.adjacentEdges(v) do
		if vertex w is not labeled as discovered then
			recursively call DFS(G,w)
]]--

--[[
UsingTheseButtons has elements with the structure
{player,button,'on'/'off',timing}
where timing is a string based solely on PREVIOUS events in the UsingTheseButtons vector as well as the start frame (0) and end frame (InThisManyFrames/AndTheFastestIveDoneItIs).  Examples of timing:
'[start,finish]'		-- Test all frames.
'[start,37]'			-- Test all frames from start to frame 37, inclusive.
'(start,37)'			-- Test all frames from start to frame 37, exclusive.
'[15,37]'				-- Any frame from 15 to 37, inclusive.
'[event 2,finish]'		-- Any frame after event 2 has begun, where event 2 is the second element of the UsingTheseButtons vector.  This can be used to force, for example, shooting only after jumping.
'[event 2+37,finish]'	-- No, that doesn't mean event 39.  It means wait at least 37 frames after event 2 has finished.
('[event 2-37,finish]')	-- I'm not sure I want to program this, since each event's timing is supposed to depend on PRIOR events.  It should always be possible to put them in order.

In total, the UsingTheseButtons table might look like this:
UsingTheseButtons={{1,'A','on','[start,finish]'},
				   {1,'A','off','(event 1, finish]'},
				   {1,'right','on','[37,60]'},
				   {1,'up','on','[event 3+2,event 3+2]'},
				   {1,'right','off','[40,finish]'}
				   }
				   
which means try pressing A on any frame, hold it for any interval (release A any time AFTER pressing it), hold right beginning sometime between frames 37 and 60, 
hold up beginning exactly 2 frames after holding right, and release right sometime between frame 40 and the end of input.  Up will be held until the end of input.

Later events override conflicting earlier events.  Generally, it's a good idea to define the timing of 'off' commands with respect to their earlier 'on' counterparts.
]]--

Posted: 8/10/2015 8:14 AM

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

Ask and ye shall receive!

CoolKirby wrote:

Bobo the King wrote:
But I'm supremely flattered that users remain interested in this script. I seriously had no idea that anyone cared at this point.
I meant to post this a few days ago, but I wanted to chime in and say thank you so much for the script! I've found it highly useful in optimizing an NES TAS I'm working on. In one instance of 2221 iterations (less than a half hour!) of aiming for a certain value, it did 6 frames better than I could do by hand. I hope to be able to use this for future projects too (especially once the BizHawk port is out).

Thanks, CoolKirby! I'm overjoyed to hear that at least one person has put this script to practical use. Let me know how the TAS goes in the long run.

Posted: 8/10/2015 11:56 PM

Quote

AntyMew

It/Its

Encoder, Player (35)

Joined: 10/22/2014
Posts: 425

Bobo the King wrote:

Download bruteforce.lua

Language: lua
local function getframeadvancefunction()
  if FCEU or bizstring then
    return emu.frameadvance
  elseif gens then
    return gens.emulateframeinvisible
  else
    print("Unrecognized emulator.")
  end
end

Desmume has emulateframeinvisible as well. Psxjin, FCEU(X), Snes9x, MAME, Mupen, Bizhawk, and possibly others have emu.speedmode (not to be confused with Bizhawk's client.speedmode). Using emu.speedmode("maximum") will cause frameadvance to act similarly to emulateframeinvisible.

Just a Mew! 〜 It/She ΘΔ 〜 ███████

Posted: 8/21/2015 10:48 AM

Quote

xy2_

Editor, Experienced player (870)

Joined: 5/2/2015
Posts: 696
Location: France

How would you go about making this script work with touchscreen inputs in DeSmuME?

Youtube

Posted: 8/21/2015 3:45 PM

Quote

AntyMew

It/Its

Encoder, Player (35)

Joined: 10/22/2014
Posts: 425

xy2_ wrote:

How would you go about making this script work with touchscreen inputs in DeSmuME?

My guess is, unless the script is heavily accommodated for a specific game by the TASer, the touchscreen would add an extra googol years or so to the search

Just a Mew! 〜 It/She ΘΔ 〜 ███████

Posted: 8/21/2015 4:25 PM

Quote

Bobo_the_King

Player (101)

Joined: 8/5/2007
Posts: 866

Anty-Lemon wrote:

Bobo the King wrote:
Download bruteforce.lua
Language: lua
local function getframeadvancefunction()
  if FCEU or bizstring then
    return emu.frameadvance
  elseif gens then
    return gens.emulateframeinvisible
  else
    print("Unrecognized emulator.")
  end
end
Desmume has emulateframeinvisible as well. Psxjin, FCEU(X), Snes9x, MAME, Mupen, Bizhawk, and possibly others have emu.speedmode (not to be confused with Bizhawk's client.speedmode). Using emu.speedmode("maximum") will cause frameadvance to act similarly to emulateframeinvisible.

Sorry it's taken me so long to reply. I've been busy, as usual. I wasn't able to incorporate emu.speedmode with Bizhawk. I think that function has been obsoleted. I was able to use client.speedmode, but could not set the speed any higher than I could otherwise-- it did not act like emulateframeinvisible. Am I missing something? I'll throw in emulateframeinvisible support for other emulators.

xy2_ wrote:

How would you go about making this script work with touchscreen inputs in DeSmuME?

Anty-Lemon is right. If you're talking about testing many different touchscreen inputs, the parameter space gets really frickin' huge. On the other hand, if all you want to do is touch a specific spot... well, it looks like my script can't do that yet. I'll get right on it. This script is useful when the buttons are reasonably well known and their timings is not (known space, unknown time). Based on your suggestion, I may drum up a script that tests touchscreen inputs when the timing is known but where to press is not (known time, unknown space). This would need to be a separate script because of the aforementioned problems with the parameter space ballooning out of control.

Posted: 8/21/2015 4:34 PM

Quote

Masterjun

He/Him

Site Developer, Expert player (2063)

Joined: 10/12/2010
Posts: 1185
Location: Germany

xy2_ wrote:

How would you go about making this script work with touchscreen inputs in DeSmuME?

Considering the touchscreen of DeSmuME is 256 x 193 pixels (yes 193, it ranges from 0 to 192, don't ask me why), which means 49408 possible input combinations, it's a bit worse than having 15 additional buttons to check for the script.

Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)

Posted: 8/21/2015 4:37 PM

Quote

xy2_

Editor, Experienced player (870)

Joined: 5/2/2015
Posts: 696
Location: France

Masterjun wrote:

xy2_ wrote:
How would you go about making this script work with touchscreen inputs in DeSmuME?
Considering the touchscreen of DeSmuME is 256 x 193 pixels (yes 193, it ranges from 0 to 192, don't ask me why), which means 49408 possible input combinations, it's a bit worse than having 15 additional buttons to check for the script.

With what I want to do, I'm only accounting for 256 'relevant' positions to be tried for each frame (on the same x pos.) Of course, trying to bruteforce on the entire touchscreen would be inhuman.

Youtube

Forum Tool-assisted laboratory Brute-force script for short, well-defined goals

Forum

Tool-assisted laboratory

Brute-force script for short, well-defined goals