Of the pure mental challenge games, I think "go" stands out as the most demanding. It was also the last such game where humans were able to hold off computers (although the computers finally won recently). You can study it for years and keep learning new techniques and patterns. It's also got a great handicapping system that allows players of any skill level to have a competitive match. It's also the only game that ever made my hand shake with fear when playing: when you're playing a stronger player with a handicap you start off with a big advantage and the match often comes down to a few traps they've left on the board near the very end of the match. You quickly learn that a mistake in those last few moves will turn your victory into defeat, and seeming "safe" moves can be disastrous.