* Random, variable rewards, with the possibility for really great rewards.
* In as many different ways as you can feasibly include.
* Optimise for 'near-misses', which have been shown to increase the addictive properties.
The more I've thought about it, the more I realize that variable reward is a key component of fun. All of the most fun and successful games have it built in, even if you don't realize it. Does it have ranked match making? That's variable reward. Why do you think online chess is so popular now? The ranked match making gives you just enough wins to keep you hooked.
Actually, Roger Caillois wrote a famous book on the different forms of play [1]. He uses four forms of play to classify games, and the one you are referring to is chance (Alea in his book). Another form of play that applies more accurately to chess is competition (Agon in his book). He also emphases two other key components of fun: playing a role (Mimicry) and physical sensations like in a roller coaster (Ilinx).
In my personal experience in competition if you are only losing or only winning it's not fun. I think competition is variable reward dressed up.