I have come to the conclusion that any board game is mathematics.

SuperInfinity

It's only recently that this occurred to me.

Graph theory such as the seven bridges of Konigsberg is considered mathematics. Knots are considered mathematical. The "knight's tour" is (usually) considered mathematical. Fitting and twisting and turning shapes are all considered mathematical. You can invent a problem with shapes (or something that can easily be reduced to shapes) and call that mathematical but not in a game?

Perhaps there is no final answer to the mathematics of some games, such as in chess. Perhaps many of the results would be considered "trivial" or meaningless by mathematical standards.... but that doesn't mean they're not mathematics. Many people would argue much of what is commonly known as mathematics is meaningless.

Fremen

G.H. Hardy had an interesting take on this, which I'm inclined to agree with:

A chess problem is genuine mathematics, but it is in some way 'trivial' mathematics. However ingenious and intricate, however original and surprising the moves, there is something essential lacking. Chess problems are unimportant. The best mathematics is serious as well as beautiful -- 'important' if you like, but the word is very ambiguous, and 'serious' expresses what I mean much better. ...

A chess problem also has unexpectedness, and a certain economy; it is essential that the moves should be surprising, and that every piece on the board should play its part. But the aesthetic effect is cumulative. It is essential also (unless the problem is too simple to be really amusing) that the key-move should be followed by a good many variations, each requiring its own individual answer. 'If P-B5 then Kt-R6; if .... then ....; if .... then ....' -- the effect would be spoilt if there were not a good many different replies. All this is quite genuine mathematics, and has its merits; but it is just that 'proof by enumeration of cases' (and of cases which do not, at bottom, differ at all profoundly [footnote: I believe that it is now regarded as a merit in a problem that there should be many variations of the same type]) which a real mathematician tends to despise.

Eliot Rosewater

A great Hardy quote, when he's talking about proof by contradiction i.e. reductio ad absurdum:

"The proof [of the infinitude of the prime numbers] is by reductio ad absurdum, and reductio ad absurdum, which Euclid loved so much, is one of a mathematician's finest weapons. It is far finer than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."

Fremen

Scott Aaronson had something pretty interesting to say about chess on his blog:

We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would not have to trust the alien or its exotic technology, and we would not have to spend billions of years analyzing one move sequence after another. We’d simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.

I suppose this applies much more generally, and is not just a result about chess. Still, I thought it was fun.

SuperInfinity

Fremen wrote: »

Scott Aaronson had something pretty interesting to say about chess on his blog:



I suppose this applies much more generally, and is not just a result about chess. Still, I thought it was fun.

That's certainly not true. That's like claiming that if aliens came to earth with amazing computational powers that could decrypt a 128-bit AES encryption that all we would need to do to decrypt a message ourselves is have a short conversation with them about the sums of polynomials.

Some things just have irreducible complexity. Nothing to do with polynomials at all. For example the Nalimov endgame tablebases take up several gigabytes for just a few pieces. And even if aliens could brute force it with computing, that would say nothing about their mathematical ability and ability to tell us it using polynomials. A ridiculous claim.

Pygmalion

SuperInfinity wrote: »

That's certainly not true. That's like claiming that if aliens came to earth with amazing computational powers that could decrypt a 128-bit AES encryption that all we would need to do to decrypt a message ourselves is have a short conversation with them about the sums of polynomials.

No, the aliens could prove to us that White or Black has the winning strategy.
That doesn't mean that we would suddenly understand the winning strategy and be able to apply it with our current technology.

Likewise the aliens could prove that they're capable of decrypting such messages in a variety of ways, but that doesn't mean we'd be able to do it ourselves.

Edit: Just looked into it and apparently the justification is that the chess problem can be shown to be in IP (Interactive Polynomial Time), so read about that if you're interested.
Of course, don't ask me how it can be shown to be in IP :P

A related topic would be a Zero-Knowledge Proof, which has the added benefit of not revealing the proof itself to the verifier, while still convincing the verifier of its correctness with probability of deceit approaching 0.

