here's my attempt to talk about how a 9x9 algorithm should be expected to scale on a bigger board, and what limits we can expect to have on perfect algorithms. i'm kind've trying to bridge the divide here. maybe it's silly. hopefully the experts can correct me.
saying that doubling computer time won't result in a constant increase in skill at any particular task is another way of saying that there is a good exponential approximation to the effort function E(s) over some particular range (say, the early skill levels), but that after some point the effort function function will increase *more quickly* than the exponential approximation. (here E(s) is the effort for a particular algorithm to play at least as well as skill level "s".) one somewhat muddying fact is that both chess and go should belong to EXPTIME. this means that to find a winning move for a fixed board position at a fixed boardsize n will require O(2^p(n)) steps, where p is a polynomial in n. to play either game "perfectly" such that the algorithm would apply to a 19x19 board, or a 9x9 board, or a 13x13 board, or an NxN board would imply that you had constructed an algorithm with at least such a running time. Lets imagine that 9x9 go has been effectively* solved by some algorithm that we all love, called algorithm X. applying algorithm X unchanged to boardsize 13x13, we will find that it takes: 2^(p(13)) / 2^(p(9)) times longer to find "the best move" for a given board position. taking the log base 2 of this we find that the difference in the doubling constants between the different boardsizes is: p(13) - p(9) if the polynomial in question is linear, then we will still observe the same doubling phenomenon for a 13x13 board as we would have on a 9x9 board. if the polynomial in question is anything other than linear, we won't, although depending upon the coefficients involved in this term and smaller terms, it may be well-approximated, again, through some number of skill levels. mitigating factors: *effectively solved is my hand-waving way of not dealing with the fact that solving the game and winning against opponents of some fixed skill level are not the same problem. what this additionally means is that any algorithm with enough _encoded knowledge_ that applies to a fixed boardsize can play arbitrarily well (note that this neatly captures the case of a pure lookup table solution). so we have two competing ideas: one is that if i double the thinking time for my existing algorithm that works quite well at size 9 and get linear improvement, what will happen to the improvement for that unmodified algorithm on a larger board? the answer is that it will definitely get better, although it may no longer gain the same amount of strength with each doubling of cpu time, or for as far across the skill level range. the other idea is that if i encode enough knowledge about details that apply to one particular boardsize into my algorithm, i can reduce its running time by an arbitrary amount. an example would be a joseki library for 19x19 boards that wouldn't have existed (or even made sense) in the same form in the code of a 9x9 program. so anyone looking for an analytic solution that will perfectly solve go needs to cope with the fact that if it works great (in the running-time sense) for a 9x9 board, it might work quite a bit less well for a 13x13 board, and significantly less well for a 19x19 board. with no knowledge about the size of the _coefficients_ of the terms in the complexity function, the possibility still exists that for the board sizes in question, the complexity is dominated by terms much smaller than 2^p(n), and so all boardsizes and skill levels are easily approximated with the 'doubling technique' until n is large. s. ____________________________________________________________________________________ Get your own web address. Have a HUGE year through Yahoo! Small Business. http://smallbusiness.yahoo.com/domains/?p=BESTDEAL _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
