What games have you played that don't feature randomness, exactly? Can you name a single one?
A great example is Diplomacy[0]. Instead of randomness, you have asymmetrical information, for which you have to use the same type of statistical reasoning. This is much more satisfying than randomness, because there is substance behind the veil.
There are 7 players, and each starts with 3 or 4 units. The outcome of an attack is determined entirely by numerical superiority. If you attack with more units than are defending, you win. However, because there are so many more players than units, and all orders for a turn are resolved at the same time, you don't know what's going to happen because you don't know what other players are going to do. Will your allies actually support your attacks, or will they backstab you and defend your opponent instead? People can make your attack or defense fail simply by not writing the order to support you, because you don't have enough units to do it alone. Therefore, the outcome is dominated by cooperation between players. You don't know what will happen only because you don't know who's lying.
And this gives you a way to overcome the "random" element by finding out who's really lying using... Diplomacy!
Mafia is another game that relies on asymmetrical information instead of randomness, if you forgive the fact that roles are randomly assigned. This is a less pure example, because there is some element of randomness. However, the information game is still more important, because the randomness is limited to setting up the board. Poker uses this kind of randomness, because once you shuffle the deck, the result of drawing a card is not random. Procedural generation is a mixed case, but I think it usually falls into this bucket as well.
In general, randomness is good when it is used to hide information, but it can become very frustrating when it is used to create information independent of any other causal structure. Randomness is bad when it destroys the narrative a player is forming about their experience. If the causal structure of your game is capable of hiding information without relying on randomness, like with Diplomacy, then you don't need any.
It does seem that if you remove randomness entirely, what you're left with is a game whose strategy revolves around information symmetry/asymmetry. Either it's a game where all the rules are known and players are on equal footing, or it's a game like Diplomacy where rules and game state are known initially but players can create information asymmetry to use to their advantage as the game progresses.
Chess is a good example of a game with perfect information for both sides. There's a variant of chess that was popular for training military officers in the 19th century called Kriegspiel that has Fog of War. It is played with 3 boards and a moderator. Each player has a board with only their pieces, and the moderator sees both sides. Players tell the moderator their move, who figures out the result. This is precisely the sort of thing for which we now use computers when playing strategy games of all kinds.
The fundamental principle of randomness, in a Bayesian sense, is that it represents a lack of information. There are two ways in which randomness can be used in games. It can be used to set up the initial conditions for the game, such as with procedural generation; or it can be used directly as part of the conflict resolution mechanism. When it is used in the latter sense, such as by having your success determined by die roll, it creates an illusion of hidden information, but it's hollow. In the case of a game like Kriegspiel or Diplomacy, there is an actual state that can be probed through clever gameplay, and probabilistic reasoning enhances your ability to do that. But when the state doesn't exist, and you model the result of missing information with a die roll, all you have to work with is the law of large numbers. When there is no hidden state about which to make inferences, it can make a game feel shallow.
Here's another example: Starcraft. If you are playing 1v1 on a 4 player map, there is some randomness in spawn positions, but ignoring that, the game is very deterministic. Units deal a specific amount of damage, pathfinding works a particular way, there's no randomness in chance to hit, or movement speed, or construction time. But there is a huge amount of hidden information because of Fog of War. At a high level of play, players may see very indirect hints of what the other player is doing, and by knowing how long it takes to build everything, they can figure out what the opponent is doing, with precision.
"If he has 8 marines at 3 minutes, he must have built early Barracks and he's not teching! I better prepare for an early attack." I don't remember the exact timings anymore but there are a lot of tells like this. A lot of the strategy of that game revolves around scouting and denying information, and making attacks at an ideal timing where the opponent has sunk the most resources into gaining an advantage (such as tech for more powerful units), but hasn't yet gained any benefit. I can't think of any randomness in Starcraft beyond the 4-position maps in 1v1, which players hate!
Instead, the main principles are hidden information, and dexterity. It is very difficult to control every unit precisely unless you have 400 actions per minute. Randomizing action resolution isn't important because it is physically impossible to play perfectly.
The topic at hand was how randomness is undesirable in video games.
> Chess is a good example of a game with perfect information for both sides.
If we're discussing perfect information with respect to Game Theory, Chess is a good example, though my favorite example is Tic-Tac-Toe because of how simple the ruleset is.
As for a 2x2 game with Fog of War and truly no randomness, I would suggest Advance Wars. Spawn locations on maps are always predictable, though a player can create hidden information by not deploying in every available spawn location.