hidden state vs. nondeterminism in games

Complexity
In certain types of games like chess, go, and checkers, there's a clear definition of the game's complexity (wikipedia entry). It's a measure of the branchiness and depth of the choices-tree that the players are building and exploring. In games that aren't combinatorial (ie. without a completely-known game state by all players), does it make sense to talk about complexity in the same sense? With either nondeterminism or hidden state, what happens to the players' mental model of the game tree?

Hidden Information
It makes planning harder, because you need to account for all the possible outcomes that depend on things you don't know: imagine deterministic poker with a sorted deck. Hidden information only makes planning harder to a limit, because if you know nothing at all then you can't plan at all. It seems like having a fraction of your game state hidden maximizes depth (or at least the difficulty of planning). Why don't more classical games have hidden state? Is it because hiding cards is easy, but hiding pieces on a board is difficult? It's hard to think of how, physically, you'd play checkers-with-secrets with someone... without easy cheating, anyway.

Alternately, imagine known-state poker, with face-up cards only. Hidden information is slightly intertwined with nondeterminism, though, because in deterministic poker there are no secrets to keep - everyone knows what cards you have, even if they're face down. To have secrets in a deterministic game, you need to make your choices secret (like fog of war in a deterministic RTS).

Nondeterminism
There are lots of games that depend on randomness for a similar effect on planning to hidden state, ie. any game where you draw shuffled cards or roll dice. It makes planning harder, because you have to think of multiple potential outcomes independent of each of your decisions. Hidden information is exploitable by the player who's keeping the secret, and adds lots of meta-game depth like bluffing and information management. I'm really interested in games where information management plays a key role, like in RTS games with fog-of-war, where visibility or radar coverage comes at a cost, and so does keeping secrets ("I could defend my main base if I use my secret cache of tanks, but if he know about my secret tank-producing base, he'd attack it from the air..."). It's like betting strategies in poker - they matter mostly because they reveal information, and the tradeoff is money, you're paying for information.

Complexity in Design
Why does complexity matter to us? If you did make chess-with-secrets, would it be a deeper game? Even if it was theoretically harder to plan your moves, chess doesn't need more planning complexity - it already maxes out our abilities. Only trivially shallow games need to be given more planning complexity. Nobody plays Go on an enormous board, even though it would be incredibly deeper. (Even increasing a 19x19 board to 21x21 would have a huge impact on complexity, but nobody would say it makes the game more fun).

Even without caring about planning complexity, nondeterminism and hidden states add a lot to a game. The boundary between determinism and nondeterminism starts to get fuzzier with videogames, where you have analog input and reaction times matter... it only makes sense to talk about it with respect to the actual decisions the player makes about the game, not the nuts-and-bolts physical input and output. It's at this level where a little bit of planning complexity is nice - deciding whether to silently walk or loudly run in counterstrike, whether to hide behind a wall in bf2142 or have a better line of sight on your enemies, or deciding when to reveal your strategies in an RTS or take pains to keep secrets. I think in almost any case in multiplayer games where you can give the choices to the other players (instead of making it random), you should. Instead of playing their own private slot machines in parallel, players enjoy dealing with each others' choices. It adds a social dimension to dealing with unpredictable outcomes where people can scheme and plot, and that adds metagame feedback where people need to anticipate and predict others' strategies.

Even without multiple players, the big thing about randomness is training players about rewards, with the Diablo/WoW style loot drops and Skinner-box feedback. Everyone claims to hate it, but its been proven to be effective (lucrative ;) design. Randomness softens the impact of losses on the ego, and gives the occasional reward to bad players to keep them playing - we're suckers for it. Giving people the chance to gamble their valuable resources on longshots lights up some primitive part of our brains - it's innately fun, even if it's only slightly related to the rest of the game.