[wyattpeak]

That just isn't true. It was widely believed through the seventies and eighties that chess inherently required creativity, and a machine could never beat a grandmaster.

Rather, I suspect, tasks which computers start outperforming humans in we reanalyse as "completely procedural". Nobody called chess procedural in the middle of last century.

[gaius]

Well, a computer playing chess is simply enumerating all possible boards. Which is the same way that a GAN produced “art”. Humans do it creatively because that’s how you do it if you lack exhaustive computing power and memory. In neither case is a computer mimicking that process of a human, they simply arrive at the same outcome by a brute force means.

[tialaramex]

No. Computers don't play chess by "simply enumerating all possible boards". That would require ludicrously more compute power than we have, and, of course, it would also _solve_ chess, rather than just allowing the computers to play once it would (if it could ever be done) show that the game itself has a solution, a best way to play, like Tic-Tac-Toe.

Historically AI chess (e.g. "Deep Blue" or Stockfish) is played by machines using one heuristic to estimate how "good" positions are without truly knowing, not so dissimilar from how humans evaluate a chess position. and then another heuristic to try out moves to get to further positions. The machine considers possible plays and how they affect the heuristic "value" of the board, preferring those with more value. Human Chess AI authors design the two heuristics used, though they often aren't very good at actually playing chess because it's a different skill.

Google's AlphaZero AI plays chess differently again, it had no preconceptions of how to play Chess, instead it learned through self-play - it knows the rules of the game but began with no idea what's a good or bad move, it adapted its own heuristics based on how well they'd won or lost. It actually recapitulated most of human chess theory history over its incubation period of thousands of games, discovering ideas like the Sicilian Defence for itself, new attacks would at first see overwhelming success, and then, playing versions of itself that had seen these attacks, they'd be defended more effectively.

Alpha Zero plays a radically "more human" style of chess than most modern human Chess grandmasters, huge multi-move strategies in which pieces are sacrificed to take positional advantage. It looks like something humans were doing last century - except Alpha Zero does it much better than they ever did.

[foldr]

A typical chess position has fewer than 100 possible moves, so a modern computer can do quite a deep exhaustive search of the state space. You won't beat Kasparov just by doing that, but I'd bet it's enough to beat me.

[tialaramex]

"Just by doing that" you can't even begin.

The problem is that you lack an evaluation function. Let's consider two of those 100 possible moves. Your rook could take this opposing pawn, or, your own pawn could move forward one space. Which is better? Why? Neither of them immediately wins the game, but we must pick something. In a smaller, tighter game, like Tic-Tac-Toe we could crank our exhaustive search until we discover that this opening move leads to a possible win... but the search space in Chess is categorically too enormous for that.

Both Google's Alpha Zero and simple human play encourages the belief that a good evaluation heuristic is essential. The evaluation heuristic looks at a board position and it doesn't recommend a move it says something like "I rate this position 0.418" where 1.0 is "I'll definitely win on my turn" and -1.0 is "My opponent wins on their turn". Google's engine contemplates relatively few possible moves (for a computer) but the results are striking because it's looking at _good_ moves more of the time rather than wasting a lot of time thinking about moves that are a bad idea.

This seems obvious, but, well, learn chess and see for yourself.

[foldr]

Yes I'm aware that you need an evaluation heuristic. My point is that you don't need a particularly good one to be able to beat an average intelligent human at chess. (After all, most humans don't have very sophisticated chess position evaluation heuristics, and they are able to examine vastly less of the search space than a computer.) Beating Kasparov is another matter, of course.

Here's an example of a simple chess engine that is good enough to beat amateur human players at least some of the time:

https://news.ycombinator.com/item?id=8133125

[gaius]

Or even https://en.wikipedia.org/wiki/1K_ZX_Chess