I think that measuring state spaces is really misleading. (Although we totally did that to aggrandize how good our synthesis system was, at least to ourselves :

I think that measuring state spaces is really misleading. (Although we totally did that to aggrandize how good our synthesis system was, at least to ourselves :P. The space of possible programs, even short ones in a small language, quickly gets hilariously large.) Past a certain point the structure of a space is what matters which dictates how well any given search strategy will perform, and that doesn't readily generalize across domains. I have not seen anything that would lead me to believe that results like AlphaGo will meaningfully generalize to such an extent. I still think that it would take more than just incremental work to get from where we are now to scalable program synthesis.