You don't specify the type of game, so I will lean heavily toward RPG/MMO games. But a lot of this can and does apply to FPS, Strategy, and Action games. The way big multiplayer game companies like Blizzard deal with this issue in their games is:
- Do all calculation and game actions server side, the client is just a dumb terminal and graphics engine. So if the players are using a different client, it really doesn't matter in game terms, they can't cheat the physics of the game.
- Checks for obvious bot programs/clients by looking for obvious computer actions like perfect repetition of click events and mouse movements.
- Checks for non-obvious bot programs/clients and alerts in-game moderators to the issue.
They then appear in game (if that's possible, for same games like Starcraft 2 it is not) or otherwise watch/talk to the player about their actions as a 'human check'. Or at least that's how it should be handled. Blizzard is pretty good about this but historically other MMO companies have not been.
Checking for non-obvious bots isn't easy, but a few basic rules to follow include
- Looking for players that, with only slight variation, are performing the same actions over and over again. This might be sitting at a resource node in an MMO and farming it when it respawns, or it might be running in circles between health/ammo packs in an FPS and never deviating from a specific path and always using the same gun. (Sub-optimal bots in FPSs are rare, but if your game has a ladder to climb where number of games is more important that the talent of the player like some modern FPSs have, bots become valuable again)
- Looking for players executing the same exact rush or strategy over and over in an RTS. There are certain build orders in Starcraft that can be nearly unbeatable when performed by a bot.
- Looking for players who have collected vast sums of resources and are now endlessly grinding out one item. This was a big problem in Ultima Online.
The problem is that the more popular your game is, and the more fruitful bots can be in reducing tedium in your game, the more likely people will be to both use and create these bots. And it is trivial to restrict mouse movement speed, add random humanistic variation to clicks, even have the bot make mistakes at a human rate, opening and closing parts of the menu, hitting the wrong button and then closing the window, switching between keyboard and mouse work like humans do to reduce hand fatigue. (you don't even realize you do it)
So the last step when someone or a bot is doing something repetitive for a very long time really has to be a human mod coming up to the player and talking to them. If they are there and respond with human answers, they are human. Typically the mods will ask the player to stop for a while, or follow them somewhere and perform some other actions, the hoops become more complex with time.
Of course, eventually someone will create a bot that is indistinguishable from a real person, passing the Turing test. And there are a lot of bot writers out there who aim to do just that.
I, myself, had a passing fascination with the idea when I first started programming and created useless bots for Ultima Online which would stand in town and imitate NPCs. The commands were super simple so they were easy to make, just key strokes to step in different directions, and watching the chat log for its own name and piping the messages to ALICE over via a web version of the AI. I don't remember which and it probably doesn't exist anymore.
Point is, you need to decide where to draw the line. If you can't afford an army of moderators to talk to people your system identifies as bots, you are probably better off letting the community mark people as bots, and then when enough do over time, kick the player for about an hour. Not ban, just kick. The real problem for most players is that bots hog resources that other human players could be using. If mobs are scarce, as was the issue with Ragnarok Online, then bots that roam about and clear whole areas of enemies while scooping up items (or not) are common, and they ruin the game for other people. So you can skirt the cost of admin armies that way.
Finally, you can also live with bots as a reality of your game space and encourage their use. This requires designing your game around the eventual and common use of bots, trainers and helper programs. I want to say there was an MMO that did this about 10 years ago, but I can't remember which one it was. It spelled the end of the game, because MMOs are grind heavy and it meant that 95% of the players we away from their keyboards at any given time and destroyed the community. If you go this route, be careful.