| |
BGonline.org Forums
Colorless Counting--A clever concept
Posted By: Timothy Chow In Response To: Colorless Counting--A clever concept (Bob Koca)
Date: Thursday, 27 December 2012, at 6:29 p.m.
You mean in Othello? Othello is fairly close to being "solved." It's certainly possible to solve Othello positions with about 35 empty squares (I'm not sure what the exact state of the art is). So we can generate (and have generated) reams of examples of perfect play, and near-perfect play. Mathematically, it is not ruled out that there could be some amazing new concept that somehow organizes all that data and allows you to "understand" it. If you try this, however, you'll quickly develop a sense that this is just not in the cards. I seem to recall that generalized Othello is PSPACE-complete, so if you believe that P ≠ PSPACE, that's pretty strong circumstantial evidence that perfect play (or even approximately perfect play) is completely intractable. Existing heuristics take the top players pretty close to perfect play in many cases, so pushing closer to the limit is probably going to push against the intractability barrier.
You get the same sense from examining solved chess endgames. If you look at the current records for the longest forced wins, the moves on both sides are (superficially at least) indistinguishable from random. Generalized chess is EXP-complete, and we can actually prove that P ≠ EXP. So it's highly unlikely that we'll be able to "explain" these kinds of endgames conceptually. Now in chess we're farther from "solving" the game than we are in "Othello," so there is still some small chance of a major conceptual advance. None of the top players show any hint of finding such a thing, though, so I'm extremely skeptical.
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.