zullil wrote:I wish you luck.
See if you can find the answer---with proof--- for N=2.
I think I have found a step in the right direction.
JONATHAN SCHAEFFER AND ROBERT LAKE wrote: A search space of 10^18 still seems impossibly large. If 10^6 positions were solved per second, 100,000 years of computing would be required to enumerate all the positions. What makes the problem of finding the game-theoretic value of checkers feasible is the idea of a proof tree. When analyzing a position that is a win, one need only consider one winning move; the alternatives moves are either inferior or redundant. When considering a position that is a loss or a draw, all alternatives must be considered (since you have to prove you cannot do better). In the best case a game that is provably winning the search only has to explore roughly the square root of the search space: a single move at winning positions and all moves at losing positions. This means that a proof of the game-theoretic value of checkers might require a search of as few as 10^9 positions. Of course, knowing which 10^9 positions out of 10^18 is the hard part.
I'm wondering if either of the authors post here or on other boards. It would be nice to get a little more information about these thoughts. Although they don't mention the number of nodes in a proof tree if the proof can be found by searching 10^9 nodes in checkers it seems that the proof tree couldn't have more nodes in it than that.
If their supposition is true, it has several useful implications. One of these is the calculation is not based on the depth of the mate or the branching factor of the various positions in the proof tree. This simplifies the analysis greatly. For many positions the estimate will still be "loose" but this is considerably better than the other method. It means that no proof tree in chess can have greater than 10^21.5 nodes in it. (This statement assumes Shannon's estimate for the total number of positions possible in chess is correct.) So any proof tree of a mate would have this upper bound regardless of length of mate or branching factor.
This number, 10^21.5 is based on the total number of positions that are reachable from the standard chess starting position. It can be shown that for any position in which pawns have been moved or any number of pieces or pawns have been captured that the number of positions that can be reached is significantly reduced. For example, approximately 2.41E+36 position can be reached from this position, which is 15 plies into the game:
[D]rnbqkb1r/pp3ppp/4p3/8/3PP3/8/P4PPP/1RBQKBNR b Kkq - 0 8
So the maximum size of proof tree starting at this position would have at most 1.55E+18 nodes in it if this idea is correct. This position which has the same material content:
[D] 2bqr1k1/r4p2/p3p2B/npb3P1/2p4p/P1N1PB2/1P2QPP1/2R1K2R b K - 0 22
would have different numbers, namely ~1.88E+34 reachable positions and a maximum proof tree size of ~1.37E+17 nodes. The difference in these numbers is a result of the second position having a more advanced (meaning degraded) pawn structure.
This may not look like its much of an improvement, and for these positions it isn't. But as more pawns advance and more pieces are removed from the board the number of reachable positions are significantly reduced and the square root of this number will become a usable bound in many but not all cases.
In a case were there is a long mate but not too much material this will give a much better estimate than the formula you gave. In a case where the mate isn't too long but there is a lot of material on the board the iterative formulae may give a better estimate. In the mate in 549 moves taken from the Lomonosov table bases this method is a huge improvement. There are, if my math is correct, less than 1.4E+13 positions possible given the material available. This implies that a proof-tree of this mate will contain ~3,744,857 or fewer nodes. This is a huge number of orders of magnitude less than the other formula gives.
It's not much but it's a step in the right direction and all I had to do was a little reading. A little more research seems to be in order.
I guess one way to test this theory is to check it against the table bases. If none of the poof trees included in or that can be constructed from the table bases exceeds the square root of the total number of positions possible with the given material then this would lend some support that this idea is correct. It won't prove it obviously, but if any of the proof trees are significantly larger than the square root of the total number of positions possible this would be sufficient to show the idea is flawed if no smaller proof tree can be found.
An alternate way to test it is to use a program such as Ben's to generate a proof tree for the position from the Lomonsov table bases (or other positions from smaller table bases). If the number of nodes in the proof tree is less than or equal to 3,744,857 then this would seem to be good evidence that the idea is a good one. If the number of nodes in the proof tree is greater than 3,744,857 then one would need to check to see if a smaller proof-tree can be found. If no smaller tree can be found I think it would be safe to discard the idea in its current form.
I don't know about getting access to the Lomonosov table bases. It seems improbable that this could be done over the internet but someone that has more direct access to them may be able to do the tests.
Of course there are probably some positions from the 5 or 6 man table bases that have long mates that would be easier and quicker to test. These would make a good first start towards a determination of the validity of this idea.
So Ben,
What do you think about trying your program on a few positions taken from the 5 and 6 man table bases? Preferably the longest one they contain. And possibly working your way up to the longest 7-man mate?
Regards,
Zen
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.