I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with this, so I'm writing to ask for some help. I think students will be more interested in popular games (in the US, to be precise), i.e. things they might have played growing up, e.g. Monopoly, Clue, Battleship, Sorry, Settlers of Catan, Dominion, Scrabble, Risk, Uno, Connect Four, Othello, Candyland, Checkers, bridge, war, gin rummy, etc. I suppose cell-phone games would also be interesting, but I don't know anything about them. I'm writing to get a sense of the literature, to make sure I don't duplicate something that's already been done, to get inspiration for the types of questions we could investigate, and to see where papers like this get published.
I'm looking for published papers that conduct a mathematical analysis, e.g. proving which player wins under optimal play, proving a game is NP-hard, or analyzing the probabilities (e.g. probability that there is no set in the game Set, if 12 cards are showing).
I'm already aware of the question "Which popular games are the most mathematical?" but it's asking for something different. Nevertheless, that link already discusses some math related to Chess, Go, backgammon, battleship, poker, minesweeper, mastermind, connect four, Mafia, Magic: The Gathering, and some cell-phone games: "Pushing Blocks", "Pixelated" (in BlackBerry) aka "Flood-It" (in iPhone). However, it doesn't give published references for all of these games, and doesn't discuss any other popular games, e.g. games from this list. I added links above to the closest I could find to a published reference, to give an idea of what I'm looking for.
Lastly, I am well-aware that sports can be analyzed mathematically, so no need to write an answer about baseball, basketball, etc. And, I'd like to avoid answers about games that people don't really play in the real world, like Nim, subset take-away, etc. There are a whole bunch of examples on the other mathoverflow question, but I don't think they'll capture student interest in the same way.
Best Answer
A few years ago several classic Nintendo games (including Mario, Donkey Kong, and Legend of Zelda) were examined from a computational complexity point of view. They proved that generalized versions of these games are NP-hard, and in some cases PSPACE-hard.