sponsoredwalk

Watching these videos:

https://www.youtube.com/watch?v=BVVfs4zKrgk

https://www.youtube.com/watch?v=zBVKmS1RzeA

you'd think the OP had it backwards


Obviously referring to the "game" part of the post gleefully ignoring that "board" part
(apart from in this annoying explanatory text - you must learn!).

SuperInfinity

Pygmalion wrote: »

No, the aliens could prove to us that White or Black has the winning strategy.
That doesn't mean that we would suddenly understand the winning strategy and be able to apply it with our current technology.

I know that is the claim, I claim that that's not possible. They could not prove to us that White or Black has the winning strategy.

Pygmalion wrote: »

Likewise the aliens could prove that they're capable of decrypting such messages in a variety of ways, but that doesn't mean we'd be able to do it ourselves.

Okay maybe that analogy doesn't fit perfectly. But the point is that chess isn't something that can be simplified. Otherwise, prove the Nalimov tables in terms of a short, quick polynomial.

I will email that guy and ask him to prove to me using polynomials in a short conversation that a mate in 500 is the optimal solution. It's not possible.

Pygmalion wrote: »

Edit: Just looked into it and apparently the justification is that the chess problem can be shown to be in IP (Interactive Polynomial Time), so read about that if you're interested.
Of course, don't ask me how it can be shown to be in IP :P

A related topic would be a Zero-Knowledge Proof, which has the added benefit of not revealing the proof itself to the verifier, while still convincing the verifier of its correctness with probability of deceit approaching 0.

Yes well there are a lot of total nutcases people out there, including in academia, who make daft, unfalsifiable and ridiculous claims. People such as Ray Kurzweil and Michio Kaku. People listen to charlatans like that because of the sensationalist claims they make. And indeed they often do very well out of it.

I'm telling you as an absolute fact, you could not in any way prove that you had the perfect game of chess. You would have to go through all the different possibilities. Sure they could be converted to some kind of polynomials, but they wouldn't lose any information in that time.... they would still have to transmit the same level of data to you.

sponsoredwalk

What's your beef with Michio Kaku?

SuperInfinity

sponsoredwalk wrote: »

What's your beef with Michio Kaku?

I don't find his arguments or theories in any way convincing, they are more just populist and sensationalist arguments. They are basically stories and fairytales but with this sort of "scientific slant" to them.

I don't buy any of his theories on time travel, teleportation or the way he categorizes "impossibilities", like: "class 1 type impossibilities". I doesn't like people who use conflicting arguments even in an allegorical sense... like "physics can make the impossible possible".... to me that is just hypocrisy and just because it's an intended contradiction doesn't make it okay.

sponsoredwalk

Well you may not like "his" theories but atomic teleportation and invisibility
have been experimentally shown to work (within limits) and as for time
travel I mean the equations of general relativity allow for time travel, your
problem would be with GR not Kaku. Sure he interprets some of his book
within the context of string theory but you can't fault him for that seeing
as he has made major contributions to the theory itself. As for "making the
impossible possible" concern, this is just plain ridiculous because his book is
chock full of historical cases of what was considered impossible being
shown to, in fact, be possible. If you'd actually read the book you'd know
that he's clearly not stating that these things are impossible, he is
speaking from the point of view of the everyday person when he calls
something impossible & then goes on to show that this is an erroneous
judgement. He makes this view explicit multiple times, even the wiki on the
book makes that clear.

According to Kaku, technological advances that we take for granted today
were declared impossible 150 years ago. William Thomson Kelvin
(1824–1907), a mathematical physicist and creator of the Kelvin scale said
publicly that “heavier than air” flying machines were impossible. “He
thought X-rays were a hoax, and that radio had no future.”[4] Likewise,
Ernest Rutherford (1871–1937), a physicist who experimentally described
the atom, thought the atom bomb was impossible and he compared it to
moonshine (a crazy or foolish idea). Televisions, computers, and the
internet would seem incredibly fantastic to the people of the turn of the
20th century. Black holes were considered science fiction and even
Einstein showed that black holes could not exist. 19th century science had
determined that it was impossible for the earth to be billions of years old.
Even in the 1920s and 1930s, Robert Goddard was scoffed at because it
was believed that rockets would never be able to go into space.[4]
Such advances were considered impossible because the basic laws of
physics and science were not understood as well as they are understood
today.

