Where in Time is Carmen Sandiego TAS bot

local function guessandcheck(action,condition,framedelay,lowguess,highguess,executeaction)
    worstpossible=highguess
    local state2=savestate.create()
    local oldstate={}
    for i=1,#condition.adr do
        oldstate[i]=memory.readbyte(condition.adr[i])
    end
    local foundit=false
    savestate.save(state2)
    while not(foundit) do
        savestate.load(state2)
        guess=math.floor((highguess+lowguess)/2)
        for i=1,guess do
            emu.frameadvance()
        end
        for i=1,#action do
            joypad.set(1,action[i])
            emu.frameadvance()
        end
        for i=1,framedelay do
            emu.frameadvance()
        end
        if condition.fn(unpack(oldstate),unpack(condition)) then
            highguess=guess
        else
            lowguess=guess+1
        end
        foundit = (highguess==lowguess)
    end
    savestate.load(state2)
    for i=1,lowguess do
        emu.frameadvance()
    end
    if executeaction then
        for i=1,#action do
            joypad.set(1,action[i])
            emu.frameadvance()
        end
    end

    if highguess==worstpossible then
        print("BAD!")
    end

    --while not(condition["fn"](oldstate,unpack(condition))) do
    --  emu.frameadvance()
    --end
end


function table.copy(t)
  local t2 = {}
  for k,v in pairs(t) do
    t2[k] = v
  end
  return t2
end


--Copies tables of two dimensions.  There's probably a better way to do this...
function table.copy2(t)
  local t2 = {}
  for k,v in pairs(t) do
    t2[k]={}
    for k2,v2 in pairs(t[k]) do
      t2[k][k2] = v2
    end
  end
  return t2
end


local function idleframes(n)
    for i = 1,n do
        emu.frameadvance()
    end
end


--local function selectedsuspect(suspectnumber)
--  if memory.readbyte(0x6039)==suspectnumber then
--      return true
--  else
--      return false
--  end
--end


local function fastmove(targetselection)
    local currentselection=memory.readbyte(0x6E)
    local downpresses=(targetselection-currentselection)%10
    local uppresses=(currentselection-targetselection)%10
    if currentselection==targetselection then
        return {{}}
    elseif downpresses==math.min(downpresses, uppresses) then
        if downpresses==1 then
            return {{down=1}}
        else
            return {{down=1,right=1}}
        end
    else
        if uppresses==1 then
            return {{up=1}}
        else
            return {{up=1,left=1}}
        end
    end
end


--Used to quickly input suspect properties in the evidence window.  Does not work on sex (note the mod 5 command).
local function fastinput(targetproperty)
    local currentproperty=memory.readbyte(0x6034 + memory.readbyte(0x6E))
    local Apresses=(targetproperty-currentproperty)%5
    local Bpresses=(currentproperty-targetproperty)%5
    if currentproperty==targetproperty then
        return {{}}
    elseif Apresses==math.min(Apresses, Bpresses) then
        return {{A=1}}
    else
        return {{B=1}}
    end
end



local function propertychanged(oldproperty,action)
    if action[1]["A"] then
        if memory.readbyte(0x6034+memory.readbyte(0x6E))==(oldproperty+1)%5 then
            return true
        else
            return false
        end
    elseif action[1]["B"] then
        if memory.readbyte(0x6034+memory.readbyte(0x6E))==(oldproperty-1)%5 then
            return true
        else
            return false
        end
    else
        return false
    end
end


local function declareevidence(targetproperty)
    local action=fastinput(targetproperty)
    local infotype=0x6034+memory.readbyte(0x6E)
    local condition={fn=propertychanged, adr={infotype}, action}
    while not(memory.readbyte(infotype)==targetproperty) do
        guessandcheck(action,condition,2,0,6,true)
        emu.frameadvance()
    end
end

local function cursormoved(oldselection,action)
    local total=0
    for k,v in pairs(action[1]) do
        if k=="down" or k=="right" then
            total=total+1
        elseif k=="up" or k=="left" then
            total=total-1
        end
    end
    if memory.readbyte(0x6E)==(oldselection+total)%10 then
        return true
    else
        return false
    end
end


local function madeselection(blah,targetselection)
    if memory.readbyte(0x70)==targetselection then
        return true
    else
        return false
    end
end


local function movecursor(targetselection)
    while not(memory.readbyte(0x6E)==targetselection) do
        action=fastmove(targetselection)
        joypad.set(1,action[1])
        emu.frameadvance()
        emu.frameadvance()
    end
