Re: computer-go: 5 x 5 perfect play

[Jeffrey Rainy <JRainy@xxxxxxxxxxxx>]

Mitchell Timin wrote:
>Of what value is the number 2^25?  That doesn't seem relevant to me.  A

2^25 is an ( inexact ) estimate for the number of possible board position. Hence, 
it is an estimate for the memory requierement of an exhaustive search, with 
hashing.

25! is an ( inexact ;-) ) estimate for the number of different posible games. It looks 
to me like a measure of the time complexity for an exhaustive search without 
hashing.

In the second case, if you use a hash during your exhaustive search, you should 
not get a complexity of 25!, since many positions will be identical, yelding 
something more like 2^25. 

An optimal AI just needs about 2^25 positions labeled with a winning or losing 
tag. Also, since it would play deterministically, it only needs labels for the position 
that would be reached when playing against it. This is a very limited subset of the 
2^25 boards.  I think the 2^25 positions would still have to be generated during the 
exhaustive search, though.

Jeff.