On a slightly (but not much) more serious note: The proposal that elicited (for better or for worse) Alain's size-of-the-universe comment was not for a complete table of all possible board states, but rather a table of winning moves. I expect that most positions will have multiple winning moves, but only a single one would need to be stored. The table does not need to store anything for a position that cannot be reached by playing those selected moves.
I believe that this greatly reduces the size needed. I certainly don't know how much smaller, although someone may be able to come up with actual numbers for 5x5 and 7x7 games, and use an educated guess on how these will scale up to 19x19. My offhand guess is that this size is still _far_ greater than the meagre memory resources that were suggested in the original post. For what it is worth, I expect that it is also larger than the number of quantum states of one of Alain's eyelashes. I would guess that it is smaller, however, than 10^100 bits, which I believe is a common back-of-the-envelope number for the total information in the visible universe. One also has the freedom to pick and choose which winning moves to store. This can be used to maximize the overlap between the different stored variations. If you also take advantage of patterns within the table, you will certainly be able to compress it. (As has been mentioned already.) At the far extreme, of course, you only need one entry in the table for each of 282 possible moves, and a hash function that simply ... er, figures out which move to play. Or, one can strike a balance between these two extremes that gives an appropriate tradeoff between computation time and memory. I would guess that kami no itte would still be impossible on 32GB, 300Mhz. However, beating a professional dan player seems reasonable to me. Of course, Alain will still have a large enough lookup table that he will be able to beat it ... in the blink of an eye. Weston On 1/24/07, Don Dailey <[EMAIL PROTECTED]> wrote:
On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: > With 10^170 legal position for 19x19 what would be the size of this > table ? > I m afraid we cannot build it with all the matter in visible > universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a "turing machine" in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - Don
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
