The Insolubility Of Chess Is Crumbling

[towforce]

In the past, at this forum, when I've said that chess will be solved either mathematically or by heuristics, I've been pointed to a peer reviewed papers showing that the complexity of chess grows exponentially with board size. Here's the outline argument, simplified:

1. The authors show that a simple game they've invented grows in complexity with size at an exponential rate

2. They show that chess is Karp reducible to this game

Well now both OpenAI and Anthropic have independently disproved the exponential time hypothesis - link. This means that algorithms will be able to solve exponential scale combinatorial problems that are Karp reducible to 3-Sat (explained in the linked article). Among the problems that are Karp reducible to 3-Sat are travelling salesman, graph colouring, set cover and knapsack (right now, the best algorithms for solving these do not use SAT).

I know that most members of this forum have a stronger emotional attachment to hardware, and get more excited by new GPUs than by mathematical progress - but I've always believed that the mathematicians would solve chess first. The hardware folk got Connect-4 and checkers - but beyond that is the realm of the mathematicians!

[Ras]

Be careful though... because a math proof means nothing if it doesn't show the moves.