The second game, melee, definitely had a more traditional engine running it, too many ~bugs~ fantastic features to have been taking advantage of lookup tables.
Are you thinking of Super Smash Bros.? This is Super Mario Bros. for the NES, over a decade older :)
I actually wonder if a version of Smash Bros could have worked on NES with lookup tables for physics? The existing games are 3d but the physics are all 2d.
Yes I read super and bros and didn't read the middle.