The rules of the game are deterministic, but you may be going a step too far with that claim.
Is the game deterministic when your opponent is non-deterministic?
Is there an optimal move for any board state given that various opponents have varying strategies? What may be the best move against one opponent may not be the best move against another opponent.
The opponent's moves may be considered non-deterministic, but you can just assume the worst case for you, that is the best case for the opponent, which is the opponent will always play the best move too.
Therefore the best move cannot be determined by the current board state, as it cannot be determined in isolation from the opponents strategy.
In a perfect information zero sum game, we can theoretically draw a complete game tree, each terminal node ending with a win, loss, or draw. With a full understanding of the game tree we can make moves to minimize our opponent’s best move.