What strategies could the server use to ensure that everyone is playing fairly,
Define unfair play: What would you consider unfair play of the following examples?
Your player is using some tool/modification to...
- help him aim and shoot at things (aim bot in a FPS)
- help with your characters skill rotation (in a RPG)
- predict/guess your opponents cards based on which cards he played (in a TCG)
- show you your opponents cooldowns and available attack moves (no genre in particular)
- give you access to normally unavailable functionality (e.g. flying or creative mode in Minecraft)
Some of these are blatantly unfair, but some (like the rotation helper) are really subtle. For example, a rotation helper might even improve the gaming experience for people with some impairment, but with some form of automated decision making it could make some boss fights trivial or allow "superhuman" reflexes in a PvP setting. Okay, rotation helpers are disallowed because of their abuse potential. Now, what about healer interfaces?
You could spend days discussing all the nuances of game altering modifications/tools and their in-game balance effects. But, there is a simple rule that is fair for everybody: Disallow any modification!
... and exclude modified clients?
This is the hard part, and so far, I know of no one who could reinforce this under all conditions. It is just too hard. (Basically, your server tries to be an interrogator in a turing test.)
The best approaches in your case (no client side anti-cheat program) are (in order of difficulty):
- verify that every client packet sent to the server contains valid values
- limiting what information is available to a client (e.g. positions of players that cannot currently be seen)
- try to detect patterns in a clients behavior
Yes, the first point should be obvious. But I think it warrants extra mention here, because it frequently gets skipped, either because of performance considerations, or because of some sort of blind trust into the client software ("Why yes, we are the only ones capable of communicating with our server." - No, you are not, especially not once someone reverse-engineered your network protocol).
The second one is also rather obvious, but can be tricky to get right in a latency tolerant fashion. Most game servers already use this in some way to save on bandwidth - but it can double as a way to make cheating more difficult.
That brings us to the last point: pattern recognition. While it is rather easy and feasible to do some easy detections this way ("that player wanted to go to those exact coordinates on X different occasions"), it can get quite hard and time consuming if the bot writers get smart about how their bots operate. To continue on the "exact coordinates" example: what prevents the bot writer to pick a coordinate in a specified area around that exact coordinate? Set a radius, add a call to
cos and suddenly you have a circle of points instead of a single coordinate. Now add varying radii on different coordinates (depending on terrain etc), and suddenly it gets a lot harder to match that pattern. (Yes, in this case it's still possible to detect that pattern - but if you additionally vary the paths a bit, you come very close to matching human behavior).
But for all this, please keep in mind that you are trying to run a game server - you have limited CPU time and memory, and, depending on your game, you normally have tight constraints regarding latency (and maybe bandwidth). Just because some operations are possible, it doesn't have to mean they are possible while running an efficient server under those constraints.
Of course, employing GMs to monitor players and identify bots will also help, but they (as humans) have limited uptime - and who monitors the monitors?
Also, you could design your game in a way that prohibits modifications from having any real influence, e.g. think about a game like go: All information is readily available to all players, and fast reflexes don't give you any advantage, so this basically makes the major cheats unavailable. On the other hand, since go is "that simple" (not really, but still), moves can be precomputed to some level which might swing the odds in someones favor.
Could the game even be considered libre software if the server did not allow modified clients to connect?
As said earlier, with enough sophistication, it gets nearly impossible to even detect a modified client. So how would you enforce this?
Some of the anti-cheat software is basically a rootkit (or something close to that): It tries to take the control over the client's computer. While this approach might prevent simple tinkering (e.g. by comparing checksums), it still has to communicate those results to some server. And if someone is able to hijack that communication, you're back to zero.
Note that all of this is oblivious on the fact that, in your case, the source code is freely available (it just sets the hurdle higher for closed source games). Also, as mentioned in the answer of @Todd Knarr, for some kinds of exploits, you don't even need to modify the executable itself - some configuration for the graphics card or a manipulated asset can be enough to allow for some simple cheating.
TL;DR: With enough sophistication, you cannot rely on any information sent by the client, and trying to match patterns will a) cost good amounts of server CPU time and b) increase in difficulty once the bot writers learn the limits of that pattern matching algorithm.