shapes vs formations

[jts]

Right, and that's exactly the problem with your approach - no chain of stones is good or bad per se without understanding where the enemy stones are. A chain of 8 stones in a 4x4 sub-grid with no neighboring stones is always a mistake. So the problem with giving heuristics is precisely to get the machine (or the man) to identify the interactions between individual stones, not the gross silhouette of the stones. It's not worthwhile for an AI to identify, oh idk, chains with prime numbers of stones if factoring the chain isn't part of the game.

For example we remember the "broken shape" sub-pattern and look for it as an element of larger groups. It's not always bad for the broken group, but the prima facie evaluation that it is often bad makes it worth recognizing and studying.

You could compare it to looking for patterns in the configuration of oxygen atoms while ignoring the presence or absence of any other element. That's pretty silly! There are configurations of oxygen that are impossible without other elements to bind it into place, and the pattern to recognize is the molecular structure as a whole.

[billywoods]

The question is, how do you store these patterns in a kind of database efficiently

Perhaps I've misunderstood: you want to store tens of thousands of patterns, rather than 361 stones? Where's the computational benefit? How does storing patterns help you, say, read faster, or read fewer moves? (I agree that hard-wiring bulky fives, L-groups and snapback shapes into a bot's mind would be nice, if that's what you mean, but I don't think that has anything to do with your original question.)

[dohduhdah]

The question is, how do you store these patterns in a kind of database efficiently

Perhaps I've misunderstood: you want to store tens of thousands of patterns, rather than 361 stones? Where's the computational benefit? How does storing patterns help you, say, read faster, or read fewer moves? (I agree that hard-wiring bulky fives, L-groups and snapback shapes into a bot's mind would be nice, if that's what you mean, but I don't think that has anything to do with your original question.)

How would storing 361 positions for stones in a database help a bot learn go from practice?
Seems more sensible to store a database of patterns somewhat similar to a collection of tens of thousands of patterns
as you can find them on the gochild tsumego website for instance. My original question was about patterns and seeing if
we can understand these patterns in terms of fundamental concepts (like chains and formations) that might allow
one to store patterns in a more efficient fashion, rather than just storing patterns as they occur without employing
any underlying patterns at a higher level of abstraction that characterize whole ranges of patterns.

[dohduhdah]

Right, and that's exactly the problem with your approach - no chain of stones is good or bad per se without understanding where the enemy stones are. A chain of 8 stones in a 4x4 sub-grid with no neighboring stones is always a mistake. So the problem with giving heuristics is precisely to get the machine (or the man) to identify the interactions between individual stones, not the gross silhouette of the stones. It's not worthwhile for an AI to identify, oh idk, chains with prime numbers of stones if factoring the chain isn't part of the game.

For example we remember the "broken shape" sub-pattern and look for it as an element of larger groups. It's not always bad for the broken group, but the prima facie evaluation that it is often bad makes it worth recognizing and studying.

You could compare it to looking for patterns in the configuration of oxygen atoms while ignoring the presence or absence of any other element. That's pretty silly! There are configurations of oxygen that are impossible without other elements to bind it into place, and the pattern to recognize is the molecular structure as a whole.

No it's not, because the point is that more complicated patterns (like patterns where stones of multiple
colors are involved, like a ladder pattern) can be understood in terms of more fundamental patterns (like
chains or formations).
Your argument is like saying to people who study language that there is no point in classifying words into categories
of verbs or prepositions, since it doesn't make sense because words occur in sentences and nobody just utters a
preposition without the context of a sentence.

To understand things, you often look for the most fundamental patterns, even if purely for theoretical purposes.
Take quarks for instance, you can't even have a single isolated quark. It's impossible. But that doesn't mean it's
pointless to think of matter in terms of quarks and leptons (as more fundamental constituents of atoms).

[billywoods]

a collection of tens of thousands of patterns
as you can find them on the gochild tsumego website for instance

But, the stronger you get, the less those patterns crop up. In the same way, you can't learn tesuji from studying professional games, because no professional will allow themselves to get into a situation where a tesuji can be effectively used against them.

My real objection is: what do you propose this bot will do when its opponent plays something that's not in any predetermined pattern? Presumably it needs to do things like weigh up influence vs. territory, look for weaknesses, read, or something like that - something that it can't do using patterns alone if there are no familiar patterns to exploit.

[Bill Spight]

Well, not just as a pure math problem. More as a kind of exploration of certain concepts that delineate
certain classes of patterns. This is not intended as a way to figure out how to play go in any optimal
fashion from the perspective of a human player, but more of a way to figure out all possible ways one
can play go from the perspective of a bot.
Try to imagine yourself as a bot that plays go, initially knowing only the rules of go and making
random moves.
After each game, you analyze what happened during the game and you try to memorize certain patterns
that occurred during the game. Bad patterns (you might want to recognize those so you know what
patterns to avoid) as well as good patterns.
The question is, how do you store these patterns in a kind of database efficiently, so you can quickly
look up a pattern in that database.

You might contact Frank de Groot. You might also try the computer go mailing list.

[dohduhdah]

a collection of tens of thousands of patterns
as you can find them on the gochild tsumego website for instance

But, the stronger you get, the less those patterns crop up. In the same way, you can't learn tesuji from studying professional games, because no professional will allow themselves to get into a situation where a tesuji can be effectively used against them.

My real objection is: what do you propose this bot will do when its opponent plays something that's not in any predetermined pattern? Presumably it needs to do things like weigh up influence vs. territory, look for weaknesses, read, or something like that - something that it can't do using patterns alone if there are no familiar patterns to exploit.

Well, you start out with simple patterns and gradually you work your way up to more advanced patterns or patterns
at higher levels of abstraction. A concept like atari or snapback is fairly concrete and rather elementary, while
concepts like influence or weakness are more abstract and advanced.

If the bot encounters opponents that play something that's not in any predetermined pattern, the bot can just
play random moves and afterwards try to learn new patterns from the game until it comes up with patterns that
match up with those moves it hadn't encountered previously.

The idea of a learning bot is that you only program certain general methods for the way it can extract patterns
from the games it plays, and to supply it only with the rules and the ability to assess the status of groups
at the end of the game. So the programmer doesn't teach the bot anything as far as go skills are concerned
and the goal for the bot is to come up with such knowledge autonomously, simply by gradually accumulating
patterns and occasionally generalizing a pattern or something along those lines. But in order for this to work,
you need a kind of formalism in terms of which it can memorize and manipulate patterns, which I think of
as higher-level patterns.

[Phelan]

Well, not just as a pure math problem. More as a kind of exploration of certain concepts that delineate
certain classes of patterns. This is not intended as a way to figure out how to play go in any optimal
fashion from the perspective of a human player, but more of a way to figure out all possible ways one
can play go from the perspective of a bot.
Try to imagine yourself as a bot that plays go, initially knowing only the rules of go and making
random moves.
After each game, you analyze what happened during the game and you try to memorize certain patterns
that occurred during the game. Bad patterns (you might want to recognize those so you know what
patterns to avoid) as well as good patterns.
The question is, how do you store these patterns in a kind of database efficiently, so you can quickly
look up a pattern in that database.

You might contact Frank de Groot. You might also try the computer go mailing list.

I'm not sure if you're being serious or not.

Edit: Well, not about the computer go mailing list. That's a good place to discuss this, as the developers probably discuss pattern storage there.

[dohduhdah]

Chains seem to coincide with the concept of polyominos at Wolfram Alpha:

http://i.imgur.com/YTIPpFs.jpg

[Yuc4h]

...which have no relevance whatsoever.

[Bill Spight]

...which have no relevance whatsoever.

You might be surprised.

[HermanHiddema]

Also, more generally, chains are what is known in graph theory as connected components.

[dohduhdah]

Also, more generally, chains are what is known in graph theory as connected components.

Do formations (i.e. a number of stones on the goban, none of which are touching each other) also have
an equivalent concept in graph theory?

Graph theory seems more about topological relationships. You can have a weight associated with an edge between
two vertices, but you can't really have a weight associated with a combination of vertices that are not connected
by an edge. In go, two stones can more or less be connected in one way when two stones are right next to each other.
But there are multiple ways for two stones not being connected. They can be at opposite sides of the goban
with a large distance between them, but they can also be relatively close to each other.

[billywoods]

Do formations (i.e. a number of stones on the goban, none of which are touching each other) also have
an equivalent concept in graph theory?

Sure, if the stones form an independent set. In general, you can call a stone 'isolated' if its connected component is just a single stone, and a 'formation' is a collection of isolated stones. I don't know to what extent this formalism helps...

Graph theory seems more about topological relationships.

I agree. (It would be interesting to ask graph-theoretic questions about go, though I don't know whether we'd learn much. )

[dohduhdah]

...which have no relevance whatsoever.

I think mathematics is relevant to go.

The abstract patterns of math are sometimes fairly similar to patterns in go:

http://i.imgur.com/AG2uCnv.jpg

This graphic is a way to depict the moebius function and one might wonder if there
are other ways to depict the moebius function in which all possible chains can
recursively be found (so given any possible finite chain, one would be able to
graph the moebius function in a finite number of recursive steps in such a way
that the chain pattern occurs in it).

http://www.wolframalpha.com/input/?i=moebius+function

The computer offers new possibilities to explore the patterns in go, for instance
a kind of time-lapse view of go by mixing up images in photoshop to visualize two
moments during a game (in the middle and at the end) simultaneously:

http://i.imgur.com/nOIGEPO.jpg

I'm interested in a mathematical approach to go, relating it to mathematical
concepts of combinations/permutations, symmetries, translations, reflections,
rotations, trees of game state progressions, etc.