What is strategy?

Sid Meier famously defined a good game as a series of interesting choices. What makes a choice interesting?

The human brain has the faculty for logical reasoning. It also has the ability to make decisions that cannot be made through logic - because they are too complex, because not all the relevant factors are explicitly known, because the the matter being decided is not logical. But it's honestly kind of terrible at it. We don't reliably make good decisions in life.

Strategy games can make use of this human faculty for irrational decision-making, and train it to do better. A game lasts for a short duration; by the end of the game the outcome of your decisions can be evaluated. In real life, the ramifications of a decision can take years to become apparent. Repeatedly applying a skill with prompt feedback on performance is an effective way to get better at it.

The game Mafia is a good example here. Playing it you learn to ignore the subjective biases that can affect your decisions but are irrelevant in the context of the game - e.g. whether someone is a persuasive speaker, attractive, or a personal friend. And if someone has a reasonable argument but everyone seems against them - well, remember that some players have a vested interest in opposing reasonable arguments, and pay attention. (Analogies to politics are easily made.)

Obviously games can also exercise logical reasoning, but this isn't so interesting to me. I find mathematics, science, philosophy, programming much more effective ways to practise logical thought, but playing games the most effective way to practise making decisions that are too complex to be decided through logical thought.

Additionally, the reasoning you can apply to games usually isn't very deep; it's just reduction to cases. The game of OX is easily solved; until you do it's possible to enjoy playing it, but as soon as you start mapping out all possible moves, it doesn't take much thought to realise that either player can always force a draw.
In any game of this form, the approach of "compute all possible moves" is applicable. In principle, you can just completely work out every response to every possible move. This formulation is sometimes used in the mathematical study of games - rather than a sequence of moves, games can be treated as having a single move where each player specifies their entire strategy at the start of the game. If a game can be reduced to a single move, why play at all?
In practise, of course, you usually can't do this. Checkers has been solved, but this took years of computation. More complex games cannot be expected to be completely solved. But even though you can't map them out to the end of the game, you can still look a few moves ahead and evaluate whether you'll end up in a better position. This is often the best way to play, and it's really really boring.
(Still, it's a very elegant way to implement hidden information in a game - instead of having it concealed on cards in your hand, it's buried right in plain sight behind an unreasonable amount of computation. Encrypted.)

So I'd define an interesting strategic choice as being one that demands more than logical decision making. As a game maker, the question that concerns me is: how can we make games where logic and computation cannot be usefully applied, so that the capacity for unconscious decision-making is exercised?

Certainly in Chess you could choose not to go through the computations of "what are my possible moves if I do this and then he does this?" and instead try to make an unconscious decision. But then you're explicitly suppressing reason where it is applicable, and this is a really bad habit to get into. I'd strongly prefer people to do this quite a bit less. If you're in a situation where it's possible for you to work out the right answer, work it out!

Randomness can help a little, but mostly it just means that working out the optimal strategy will involve some probability calculations. You choose the move that has the greatest chance of success. Still, randomness is useful in conjunction with other tools for making decisions interesting, and can greatly increase the variety of situations that you need to think about - Chess openings are well understood, but if the initial position is shuffled this knowledge becomes useless.

Simultaneous or hidden actions can help too. But again they don't cut it on their own - Rock Paper Scissors is the classic example of a game with simultaneous actions and no deep decision-making. RPS - and more generally, many games with simultaneous actions - can be mathematically solved, and the optimal solution is of the form "choose randomly between these moves with these probabilities".

Playing with more than two players can help. But mathematical analysis of games with more than two players can usually reduce the situation to two teams; from a reductionist viewpoint all other players are aligned against the leader. This can lead to terrible games, where being ahead is a disadvantage because it makes you a target, and anyone who approaches winning is consistently attacked and brought back down. But this relies on perfect information; with enough concealment players can be uncertain about who their interests are currently aligned with. Still, this mostly degenerates into the politicking of trying to convince everyone that someone else is in the lead; fun for a while but ultimately fairly limited.
The curious thing about this to me is how much it depends just on the number of players, and not on the specifics of the game system. If there's any way of choosing to target another player, whether explicitly or not, you see the same dynamics playing out again and again. The simple numerics of one-against-many work out much the same in any system. It's possible to get away from it, but takes a legitimate effort.

Adding time pressure helps a lot. David Sirlin talks about this here, under "GDC Microtalks 2012". When you have limited time, you can't do the computations, you have to rely on your unconscious ability to make complex decisions. This applies best to real-time games, but in turn-based games too you can place a time-limit on turns. Chess is way better with a hard time-limit on turns than a soft limit of "should I work things out one step further ahead, or will that just be really annoying for my opponent?"
Real-time games have a different slant on simultaneous actions and hidden information: even if all information is visible, you can't take it all in at once. You have to choose where to look and how quickly to act on what you see; to find the middle ground between reacting prematurely and hesitating too long. In the words of Frank Lantz, "Seeing is statistical".