Simple ways to protect your game:
- Duplicate your data: store some information twice and compare the copies. If they are different, something is going wrong. You don't have to do it per variable, you can also make CRC's on some big areas of memory (ex: on a struct that contains all player information).
- Encrypt your data before its written to memory (and unencrypt after reading). A simple xor could be effective. This will make finding the addresses of some interesting variables a LOT harder.
- Never declare sensitive data "static" (with a fixed memory address) but rather use pointers. If someone find the address of interesting variable, the address will change next time process is run, making it harder to create a trainer (but not impossible).
In some professional games (like GTA IV), the game is split in two parts:
- One main process for rendering, input and processing game logic, which is unprotected (like most games).
- Another process that keep sensitive data (ex: player health, money, weapons, ...). This process has several protections against cheating (memory regions are readonly, data is encryted and so on). It's not possible to modify these values directly by writing in them, but only by using a set of functions that the process provide. These functions are only available after you have been authenticated using a set of keys/challenges. I guess other sensitive stuff like load/save savegames is also done here.
I guess this has some costs. Every modification of game data require some interprocess communication and some other checks (instead of a single read/write to memory).
However, all protections can be defeated: someone could disassemble your game to figure out exactly where and how data is stored. Or even better, modify the .exe himself to directly remove the protections. Anyway, I think using what I described above will stop most cheaters.
EDIT:
If it's a Flash game, you can regularly send some game events to a server (eg: "+50 points at frame 41, lose one life at frame 1231"). Then analyze these events and some statistics (eg: total seconds the game was played, number of player actions (mouse moves, key presses)) and compare to the submitted score to see if it appears to be possible...