To make it more fiendish, what if the gods / natives don't know about each other's TRUE/FALSE/RANDOM status (but they are excellent logicians, so they can intuit any information from answers to your previous questions).