Jason Rohrer's 'Game Design Sketchbook' has an interesting meditation up on the nature of single player game mechanics — a lot of the achingly simple, but endlessly challenging board games that Rohrer points to require a minimum of two players. Rohrer's question is how to make a single player game that doesn't rely on typical mechanics to provide depth and challenge? Is it possible to have a game with the (gameplay) depth of go without falling back on AI or randomness or 'physical' contests? Well, in short, no:
Can you make an AI-free, randomness-free, physical-challenge-free, single-player game with gameplay depth akin to that of Go? Is there any hope for the single player art game that seeks to provide that kind of depth at the gameplay level? I now firmly believe that the answer is "no." The proof comes from considering how one might go about winning, or doing well at, such a game. If there is a single, optimal path to victory, then systematically finding that path is the main task in the game. Once the path has been discovered and documented for future use, the game's depth is exhausted. If there are multiple possible paths to victory, finding the rest after you've found one is an optional act of completionism, an exploration of mechanical depth.
He provides the fruits of his exploratory labors in the form of a board game-type game called i45hg. It's an interesting piece to digest even if you don't bother with the game — as Rohrer points out, a lot of things that failed as single player experiments would've 'sprung to life' with two or more players. Game Design Sketchbook: Testing the Limits of Single-Player [The Escapist]