end


local function makeselection(targetselection)
    guessandcheck({{A=1}},{fn=madeselection,adr={},targetselection},2,0,4,true)
end


local function makeselectionfast()
    joypad.set(1,{A=1})
    emu.frameadvance()
    emu.frameadvance()
end


--Waits for beeps to finish and for control to be relinquished to player.  Unfortunately, 0x70=255 strictly AFTER control has been relinquished, so the script backtracks.
local function waitforcontrol(backtrackframes)
    local state2=savestate.create()
    savestate.save(state2)
    while not(memory.readbyte(0x70)==255) do
        emu.frameadvance()
    end

    if backtrackframes>0 then
        local howlong=movie.framecount()
        savestate.load(state2)
        --print(howlong-movie.framecount())
        while movie.framecount()<howlong-backtrackframes do
            emu.frameadvance()
        end
    end
end


local function waitforcursorwarp(whereto)
    if not whereto then
        while memory.readbyte(0x6F)>250 do
            emu.frameadvance()
        end
    else
        while not(memory.readbyte(0x6F)==whereto) do
            emu.frameadvance()
        end
    end
    emu.frameadvance()
end


local function suspectproperties(suspectnumber)
    --Fastest way to select characteristics:
    --Sex: Male, press A.  Female, press B.
    --Hair: Black, press A.  Blond, press A twice.  Brown, press B twice.  Red, press B.
    --Eyes: Blue, press A.  Brown, press A twice.  Gray, press B twice.  Hazel, press B.
    --Artist: Cassatt, press A.  Degas, press A twice.  Orozco, press B twice.  Van Gogh, press B.
    --Author: Dostoyevsky, press A.  Hugo, press A twice.  Kipling, press B twice.  Porter, press B.

    --Selections:
    --Sex: 6034 (0 none, 1 male, 2 female)
    --Hair: 6035 (0 none, 1 black, 2 blond, 3 brown, 4 red)
    --Eyes: 6036 (0 none, 1 blue, 2 brown, 3 gray, 4 hazel)
    --Artist: 6037 (0 none, 1 Cassatt, 2 Degas, 3 Orozco, 4 Van Gogh)
    --Author: 6038 (0 none, 1 Dostoyevsky, 2 Hugo, 3 Kipling, 4 Porter)
    --These values are preserved even if you exit the evidence menu.

    --Dossiers (star denotes optimal properties to set):
    --0) Carmen Sandiego.  Female, *black, brown, *Degas, Dostoyevsky.  (2,1,2,2,1)
    --1) Auntie Bellum.  Female, blonde, hazel, *Cassatt, *Porter.  (1,2,4,1,4)
    --2) Earl E. Bird.  Male, *red, *brown, Orozco, Kipling.  (1,4,2,3,3)
    --3) Justin Case.  Male, *black, *blue, Van Gogh, Hugo.  (1,1,1,3,2)
    --4) Molly Coddle.  Female, brown, *blue, *Degas, Hugo.  (2,3,1,2,2)
    --5) Lee and Bill Ding.  Male, *red, gray, *Degas, Kipling.  (1,4,3,2,3)
    --6) Ernest Endeavor.  Male, blond, *blue, Cassatt, *Dostoyevsky.  (1,2,1,1,1)
    --7) Lynn Gweeny.  Female, black, *gray, Van Gogh, *Dostoyevsky.  (2,1,3,4,1)
    --8) Russ T. Hinge.  Male, blond, hazel, *Cassatt, *Hugo.  (1,2,4,1,2)
    --9) Nosmo King.  Male, brown, *hazel, *Degas, Porter.  (1,3,4,2,4)
    --10) Rudy Lepay.  Male, *brown, gray, *Orozco, Porter.  (1,3,3,3,4)
    --11) Kari Meback.  Female, *brown, brown, *Van Gogh, Hugo.  (2,3,2,4,2)
    --12) Minnie Series.  Female, blonde, *blue, Cassatt, *Kipling.  (2,2,1,1,3)
    --13) Sybil Servant.  Female, *red, gray, Orozco, *Porter.  (2,4,3,3,4)
    --14) Sharon Sharalike.  Female, *red, *hazel, Orozco, Kipling.  (2,4,4,3,3)
    --15) Gene Yuss.  *Male, black, brown, *Van Gogh, *Dostoyevsky.  (1,1,2,4,1)
    evidence={  [0]={{1,1},{3,2}},  --0) Carmen Sandiego (fastest?)
            {{3,1},{4,4}},      --1) Auntie Bellum
            {{1,4},{2,2}},      --2) Earl E. Bird
            {{1,1},{2,1}},      --3) Justin Case
            {{2,1},{3,2}},      --4) Molly Coddle
            {{1,4},{3,2}},      --5) Lee and Bill Ding
            {{2,1},{4,1}},      --6) Ernest Endeavor
            {{2,3},{4,1}},      --7) Lynn Gweeny
            {{3,1},{4,2}},      --8) Russ T. Hinge
            {{2,4},{3,2}},      --9) Nosmo King
            {{1,3},{3,3}},      --10) Rudy Lepay
            {{1,3},{3,4}},      --11) Kari Meback
            {{2,1},{4,3}},      --12) Minnie Series
            {{1,4},{4,4}},      --13) Sybil Servant
            {{1,4},{2,4}},      --14) Sharon Sharalike
            {{0,1},{3,4},{4,1}}}    --15) Gene Yuss

    return evidence[suspectnumber]
