How to find good features for a linear function approximation in RL with large discrete state set?

I've recently read much about feature engineering in continuous (uncountable) feature spaces. Now I am interested what methods exist in the setting of large discrete state spaces. For example consider a board game with grid as a basic layout. Each position on a grid can contain exactly one of multiple elements and the agent makes decisions according to the current board position. If the grid is large enough, say 30x30, and there are only two different elements we could model the states as a linear model with $$2*30*30 = 1800$$ variables (using dummy variables) and this model can't even distinguish relationships between positions. For this we would need to use $$\binom{90}{2}$$ or even $$\binom{90}{k}$$, $$k = 2, 3, 4$$ more features.

How would one approach this problem? Are the methods for feature selection for linear approximations, which even automatically find/learn non-linear combinations? What was the approach to solving these problems when NN where not around?

• Heuristics. Deep Blue used heuristics which can determine the goodness of a postion in chess (e.g no. of bishops, degree of freedom of a piece, existence of a queen, etc) – user9947 Mar 7 at 17:36
• @DuttaA So it's almost necessary to rely on hand crafted features? – s1624210 Mar 8 at 12:38
• I am not aware of current developments. But as far as I know in Atari games they used the entire frame for learning, by passing it to a CNN. Hence I presume of computational complexity is not a constraint you can just use big Neural Nets. – user9947 Mar 8 at 13:09
• @DuttaA Ok, of course NN do feature engineering themselves, but for linear models the features have to be selected separately (and we can't use all features). – s1624210 Mar 8 at 13:24
• I don't know much. But in older times when computation was expensive they used this stuff. Maybe you can head over to David silver's lecture on Atari games which can be of help. Or check out how deep blue was choosing heuristic. – user9947 Mar 8 at 13:33