Post subject: Yoshi's Cookie
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
Honestly, I'm not sure if these forums has to be about specifically TASing the game or if I can simply plunk down a lua bot, but in any case, someone (t3h Icy?) on IRC wanted to create a LuaBot for this game. I got interested in creating my own bot due to that, and here's the result: .fm2 of me getting wiped by my own creation. As for the bot itself... Nothing extravagant. The idea is that we find which cookie appears the most, find a line which has the most of them, then move cookies into place. Said idea was mentioned in IRC... No attempt was made at checking to see if lining up those special cookies would end up smacking oneself with a -7 or panic. Also, No attempt was made at making more than one line at once. Could also be cleaned up a bit...
local grid= {{},{},{},{},{}}

local C_Count= {}
local C_Row=    {}
local C_Column= {}
local Ri,Ci,tx,ty,cx,cy,Type,ToX,ToY


--*****
function count()
--*****
-- Everything's fine if it returns false.

-- (re-)initialize arrays
    for i= 1, 5 do
        C_Count[i]= 0
        C_Row[i]= 0
        C_Column[i]= 0
    end
    C_Count[6]= 0

    for x=1,5 do
        for y=1,5 do
            grid[x][y] = memory.readbyte(0x026A + 0x02*x + 0x14*y)/2 -7
            if grid[x][y] > 6  or  grid[x][y] < 1  or  grid[x][y] ~= math.floor(grid[x][y]) then
                return true  -- Error: Unusual value
            end
            C_Count[grid[x][y]]= C_Count[grid[x][y]]+1
        end
    end
    return false
end

--*****
function CursorGoTo(TargetX,TargetY)
--*****
-- Eats 0 to 4 frames to reach destination
    local zx = memory.readbyte(0x03E5); zx = (zx+ 2)/ 2
    local zy = memory.readbyte(0x03E4); zy = (zy+ 2)/ 2
    local up,dn,lf,rt= {},{},{},{}
    up["up"]= true; dn["down"]= true; lf["left"]= true; rt["right"]= true

    zx= (zx-TargetX+2)%5-2  -- range of output is -2 ~ +2
    zy= (zy-TargetY+2)%5-2

    if zy == -2 or zy == 2 then
        if zy == 2 then
            joypad.set(2,up)
            zy= zy-1
        else
            joypad.set(2,dn)
            zy= zy+1
        end
        FCEU.frameadvance()
        if zx == 0 then
            FCEU.frameadvance() -- Idle, holding the button won't help.
        end
    end

    if zx ~= 0 then
        if zx > 0 then
            joypad.set(2,lf)
            zx= zx-1
        else
            joypad.set(2,rt)
            zx= zx+1
        end
        FCEU.frameadvance()
        if zy == 0 and zx ~= 0 then
            FCEU.frameadvance() -- Idle, holding the button won't help.
        end
    end

    if zy ~= 0 then
        if zy > 0 then
            joypad.set(2,up)
        else
            joypad.set(2,dn)
        end
        FCEU.frameadvance()
    end
    if zx ~= 0 then
        if zx > 0 then
            joypad.set(2,lf)
        else
            joypad.set(2,rt)
        end
        FCEU.frameadvance()
    end
end

--*****
function MoveCookie(dir)
--*****
local pad= {}

    pad["A"]= true
    pad[dir]= true
    joypad.set(2,pad)
    for i= 1, 8 do
        FCEU.frameadvance()
    end
end

gui.register(DispCookieVal)
FCEU.pause()
--*****
while true do

    local Dot= 0
    while count() do    -- grid[][] and CookieCount[] are refreshed
        Dot= (Dot+1)%30
        gui.drawbox(10+Dot,10,11+Dot,11,"green")  -- Gogo dancing dot!
        FCEU.frameadvance() -- If something's wrong, do not act.
    end
    gui.drawpixel(0,10,"clear") -- For some reason, the gui "sticks"...

-- Find the greatest cookie count
    Type= 1
    for i= 2, 6 do
        if C_Count[i] > C_Count[Type] then
            Type= i
        end
    end

-- Count up the right cookies in rows/columns
    for x=1,5 do
        for y=1,5 do
            if grid[x][y] == Type then
                C_Row[y]= C_Row[y]+1
                C_Column[x]= C_Column[x]+1
            end
        end
    end

-- Compare rows and columns
    Ri, Ci= 1, 1
    for i=2,5 do
        if C_Row[i] > C_Row[Ri] then
            Ri= i
        end
        if C_Column[i] > C_Column[Ci] then
            Ci= i
        end
    end
    local Var= "Row"
    if C_Column[Ci] > C_Row[Ri] then
        Var= "Column"
    end