end


local function inputallevidence()
    local suspect=memory.readbyte(0x6014)
    local evidence=suspectproperties(suspect)
    for i=1,#evidence do
        movecursor(evidence[i][1])
        declareevidence(evidence[i][2])
    end
    movecursor(5)
    makeselection(5)
end


local function getwarrant()
    movecursor(8)
    makeselectionfast()
    waitforcursorwarp()
    makeselection(0)
    waitforcontrol(0)
    inputallevidence()
    idleframes(480)
    waitforcontrol(0)
end


local function suspectlocation()
    local i=0
    while memory.readbyte(0x6017+i)<100 and i<14 do
        location=memory.readbyte(0x6017+i)
        i=i+1
    end
    return location
end


local function incommon(fromstart,fromend)
    local shared={}
    for i=0,47 do
        if fromstart[i] and fromend[i] then
            table.insert(shared,i)
        end
    end
    if #shared>0 then
        return shared
    else
        return false
    end
end


local function makegraph()
    local graph={}
    for i=0,47 do
        graph[i]={}
        for j=0,3 do
            graph[i][j]=memory.readbyte(0x62DA + 4*i + j)
        end
    end
    return graph
end


--Concatenates tables in a sensible way.  Only concatenates elements whose indices are consecutive integers starting with 1.
local function tableconcat(table1,table2)
    local output=table1
    for i=1,#table2 do
        table.insert(table1,table2[i])
    end
    return output
end


