- Blind mode tutorial
lichess.org
Donate

There is no reachable chess position with more than 218 moves.

#51

@LokiBrot said in #41:

Very interesting post, thank you!

A "layman's" question I have after reading is: If your code "swims" through solution space to find a maximum, how can you be sure that it isn't just a local maximum instead of the global one you're searching for?

Because in the linear programming relaxation, the solution space is convex. So every local optimum is also a global one. Convex means, that for any two points of the solution space, the line connecting those points is inside the solution space as well. Or more intuitively: You can create the solution space by making straight cuts only. This absence of weird holes makes search easier: Just walk in the right direction until you hit a wall, then slide along the wall into the right corner. Because of convexity, we know that it's the best corner. If we were stuck in a local optimum and there was another deeper local optimum, then due to convexity, the line connecting those holes would be in the solution space too and we could just local search our way to the deeper local optimum. Proof by contradiction! Usually it's not a corner though but a giant flat wall, but the idea is the same. If you have any further questions, consult a great LLM of your choice. I'm not gonna recommend Google Gemini nor OpenAI ChatGPT, since the former is complicit in helping Netanjahu cover up crimes against humanity and the latter is involved with the American military.

Thanks for being interested in my article ^^

@LokiBrot said in #41: > Very interesting post, thank you! > > A "layman's" question I have after reading is: If your code "swims" through solution space to find a maximum, how can you be sure that it isn't just a local maximum instead of the global one you're searching for? Because in the linear programming relaxation, the solution space is convex. So every local optimum is also a global one. Convex means, that for any two points of the solution space, the line connecting those points is inside the solution space as well. Or more intuitively: You can create the solution space by making straight cuts only. This absence of weird holes makes search easier: Just walk in the right direction until you hit a wall, then slide along the wall into the right corner. Because of convexity, we know that it's the best corner. If we were stuck in a local optimum and there was another deeper local optimum, then due to convexity, the line connecting those holes would be in the solution space too and we could just local search our way to the deeper local optimum. Proof by contradiction! Usually it's not a corner though but a giant flat wall, but the idea is the same. If you have any further questions, consult a great LLM of your choice. I'm not gonna recommend Google Gemini nor OpenAI ChatGPT, since the former is complicit in helping Netanjahu cover up crimes against humanity and the latter is involved with the American military. Thanks for being interested in my article ^^
#52

@Tobs40 , I believe I understand your claim.

But, although I have evaluated and produced my share of mathematical proofs, I do not entirely understand your proof.

It's quite possibly my problem. Indeed, I'll suggest that's even likely. After all, many mathematical proofs "skip steps" when the author assumes them too obvious to mention without insulting his intended readers.

But danger lies in such assumptions.

I do like your analogy to a password, however. It's an interesting mental model that does seem to lead toward light. But, at the moment, I find myself still in pre-dawn, hoping for the metaphorical terminator to advance toward the west.

Elaborate a bit more, perhaps -- for those of us with less trusting minds. Can we assume that the "12" you mention arises from 2 x KQRBNP? I suppose we can.

But can an un-castled king and a castled king be viewed as a single sort of piece, since each can move differently? Can a pawn without further opportunity for en passant capture be viewed the same as a pawn that retains that opportunity? Since the two pawns have a different set of possible moves? And, I suppose, I should mention the castled and un-castled rooks, as well. Are they really just one piece, to add up to the "12" you appear to assume -- at least to those of us with lesser ratings?

Those are the sort of questions that linger for me. Perhaps I should re-read, or perhaps things will clear after a bit more cogitation. Although proofs that depend upon the intervention of software assistance will always be a bit difficult to accept, in much the same way that the "four color" proof (arising out of the work of Kenneth Appel and Wolfgang Haken and perhaps John A. Koch) left skeptics only gradually coming to grudging admission.

But, in the meantime, some elaboration might be helpful. Nice effort, in any event. You're an impressive person, of that I need no further proof.

But, to be honest, I'm not yet convinced you are correct. That makes me uneasy, of course, since you are clearly intelligent.

