Thanks, David. You raise some interesting questions and thoughts.
I think the amount of time someone will invest in learning a game depends mostly on the entertainment value but then also on potential social rewards for culturally significant games. Entertainment value needs to begin almost immediately and continue throughout the learning curve as opposed to only becoming entertaining after a significant learning investment. The problem I'm running into personally these days, is that the entertainment value falls off too quickly for most games. I somewhat arbitrarily decided that if I get 30 minutes to an hour of entertainment per dollar then I will look back on a game as a good purchase. The problem I have is mostly because the big budget games today are still very similar to the ones I bought and played several years ago. Regarding culturally significant games, I don't actually find chess, for example, to be very fun. It just seems like a somewhat arbitrary example from the class of capture board games with pieces that have varying rules for movement. No one would just sit down and intuitively guess the rules because they resemble the real world. However, it has historical cultural significance. People associate it with intelligence, so I think it is worthwhile to be familiar with the rules. Many popular sports also have a fair bit of arbitrariness in the rules. Also, I suspect most of the dramatic and exciting situations in popular sports from the past few years have happened several times before. However, large amounts of time and money are invested in them due to the potential rewards from their cultural significance.
I think those factors definitely work against new, complex strategy games becoming very popular without significant marketing. I think another factor driving the investment focus on increasing polygon, texture, and lighting detail and rough Newtonian physics for the AAA titles these days is a desire to incorporate scenes that are pulled straight out of popular action movies. That's why so many games have barrels that explode when they are shot.
On the flip side of the realism drive though, I think fantasy stories and settings are more popular than ever in film and television. Look at the success of The Lord of the Rings films or Game of Thrones or of course the new Star Wars movie coming out.
I agree completely that if you are designing a game to be unpredictable, then the amount of enjoyment a player will have could be unpredictable. That's why I'm focusing on adding rules that have many downstream influences. That way hopefully no matter what choice a player makes, the system will respond in some way, which will hopefully keep them interested. Ultimately though, I think I just have to play it as I make it and add details to situations that seem fun as they are discovered.
I think the search approach will handle unforeseen situations naturally. However, I think the challenge will be to keep the computation times feasible as the system grows. If I start adding graphics and animations to a game, it will probably be important to decouple the simulation used for the logic from the simulation used for the presentation. Maybe certain search hints can be pre-computed, or appropriate hierarchical levels of abstraction regarding decision making can be introduced to reduce a large search to multiple small searches.