You have multiple questions going on, here.
The easy questions is, "What do I do about this huge move space?" One good answer is, tree search with board evaluation heuristics. The basic notion is that because the search space is too large to deal with directly, you search as far forward as you reasonably can and at the end of that you use your knowledge of the game itself to evaluate which leaves are best.
For instance, there's a rough rule in chess that pawns are worth 1, bishops and knights are worth 3, rooks are worth 5, and queens are worth 9, so at the end of your search process, you might use a board evaluation function that tallies up the sum of points for both sides and use that as an evaluation function. (Warning: That particular evaluation function is very crude. Good functions will depend on the position of the pieces, being in check, etc. Board evaluation functions are not trivial to figure out.)
The hard question is, "How do I deal with more than two players?" This is a very hard question. One way to deal with it is to assume that each player is out strictly to win the game, and adapt the search algorithm accordingly. This is not quite the same as assuming that all opposing players are cooperating and coordinating. I believe Russell and Norvig have a few pages devoted to the idea in AIMA in the chapter on adversarial search. What little AIMA has on the topic are only gestures in the direction of multi-player AI, though.
Multi-player-- which is to say, multi-agent-- AI is a vastly more difficult endeavor than just single-agent AI.