I don't think there is a meaningful distinction between board games and video games in terms of gameplay. Many board games have been turned into video games. Battletech and Warhammer have both tabletop and computer implementations. Civilization is just a complex board game. Diplomacy is more often played by email or through a web app than it is played tabletop, so it might as well be considered a video game. Magic: The Gathering has been turned into a video game as well, with microtransactions and matchmaking and everything you would expect. Hearthstone is a MtG clone that never even had a physical incarnation: it is nothing but a video game.

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.