Re: computer-go: 5 x 5 perfect play

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

Jeffrey Rainy wrote:
> 
> >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.

If you're talking about state space it should be 3^25, not 2^25.
(history not included) The full game tree may even be larger. (BTW games
may take over 25 moves.)

Can your PC handle that?

Erik.