Math Question

[Surlethe]

Ahah! I made a connection: the sequence of partial sums of \sum_{n=1}{1/n(n+1)} is the sequence of inverted tetragonal numbers. The reason this bothers me is I tried for a week several months ago to come up with a closed formula for the nth tetragonal number.

If you mean that the summation is of the recipricol triangular numbers (times a constant), then yes. How do you define tetragonal numbers? The sequence of partial sums a_n = \sum_{k=1}^n{1/k(k+1)} definitely does not tend to zero.

Tetragonal numbers are defined like 3D triangular numbers: the number of dots in the tetragon as you increase each side length by 1 dot per iteration.

...

And apparently, the nth triangular number is n+1_C_2. I did not realize that.

[Zadius]

I think you mean tetrahedral number. At least that's the term I'm familiar with.

[Surlethe]

I think you mean tetrahedral number. At least that's the term I'm familiar with.

Damn. You're right.

[Kuroneko]

Tetragonal numbers are defined like 3D triangular numbers: the number of dots in the tetragon as you increase each side length by 1 dot per iteration. And apparently, the nth triangular number is n+1_C_2. I did not realize that.

That doesn't quite make sense. Do you mean "tetrahedron" instead "tetragon", perhaps? Triangular numbers are C(n+1,2), yes; that would make tetrahedral numbers T(n) = \sum_{1<k≤n}{C(k+1,2)} = C(n,3).

[Surlethe]

*groan*

I can break \sum_{k=1}{1/k(k+1)} up into partial fractions, can't I? So then it's a telescoping sum \sum_{k=1}{1/k(k+1)} = \sum_{k=1}{1/k - 1/(k+1)} = 1.

And, in general, since every f(x) = c is a quadratic, I can factor that and sum it with partial fractions. Correct? Or do I need to establish each quadratic has two real roots?

[Kuroneko]

I can break \sum_{k=1}{1/k(k+1)} up into partial fractions, can't I? So then it's a telescoping sum \sum_{k=1}{1/k(k+1)} = \sum_{k=1}{1/k - 1/(k+1)} = 1.

Right.

And, in general, since every f(x) = c is a quadratic, I can factor that and sum it with partial fractions. Correct? Or do I need to establish each quadratic has two real roots?

In general, \sum_{k=1}^\infty{1/(k(k+m))} = H_m, the mth harmonic number. However, since not every number x in the form x = k(k+m) satisfies f(x) = m, except perhaps for very specific m (e.g., m = 0,1,2), there is a difficulty in computing the desired results. That is why I posed the problem in terms of an algorithm rather than a closed forumula, although ot may in fact be insurmountable for the general case either way.

[Surlethe]

In general, \sum_{k=1}^\infty{1/(k(k+m))} = H_m, the mth harmonic number. However, since not every number x in the form x = k(k+m) satisfies f(x) = m, except perhaps for very specific m (e.g., m = 0,1,2), there is a difficulty in computing the desired results. That is why I posed the problem in terms of an algorithm rather than a closed forumula, although ot may in fact be insurmountable for the general case either way.

Could one possible sieve out numbers which aren't in the sum?



Also -- completely irrelevant to the current thread -- is it possible to produce a mathematical description of the game of go? If so, is such a description feasible?

[Kuroneko]

Could one possible sieve out numbers which aren't in the sum?

Possibly. I would imagine this would require some considerations of quadratic residues, although they are notoriously hard to work with (with the notable exceptions of prime numbers).

Also -- completely irrelevant to the current thread -- is it possible to produce a mathematical description of the game of go? If so, is such a description feasible?

That's alright; it's an interesting question that others might not approve of having a thread on its own. In fact, this question has been an "almost-project" of mine for several years now, "almost" in the sense that somehow I never get around to studying it seriously despite telling myself that I would. Part of my interest in surreal numbers, which I have mentioned in another thread, was due to their applications in game theory. Conway's game theory defines a game as an ordered pair of other games, which are the positions available to the left and right players. This mimicks the recursive nature of surreals exactly, except that there is no requirement of left games (numbers) being less than the right ones. (If the game happens to be a surreal number, it indicates which player can, in theory, win regardless of how the opposing player behaves.) Applying this to go, however, isn't exactly easy--ko fights, for example, enable "game loops" that are quite pathological to model by these means. That was also partially the reason for my interest in hyperset theory, which replaces the foundation axioms (aka axiom of grounding aka axiom of well-foundedness) with one that is essentially equivalent to "every directed graph is isomorphic to some set" (thus enabling set-inclusion loops and other phenomena forbidden in classical set theory). There are interesting mathematics in attempting to mathematically model go, though I'm loath to make strong claims regarding its feasibility, since, as I've said, this interest of mine has never progressed past being an almost-project.

[Surlethe]

That's alright; it's an interesting question that others might not approve of having a thread on its own. In fact, this question has been an "almost-project" of mine for several years now, "almost" in the sense that somehow I never get around to studying it seriously despite telling myself that I would. Part of my interest in surreal numbers, which I have mentioned in another thread, was due to their applications in game theory. Conway's game theory defines a game as an ordered pair of other games, which are the positions available to the left and right players. This mimicks the recursive nature of surreals exactly, except that there is no requirement of left games (numbers) being less than the right ones. (If the game happens to be a surreal number, it indicates which player can, in theory, win regardless of how the opposing player behaves.) Applying this to go, however, isn't exactly easy--ko fights, for example, enable "game loops" that are quite pathological to model by these means. That was also partially the reason for my interest in hyperset theory, which replaces the foundation axioms (aka axiom of grounding aka axiom of well-foundedness) with one that is essentially equivalent to "every directed graph is isomorphic to some set" (thus enabling set-inclusion loops and other phenomena forbidden in classical set theory). There are interesting mathematics in attempting to mathematically model go, though I'm loath to make strong claims regarding its feasibility, since, as I've said, this interest of mine has never progressed past being an almost-project.

