A similar example, is that we know that 2-color match-Ns (and some further generalizations therefrom) such as Tic Tac Toe, Connect 4, and even wilder variants like Lumines have solved, polynomial solutions and machines can play them better than humans ever will. Humans will probably play some of these games forever, and its still a continual surprise to me how many people don't know the generalized Tic Tac Toe solution, much less that the only way to win is not to play.

Lumines will probably remain interesting to humans for a long time for those orthogonal reasons such as timing and accuracy (and music). But the interesting comparison here is to Tetris which we also generally know to be NP-hard as a direct relative to the generalized packing problem. I would think that to a human both games "feel" equally complex and yet in terms of computational complex you have easy solved algorithm in Lumines and computationally hard problem in Tetris. Lumines certainly feels at first glance to a human like an equal to the packing problem, even though it is not.