Looks like we'll never learn what BB(5) is. That'd require running the 5-state Turing Machines we're uncertain about forever to see if they halt. I don't think we'll be able to think of any ways to apply mathematical ingenuity to this problem to reduce the amount of compute we'd need to determine the solution. Just a lost cause imo

@AdamK fair! but also chess has really weird rules that make it hard to apply mathematical ingenuity

@diracdeltafunk I feel like humanity hasn’t yet given formal mathematical analysis of chess a serious try. Let’s circle back when the notion of checkmate is formalized in Lean.

@AdamK We already know what BB(5) is. We don't have to run a machine forever to know if it halts, we can prove it with logic, and that was done just last year. https://scottaaronson.blog/?p=8088

@IsaacKing I think Adam is being facetious and saying that there's alternatives to brute force heavy techniques he feels NO holders are assuming.

@AdamK Incidentally, checkmate seems to have been formalized in Lean a few months ago (not sure if that was you being facetious as well).

Was this market based on this tweet?

Anyway, obviously chess will not be solved absent quantum computers or whatever some other magical technology

@johnwhiles No, you may notice I opened it two years before Elon's tweet. :)

So for fun and to ever so slightly accelerate the resolution, I used an LLM to draft small programs to search syzygy's 6 piece table base for useful conditioned properties that guarantee a draw.

From this I got the lemma:

For a chess board with 6 pieces or less, perfect play results in a draw if all conditions below are satisfied:

- the position is mirrored

- there are no attacking pieces

- there are no checks

- there are no passed pawns

- there is a single pawn island

- There are no trapped pieces, ex: [ rk6/b7/8/8/8/8/B7/RK6 w - - 0 1 ]

The starting position satisfies all of these conditions, so it will be interesting to see if this lemma holds for 8 pieces, 10 pieces, etc.

Trust this as far as you trust auto-generated code.

Unfortunately, this does not hold for 4 pair boards. If we expand the condition <no trapped pieces> to <no discoverable threats>, then the lemma very likely holds for boards with 4 pairs or less.

Github: (https://github.com/saternius/StaleChess)
o3 DeepResearch insights: https://chatgpt.com/share/67a412ff-6c68-8013-a391-04625f09a8af

I think it's possible that there might be a program to play chess with a formal proof that the program is optimal. But that neither the program nor the proof may be understood by humans.

@MalachiteEagle I know that there is such a program which is easily understandable by humans. It works like this:

1. The program iterates through every possible chess game.

2. The program plays a move such that it is guaranteed to win (or draw if winning move isn't possible).

3. Repeat step 2 when it's your turn again.

Pretty easy to write the code for it, and easy to prove that it plays optimally. Of course, running the program would be pretty hard 🙃

@Pazzaz ah that's a good point. Maybe then update what I was saying as a program that executes in constant time, and this constant being something we can run fairly quickly on a standard computer.

@Pazzaz so we have a program we can run, and it always wins, and there's a proof that it always wins, but we just can't wrap our brains around the explanation

Would be cool if you specified precisely which codified set of rules, otherwise it is a bit of a moving goal posts thing. Perhaps find out if the efforts concentrate on say the federation rules of a certain age

@JussiVilleHeiskanen I'm not sure how this could be a moving goalpost thing. This isn't about over-the-board chess, it's about chess about an abstract combinatorial game, the rules of which are very standardized these days. If you want something very precise, we can take "chess" to be the game whose game states and allowable moves are those given by the lichess.org analysis board.

@diracdeltafunk would you allow unlimited moves withou capturing or promoting a pawn in the spirit of the game in an abstract sense (or castling)

@JussiVilleHeiskanen Fair question, and I'm sorry for being dismissive. I'm not the market creator, but I feel pretty confident about what the ruleset is meant to be here. So: no, the 50-move rule applies (to make sure the game tree is finite). For the same reason, 3-fold repetition is an automatic draw. @IsaacKing is this what you have in mind?

@diracdeltafunk correct if I am wrong but haven't new theoretical work forced the 50 move rule to have been relaxed for certain combinatins of forces in a change of the rules for specific durations of games?

Oh, good point. No 50-move rule, that's a tournament rule and not inherent to chess. It was relaxed a few decades ago as endgames that needed more moves to win were discovered, then reimplemented I think because those endgames were just tedious.

@IsaacKing "that's a tournament rule and not inherent to chess" what does that even mean? It's used even in TCEC. It's as much part of chess as any other rule

@Lorenzo It's clearly not as much of a hard-and-fast rule as the others. https://en.wikipedia.org/wiki/Fifty-move_rule

Interesting that the TCEC uses it, do you know why?

@IsaacKing without the 50 move rule and/or some variation of the repetition rule (which is even less of a "hard-and-fast" rule, as you put it) it's not clear the game is even finite, how can it be solved then ?

@Odoacre I presume if the best move for each side is to perpetuate an infinite game, you would consider that position to be a draw

@JimHays well yes, but if there's no rule to make it a draw, then what are we even talking about

@Odoacre Including the repetition rule