I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game attractive and fun:
- simple rules;
- simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is meaningless if the game can be played on a computer;
- a clear ending/winning condition;
- a well balanced (usually short) duration;
- as game proceeds the "current position" should get simpler and should soon or later clearly reflect a draw or winning/losing condition;
- the game contains tactical aspects (usually short term) or long term strategic aspects (usually long-term);
- many games are played using dice, so a random component can make the game more balanced and attractive;
- it abstracts an aspect of reality (war, conquer, destroy, survive, escape, build, ...);
- the difficulty should be balanced and the players must have the sensation that if they play more games they can improve their playing skills and/or discover new (tactical/strategical) aspects of the game;
- the game offers many strategies that can be chosen to win (a human player should not be able to learn a perfect winning strategy) and each match can lead to completely different positions and "situations";
- errors are "scaled": if a player makes small error then he can recover if he plays well or the other player makes a similar error.
Two-players games usually share some basic settings or meta-rules (some of them also apply to one-player puzzles):
- the board is finite and (usually) doesn't change during the game;
- a move is well defined; and it is (usually) local;
- player A and player B alternate during the game and a turn is usually a single move;
- there is usually an initial position (if the elements of the game are not placed on th eboard during the game);
- during the game there are some elements on the board (they are placed on the board at the beginning or during the game) and there is a clear distinction between elements owned by player A and elements owned by player B, i.e. both players have their avatars on the board :-)). A move can change the ownership of an element or kick it out of the baord;
- there is a winner;
- initially both players have allmost the same winning chances.
There are a lot of classic and popular two player games (that were invented before the computer age); and most of them have very different rules and settings: e.g. chess, go, card games, mancala, othello, hex, risk, master mind, scrabble, and so on. Many of them have been proved to be at least PSPACE-complete (the generalized version).
So, returning to your question, I think that there are enough evidences that:
- there are no "special rules" (exept for some common meta-rules), but there is a mix of elements involved (the list above can probably be further extended);
- there is a a clear connection between the (underlaying) computational complexity and the addictiviness/fun of a game;
Though point 2. is also related to the age of the players (or how much a player "want to think" while playing); e.g. simpler games like "game of the goose" (which is purely random) or the $O(n^2)$ "connect the dots" are funny for children.
Oldest games like chess, checkers and go satisfy many of the (orthogonal) aspects underlined above, but each in a different way: e.g. chess has harder rules than checkers, but it is deeper from a tactical/strategical viewpoint.
I'm not an expert of their history, but I'm sure that initially there were many variations of them, and their rules/settings have "slowly been tuned" to better satisfy the above aspects. For example, in order to shorten the duration of a chess game and enter the middle game faster, rules were changed (see history of chess or History of chess variants). Go rules in ancient times were always passed on by word of mouth, and were usually not clear; and even nowadays there are many variants (two main variations are about scoring, i.e. winning conditions) (see for example The History of Go rules). Even draughts has many national variants.
As a further confirmation of point 1. and 2. you can examine how many addictive video games (most of them are single player puzzles) have been created in the last years and have become "classics": candy crush, sokoban, snake, minesweeper, atomix, tetris, portal, ... they have completely different rules and settings, but they share a common point: they are theoretically hard :-)
From a theoretical point of view; a game is simply a path on a state graph (or state space) in which each node is a valid position and many of the above aspects are closely related to the structure of such a graph. We could write pages about such relation, but I think that a key concept is:
- the players don't play (theoretical) perfect strategies, so a game is addictive if they can perceive the state space in a strategical/tactical way exactly like on a battlefield with hills, valleys, hidden parts that will be discovered later, positions that look good, positions that look bad, one or more target to reach, temporary disadvantages that will lead to future advantages, different ways to reach a target, the possibility of hindering the opponent's strategy, and so on ...