Kaku states that “as a physicist [he] learned that the impossible is often a
relative term.” By this definition of "impossible", he poses the question "Is it
not plausible to think that we might someday build space ships that can
travel distances of light years, or think that we might teleport ourselves
from one place to the other?"[4]

Pygmalion

SuperInfinity wrote: »

Yes well there are a lot of total nutcases people out there, including in academia, who make daft, unfalsifiable and ridiculous claims. People such as Ray Kurzweil and Michio Kaku. People listen to charlatans like that because of the sensationalist claims they make. And indeed they often do very well out of it.

The paper referenced in Scott's blog (the one that proved that IP=PSPACE, that is, the set of problems that can be solved using some Polynomial(input size) space is equivalent to the set of problems for which there exists an interactive proof running in some Polynomial(input size) time) was by this guy.
That is, one of the most respected cryptographers in the world and a large part of the reason that you can securely transmit data online, it's been reviewed extensively, as it's a very important proof, and has been universally accepted; I think I can safely say it's not a daft and ridiculous claim.

As for the specific problem of chess, it's actually fairly easy to show it to be in PSPACE if you have some limit on the number of moves that can be made (it can be arbitrarily high, but not infinite) it follows that the number of possible outcomes is a polynomial in the size of the board (let's say NxN).
Assume that each piece (P in total per player) can move to each other position on the board, no piece will die, and there are M moves allowed before the game ends, you end up with a total of (2 * (P * (NxN)))^M possible outcomes if I'm not mistaken, which is a polynomial in N.
In practice of course this is completely over-estimated, as not every piece can move to every position, pieces will die, and there may be many ways to get to the same position, but all that means is that it's much much lower than this estimate, it's still a polynomial in N, which is the important thing.
This is also enough information for deciding whether a winning strategy exists (if you have all possible move combinations and their outcomes just go through all of them, implementation would be a bitch but who cares, this is theory, and we're assuming the aliens have the computing power to do it, even if we don't :P).

Since it's in PSPACE, by this observation, and Shamir has proven that for all problems in PSPACE there exists an interactive proof in polynomial time, the statement holds.
The interactive proof may not be trivial, but as IP=PSPACE it's been proven that it can be done in polynomial time, rather than the exponential time that (might?) be needed to prove it by looking at all possibilities.

SuperInfinity

Pygmalian, I see you've put a lot of effort into your post. I'm not really interested in all that right now, but it's incorrect to state that the perfect game of chess could be verified to us in a simple conversation with aliens.

If you look at the Nalimov tablebases (each position can be considered as like chess, but a much simpler game), look at how they verify the solutions:

http://en.wikipedia.org/wiki/Endgame_tablebase#Step_3:_Verification

They don't verify the solution by polynomials, they have to go through each possible step, to make sure it agrees with all of the tablebases that are one move away from it. Otherwise, they would just use the polynomials that could be talked about and solved/verified in a simple conversation.

The polynomials they talked to us about would have to contain at least the same amount of information as the tablebases themselves. Otherwise they could not prove to us that it was a perfect game. Even if they sent us every perfect response they had for every possible white move and every possible perfect move for black we still couldn't verify they were right except through trial and error.

Have you ever heard of the travelling salesman problem? That's what chess is like, except on a much, much larger and more complicated scale. http://en.wikipedia.org/wiki/Travelling_salesman_problem There are no general mathematical solutions for such a thing, they boil down to computers using optimized trial and error. If there were solutions like that, then chess would be solved mathematically anyway.

His comment was just a mistake, probably stemming from trying to gain attention, I doubt he would stand by this. I think it's strange that you don't realize the mistake. It would be like saying after sending a movie over the internet, you stated you could verify every single pixel of the movie was correct with a quick conversation about polynomials.

