Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
If each player has n choices (here 5) then there are two upper bounds, both of which are functions of n. For most n, (n^2/4) is the larger, but for some it's the other bound. These two functions emerge from the graph theory.
@Gerry thanks for your response. I hope you can "move to my page". 25/4 is one upper bound (there's another) for the 2 bishops game. How about the set of 49 positions 1. a4 a5 2. Ra3 Ra6 3. R~ R~? This approach won't solve chess, but I do suspect that there should be a general result about why this kind of approach is not able to prove that a symmetric loopy game is not a second player win. I showed this problem to Elwyn Berlekamp a long time ago, and he thought it was cool, but had no idea either how to generalize
My guess is that there must be some kind of "consistency protection theorem" which implies you can't use this kind of strategy stealing in loopy games to prove that the second player does not have a win. Surely someone must have looked at this already?
@GerryMyerson. And another year has passed. This has been an object lesson to me about the difficulties in getting anyone to read what someone has actually written, rather than skipping to a preconception about what they must be saying. Have you figured out the solution to the 2 bishops problem? Isn't it interesting that the number N = 25/4 emerges? What would it take in a game's structure for this kind of reasoning to suffice to solve the entire game? If N dipped below the number of White choices, then there would be a White move which denies Black a win. Or is this impossible?
@PeterTaylor "L" stands for Läufer, which is bishop. Sorry about failing to translate. I've fixed. The other German pieces are König, Dame, Turm, Springer and Bauer. Please have a go at this puzzle, then you can see where I am trying to go with this question
Natch is a really good program: one of the fastest around at its chosen task. The chess problem database PDB contains 1350+ proofgames validated by Natch. These include some with over 60 single moves. Hence I myself wouldn't have selected the word "purport" to describe its capabilities.
My answer in chess.stackexchange.com/questions/33347/… to compute the number of legal collections to be 58,084,310. This matches a prior table computed by Kryukov, so I can now go on to the "extra credit" challenge of distinguishing the bishops