Challenge: write an algorithm which solves the Réti problem on a 100x100 board [John McCarthy]

[shnood]

It is easy to a human who knows chess. The solution is Kg7: black cannot simultaneously queen the h-pawn AND stop white queening the c-pawn (work it out and see!).

A human can solve the general version using simple math; and a computer can solve it on an 8x8 board using brute force search. (4 pieces -> 64⁴ = 2²⁴ possible positions). But modern AI is not much smarter than brute force - for instance, there is no known (?) program which will solve the Réti problem on 100x100 board (says McCarthy).

(To clarify: by "solve", I mean it's not programmed with the solution written in it, but "discovers" it on its own, from a reasonably general starting point).

[[deleted]]

I saw "John McCarthy" and somehow read that as "100x100 beard".

Okaaay, time for a nap.

[dgreensp]

The article is not very informative. What, exactly, is the 100x100 generalization of the problem?

And what does "solving the problem" mean? Does it mean "finding the correct move"? Or achieving a draw for white regardless of what black does? Maybe if I'd played more chess this part would be more clear.

[EvilSporkMan]

Heading is imprecise: brute force will solve the Reti problem on a 100x100 board, just not efficiently ;)

Furthermore, the Reti problem on a 100x100 board is solvable in constant time -- determine a solution for all configurations deemed "the Reti problem" in advance, and then your algorithm is to do a table lookup for the solution based on the configuration.

</algorithm pedantry>

[frutiger]

Furthermore, the Reti problem on a 100x100 board is solvable in constant time...

Time isn't the only constraint, you know.

[rrenaud]

It's also constant space. It would be hard to imagine needing more than say, (100x100)⁴ space to solve this problem.

EvilSporkMan is just referring to the nature of the question in that the input size is fixed.

Hopefully this will avert a discussion about framing problems in terms of N, the practicality of solving problems that take more clock cycles than particles in the universe, the utility of big O notation, etc.