Transfinite game values in infinite chess (2013)

jdh.hamkins.org

32 points·alexmolas··7 comments

If you're like me and got very excited by teasers like this:

> Another interesting thing we noticed is that there is a computable position in infinite chess, such that ... white has a computable strategy defeating any computable strategy of black—but in the category of arbitrary play, both players have a drawing strategy.

...then here is the original paper, where they go into much more detail:

https://arxiv.org/pdf/1302.4377.pdf

It sounds absolutely fascinating, and I want to learn more.

Hmm. That is interesting - does that mean that in an infinite game, first mover's advantage is essentially enough to guarantee a victory for white? If so, does that mean that infinite chess is a solved problem?

No, it means there is a specific computable position where white has a forced win, when both white and black have to follow computable strategies. But if they can use uncomputable strategies, it is a draw. Uncomputable = "if arbitrary Turing machine X halts, I move here, otherwise I move there", that sort of thing.

Great explanation - thanks!

Reminds me of deep blue not knowing what to do and moving randomly while being white in the first match against Kasparov. It won.

> Here is a similar position with value , which we call, “releasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right.

Do you ever encounter a paper where you suspect that one clever line came first and they built the rest of the theory backwards from there?

From 2013, though still cool.

Reply on news.ycombinator.com