I had a question today that I feel it must have an answer already, so I'm shopping around.
If we ask a model to learn the binary OR function, we get perfect accuracy with every model (as far as I know).
If we ask a model to learn the XOR function we get perfect accuracy with some models and an approximation with others (e.g. perceptrons).
This is due to the way perceptrons are designed -- it's a surface the algorithm can't learn. But again, with a multi-layered neural network, we can get 100% accuracy.
So can we perfectly learn a solved game as well?
Tic-tac-toe is a solved game; an optimal move exists for both players in every state of the game. So in theory our model could learn tic-tac-toe as well as it could a logic function, right?