@Tobs40 , I believe I understand your claim. But, although I have evaluated and produced my share of mathematical proofs, I do not entirely understand your proof. It's quite possibly my problem. Indeed, I'll suggest that's even likely. After all, many mathematical proofs "skip steps" when the author assumes them too obvious to mention without insulting his intended readers. But danger lies in such assumptions. I do like your analogy to a password, however. It's an interesting mental model that does seem to lead toward light. But, at the moment, I find myself still in pre-dawn, hoping for the metaphorical terminator to advance toward the west. Elaborate a bit more, perhaps -- for those of us with less trusting minds. Can we assume that the "12" you mention arises from 2 x KQRBNP? I suppose we can. But can an un-castled king and a castled king be viewed as a single sort of piece, since each can move differently? Can a pawn without further opportunity for en passant capture be viewed the same as a pawn that retains that opportunity? Since the two pawns have a different set of possible moves? And, I suppose, I should mention the castled and un-castled rooks, as well. Are they really just one piece, to add up to the "12" you appear to assume -- at least to those of us with lesser ratings? Those are the sort of questions that linger for me. Perhaps I should re-read, or perhaps things will clear after a bit more cogitation. Although proofs that depend upon the intervention of software assistance will always be a bit difficult to accept, in much the same way that the "four color" proof (arising out of the work of Kenneth Appel and Wolfgang Haken and perhaps John A. Koch) left skeptics only gradually coming to grudging admission. But, in the meantime, some elaboration might be helpful. Nice effort, in any event. You're an impressive person, of that I need no further proof. But, to be honest, I'm not yet convinced you are correct. That makes me uneasy, of course, since you are clearly intelligent.
#54

@RabbitsGrowOnTrees said in #50:

Your comment stated "with all those pictures" not just the first 2 and hence I thought you were referring to the final solutions:
It's stated in the article that the first two positions shown are not the final reachable solutions and were failed attempts along the way.

Maybe you are right, I should not have said "with all those pictures", but "with some pictures", I apologise for the confusion.
I'm not sure why you chose to repost a picture of an easily understandable legal position, but not any of the crazy ones.

@RabbitsGrowOnTrees said in #50: > Your comment stated "with all those pictures" not just the first 2 and hence I thought you were referring to the final solutions: > It's stated in the article that the first two positions shown are not the final reachable solutions and were failed attempts along the way. Maybe you are right, I should not have said "with all those pictures", but "with some pictures", I apologise for the confusion. I'm not sure why you chose to repost a picture of an easily understandable legal position, but not any of the crazy ones.
#55

But seriously now: There is no proof of the claim in this article. Just a description of some elaborate tries to use one particular solving programme (which may or may not be appropriate for this task). Maybe the next version of it will find 219, and then 220.

But seriously now: There is no proof of the claim in this article. Just a description of some elaborate tries to use one particular solving programme (which may or may not be appropriate for this task). Maybe the next version of it will find 219, and then 220.
#56

@Noflaps said in #52:

@Tobs40 , I believe I understand your claim.

But, although I have evaluated and produced my share of mathematical proofs, I do not entirely understand your proof.

It's quite possibly my problem. Indeed, I'll suggest that's even likely. After all, many mathematical proofs "skip steps" when the author assumes them too obvious to mention without insulting his intended readers.

But danger lies in such assumptions.

I do like your analogy to a password, however. It's an interesting mental model that does seem to lead toward light. But, at the moment, I find myself still in pre-dawn, hoping for the metaphorical terminator to advance toward the west.

Elaborate a bit more, perhaps -- for those of us with less trusting minds. Can we assume that the "12" you mention arises from 2 x KQRBNP? I suppose we can.

But can an un-castled king and a castled king be viewed as a single sort of piece, since each can move differently? Can a pawn without further opportunity for en passant capture be viewed the same as a pawn that retains that opportunity? Since the two pawns have a different set of possible moves? And, I suppose, I should mention the castled and un-castled rooks, as well. Are they really just one piece, to add up to the "12" you appear to assume -- at least to those of us with lesser ratings?

Those are the sort of questions that linger for me. Perhaps I should re-read, or perhaps things will clear after a bit more cogitation. Although proofs that depend upon the intervention of software assistance will always be a bit difficult to accept, in much the same way that the "four color" proof (arising out of the work of Kenneth Appel and Wolfgang Haken and perhaps John A. Koch) left skeptics only gradually coming to grudging admission.

But, in the meantime, some elaboration might be helpful. Nice effort, in any event. You're an impressive person, of that I need no further proof.

