Could a game similar to the example do away with the randomness? If
so, how could that change the experience?
The way I see it is that randomness is used for what the player cannot directly control. In an action platformer, you can control the player to a very fine degree: make him dodge things, jump over traps, etc using your reflexes and hand-eye coordination. In a turn-based game, the control is very coarse. No player is going to deliberately click on a trap to walk into. So what the player cannot control anymore in such a case is replaced with the analogical coin toss or dice roll, and I actually think that's perfectly fine and great.
Normally I don't think a game has to be realistic or resemble life at all to be fun, but here I think there's something interesting to note. Life is full of surprises. It's not entirely predictable, and it'd probably be boring if it was. We don't know if that girl we're going to ask out is going to agree. We don't know if we'll be hired for that job. We don't know if that programming idea that seems so promising is going to pan out. There's an element of chance in everything we do, and I think that's what makes things so fun, so dangerous, so surprising, and interesting. It seems to me like things would become incredibly dull if we took out that element of chance to the point where we could start predicting and perfectly calculating the outcome of everything we do while the world stops and waits for us to make a move.
I read a blog from a designer before who was determined to create a perfectly deterministic (as in lacking random events) turn-based game, and I couldn't help but disagree to a great extent with his thoughts for these reasons. That said, he made a very solid turn-based strategy game, but it felt to me more like a puzzle game where you're just kind of figuring out the optimal play against perfectly predictable and repeatable patterns. It changed the way the game felt considerably from other games like it which used random events and it wasn't quite my cup of tea even though I usually love those types of games. It starts to feel like playing chess, and not against a human player, but against a very predictable AI which always makes the exact same moves.
And that can still provide this kind of puzzle challenge to figure out those patterns and how to exploit and beat the AI after seeing it repeatedly do the same things over and over, but it feels very different, and it's not like learning enemy patterns in an action game. Action games which start revealing very predictable patterns are very interesting to me and I like determinism in action games, but there you never quite get the exact same result since it's too hard to repeat everything in perfect timing at the precise millisecond when you're controlling things in realtime, and it still feels like the game is taxing your reflexes and hand-eye coordination even when you know its patterns. With a turn-based game, you start seeing the exact same results repeating very quickly when it's perfectly deterministic while allowing you to do the exact same things every turn at your leisure, and that feels very different to the point where I'm wishing there's a fast forward button when I'm seeing the exact same things happen while repeating my previous moves up to a point.
But I could see where he was coming from. He wanted to avoid the analogical: 7 damage, 3 damage, miss, miss, miss, 1 damage, 3 damage, miss, miss... boring and frustrating! And in those cases when the RNG is just used to determine how much damage you do ranging from 0 (miss) to some other number, it can get quite boring and frustrating. In those cases I think just: 8 damage, 8 damage, 8 damage, enemy dies is already more fun.
Yet I actually think the problem there is that it's not random enough. It's boring. Imagine instead that snake eyes results in the player fumbling while the enemy gets a free counterattack, while boxcars causes an instant decapitation, and yo-leven causes you to stun the enemy, and there's always a chance that a clumsy player could trip and lose his turn just in the process of moving. I think that's considerably more interesting. It's not just outputting a number anymore. It's kind of like drawing a random card and reading what happens as a result.
I think this is what made games like Fallout really fun (or at least to me). A whole lot of different things could happen just by trying to shoot an enemy in the arm from glancing off and barely causing damage to making him drop his weapon to crippling him to the point where he can't use that arm or even blowing his entire arm off and killing him with a really lucky shot. That's interesting and really fun in ways that go beyond: miss, 2 damage, miss, miss, 7 damage, miss, 3 damage, miss, 1 damage...
So anyway, in my opinion turn-based games shouldn't be trying so hard to do away with randomness. I would prefer that more embrace and utilize it in more interesting ways than miss here and N damage there. If they do move away from randomness, then it does tend to change how the game feels considerably not that it's necessarily bad, but I would say it tends to push the game towards that kind of puzzle realm of gaming.