In my opinion, to qualify for a game it requires:
1. Meaningful input from the player: If you're given 3 choices and they all result in the same thing, that's not meaningful input. There has to be choices to be made, and those choices must have consequences. Note that even a pure, linear FPS with no story counts, the input being the mouse movements and such.
2. The ability to lose. A "game over" screen after your avatar dies horribly is not required, there just has to be some sort poor conclusion, bad ending, or something else that you must work to avoid. You can't automatically win.
3. The ability to win. I'm sure this will be the most controversial thing here, but if there's no victory, and nothing to strive for it's not a game. I'm not automatically disqualifying endless games here, by the way - if it constantly gets harder the implied victory condition is surviving longer then you did previously, or collecting more points then you did previously.
And... yes, technically this means I don't think DF is a game at all. You can play a game inside DF (I win by collecting 5000 socks before the goblins kill me!) but the program it's self is not a game, it's a software toy.
Another interesting thing is I'm not sure I consider "prey" to be a game either. If you don't remember, it was an FPS where when you died you just teleported to a different area and shot some ghost things (afaik you couldn't lose this part at all, you just shot till you got them all) and then you teleported back with your health restored. It was impossible to lose, so I think maybe it was more of a highly interactive, extremely detailed visual novel.
The biggest problem with defining a 'game' is that the word itself is antiquated and un-befitting of the medium (that is, if we're bundling up interactive experiences as one fenced off medium).
I agree with this. Dayz or minecraft for example are not games at all, they are software toys and they should be sold as such. Similarly visual novels are not games, they are... well, visual novels which is it's own sort of thing. There needs to be more categories, rather then bunching everything together.
The problem is marketing, of course. Anything that loses the "game" label will automatically be considered inferior. It's too bad though, more categories would be useful.