But, to be honest, I'm not yet convinced you are correct. That makes me uneasy, of course, since you are clearly intelligent.

Ah, a fellow mathmatician!

I'm happy to clarify!

The password analogy is an oversimplification. Combinatorial optimization problem would be the professional term. I did model logic for castling and en passant, but dropped them again due to performance reasons, although this does not harm the proof. To put it in the tightest nutshell possible:

I formulated the problem as an optimization problem of maximizing the number of moves and solved it using an algorithm which always finds the optimal solution. And since the algorithm found 218 as the optimal solution, this is proof that 218 is the best you can do. This algorithm works by branching through a tree and computing an upper bound to stop early. Improving this upper bound, so that the algorithm runs in a feasible amount of time, was the core of the work.

I applied several tricks, most mentioned in the article, such as leaving out constraints (this only makes the solutions space bigger!) - yet we still got 218 moves only. And since I filtered out the illegal solutions and those that don't actually have 218 moves (because the king is in check or something else I left away for performance reasons), then we are left with the optimal solutions.

I should point out that the code is on Github if you want to replicate.

I don't think that it's impossible that there is a more "elegant" proof of the conjecture. Maybe something you would like to try? I'm gonna stick with computers though. Already got eyes on the next record :)

Thank you for your interest in my article ^^

@Noflaps said in #52: > @Tobs40 , I believe I understand your claim. > > But, although I have evaluated and produced my share of mathematical proofs, I do not entirely understand your proof. > > It's quite possibly my problem. Indeed, I'll suggest that's even likely. After all, many mathematical proofs "skip steps" when the author assumes them too obvious to mention without insulting his intended readers. > > But danger lies in such assumptions. > > I do like your analogy to a password, however. It's an interesting mental model that does seem to lead toward light. But, at the moment, I find myself still in pre-dawn, hoping for the metaphorical terminator to advance toward the west. > > Elaborate a bit more, perhaps -- for those of us with less trusting minds. Can we assume that the "12" you mention arises from 2 x KQRBNP? I suppose we can. > > But can an un-castled king and a castled king be viewed as a single sort of piece, since each can move differently? Can a pawn without further opportunity for en passant capture be viewed the same as a pawn that retains that opportunity? Since the two pawns have a different set of possible moves? And, I suppose, I should mention the castled and un-castled rooks, as well. Are they really just one piece, to add up to the "12" you appear to assume -- at least to those of us with lesser ratings? > > Those are the sort of questions that linger for me. Perhaps I should re-read, or perhaps things will clear after a bit more cogitation. Although proofs that depend upon the intervention of software assistance will always be a bit difficult to accept, in much the same way that the "four color" proof (arising out of the work of Kenneth Appel and Wolfgang Haken and perhaps John A. Koch) left skeptics only gradually coming to grudging admission. > > But, in the meantime, some elaboration might be helpful. Nice effort, in any event. You're an impressive person, of that I need no further proof. > > But, to be honest, I'm not yet convinced you are correct. That makes me uneasy, of course, since you are clearly intelligent. Ah, a fellow mathmatician! I'm happy to clarify! The password analogy is an oversimplification. Combinatorial optimization problem would be the professional term. I did model logic for castling and en passant, but dropped them again due to performance reasons, although this does not harm the proof. To put it in the tightest nutshell possible: I formulated the problem as an optimization problem of maximizing the number of moves and solved it using an algorithm which always finds the optimal solution. And since the algorithm found 218 as the optimal solution, this is proof that 218 is the best you can do. This algorithm works by branching through a tree and computing an upper bound to stop early. Improving this upper bound, so that the algorithm runs in a feasible amount of time, was the core of the work. I applied several tricks, most mentioned in the article, such as leaving out constraints (this only makes the solutions space bigger!) - yet we still got 218 moves only. And since I filtered out the illegal solutions and those that don't actually have 218 moves (because the king is in check or something else I left away for performance reasons), then we are left with the optimal solutions. I should point out that the code is on Github if you want to replicate. I don't think that it's impossible that there is a more "elegant" proof of the conjecture. Maybe something you would like to try? I'm gonna stick with computers though. Already got eyes on the next record :) Thank you for your interest in my article ^^
#57

@kroksy said in #55:

