Especially that first one. I'm suspecting that the answer is something like "the extent to which the player can meaningfully impact the game world through his actions," but I'm not completely sure.
I had a bit of time to think about this while stuck in traffic. Let's take Super Mario Bros. as an example. Most people would probably agree that it is a simple and fun game (icy would either claim it either is fun or it is simple, but let's ignore that).
So, how complex is SMB? (I'm going to assume Mario can backtrack for ease of calculations, so pretend this is some rom-hack emulator version or something)
Let's look at the state space of SMB 1-1:
Number of possible inputs: Left, Right, Down, Down+Left,Down+Right,Down+Left+B, Down+Right+B,Down+B, Left+B,Right+B and then all of those again with A, so 21 possible inputs (including the null input).
Given that the NES was 8-bit let's assume that 2 8-bit numbers describe Mario's x and y velocities. This means there are 2^16 possible Mario velocities.
Number of possible positions Mario can occupy (gross simplification): Let's say as a reasonable estimate Mario can occupy the lower third of a level (this ignores things that occupy his path, but he is never constricted on top by things, so this seems reasonable). This means that Mario can occupy 3324*75 different locations or 249,300 diffferent locations.
If Mario is on a flat surface he can jump. The jump will be different depending on how long the button is held. Estimate Mario FPS at 30 and maximum jump hold time at 1 second (no idea how correct these are), so 3324*30 (approximately, this ignores gaps and places where Mario could be on a block so I'll call it a wash) or 99720.
There are 55 different blocks that Mario can hit (10 possible hits on the coin-block). So there are 2^55 different combinations of these.
There are 5 powerups Mario can collect. So there are 2^5 different collections of these.
There are 152 different locations you can hit the flag.
There are 300 different times you can hit the flag. (obviously you can't hit the flag at time 300, but we'll ignore that).
There are 15 enemies that can each occupy ~300 different states [position and direction] (this is a gross simplification, but given bouncing and distance until falling off of something it seems reasonable to me). So there are 300^15 different positions of these enemies (overestimation since the enemies only move while on screen). There are 2^15 different possible states of them being dead.
There are 226*75 locations Mario could be if he went into the bonus area and 226*30 different jump locations.
There are 19 coins in the bonus area that Mario could get. There are 2^19 different collections of these coins (might not be possible, I don't know SMB physics that intimately).
So, simple rough estimate at the number of different play states of SMB 1-1 is
or ~5.0957e14 times as many Mario 1-1 states as there are protons in the universe
If we don't use the number I am least proud of (300^15) and say that those enemies as a whole can only have 300 possible positions then we get
Comparing that to Chess with ~1e47 possible states, we see that Mario 1-1 is ~1.0654e13 times as complex as Chess!
Take that Kasparov!
I hope this demonstrates how stupid *complexity* is as a measure for games. This is also heavily caveated by the fact that Mario is much simpler to predict because there isn't an adversarial intelligence fighting you, but really we aren't talking about the game itself if we have to allow for intelligent opponents.
Again, open question to all of the icycalm followers, non-subhumans that you are, prove me wrong. Tell me why complexity is always better than simplicity when it comes to games. Tell me how you can objectively state the complexity of a game. Or do you want to be defeated by a subhuman, unable to uphold one of the key tenets of Zirbas?