I have been thinking about a game which would have an AI, and the AI would ideally do extensive calculations thinking many turns in advance. I am curious if there is some way to put most of the burden of the AI calculations on the client while still preventing cheating. Obviously some processing has to be done on the server, but is there a way to find some happy middle?
You are right that when a client does the AI calculations for its own player, it's an invitation for cheating. But what you could do, is make each client do the AI computations for randomly chosen other players.
Players could then still screw with the games of others, but as long as the computation tasks are sufficiently anonymized, there would be no incentive for them to do so. Should this still be a problem, you could send each computation task to three different random clients, and kick the one which returns a result different from the two others. That way a cheater needs at least two clients which cooperate AND be lucky enough that the server randomly assigns them the same computation task which ALSO happens to be worth manipulating.