Thank you: this is exactly the game I was looking for in the list, but forgot the name. It, too, was my first introduction to Moai as a kid.

Those Moai were the worst.. luckily there was up, up, down, down, left, right, left, right, B, A