If the security controls exist only on the client, you have no control over the security controls. That's an intractable problem that appears in all corners of security. If your security model presupposes that a device that the user owns will not be manipulated, then your security model is based upon an incorrect assumption.
You've mentioned a few approaches to making it more difficult, but none of them offer concrete protection because your game logic is completely in the control of a malicious user. This comes up in game cheating all the time, and the only concrete solution is a server authoritative model. In absolute terms, this means running the game logic on the server, not the client.
A fully server-authoritative system is not always feasible. Consider, for example, a first-person shooter game. If the server was responsible for the entire game, including rendering the images that the user sees, it would be unplayable due to latency issues. The first obvious concession is that the game must be rendered on the client-side, but this already opens up avenues for exploitation, such as wallhacking. The work involved with developing a secure game model lies primarily in coming up with a reasonable compromise between user experience, development cost, and security. What you'll likely arrive at is a combination of concrete controls, and compensating controls. The concrete controls enforce certain behaviours and capabilities absolutely, and the compensating controls make it harder to exploit the gaps in between.
You mentioned questions in one of your comments. This type of game mechanic is much more easily adaptable into a server-authoritative model. The game asks the server for a question, the player answers the question, and the answer is sent back to the server for verification. The answer never leaves the server, and the server has authority over whether or not the question was answered correctly, which makes it much harder to abuse. You can apply reasonable time limits on how long a user can take to answer the question, as well as rate limits to prevent obvious automation.
In games where the player moves about a space, e.g. a platformer or RPG, you can enforce that the game cannot progress beyond a certain stage without reaching certain milestones. The server can reject a game completion request if the client has not sent the prerequisite milestone notifications, and minimum timings can be enforced between each notification.
In more interactive game designs (e.g. MMOs or FPS) the server keeps track of player positions in realtime, and rejects actions that are not possible, such as changing position too quickly (speedhacking), interacting with an object that is too far away, or using currency or items that the player is not in possession of.
For turn-based games, such as chess or backgammon, it is possible to perform post-hoc validation of the game at its conclusion. This can be done even if the "AI" player's moves are computed on the client. The game client handles all of the game logic, but must record all of the player's moves and the ending state. If the AI's behaviour must appear to be random in some way, the server is responsible for sending a random seed to the client at the start of the game, which seeds a deterministic pseudorandom number generator. When the game is finished, the client sends the list of player moves and ending game state back to the server. The server then re-plays the entire game through and checks that each player move was valid and that the server arrives at the same ending state as the client provided. Since the same PRNG seed is used on both the client and server, the AI will make the same moves in both play-throughs. If the ending state fulfils the win condition for the game, and the moves/state were all correct, then the win is accepted.
More generic advice:
- Ensure that a completion notification is tied to a new game notification, and that the time between those requests is neither too short or too long. New game notifications should contain all the relevant parameters for that game (game type, difficulty level, etc.) and server-authoritiative parameters (e.g. the AI seed) should be tracked.
- Require that games with stages include stage completion notifications. Implement time restrictions on these.
- Where possible, make random decisions on the server rather than on the client. For example, if a player gets a random prize, decide that prize on the server rather than the client.
- Where you have deterministic games, get the client to record the sequence of moves and send them to the server. Hash the results and store this alongside the user profile. If the user then makes the exact same set of moves again over and over, the hashes will match up and you can identify that they are automating the game.
- Analyse your player behaviours, based on logs, and come up with a reasonable upper bound for the rate at which games are completed and scores are increased. Set up alerts when users exceed this bound. If you ban cheaters quickly, they're less likely to come back and less likely to form communities that make your life difficult.