But seriously now: There is no proof of the claim in this article. Just a description of some elaborate tries to use one particular solving programme (which may or may not be appropriate for this task). Maybe the next version of it will find 219, and then 220.

Hi,

being skeptical is cool, high five!

I think the problem is with understanding what I did:
I formulated the problem as an optimization problem that maximizes the number of moves and solved it using professional software, choosing an algorithm that always finds the optimal solution (when run to completion). The difficulty was in modelling the problem in a smart way, so that the algorithm completes within our lifetime.

The code is available on Github and Gurobi gives free non-commercial licenses - you can reproduce the result if you like. Perhaps even adapt the code and compute yourself a world record or prove something? :)

Keep in mind that I ran this on a machine with an Intel 13700F (8 performance cores). On an older laptop (extreme case), it might need weeks or months to complete. Good news: Gurobi prints its progress to the terminal, so you can make an educated guess on whether it's gonna finish during your lifetime.

@kroksy said in #55: > But seriously now: There is no proof of the claim in this article. Just a description of some elaborate tries to use one particular solving programme (which may or may not be appropriate for this task). Maybe the next version of it will find 219, and then 220. Hi, being skeptical is cool, high five! I think the problem is with understanding what I did: I formulated the problem as an optimization problem that maximizes the number of moves and solved it using professional software, choosing an algorithm that always finds the optimal solution (when run to completion). The difficulty was in modelling the problem in a smart way, so that the algorithm completes within our lifetime. The code is available on Github and Gurobi gives free non-commercial licenses - you can reproduce the result if you like. Perhaps even adapt the code and compute yourself a world record or prove something? :) Keep in mind that I ran this on a machine with an Intel 13700F (8 performance cores). On an older laptop (extreme case), it might need weeks or months to complete. Good news: Gurobi prints its progress to the terminal, so you can make an educated guess on whether it's gonna finish during your lifetime.
#58

Love this article :) did not expect to find computer science in my lichess.

Is it correct you make variables p[r,c,piece,color] for every row r, column c, piece, color, which is 1 if and only if [color] [piece] is on square ([r], [c])? Then how do you turn the LP relaxation (which, with these variables, might have multiple pieces on the same square) into an actual chess position while also guaranteeing that the # of legal moves of this position is still bounded by the objective value of the LP relaxation?

Also, I am confused about the second try and why Gurobi thinks it has 271 2/3 moves when you just gave it the redundant constraint that pieces cannot move over other pieces?

Finally, are the 12 witness positions you give at the end all possibilities with 218 legal moves? Or does Gurobi only give you a few samples?

Love this article :) did not expect to find computer science in my lichess. Is it correct you make variables p[r,c,piece,color] for every row r, column c, piece, color, which is 1 if and only if [color] [piece] is on square ([r], [c])? Then how do you turn the LP relaxation (which, with these variables, might have multiple pieces on the same square) into an actual chess position while also guaranteeing that the # of legal moves of this position is still bounded by the objective value of the LP relaxation? Also, I am confused about the second try and why Gurobi thinks it has 271 2/3 moves when you just gave it the redundant constraint that pieces cannot move over other pieces? Finally, are the 12 witness positions you give at the end all possibilities with 218 legal moves? Or does Gurobi only give you a few samples?
#59

You could also reduce your search space by always making sure that queens are on spots reachable by knights (since otherwise, they would overlap greatly) and I have a suspicion for knights they must also follow a similar line of thought. I think that should give it a speed boost, if you would like to try it again.

You could also reduce your search space by always making sure that queens are on spots reachable by knights (since otherwise, they would overlap greatly) and I have a suspicion for knights they must also follow a similar line of thought. I think that should give it a speed boost, if you would like to try it again.
#60

@strawberry_queen said in #58:

Love this article :) did not expect to find computer science in my lichess.

Is it correct you make variables p[r,c,piece,color] for every row r, column c, piece, color, which is 1 if and only if [color] [piece] is on square ([r], [c])? Then how do you turn the LP relaxation (which, with these variables, might have multiple pieces on the same square) into an actual chess position while also guaranteeing that the # of legal moves of this position is still bounded by the objective value of the LP relaxation?

Also, I am confused about the second try and why Gurobi thinks it has 271 2/3 moves when you just gave it the redundant constraint that pieces cannot move over other pieces?

