I'm certainly not challenging anything you're writing, because I only have a very distant understanding of deep learning, but I do find the question interesting.

Isn't there a bit of a defining line between something like tic-tac-toe that has a finite (and pretty limited for a computer) set of possible combinations where it seems like you shouldn't need a training set that is larger than said set of possible combinations, and something more open-ended where the impact of the size of your training set mainly impacts accuracy?