Evaluation Using Flow Graphs

[towforce]

This idea popped into my head about an hour ago, and it's not fully formed, but how about creating a flow graph for a chess position?

Here's a sample flow graph:



* generate lookup tables for each chess piece for how many moves it takes to move to every square from every other square. From a single piece on an empty board on any square, you could then see how many moves it would take to reach any other square.

* for each piece in the chess position, start by making a weighted graph from the lookup table. Each vertex on the graph would represent a single square on the chess board that the piece could reach

* on each pieces' graph, calculate, from the other pieces' graphs, the resistance at each step in getting close to where the opponent king can get to (weighted by the cost of that king getting to each square on the board)

* opponents pieces' graphs would create resistance to your own pieces graphs (as would, to a lesser extent, your own pieces)

There would be a lot of circular expressions in this set of expressions (X depends on Y, Y depends on Z, Z depends on X), but getting to balance in circular expressions can be done quickly using various methods.

The move to choose would be the one that gives maximum flow to squares close to the opponents king and minimum flow for opponents pieces to get to your king.

[MonteCarlo]

It's an interesting thought, and I would be curious to see how such an approach played, regardless of its strength (which I suspect would not be so good).

Something like this was the best performing approach to Hex for a while (15-20+ years ago), but has since been superseded by other approaches even there, where it seems more apt to begin with.

Cheers!

[Henk]

This idea popped into my head about an hour ago, and it's not fully formed, but how about creating a flow graph for a chess position?

Here's a sample flow graph:



* generate lookup tables for each chess piece for how many moves it takes to move to every square from every other square. From a single piece on an empty board on any square, you could then see how many moves it would take to reach any other square.

* for each piece in the chess position, start by making a weighted graph from the lookup table. Each vertex on the graph would represent a single square on the chess board that the piece could reach

* on each pieces' graph, calculate, from the other pieces' graphs, the resistance at each step in getting close to where the opponent king can get to (weighted by the cost of that king getting to each square on the board)

* opponents pieces' graphs would create resistance to your own pieces graphs (as would, to a lesser extent, your own pieces)

There would be a lot of circular expressions in this set of expressions (X depends on Y, Y depends on Z, Z depends on X), but getting to balance in circular expressions can be done quickly using various methods.

The move to choose would be the one that gives maximum flow to squares close to the opponents king and minimum flow for opponents pieces to get to your king.

What about markov chains.

[towforce]

What about markov chains.

As it happens, there's a video about Markov chains in chess. As a bonus, it's presented by a pretty girl! Link.

Looking at that video, it looks as though there's some similarity between Markov chains and flow graphs. However, in the video, only one piece was moved: I can see it getting a lot more complicated when there are a lot of pieces moving.

Another thing is, we're not really interested in the probability of a piece moving to a particular square: we're interested in the resistance to it getting there.

[Collingwood]

As a bonus, it's presented by a pretty girl!

I won't try to predict whether Kelsey Houston-Edwards would be happy about your comment.

[towforce]

It's an interesting thought, and I would be curious to see how such an approach played, regardless of its strength (which I suspect would not be so good).

There could be some negatives:

* it might turn out to be more difficult than expected to get the modelled flows to each king close to reality

* it might lead to an attack against an opponent's king which is not successful - and this could then leave a losing position

Still, for a long time I've had this nagging feeling that chess must be mathematically solvable - that there must be a way to determine which side is winning without generating a game tree. The essence of chess is maximise access to the opponent's king while minimising access to your own king.

[Henk]

Feeling is worthless for this. Needed is introverted intuition. I don't have it conscious.