Finally, are the 12 witness positions you give at the end all possibilities with 218 legal moves? Or does Gurobi only give you a few samples?

Hi!

thanks for reading my article

Yes, that's roughly how the model is modeled.
The code is available on Github, the link is in the article, it's in Python. Gurobi gives out free non-commercial licenses, you can run it, although it might take a couple days and your computer might be a bit noisy!

Regarding the LP relaxation: I don't turn it into anything! In fact, I don't even create it.

I model the problem with variables that are either 1 or 0, a linear objective (e.g. 3x+4y-2z) to maximize, and a lot of linear constraints (2x-7y+8z ≤ -3). I omit some difficult constraints for speed. This leads to some illegal solutions, but I just filter them out later.

This is a so-called integer linear program. Integer variables, linear constraints and objectives. Very hard to solve. I pass it to Gurobi, a commercial solver, and it uses a branch-and-bound algorithm. Which means that it branches on an integer variable, creating two new subproblems, then repeats recursively, ... until it can stop. For this, it uses the LP relaxation, which is the same as the original problem, but with the integer variables (either 0 or 1) being relaxed to 0 to 1. This extends the solution space by looots of fractional solutions, lots of them far better than the actual solution - but it is astronomically faster to solve. And it gives an upper bound since if a solution is the best of an LP, it's also the best of the corresponding ILP.

Does that clarify things? :)

The core of the article is about improving the model formulation to make the solution space nicer and cut off at least some of those ridiculously too good LP solutions. This gives us far better bounds, e.g. 271 2/3 instead of ~305.0 moves at the root node of the brand-and-bound tree.

The 12 positions are representative of the ~40,000 mirrored solutions. I made Gurobi output all solutions with 218 moves, then did some scripting to confirm my suspicion that there really are only 12 positions and that the rest is mirrored or slightly varied.

Hope I could help!

@strawberry_queen said in #58: > Love this article :) did not expect to find computer science in my lichess. > > Is it correct you make variables p[r,c,piece,color] for every row r, column c, piece, color, which is 1 if and only if [color] [piece] is on square ([r], [c])? Then how do you turn the LP relaxation (which, with these variables, might have multiple pieces on the same square) into an actual chess position while also guaranteeing that the # of legal moves of this position is still bounded by the objective value of the LP relaxation? > > Also, I am confused about the second try and why Gurobi thinks it has 271 2/3 moves when you just gave it the redundant constraint that pieces cannot move over other pieces? > > Finally, are the 12 witness positions you give at the end all possibilities with 218 legal moves? Or does Gurobi only give you a few samples? Hi! thanks for reading my article Yes, that's roughly how the model is modeled. The code is available on Github, the link is in the article, it's in Python. Gurobi gives out free non-commercial licenses, you can run it, although it might take a couple days and your computer might be a bit noisy! Regarding the LP relaxation: I don't turn it into anything! In fact, I don't even create it. I model the problem with variables that are either 1 or 0, a linear objective (e.g. 3x+4y-2z) to maximize, and a lot of linear constraints (2x-7y+8z ≤ -3). I omit some difficult constraints for speed. This leads to some illegal solutions, but I just filter them out later. This is a so-called integer linear program. Integer variables, linear constraints and objectives. Very hard to solve. I pass it to Gurobi, a commercial solver, and it uses a branch-and-bound algorithm. Which means that it branches on an integer variable, creating two new subproblems, then repeats recursively, ... until it can stop. For this, it uses the LP relaxation, which is the same as the original problem, but with the integer variables (either 0 or 1) being relaxed to 0 to 1. This extends the solution space by looots of fractional solutions, lots of them far better than the actual solution - but it is astronomically faster to solve. And it gives an upper bound since if a solution is the best of an LP, it's also the best of the corresponding ILP. Does that clarify things? :) The core of the article is about improving the model formulation to make the solution space nicer and cut off at least some of those ridiculously too good LP solutions. This gives us far better bounds, e.g. 271 2/3 instead of ~305.0 moves at the root node of the brand-and-bound tree. The 12 positions are representative of the ~40,000 mirrored solutions. I made Gurobi output all solutions with 218 moves, then did some scripting to confirm my suspicion that there really are only 12 positions and that the rest is mirrored or slightly varied. Hope I could help!