Where Does The Solution To Chess Lie?

[towforce]

My definition of a solution: the smallest (in terms of number of calculations) static evaluation function for a chess position, with no game tree generation, that will accurately tell you whether the position is a win, a draw or a loss for white.

A short while ago, I wrote this post - link - but when I started working out how to build the best fit curve, I realised that it's probably not going to work: very simply, in 512 dimensions, the gaps between data points are going to be too large - especially considering that chess can be sensitive: a tiny difference in a piece's position can easily be the difference between a win and a loss.

With simpler games (nim is my favourite example, because the solution rule is so simple - and could have been worked out by polynomial fitting if it hadn't already been known), it can be quite easy to work out the rules for evaluating a position, and it would be surprising if they didn't exist in chess - but knowing where they're likely to be, and hence designing the search well to look for them, would greatly increase the chances of finding them.

As I think about it, I think good places to look might be:

* relationships between pieces on the board
* proximity of pieces to edges
* proximity of pieces to corners

Of course, there's always the risk that, like physicists searching for the Grand Unification Theory (link), and like computer chess itself (getting computers to GM level at tournament time controls took a lot longer than most people thought it would in the early years), it's entirely possible that the smallest accurate solution expression could be absolutely huge, and entail doing a ginormous number of calculations, but my instinct is that it will be smaller than most people are expecting if we can find a good way to search for it.

[zullil]

My definition of a solution: the smallest (in terms of number of calculations) static evaluation function for a chess position, with no game tree generation, that will accurately tell you whether the position is a win, a draw or a loss for white.

A short while ago, I wrote this post - link - but when I started working out how to build the best fit curve, I realised that it's probably not going to work: very simply, in 512 dimensions, the gaps between data points are going to be too large - especially considering that chess can be sensitive: a tiny difference in a piece's position can easily be the difference between a win and a loss.

With simpler games (nim is my favourite example, because the solution rule is so simple - and could have been worked out by polynomial fitting if it hadn't already been known), it can be quite easy to work out the rules for evaluating a position, and it would be surprising if they didn't exist in chess - but knowing where they're likely to be, and hence designing the search well to look for them, would greatly increase the chances of finding them.

As I think about it, I think good places to look might be:

* relationships between pieces on the board
* proximity of pieces to edges
* proximity of pieces to corners

Of course, there's always the risk that, like physicists searching for the Grand Unification Theory (link), and like computer chess itself (getting computers to GM level at tournament time controls took a lot longer than most people thought it would in the early years), it's entirely possible that the smallest accurate solution expression could be absolutely huge, and entail doing a ginormous number of calculations, but my instinct is that it will be smaller than most people are expecting if we can find a good way to search for it.

But how would you prove that your expression's predicted 0, .5 or 1 is accurate? Without someone actually solving chess?

[towforce]

But how would you prove that your expression's predicted 0, .5 or 1 is accurate? Without someone actually solving chess?

IMO having a relatively simple evaluation function that produced the correct result in all known positions would likely be a stepping stone to the final proof: having the answer to a problem is normally a big help in working out the problem's underlying principles.

For example: suppose nim wasn't solved: your best fit polynomial would show you that there's a simple solution, and the simplicity of the solution (x+n in this case) would lead you to the inductive reasoning, which would be followed by a statement of the solution in natural language (obviously, dynamic programming (link) is a better way to solve nim than polynomial fitting - I am just using it as a simple example).

[zullil]

But how would you prove that your expression's predicted 0, .5 or 1 is accurate? Without someone actually solving chess?

IMO having a relatively simple evaluation function that produced the correct result in all known positions would likely be a stepping stone to the final proof: having the answer to a problem is normally a big help in working out the problem's underlying principles.

For example: suppose nim wasn't solved: your best fit polynomial would show you that there's a simple solution, and the simplicity of the solution (x+n in this case) would lead you to the inductive reasoning, which would be followed by a statement of the solution in natural language (obviously, dynamic programming (link) is a better way to solve nim than polynomial fitting - I am just using it as a simple example).

Why don't you first restrict to K+P vs. K? Once you've gotten that case, we can try something else.

[Pafifi]

I think there are several steps to the solution:
Step 1: Build an engine that will never lose on either color, or always win on a certain color, from the start position, against any opponent, including iteslf.
Step 2: If the engine never loses on either color, the ultimate solution may very likely be a draw. Then we test it on random positions against itself or any other opponents, when it should be able to achieve the following:
If it wins against itself, it will never draw nor lose to any opponent;
If it draws against itself, it will never lose to any opponent.
Step 3: Give it any position, it will tell if it is a wining, drawing, losing or invalid position. And it can defend its confidence against any opponent.
Step 4: If winning or losing, it can tell exactly how many moves left to checkmate, if both sides try their best. And presumably it will offer one possible PV. If drawing, it can also tell how many moves left to a compulsive draw if neither, one or both sides try their best to draw as quick or slow as possible.
Step 5: It can answer statistic questions asked by humans. For instance, exactly how long is the longest possible game with or without the 50-move rule? At a drawing position, which move will lead to a position that the opponent will most likely to make a losing mistake?
If we can one day make a machine at step 5, that is the ultimate solution, or the god, of chess.

[zullil]

I think there are several steps to the solution:
Step 1: Build an engine that will never lose on either color, or always win on a certain color, from the start position, against any opponent, including iteslf.
Step 2: If the engine never loses on either color, the ultimate solution may very likely be a draw. Then we test it on random positions against itself or any other opponents, when it should be able to achieve the following:
If it wins against itself, it will never draw nor lose to any opponent;
If it draws against itself, it will never lose to any opponent.
Step 3: Give it any position, it will tell if it is a wining, drawing, losing or invalid position. And it can defend its confidence against any opponent.
Step 4: If winning or losing, it can tell exactly how many moves left to checkmate, if both sides try their best. And presumably it will offer one possible PV. If drawing, it can also tell how many moves left to a compulsive draw if neither, one or both sides try their best to draw as quick or slow as possible.
Step 5: It can answer statistic questions asked by humans. For instance, exactly how long is the longest possible game with or without the 50-move rule? At a drawing position, which move will lead to a position that the opponent will most likely to make a losing mistake?
If we can one day make a machine at step 5, that is the ultimate solution, or the god, of chess.

And how will you verify Step 1. None of us lives very long. (Or has access ti every opponent!)

[zullil]

My definition of a solution: the smallest (in terms of number of calculations) static evaluation function for a chess position, with no game tree generation, that will accurately tell you whether the position is a win, a draw or a loss for white.
...

This simply sounds like replacing WDL table lookups with functional evaluations using variables derived from the position. But WDL tables are provably correct, by their recursive generation. Again, how would you ever prove your evaluation function is correct for all positions? Without some sort of tree generation/recursion?

[towforce]

My definition of a solution: the smallest (in terms of number of calculations) static evaluation function for a chess position, with no game tree generation, that will accurately tell you whether the position is a win, a draw or a loss for white.
...

This simply sounds like replacing WDL table lookups with functional evaluations using variables derived from the position. But WDL tables are provably correct, by their recursive generation. Again, how would you ever prove your evaluation function is correct for all positions? Without some sort of tree generation/recursion?

It depends on how complicated the solution turns out to be: if there's something about chess we've all missed that enables a simple evaluation to give accurate results, then humans might be able to work out why these rules determine whether a position is won, drawn, or lost.

If the solution turns out to be complex, with a large number of parts, then the next step would be to start thinking about writing some software to prove it from the expression (work out how humans do such proofs for simple games, and make the software very good at doing those things on a large scale).

[towforce]

Why don't you first restrict to K+P vs. K? Once you've gotten that case, we can try something else.

Thanks for the feedback - it's prompted me to have a good think: my first thought was that this is an excellent idea!

The problem is, there's a good chance it won't scale up: I was thinking in terms of a polynomial for each piece/square combination's relationship with every other piece/square combination. But an important part of what I want to do is to make the final polynomial as simple, with as few parts, as possible (my initial estimate was that the polynomial would have several hundred dimensions. Think of a polynomial with 3 dimensions:

x = 3y^2*4z^2*30y*5z + 4y^2*2z^2*3y - 2y^2*z^2*6z - 4z^2*30y*5z + 2z^2*2y*8z + 4y*3z - 5y + 2z + 44

Obviously there is some factorisation I can do above, but keeping things simple, the main thing I want to be able to do is be able to do the curve fit with as few expressions as possible. Removing some of the above expressions, I might get, for example:

x = 3y^2*4z^2*30y*5z + 2z^2*2y*8z + 4y*3z - 5y + 2z + 27

However, doing this risks losing some important information about the relationship of pieces on various squares, and if I get an endgame with a combination of pieces for which I have lost information, then my evaluation of positions in that endgame might be too inaccurate. Working with 3 pieces could miss this issue - but starting small is good: I want to be able to start small, but I want to work with a solution that can scale up.

So I need a different way of representing a chess position - one in which, as I fit all the sample positions, there is a chance that good knowledge of a very wide range of positions can emerge.

The proof that this is possible lies in what we know about human players: to become a human GM, you need good knowledge of about 50,000 patterns that can arise on a chess board. From this learning, emergent knowledge arises which enables you understand a huge variety of positions (not all: if you generate a random legal position with a lot of pieces, a GM will look at it and say that it "doesn't make sense").

We need a way of representing chess positions that doesn't require a study of every combination of pieces, each in a wide variety of different positions: I've thought about heat maps for the number of pieces for each side that can reach each square after 1..n moves (n probably doesn't need to be a high number). Pawns are messy because they move differently when they're taking an opponent's piece. But I have a nagging feeling that the same heat map could have different evaluations in different positions: if so, then we need more than just heat maps.

Working out a position representation that would allow curve fitting to capture what's important in chess without generating all piece/position possibilities could be the key to solving chess.

[towforce]

We need a way of representing chess positions that doesn't require a study of every combination of pieces, each in a wide variety of different positions: I've thought about heat maps for the number of pieces for each side that can reach each square after 1..n moves (n probably doesn't need to be a high number). Pawns are messy because they move differently when they're taking an opponent's piece. But I have a nagging feeling that the same heat map could have different evaluations in different positions: if so, then we need more than just heat maps.

Working out a position representation that would allow curve fitting to capture what's important in chess without generating all piece/position possibilities could be the key to solving chess.

Thinking, thinking, thinking...

* heat map for squares a piece can reach in the next 1..n moves

* heat map for squares pawns can attack in the next 1..n moves (pawn move squares are different from pawn attack squares)

* column number each piece is in (a..h, represented numerically as 1..8)

* row number each piece is in (1..8)

* value of each piece

* number of pieces each side has (this would be one factor that would amend the value of pieces. For example, highly mobile pieces have more value on a nearly empty board)

Given that I want the representation to be as simple as possible, and for as much knowledge as possible to be emergent, that might be sufficient for polynomial fitting to capture enough emergent knowledge about the deep relationships between these dimensions.

A quick estimate of how many dimensions the polynomial will need (n: number of moves ahead on the heat map):

Heat map 1: 64n

Heat map 2: 16n

Each piece's column: 32

Each piece's row: 32

Value of each piece: 32

Number of black pieces: 1

Number of white pieces 1

So maybe... 98 plus 80n? So at least 178 then.

Can anyone think of any important pieces of emergent knowledge that this representation of a chess position could not possibly capture?