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).

Very interesting, but incredibly complex. I'm tempted to make a python implementation to play around with for better understanding.