What about games that have already been solved, like checkers and connect 4, is he claiming that he could prove the solutions are perfect? Why doesn't he go ahead and do it then?

Pygmalion

SuperInfinity wrote: »

They don't verify the solution by polynomials, they have to go through each possible step, to make sure it agrees with all of the tablebases that are one move away from it. Otherwise, they would just use the simple polynomials.

The polynomials they talked to us about would have to contain at least the same amount of information as the tablebases themselves. Otherwise they could not prove to us that it was a perfect game. Even if they sent us every perfect response they had for every possible white move and every possible perfect move for black we still couldn't verify they were right except through trial and error.

Well the assumption here is that each step might still need to be considered by trial and error, but it would be done so by the aliens with their infinite computing powers, not us.
Once they have done that the result IP=PSPACE shows that the result they got, which took an exponential amount of time for them to show, can be verified to us in polynomial time if we can ask the Aliens certain questions about the sums of polynomials over fields.
This is a direct result of IP=PSPACE; we may or may not know which questions to ask them to minimise the time spent, or exactly how long it would take, but we've shown it to be possible, and in polynomial time instead of exponential.

It's also a very misleading usage of the phrase "short conversation", as it would likely still be a pretty long time and require a lot of data to be transfered, but it would still be many, many orders of magnitude less time than it would take for us to compute it ourselves.
It's "short" in the same way computer scientists often refer to problems that have polynomial time solutions as being "easy" compared to those that don't.

Have you ever heard of the travelling salesman problem? That's what chess is like, except on a much, much larger and more complicated scale. http://en.wikipedia.org/wiki/Travelling_salesman_problem There are no mathematical solutions for such a thing. If there were, then chess would be solved mathematically anyway.

Indeed, and the decision variant of it is NP-complete, meaning that while it's probably* not possible for a computer to calculate it in polynomial time, if some super advanced alien species gave us an answer to it thanks to their extraordinary computing powers, we could verify that the answer is correct in polynomial time.

*It is if P=NP, but I doubt that to be true :P

RoundTower

I think the proof was that the aliens could convince you to an exponentially vanishing level of doubt that they had solved chess. But I haven't read the paper and only got the bit about zero-knowledge proofs.

Enkidu

SuperInfinity wrote: »

I don't buy any of his theories on time travel, teleportation

I agree with you about Kaku, but teleportation is a real observable effect in quantum mechanics. It's used in a few quantum computation algorithms.

SuperInfinity

Enkidu wrote: »

I agree with you about Kaku, but teleportation is a real observable effect in quantum mechanics. It's used in a few quantum computation algorithms.

Teleportation on the atomic level maybe, like apparently instantaneous jumps of electrons to different quantized orbitals. This has been known for decades.

sponsoredwalk

Quantum State: (1998)
http://media.caltech.edu/press_releases/11935

Light: (2002)
http://news.bbc.co.uk/2/hi/sci/tech/2049048.stm

Atoms: (2004)
http://news.bbc.co.uk/2/hi/science/nature/3811785.stm
http://news.cnet.com/Atomic-particles-teleported/2100-1008_3-5238136.html

Light to Matter: (2006)
http://www.cbc.ca/news/technology/story/2006/10/05/tech-teleport-061005.html

https://www.youtube.com/watch?v=-FqLCLooayM

"600m across the Danube River" - Kaku in the video...

But yeah, nutcase! :pac:

Enkidu

SuperInfinity wrote: »

Teleportation on the atomic level maybe, like apparently instantaneous jumps of electrons to different quantized orbitals. This has been known for decades.

No, that is something different. It's simply time evolution in quantum mechanics and measurement projection and not really teleportation.

What I'm talking about is genuine quantum teleportation which grew out of quantum computation and was first measured experimentally in the 1990s. It has been performed over kilometers. Of course it scales terribly so it's not going to be useful at all on a large scale, but still it exists.