Most games deal with finding patterns.  Sometimes designers try too hard to hide these patterns by adding some difficulty (to add fun to the game experience) but by doing this they fails to deliver what the player is looking for.  This happens because when the player is unable to make a coherent analysis about the game mechanics then frustration comes into the picture. 

So there is this big deal when dealing with difficulty and frustration: there's a balance that must be achieved (A game that is not difficult is not fun, but a game too difficult isn't either).  I think there's a very good method used in order to balance these two and I've found it in some good games.  This method's basic idea is to add some clues in order for the player to predict the future, or in other words, he's given the tools in order to find the pattern.

I find that this predicting thing goes from giving clues to small events that are going to happen (like clues to predict one opponent's next move) or things that may help you complete an objective (to know where to find something or how to do something).  The whole concept works like having a fortune teller next to you in case you need any help to complete the game. 

Sometimes there's even a fortune teller somewhere to help you in case you're stuck, like in Zelda: A link to the past, there was a fortune teller that if you paid her she would give you advice on what to do or where to find stuff. 

An example of clues on instant events would be the case of Punch Out, where the rival is constantly giving the player clues about what he is going to do.  Unfortunately for Punch Out, these clues become harder to find until you reach a level where the rival fighter start doing fake clues and predicting what he is going to do becomes a question of luck.

Now, luck is another variable in the equation. Luck is something that is completely up to the game.  For example in poker, luck fits very well into this game because the whole idea is for each player to be unable to know the other player's strategy so the only way to achieve this is by assigning each player's cards by luck. 

It is not something frustrating since it something based on randomness and you will be able to play with good hands if you play long enough (and intelligently also, otherwise frustration would come because you lost your car).  In other cases, like Punch Out, luck is highly frustrating because what you are looking for in the game is to find the enemy''s patterns and win by doing so.  If you don't find the pattern you'll probably loose and it wouldn't be your fault at all.

The balance between difficulty, frustration and luck is something that is not that hard to find.  As a designer you can add all the difficulty you want into the game as long as you give the player tools to break the difficulty by hinting the game's patterns. 

This will give the player the advantage of learning from the game to complete it, and achieving success.  Otherwise if the player doesn't learn two things could happen: he would get bored or he could finish the game but the feeling of success would be lost.  A good example of a game lacking the tools to help the player is Braid.  The player is forced to solve every puzzle of the game or otherwise he won't be able to advance.  There's no alternative choice to this or a system of hints to help the player in case he gets stuck so if this happens it is most probable that he would stop playing out of boredom.