CANT GET ANY IDEAS ... D:
The game necessarily itself doesn't need to lie. I'd like to think that the characters in the game can lie to the main character. Like "Oh, you're a frog? You used to be a handsome prince. If you get a princess to kiss you, you'll turn back into a prince!" And it turns out, you're just a normal frog
Okay... I would call it "Book of Lies" or something. You have a platformer which basically plays itself. Your job is to replace one type of object with another type by placing them on both open sites on the book, in a way that the AI can reach the end. When it's written down the page turns. So you can't revert it and you can place a new "lie". When you are finished with the level, the book reveals that it tricked you. It showed you a mirror world. In the actual world the guys who were trying to get through the level could have reached the end easily. Due to you changing stuff they all died. (Edit: So, you change both worlds with every spell/lie)
The book sucks you into the game and you have to finish the actual world by yourself.
Edit: So, the challenge is (as soon as you know it) create a mirror world, that the AI can beat, but make sure that the actual world is still beatable.