Interesting. From my rather naive and uninformed standpoint, it seems a "good move" in go could be modellable with a rather simple set of priorities, e.g.: how much space it stakes out vs. how much risk of invasion (essentially a maxmin problem); and the amount of material to be potentially gained. Then assign a function from Z² (gameboard) to R (move value) based on those two criteria, and you should have an effective map of the values of each possible move. Given a sufficiently strong computer, it should be able to number-crunch through the possible moves by assigning deeper calculations to the stronger lines of play.

I'm not sure how this ties in with the deeper mathematics you've mentioned, though.

[Kuroneko]

Interesting. From my rather naive and uninformed standpoint, it seems a "good move" in go could be modellable with a rather simple set of priorities, e.g.: how much space it stakes out vs. how much risk of invasion (essentially a maxmin problem); and the amount of material to be potentially gained.

You simply assume that the holy grail of computer go has been found? This is not simple, and attempts at doing so have given decidedly poor results.

I'm not sure how this ties in with the deeper mathematics you've mentioned, though.

The point of the mathematics is very simple--how does one determine how much space a stone stakes out and how dangerous invasions are? As for the rest, surreal numbers have a kind of minimax principle built-in into them. By definition, a number x = {L|R}, where L and R are other numbers is the 'simplest' number (this can be specified more precisely) larger than all in L and smaller than all in R. Thus, if there is an l in L that is not maximal, it may be omitted without changing the value of x, and this is obviously mirrored for R. In game terms, if the left player does no better in the subgame l than some other game in L, it may be removed from the game tree as irrelevant--a minimax principle. Conway's games are not guaranteed to be numbers, but the same principle still holds. (To correct a possible mischaracterization of the surreal connection, Conway's interest was actual games first--the numbers fell out as a particularly interesting subclass that is also simpler to study. Incidently, Conway made his theory with specific interest in go endgames.)

[Surlethe]

Interesting. From my rather naive and uninformed standpoint, it seems a "good move" in go could be modellable with a rather simple set of priorities, e.g.: how much space it stakes out vs. how much risk of invasion (essentially a maxmin problem); and the amount of material to be potentially gained.

You simply assume that the holy grail of computer go has been found? This is not simple, and attempts at doing so have given decidedly poor results.

What's the flaw in my reasoning? Is it simply there is no simple way to model those priorities, or are the priorities flawed?

The point of the mathematics is very simple--how does one determine how much space a stone stakes out and how dangerous invasions are? As for the rest, surreal numbers have a kind of minimax principle built-in into them. By definition, a number x = {L|R}, where L and R are other numbers is the 'simplest' number (this can be specified more precisely) larger than all in L and smaller than all in R. Thus, if there is an l in L that is not maximal, it may be omitted without changing the value of x, and this is obviously mirrored for R. In game terms, if the left player does no better in the subgame l than some other game in L, it may be removed from the game tree as irrelevant--a minimax principle. Conway's games are not guaranteed to be numbers, but the same principle still holds. (To correct a possible mischaracterization of the surreal connection, Conway's interest was actual games first--the numbers fell out as a particularly interesting subclass that is also simpler to study. Incidently, Conway made his theory with specific interest in go endgames.)

Is an opening analysis more difficult than an endgame analysis, or vice versa?

[Kuroneko]

Opening analysis is much more difficult. Endgames tend to be decompose into many disjoint but much smaller subgames that could be handled fairly easily on a computer, since for small games the computer can afford to use brute force. Of course, the subgames are still interrelated in the sense that playing in one means one has to pass on another, but there is actually a fairly well-defined mathematical theory as to how such decisions should be made. Engames are probably the only part of go in which computers can actually be better than professional players. (Of course, that doesn't help if by the time of the endgame, one is hopelessly behind.)

The brute force approach is based on a very simple premise: if one looks deeply enough into the game tree, the optimal or near-optimal move will be obvious even to a computer. That's true enough, but there are simply too many moves in a go game. To deal with this, certain strategic rules of thumb can be used--for example, "corners > sides > center" is a very good strategic principle for securing potential territory that will keep a computer from spending unnecessary time looking into bad moves. The problem, however, is that generally speaking such rules of thumb are only vague and intuitive--they all have exceptional situations, some more than others, and may even conflict with one another at times. In short, one can either have a simple evaluating function but look very deep into the game tree or look only on the surface but using a very complicated "intuitive" evaluating function. Neither alternative is good for the computer: the former can be modelled but is completely intractable, while the latter is somewhat tractable if it can be modelled, which has so far proven to be an 'if' too difficult to overcome. Go programs tend to be vulnerable against same tricks over and over again, which is particularly maddening if the trick involves what would be very bad moves against a human player.

As for your list of priorities, it's a good list as long as they are not claimed to be hierarchial, except possibly in the endgame. For example, the relatively value between immediate territory and potential territory (influence, moyo) varies. In the opening, moyo is generally much more important--one can easily gain a good chunk of territory right away, but that won't help you all that much if the opponent gains a moyo many times larger than your territory in the meantime.