3 ms·
Sometimes with this sort of thing you can exploit symmetry in the game board to reduce the amount of work you need to do. I don't know enough about Go (or anyt
by jeffreyrogers 12y ago
Sometimes with this sort of thing you can exploit symmetry in the game board to reduce the amount of work you need to do. I don't know enough about Go (or anything at all really) to say if that's possible or not in this situation, but it is probably worth looking into.
I agree though, this does seem like the type of problem that should have a relatively simple solution, or at least a reasonable approximation.
- tromp 12y agoWe have excellent approximations; for 19x19 the number is known to be approximately 2.081681994 * 10^170. Getting the exact number is the big challenge. You can see in the paper that we spent a lot of effort on reducing the complexity of the counting problem. We welcome suggestions for further improvement, but suspect our current algorithm (counting paths in the border state graph) is already close to optimal.