[itishappy]

Do chess-bots rely on this? I was under the impression that a full search of the space was infeasible, so our current state-of-the-art approaches use heuristics, bounded search, and learned strategies. In other words, I suspect our current models apply to programming better than we might expect.

[nyrikki]

Chess is decidable, it may be PSPACE-hard or EXPTIME-hard, but there are reductions.

Entscheidungsproblem and Halt are not decidable in the general case.

While you have to find reductions, decidable problems having access to both yes-instances and no-instances makes it easier to find them.

[itishappy]

Knowing that we don't approach either by attempting to fully solve them, does that change the architecture, or just the difficulty?

[softirq]

Chess is a bounded, non-moving target. Think about the difference between chess in the 1970s and today, and compare that to the same time period with programming. Chess is a single game whereas programming is a federation of tools, protocols, and standards that are ever evolving. They're not comparable in any sense.

[itishappy]

I don't think that's a particularly relevant metric, as we can easily restrict programming to languages like Lisp/Pascal from the 70s, and the landscape doesn't change much.

I'd also suggest that our chess bots have evolved dramatically in that time. Deep Blue works very differently than AlphaZero, for example. Deep Blue might not be suited to code generation, but AlphaCode spawned from AlphaZero.