-- Find a spot where we need to put a cookie!
    FCEU.frameadvance()
    tx,ty= 0,0
    for i= 1, 5 do
        local x,y= Ci, Ri
        if Var == "Row" then
            x= i
        else
            y= i
        end
        if grid[x][y] ~= Type then
            tx, ty= x, y
            break
        end
    end

   if tx ~= 0 then -- Did not find a target location? Stop now.
-- Find a cookie to move to the spot!
    cx,cy= 0,0
    local SmarTarg= { 0, 1,-1, 2,-2} -- What direction should we scan?
    for x=1, 5 do
        local found= false
        for y=1, 5 do
            local Xx= ((tx+SmarTarg[x]-1)%5)+1
            local Yy= ((ty+SmarTarg[y]-1)%5)+1
            if (Var=="Row" and y==1) or (Var=="Column" and x==1) then
                -- Uh, sir... We're looking at our own target line...
            elseif grid[Xx][Yy] == Type then
                found= true
                cx,cy= Xx,Yy
                break
            end
        end
        if found then break  end
    end

-- Move cursor to target location
    ToX,ToY= 0,0
    if Var == "Row" then
        ToX,ToY= tx,cy
    else
        ToX,ToY= cx,ty
    end
    CursorGoTo(ToX,ToY)

    if Var == "Row" then
        while (tx ~= cx) do
            if (tx-cx+2)%5-2 < 0 then
                MoveCookie("left")
                cx= (cx-2)%5 +1
            else
                MoveCookie("right")
                cx= (cx  )%5 +1
            end
        end
    end
    while (ty ~= cy) do
        if (ty-cy+2)%5-2 < 0 then
            MoveCookie("up")
            cy= (cy-2)%5 +1
        else
            MoveCookie("down")
            cy= (cy  )%5 +1
        end
    end
    while (tx ~= cx) do           -- If it's column, we didn't move x yet
        if (tx-cx+2)%5-2 < 0 then -- If it's row, we're already there
            MoveCookie("left")
            cx= (cx-2)%5 +1
        else
            MoveCookie("right")
            cx= (cx  )%5 +1
        end
    end
   end
