Maximum Q value for new state in Q-Learning never exists
Your problem is with how you have defined $s'$. 

The next state for an agent is not the state that the agent's action immediately puts the environment into. It is the state when it next takes an action. For some, more passive, environments, these are the same things. But for many environments they are not. For instance, a robot that is navigating a maze may take an action to move forward. The next state does not happen immediately at the point that it starts to take the action (when it would still be in the same position), but at a later time, after the action has been processed by the environment for a while (and the robot is in a new position), and the robot is ready to take another action.

So in your 2-player game example using regular Q learning, the next state $s'$ for P2 is not the state immediately after P2's move, but the state after P1 has also played its move in reaction. From P2's perspective, P1 is part of the environment and the situation is no different to having a stochastic environment.

Once you take this perspective on what $s'$ is, then Q learning will work as normal. 

However, you should note that optimal behaviour against a specific opponent - such as a random opponent - is not the same as optimal play in a game. There are other ways to apply Reinforcement Learning ideas to 2-player games. Some of them can use the same approach as above - e.g. train two agents, one for P1 and one for P2, with each treating the other as if it were part of the environment. Others use different ways of reversing the view of the agent so that it can play versus itself more directly - in those cases you can treat each player's immediate output as $s'$, but you need to modify the learning agent. A simple modification to Q learning is to alternate between taking $\text{max}_{a'}$ and $\text{min}_{a'}$ depending on whose turn you are evaluating (and assuming P1's goal is to maximise their score while P2's goal is to minimise P1's score - and by extension maximise their own score in any zero-sum game)