» List all forums
» » Forum: Piratical Parley and Politics
» » » Thread: Botting
» » » » Post: Re: Botting
Print at Aug 21, 2019 5:56:52 PM
|Posted by tanonev at Mar 26, 2012 1:13:53 PM|
Editorial note: There is a delicate balance here between explaining enough to be enlightening about the situation and explaining so much that others would be encouraged to bot the puzzle. To ensure I don't disrupt the balance, I'm going to talk about very different problems in some detail and only talk about carpentry in very vague terms. For reference, I've seen a bot in action that almost never does worse than MP15, and I know it doesn't look ahead at unseen pieces. Thankfully, it's not "in the wild" because the author is an academic (he entered thesis procrastination mode for a while, and suffice to say carpentry is a much easier problem than a PhD thesis problem in computational genomics).
The main issue with your analysis is that you're assuming you have to use some variation on brute force to solve carpentry with a computer. The thing is, you don't; it turns out there's some extra structure to the problem that allows you to cut out an exponential number of possibilities. Let's consider a classic problem: finding the shortest path between two points on a map of roads. Sure, there's an exponential number of paths (sequences of roads) between those two points, but it turns out that this is an easy problem to solve because you can show the optimality of a subpath, namely, that if the shortest path from A to B passes through C, then it includes the shortest path from A to C and the shortest path from C to B. This means that you can solve the subpath problem first, and use that information to solve the original problem. In fact, you can solve the subpath problem by looking at subpaths of subpaths, which implies building up a hierarchy of paths based on length. Now, an interesting observation is that the longest path problem is NOT an easy problem. Again, there are the same number of possible paths, but the difference is that there is no (known useful) decomposition into subproblems for which we can prove optimality.
So in order to claim that carpentry isn't an easy problem, it isn't sufficient to just show that the number of possible moves is large; you have to show that there isn't some additional structure to the problem that allows you to solve a small number of easy subproblems and combine them together to obtain solutions to the whole thing. As it turns out, there are two structural properties of carpentry that allow this massive amount of simplification. One is the obvious "if you have two holes of the same shape, they can be solved the same way, regardless of what you did to get the hole to be that shape." This allows the construction of what's known as a dynamic programming table (I'm NOT giving the details on how to construct this specific table), which allows you to "consider millions of moves" with a single lookup. The other is a property that can't be proven (omitted for safety), but just turns out to be true often enough in practice. This property allows you to create an approximation of the game where the holes on the board are completely independent of each other, which means if you can solve a single hole in a reasonable amount of time, then you can solve X of them with only an X-fold increase in time (which is tiny). So now this boils down to the following question: Can I play out all the possibilities for a single hole in a reasonable amount of time, given that I can consider a million moves as a single operation? The answer turns out to be "close, but not quite," but there's one more trick (again omitted for safety) that becomes clear once you successfully construct and examine the aforementioned table.
Tanonev on all oceans; currently exploring Meridian.
Puppetar by Tilinka
Powered by mvnForum
mvnForum copyright © 2002-2006 by MyVietnam.net