Physical exercise. I'm not kidding. I recall hearing about a researcher that worked with people age (65+) to see how they could recover and/or improve their cognitive skills. He tried other things (including brain training) before jumping to exercise. Its research lab ended up being a Gym.

Brain training does work for some people; around 20% of the population won't gain anything from it, regardless of what you make em do. And even for those that works it has limited scope on the benefits.