end
Former player
Joined: 8/31/2009
Posts: 236
Yeah it was me working on it. It works, I think it's equal in speed as yours, but mine is a fat mess of code, since it was my first major Lua. Nice job on it! I think having the bot do doubles might be possible without much difficulty since it will always be opposite in direction (horizontal/vertical), and it could be triggered once there is four in a row/column and then create another that "runs" into the first row/column. I'm not really interested in doing that bit, but maybe if someone wants to expand on it.
Joined: 8/23/2009
Posts: 2
I think this is a very interesting idea. TASing a game is in a sense a mathematical problem: you are seeking to minimize the number frames it takes to put the games internal state into one most people consider "finished", even if the way people often approach this problem is to do it by hand. I'm wondering there could be provably optimal strategies for winning a game like yoshi's cookie, or if it has enough gameplay depth that finding such a strategy would be unlikely. Have you figured out how new cookie creation works? Is it something you would be able to manipulate with button presses?
Former player
Joined: 8/31/2009
Posts: 236
Creating a bot that could press buttons to manipulate which cookies it gets.... That would be the most amazing thing....
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
Hmm... How about a bot that will be a challenge even for a TASer to win against? THAT would be quite the accomplishment, no? A TASer will use frame advance, save states, and any possible errors in the bot itself. Theoretically, a TASer can save and load states repeatedly in order to kill my current bot. Make a single match so the timers don't expire simultaneously, then just abuse the exploit that my bot is simply no good against state saves. And of course, luck manipulation. It's likely possible one can change what cookies will show up, so all one needs to do is read what the game does with the RNG. Okay, this would be tricky... Even trickier would be to find a reason to delay a few frames for a more optimal cookie placement. Something deviously tricky would be, if you can manipulate the enemy's cookies, do so to minimize their ability to match cookies quickly. And of course, planning. Should the bot clear lines as fast as possible? Or maybe get Yoshi cookies and use 'em when luck says so. Something that can beat a TASer who doesn't take decent time optimizing their strats. I shall tell you that I will make an attempt at creating such a bot. I may or may not finish, but it will be attempted anyway. I've thought of a new design I could use which won't leave the bot as vulnerable to save states, and make it easier to change the bot. If I do manage, against all odds, finish the bot, or a decent prototype, I'll let you know.
Former player
Joined: 8/31/2009
Posts: 236
Make haste young warrior!
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
Well, I'm far from completing the bot, but I can already come to one conclusion: It is possible to permanently disable your opponent. Here's the list of evidence that suggests the possibility of a permanent disable: - The SLAVE power lasts 420 frames - Powers refresh every 300 frames - Powers always alternate between targeting 1P or 2P - It is possible to manipulate what power you get - 5 Yoshi cookies are generated when you clear two normal lines at once - It will take a rather short time to set up two normal lines to clear at once So basically, once you fire off a SLAVE at the opponent, the game will refresh a new power targeting you. But, by waiting 300 frames, a new power will take its place, targeting your opponent once again. Since SLAVE lasts 420 frames, you still have 120 frames where the opponent can't act. During which, you could match up more Yoshi cookies and re-apply a SLAVE, giving you another 420 frames of relentless control. But what are the chances of another SLAVE showing up, you ask? Why, this is a TAS-level bot we're talking about. This is one that will actively manipulate luck in order to force SLAVE to show up every time. And how does one manipulate the powers? Change the RNG. All it will take is studying how the RNG works for a little bit, and then do it. My current bot on display here takes an average of approximately 120 frames to match up one line. It is not optimal. Double-lines shouldn't take much longer to make, if at all, giving you 5 Yoshi cookies to use well before the 420 frames are up. Even if you mysteriously have 3 each of 4 types of cookies and the rest is the fifth type, you have time to make a junk match to help set up a double-match. But the whole thing hinges on luck manipulation. To what extent can we manipulate the luck? Cursor movements alone certainly isn't enough. I'll just have to search harder. But I did change what power shows up by doing different stuff. So basically, SLAVE-lock your opponent by manipulating luck and making double-matches. Just make sure you don't accidentally match a line in the opponent's grid, or you'll break the SLAVE effect. I now want to create a movie that demonstrates this. See if it really is possible. If it is, this would be the "unbeatable" strategy to follow under TAS conditions. Basically, whoever can SLAVE the other first wins.
Former player
Joined: 8/31/2009
Posts: 236
That really is awesome!
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
Here's an example of locking a player out until you win. Both players are done by me, no bots. While TASing that up, I believe there is still a defense against SLAVE. Basically, match up some cookies at the right time. Get some cookies started and match 'em right as SLAVE is getting applied to you. When an opponent ends up making you match something, it breaks you out of SLAVE, but if you get a match going, I believe it is possible to trick the game into allowing you to break SLAVE. In any case, I want to show off some more quirks in a 2-player match. I'm actually thinking about submitting a movie with a couple of TASed players beating each other up. SNES version would likely be preferable, as you can actually see the cookies moving smoothly and things might make sense, but NES is so much easier as I can use my multitrack script. Ease isn't a good excuse for a good movie, though. After all, even without an objective goal like "fastest time" or "maximum score", one can still create entertainment. There's a few good published videos where speed isn't a goal. Lastly, I may well have given up on that bot. I'm having troubles messing around with the RNG... I believe the RNG changes only when the game needs a random number, such as determining cookies or a new power, but it still eludes me.
MediaMagnet
He/Him
Moderator
Joined: 8/15/2016
Posts: 27
Location: Austin TX
Hello there, So I've been playing around with Yoshi's Cookie using the Japanese version of the game mostly as a learning experience, my goal is to clear all of stage 10 using just the cookies given to you at the beginning of the level itself after watching a video of someone doing that on YouTube it sounded like a fun challenge and not something I've been able to do as well I don't have the time to analyze the screen before overfilling the field. After that I want to jump to level 99 and repeat the process as much as I can as it adds a Koopa shell that can only be cleared with a Yoshi Cookie. Also the gravity of the cookies falling in is much faster giving me less time to sort the cookies. I feel like I’ve already got stage 10 down itself. As far as I can tell it is slower to clear the screen at once than clearing a row or column on its own. But it looks cool having all the cookies leave one after the other. Any input one can offer would be much appreciated.
"Do not meddle in the affairs of Dragons, for you are crunchy and taste good with ketchup!"
MediaMagnet
He/Him
Moderator
Joined: 8/15/2016
Posts: 27
Location: Austin TX
Here are some of the useful addresses I've found Thanks to Invariel and Scum for pointing me in the right direction with finding a few of these. $040B Round number $040C Stage number $00A1 Speed (1=low 2=medium 3=high 4="T") the T speed I found it in the debug menu as best I can tell it only triggers the cookies falling when you press B instead of just speeding them up. $0310-$031C Next row of cookies $032A-$0343 Next column of cookies $03C8 cycles through values when moving 112 when "A" is pressed $0490 Speed up next cookies 64 when held The cookie that drops into the corner is counted with the column of cookies each cookie has a value for its upper right and upper left Values: Heart: 32 & 33 Flower: 34 & 35 Diamond: 36 & 37 Square: 38 & 39 Doughnut 40 & 41 edit note: goofed some of the addresses up and added note about corner cookie
"Do not meddle in the affairs of Dragons, for you are crunchy and taste good with ketchup!"