Re: computer-go: 5 x 5 perfect play

[Tristan Cazenave <cazenave@xxxxxxxxxxxxxxxxx>]

Hi,

3^25 = 847 288 609 443 positions for the index, one bit per position
gives (3^25)/8 = 105 911 076 181 octets. Therefore 100 Go is enough if
you only have one bit per position. One bit per position is enough if
you assume you know the score at the end which should be around 25 for
Black (depending on rules). So solving 5x5 Go with retrograde analysis
on a current PC looks doable from a memory point of view. I suspect the
program will be bound by the I/O on the disk.

I am interested in understanding why you use 2^25 instead of 3^25.

Jeffrey Rainy a écrit :
> 
> >I just wanted to ask if perfect play on 5 x 5 boards has been solved. It
> >seems
> >within the realms of computability (2^25 is something my desktop PC
> >computer
> >can handle, I think).
> 
> I've only seen papers about 4x4 being proved. (2000)
> http://homepage1.nifty.com/Ike/katsunari/paper/4x4e.txt
> 
> Also, 2^25 is not the actual number of possible 5x5 board positions. On one hand,
> the capture rule lowers this number a lot. On the other hand, the ko rule raises this
> number somehow. But that is just nitpicking ;-)
> 
> Jeff.