to be fair, i'm not sure that this means much at all. for the 19x19 case in go, this could all just be wrapped up in some constant somewhere in front of someone's uber-clever code that takes advantage of the particulars of 19x19 go. similarly for chess on an 8x8 board.
perhaps this means that 9x9 code cannot be thrown at a 19x19 board and hope to have only a polynomial in (19/9) decrease in strength, but i haven't proven this. s. ----- Original Message ---- From: steve uurtamo <[EMAIL PROTECTED]> To: computer-go <computer-go@computer-go.org> Sent: Thursday, November 22, 2007 3:02:31 PM Subject: Re: [computer-go] The global search myth it's PSPACE-hard and EXPTIME-complete, although this is dependent upon the rules involved. i think that superko changes things a tiny bit. in any case, it's brutally difficult as the boardsize increases. JM Robson, The Complexity of Go. In Information Processing; proceedings of IFIP Congress, pages 413-417, 1983 is the reference from wikipedia and from: http://www.msri.org/publications/books/Book42/files/wolfe.pdf it's thanksgiving, but i'll track it down at the library over the holiday, s. ____________________________________________________________________________________ Be a better pen pal. Text or chat with friends inside Yahoo! Mail. See how. http://overview.mail.yahoo.com/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ____________________________________________________________________________________ Be a better sports nut! Let your teams follow you with Yahoo Mobile. Try it now. http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