local function shortestpaths()
    local graph=makegraph()
    local initial=memory.readbyte(0x6017)
    local final=suspectlocation()

    local map={[0]={},{}}
    map[0][initial]={{}}
    map[1][final]={{}}
    local depth=0
    while not(incommon(map[0],map[1])) do
            for i=0,47 do
                if map[depth%2][i] and #map[depth%2][i][1]==math.floor(depth/2) then
                    for j=0,3 do
                        local destination=graph[i][j]
                        map[depth%2][destination]={}
                        local temp=table.copy2(map[depth%2][i])
                        for k=1,#temp do
                            table.insert(temp[k],#temp[k]*(1-depth%2)+1, destination*(1-depth%2)+i*(depth%2))
                            map[depth%2][destination][#map[depth%2][destination]+1]=table.copy(temp[k])
                            temp=table.copy2(map[depth%2][i])
                        end
                    end
                end
            end
        depth=depth+1
    end
    shared=incommon(map[0],map[1])
    local paths={}
    for i=1,#shared do
        for j=1,#map[0][shared[i]] do
            for k=1,#map[1][shared[i]] do
                paths[#paths+1]=tableconcat(map[0][shared[i]][j],map[1][shared[i]][k])
            end
        end
    end
    return paths
end


local function bytematches(blah,address,value)
    if memory.readbyte(address)==value then
        return true
    else
        return false
    end
end


local function nameentered()
    local firstletter=bytematches(1,0x62CA,221)
    local secondletter=bytematches(1,0x62CB,234)
    local thirdletter=bytematches(1,0x62CC,221)
    local fourthletter=bytematches(1,0x62CD,234)
    local pressedstart=bytematches(1,0x01F4,208)
    return firstletter and secondletter and thirdletter and fourthletter and pressedstart
end


local function enterbobo()
    local action={  {right=1,A=1},{},{down=1,left=1},{down=1,A=1},
            {},{right=1,up=1},{up=1,A=1},{},{left=1,down=1},
            {down=1,A=1},{},{up=1,left=1},{up=1,A=1}}
    guessandcheck(action,{fn=nameentered,adr={}},10,0,80,true)
end


local function fastcountdown()
    idleframes(14)
    for i=1,4 do
        guessandcheck({{A=1}},{fn=bytematches,adr={},0x450,130},5,0,4,true)
        idleframes(11)
    end
    guessandcheck({{A=1}},{fn=bytematches,adr={},0x349,201},5,0,60,true)
end


local function startgame()
    idleframes(160)
    guessandcheck({{A=1}},{fn=bytematches,adr={},0x1B,92},10,0,80,true)
    while emu.framecount()<464 do
        emu.frameadvance()
    end
    for i=1,2 do
        joypad.set(1,{A=1})
        emu.frameadvance()
    end
    --idleframes(200)
    --guessandcheck({{A=1},{A=1}},{fn=bytematches,adr={},0x1B,78},40,0,80,true)
    guessandcheck({{up=1}},{fn=bytematches,adr={},0x535,2},10,0,40,true)
    guessandcheck({{A=1}},{fn=bytematches,adr={},0x52,10},10,0,10,true)
    idleframes(200)
    guessandcheck({{left=1}},{fn=bytematches,adr={},0x536,92},10,0,60,true)
    guessandcheck({{A=1}},{fn=bytematches,adr={},0xC,1},10,0,10,true)
    enterbobo()
    guessandcheck({{A=1}},{fn=bytematches,adr={},0x1B,137},10,0,40,true)
    guessandcheck({{A=1}},{fn=bytematches,adr={},0xD,0},10,0,40,true)

    idleframes(122)
    waitforcontrol(0)
    for i=1,6 do
        makeselectionfast()
        waitforcontrol(0)
    end
    makeselectionfast()
    idleframes(20)
    fastcountdown()
    idleframes(20)
end


local function fastcapture(lazy)
    movecursor(7)
    makeselection(7)
    waitforcursorwarp()
    local capturesave=savestate.create()
    savestate.save(capturesave)
    local startframes=emu.framecount()
    local quickest=10000
    local perm={0,1,2}
    local bestperm={}
    if not(lazy) then
        for i=1,3 do
            for j=1,2 do
                while emu.framecount()-startframes<quickest do
                    local k=1
                    local gotem=false
                    while k<4 and not(gotem) do
                        movecursor(perm[k])
                        makeselection(perm[k])
                        if perm[k]==2 then
                            idleframes(160)
                        else
                            idleframes(60)
                        end
                        if memory.readbyte(0x603A)==238 then
                            gotem=true
                            if (emu.framecount()-startframes)<quickest then
                                bestperm={}
                                quickest=emu.framecount()-startframes
                                for m=1,k do
                                    bestperm[m]=perm[m]
                                end
                            end
                        else
                            waitforcursorwarp()
                            movecursor(7)
                            makeselection(7)
                            waitforcursorwarp()
                            k=k+1
                        end
                    end
                end
                savestate.load(capturesave)
                perm[1],perm[2]=perm[2],perm[1]
            end
            perm[1],perm[2],perm[3]=perm[2],perm[3],perm[1]
        end
    else
        bestperm={0,1,2}
    end
    savestate.load(capturesave)
    for i=1,#bestperm-1 do
        movecursor(bestperm[i])
        makeselection(bestperm[i])
        waitforcursorwarp()
        movecursor(7)
        makeselection(7)
        waitforcursorwarp()
    end
    movecursor(bestperm[#bestperm])
    makeselection(bestperm[#bestperm])
    waitforcursorwarp()
end


local function betweencases()
    for i=1,6 do
        makeselectionfast()
        waitforcontrol(0)
    end
    if memory.readbyte(0x6014)==0 then
        makeselectionfast()
        waitforcontrol(0)
        makeselectionfast()
        waitforcontrol(0)
    end
    makeselection(5)
    waitforcursorwarp(4)
    makeselectionfast()
    waitforcursorwarp()
    for i=1,6 do
        makeselectionfast()
        waitforcontrol(0)
    end
    makeselectionfast()
    idleframes(20)
    fastcountdown()
    idleframes(20)
end


local function solvecase(path,getwarrantwhen)
    waitforcursorwarp()
    if getwarrantwhen==0 then
        getwarrant()
    end
    for i=1,#path do
        movecursor(6)
        makeselectionfast()
        waitforcursorwarp()
        local enroute=false
        local j=0
        while not(enroute) and j<4 do
            if memory.readbyte(0x6000+j)==path[i] then
                movecursor(j)
                makeselection(j)
                waitforcursorwarp()
                enroute=true
            end
            j=j+1
        end
        if i==getwarrantwhen then
            getwarrant()
        end
    end
    fastcapture()
    betweencases()
end

--Breadth: how many of the best runs to keep.  Depth: how many levels to beat before evaluating the tree.
--tree[i]: runs to ith depth
--tree[i][j]: jth run
--tree[i][j][1]: savestate for jth run
--tree[i][j][2]: frames of jth run
local function bot(trunk,breadth,depth)
    local tree={{}}
    for i=1,#trunk[1] do
        tree[1][i]={}
        tree[1][i][1]=trunk[1][i][1]
        tree[1][i][2]=trunk[1][i][2]
    end
    for i=2,depth+1 do
        tree[i]={}
    end
    for i=1,depth do
        for j=1,#tree[i] do
            savestate.load(tree[i][j][1])
            paths=shortestpaths()
            for k=0,#paths do
                solvecase(paths[1],k)
                tree[i+1][#tree[i+1]+1]={}
                tree[i+1][#tree[i+1]][1]=savestate.create()
                savestate.save(tree[i+1][#tree[i+1]][1])
                newpaths=shortestpaths()
                tree[i+1][#tree[i+1]][2]=emu.framecount()+665*#newpaths[1]
                savestate.load(tree[i][j][1])
            end
        end
    end
    trunk={{}}
    worstbranch={0,0}
    for i=1,#tree[depth+1] do
        for j=1,#trunk[1] do
            if trunk[1][j][2]>worstbranch[2] then
                worstbranch={j,trunk[1][j][2]}
            end
        end
        if #trunk[1]<breadth then
            trunk[1][#trunk[1]+1]={}
            trunk[1][#trunk[1]][1]=tree[depth+1][i][1]  --Copies savestate
            trunk[1][#trunk[1]][2]=tree[depth+1][i][2]  --Copies estimated frame count
        else
            if tree[depth+1][i][2]<worstbranch[2] then
                trunk[1][worstbranch[1]][1]=tree[depth+1][i][1]
                trunk[1][worstbranch[1]][2]=tree[depth+1][i][2]
            end
        end
    end
    return trunk
end




local breadth=2
local depth=1
--startgame()
firstsave=savestate.create()
savestate.save(firstsave)
paths=shortestpaths()
trunk={{{firstsave,0}}}


for i=1,78 do
    trunk=bot(trunk,breadth,depth)
end


emu.pause()



--Interesting RAM addresses
---------------------------
--0070: Selection being loaded.  Use this to get instant feedback instead of waiting for the beeps to finish.
--04D7: Warrant suspect ID.
--01F9: In main menu?
--6025: # cases solved.
--6016: Rank.
--01ED, 0729, 603A, 6043, 6044: All seem to be consistent on the "suspect spotted" screen.  (603A and 6043 seem to be best.)
--006F: Cursor warp.  After some actions, the cursor will warp to a particular selection.  This address signifies where the cursor will warp to, but only on the frame immediately

prior to the warp.  Note that any cursor movements prior to the warp are negated by it.

--Other notes
-------------
--Checked shortest path and aborted game 100 times (with some accidental repeats...).  The statistics follow:
--3 games had a shortest path of 1
--13 games had a shortest path of 2
--51 games had a shortest path of 3
--33 games had a shortest path of 4

--The same test was repeated by "forcing" the RNGs (the RNGs were randomized via the math.random function).  The sample size was 1000.  This resulted in the following

distribution:
--94 games had a shortest path of 1
--307 games hada  shortest path of 2
--431 games had a shortest path of 3
--168 games had a shortest path of 4

--This seems to fairly strongly indicate that the game's PRNG and Lua's PRNG are not accurate simulations of each other.

--First test ("natural" RNGs) repeated except with 1000 iterations.  New distribution follows:
--76 games had a shortest path of 1
--154 games had a shortest path of 2
--469 games had a shortest path of 3
--301 games had a shortest path of 4