Harvard mathematician answers 150-year-old chess problem(news.harvard.edu)

63 pointsby axiomdata3164 tahun yang lalu23 comments

news.harvard.edu

Harvard mathematician answers 150-year-old chess problem

https://news.harvard.edu/gazette/story/2022/01/harvard-mathematician-answers-150-year-old-chess-problem/

27 comments

Traster4 tahun yang lalu

It does make me chuckle the way this is reported. We answered this problem! Ok what's the answer "well about (0.143n)^n". I've figured out the value of Pi! It's about 3. Firstly, that's not an answer that's's an approximate answer, and secondly, it's wrong for a practical values of n. I really don't have the mentality of a mathematician.

mauricioc4 tahun yang lalu

You say "practical values of n", but the answer to n = 27 is already known and I would be very surprised if the final result had any practical application. The point of these problems is rarely the numerical answer, but the development of new techniques: The problem of determining the asymptotic growth of this number is studied because it is a good playground for sharpening mathematical tools and methods. In this sense, the asymptotic problem is an interesting one, and it was solved. Now that the main term is characterized, people can investigate sharper estimates.

The problem of determining an efficient algorithm for every n, on the other hand, is just hopeless, which means that it is not interesting for the purpose I described above. Studying "small" n (up to 40, say) is not useless, though, if it leads to algorithmic breakthroughs (in SAT solving, for example). It is, however, an "orthogonal" problem, in the sense that it requires a completely different set of techniques.

To illustrate my point: If the answer for n = 50 appeared out of nowhere, would people care about the number itself? I bet people would be much more interested in how it was done.

random3144 tahun yang lalu

Given the number of significant digits, the answer is closer to stating that pi is approximately equal to 3.14

I agree, you don't have the mentality of a mathematician.

alisonkisk4 tahun yang lalu

sockpuppet694 tahun yang lalu

sohkamyung4 tahun yang lalu

Also featured in this Quanta Magazine article [1]

[1] https://www.quantamagazine.org/mathematician-answers-chess-p...

fjfaase4 tahun yang lalu

The related OEIS sequence is https://oeis.org/A000170. It only gives exact values for n up to and including 27. The value for n = 27 was calculated with the help of an FPGA. See: https://github.com/preusser/q27

dmch-14 tahun yang lalu

Thanks to this I know that there is exactly 1 way of positioning 0 queens on 0x0 chessboard without any two of them attacking each other.

OJFord4 tahun yang lalu

Previously (4 months ago): https://news.ycombinator.com/item?id=28605220

Related (N-Queens is NP-hard, 4 years ago): https://news.ycombinator.com/item?id=15168867

greyman4 tahun yang lalu

I must be missing something, but when I take the formula (0.143n)^n, for n=8 the result is 2.933, while it should be around 92?

jdlqpdo4 tahun yang lalu

I noticed the same :-)

Knowing mathematics though, it's quite likely that this result is valid only for some regimes of N, for example assymptotically

readthenotes14 tahun yang lalu

From the paper

We show that there exists a constant α = 1.942±3×10−3 such that Q(n) = ((1 ± o(1))ne^−α)^n

Dunno what o(1) is.

edflsafoiewq4 tahun yang lalu

o(1) is some term that goes to 0 as n goes to infinity.

knuthsat4 tahun yang lalu

It's little o notation. It does not depend on n.

For example x^2 is in O(x^2) but is not in o(x^2).

dwohnitmok4 tahun yang lalu

When used in that equation it's meant to implicitly depend on n as edflsafoiewq points out. o(1) stands for o(f(n)) where f(n) = 1. Hence any function g(x) in the family of functions represented by o(1) must be less than c * f(x) for every positive c and all x greater than some m. This is exactly the statement that any function in the family of functions o(1) must tend to zero.

Whenever you see big-O/little-O/theta notation there is always an implied dependent variable, even for o(1)/O(1)/Theta(1).

omegalulw4 tahun yang lalu

I think a nuance people are missing is that for big O, it is sufficient for the existence of any positive C and x, but for small o there must always exist an x for every c.

tromp4 tahun yang lalu

The (0.143n)^n leaves out some smaller order factors that would help to give more accurate results. The situation is very similar to the number of legal Go positions on an nxn board [1], which Theorem 6 in that paper states as

L(m, n) ~ A * B^{m+n} * L^{mn(1 + O(mφm))}

[1] https://tromp.github.io/go/gostate.pdf

kevinventullo4 tahun yang lalu

Looking at the actual result, you can really only expect that (92^(1/8))/8 should be close to 0.143. It works out to about 0.22, which is less than double. The result actually says this ratio tends to 1 as n tends to infinity.

PinguTS4 tahun yang lalu

Also wondering where the authors of the article got this formula from. Because it is not in the paper. At least not that obvious.

The paper discusses an upper bound and a lower bound, but not a singular formula.

edflsafoiewq4 tahun yang lalu

The paper gives Q(n) = ( (1+o(1)) e^(-α) n )^n. (1+o(1)) is about 1 for large n. e^(-α) is about e^(-1.942) = 0.143. Inserting gives (0.143 n)^n.

pfortuny4 tahun yang lalu

There is the always elided “constant coefficient”, which the press release does not even mention.

[deleted]4 tahun yang lalu

keymone4 tahun yang lalu

Close enough.

- a mathematician

mauricioc4 tahun yang lalu

It's worth pointing out that Bowtell and Keevash proved a similarly impressive result for the toroidal case: https://arxiv.org/abs/2109.08083

dfan4 tahun yang lalu

I was very surprised to see a headline involving "Harvard mathematician" and "chess problem" and find that the article was not about Noam Elkies.

alisonkisk4 tahun yang lalu

ThinBold4 tahun yang lalu

Note that the preprint on arXiv dated back to July 2021.