Hi Weston, I is only necessary to store a table with 1 bit per position, either it's a win or a loss (I'm assuming Chinese rules with some fixed komi.)
If you want to be more complete, you can store just the score of each position in the table - just 9 bits per position. If you only care if it's "close" but still want some scoring resolution, you store 3 or 4 bits per position. To choose a move, you do a 1 ply search and look up the resulting score in the table - in this way you get a more flexible table - you can locate all the best moves of equal value for instance - or even locate the worst move(s) on the board. - Don On Wed, 2007-01-24 at 20:14 -0500, Weston Markham wrote: > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
