Game of go: A complex network

Apr 16, 2012
From their network, the researchers obtained these patterns (each one with 9 intersections) which show the most frequent moves or combine strategic moves (these are patterns on which eigenvectors associated with three large eigenvalues from the weighted adjacency matrix of the graph are localized). The top line corresponds to the ten most frequent moves in go. The middle line isolates patterns most of which correspond to a well known situation in go, ko ('eternity'). In the bottom line, most of the patterns correspond to situations where chains of stones become connected. Black is playing at the cross. Credit: O. Giraud et B. Georgeot

Could computers ever beat the best go players? Although unthinkable at this stage, this could soon become possible, thanks to CNRS theorists. For the first time, two scientists from the Theoretical Physics Laboratory and the Laboratory of Theoretical Physics and Statistical Models, have applied network theory to a game of strategy. Their findings, published in the journal Europhysics Letters, should help to improve future simulation programs.

The study of has attracted increasing interest over the past few years, fuelled in particular by the development of communication and . This new research field is proving very useful for the description of complex systems such as social networks and the Internet. For instance, when is applied to the Internet, every page is a node and hypertext links are links between the nodes. However, this type of approach had never been contemplated for the study of games of strategy such as go or chess. These games, which have a very long history and millions of players around the world, are extremely difficult to model. Computer programs have only been able to beat chess champions since the last fifteen years, and are still unable to compete with top go players. 

Using a database containing around 5 000 games played by professional and amateur go players in international tournaments, Bertrand Georgeot from the Theoretical Physics Laboratory and Olivier Giraud from the Laboratory of Theoretical Physics and Statistical Models applied network theory to this game of strategy. They constructed a network whose nodes are local patterns on the board, while the vertices (which represent the links) reflect the sequence of moves. This enabled them to recapture part of the local game strategy. In this game, where players place their stones at the intersections of a grid consisting of 19 vertical and 19 horizontal lines (making 361 intersections), the researchers studied local patterns of 9 intersections. They showed that the statistical frequency distribution of these patterns follows Zipf's law, similar to the frequency distribution of words in a language. 

Although the go network's features resemble those of other real networks (social networks or the Internet), it has its own specific properties. While the most recent simulation programs already include statistical data from real games, albeit at a still basic level, these new findings should allow better modeling of this kind of board game.

Explore further: Everglades trail surveyed for cultural artifacts

More information: "The game of go as a complex network," Europhysics Letters, EPL 97, 68002 (2012).

add to favorites email to friend print save as pdf

Related Stories

'Civilization' lets Facebook players rule world

Jul 07, 2011

Facebook friends will be able to conspire together to rule the world in a free version of blockbuster "Civilization" strategy videogame crafted for the online social network. ...

Revealing how experts’ minds tick

Apr 04, 2011

Primates, particularly humans, are set apart from other vertebrates by more than a huge expansion of the cerebral cortex, the region of the brain used for thinking. The connection and coordination of the cerebral ...

What's the semantic organization of human language?

Aug 11, 2009

A Chinese semantic network with semantic (argument structure) annotation was built and investigated for finding its global statistical properties. The results show that semantic network is also small-world and scale-free ...

NASA releases new interactive space communications game

Oct 12, 2011

NASA has released an interactive, educational video game called NetworKing that depicts how the Space Communication and Navigation (SCaN) network operates. The release of the video game coincides with the close of World Space ...

Recommended for you

Secrets of dinosaur ecology found in fragile amber

18 hours ago

Ryan McKellar's research sounds like it was plucked from Jurassic Park: he studies pieces of amber found buried with dinosaur skeletons. But rather than re-creating dinosaurs, McKellar uses the tiny pieces ...

User comments : 31

Adjust slider to filter visible comments by rank

Display comments: newest first

Lurker2358
1 / 5 (3) Apr 16, 2012
Designing an algorithm to beat a human at a turn based game, or at the very least draw the human ever time, and without reading from a table of all possible games, will always be possible. It's just a matter of time.

I computer program should be able to find all possible moves and rank them, much like a chess algorithm.

Heck, this is even easier than chess, because there aren't complicated rules for different pieces. there is only one rule.

Somebody with a brain has just never bothered to make an algorithm.
antialias_physorg
4 / 5 (4) Apr 16, 2012
I computer program should be able to find all possible moves and rank them, much like a chess algorithm.

Such brute force algorithsm aren't possible for go (because the number of possible future move combinations quickly exceeds the number of atoms in the universe).

For chess the numbers are much more limited, so it's possible for a computer to 'look ahead' a number of turns and rate the situation.

Go is NOT an easier game than chess (quite the contrary). The very fact that chess has limited movement options for each piece makes it a much more limited game.

Still, even chess isn't a solved game (like e.g. connect four). So it is still theoretically possible for a human to beat a computer.
Lurker2358
1 / 5 (2) Apr 16, 2012
Still, even chess isn't a solved game (like e.g. connect four). So it is still theoretically possible for a human to beat a computer.


The best human players have to be following some sort of algorithm which scales, else their win/loss ratio would show little or no skill correlation.

Intuitively, a priority on capturing and avoiding capture is the most obvious place to start, since a lost piece is equivalent to a lost turn.

Tempo in a turn-based strategy game is all-important, and since in this game capturing material is exactly costing an opponent their past turns, then that aspect of material vs tempo should be equivalent, or at least much more so than in Chess.

The next obvious rule is to avoid placing a stone in edges and corners unless doing so allows you to make an immediate capture or prevent an immediate capture.

Beyond that, the basics of winning linear and diagonal configurations should scale.
Lurker2358
1 / 5 (2) Apr 16, 2012
Ok, you don't have to check all possible moves.

You only have to check about the next 20 moves in a small family of moves related to moves already made.

Since the majority of human players can only think a few moves ahead, because they forget or lose track of things, etc, then a computer thinking 20 moves ahead should play better than almost anyone.

You could design an algorithm to quickly discard families of moves that are obviously less important, for example, ignoring the empty side of the board, etc, since half of all games are a reflection of one another, and 75% of all games are a rotation of the first 25% of games.

Effectively, if you are the better player on a 13by13 board, you will be the better player on a 19by19 board, and therefore a 10by10 "corner" of the 19by19 board is sufficient to establish all patterns, since 19by19 is just 4 9by9 boards connected by an additonal 1 space wide row and column.

Just solve a 9by9 board and a 10by10 board, 19by19 by default.
InterPur
5 / 5 (1) Apr 16, 2012
To antialias:

FYI, there actually are more possible chess games than atoms in the known universe.

I play both Go and Chess and have done research on each. For some reason there has been little computer analysis done on the game of Go, while there has been extensive computer study of chess, possibly because it's a more universally played game. Currently the best computer chess program is Hudini 2.0. I can't recall any computer go program that is at all worthy of mention.
Lurker2358
1 / 5 (2) Apr 16, 2012
Most chess engines actually introduce random errors now, because they are nearly unbeatable except to about the top 1% of players.

Even windows Chess Titans inserts random errors, even on the 10th difficulty level, and I've never won a game on 9th or 10th difficulty.

If you get "Winboard" and some of it's compatible chess engines the computer will make you look like a complete idiot, even if you use custom pieces or some other modifications. the damn thing is almost completely unbeatable.
Lurker2358
not rated yet Apr 16, 2012
To antialias:

FYI, there actually are more possible chess games than atoms in the known universe.


Yes.

And yet players and computers alike are able to evaluate entire families of moves and discard them as inferior with a minimum of effort, by using a few basic rules of position, material, and tempo.
Lurker2358
1 / 5 (1) Apr 16, 2012
And consider this.

On real time strategy games, like Starcraft 2, the "Very Hard" computer, which is the strongest one that does not cheat, apparently beats about 80% to 90% of players in 1vs1, even though it's understanding of position and tactics is practically non-existent.

To put that in perspective, as either Protoss or Terran, I can handicap myself to just 1 of each unit and go kill the Very Hard Zerg computer without losing a unit.

I can defeat 1vs2 Very Hards without cheesing or abusing the ai.

I have defeated 1vs4 Insanes one time on one map.

So obviously A.I. in RTS games still has a long, long way to go, as I am 3 whole leagues below the number 1 ranked Grand Master, or 2 leagues and 1 rank below the bottom of Grand Master league.

I said all that to say this, the complexities of an RTS are far more than any turn based board game, but they can make a computer that beats 90% of players without cheating, just on pure multi-tasking really.
Sonhouse
5 / 5 (3) Apr 16, 2012
To Lurker: Good luck with that, you seem to think it is so easy, then do it. Lets see you make a go program that can even beat me, a 10th kyu, not even close to pro level. I dare you to make a go program that can even beat me. Oh, good luck beating even the lowest Dan level.
Lurker2358
2 / 5 (2) Apr 16, 2012
To Lurker: Good luck with that, you seem to think it is so easy, then do it. Lets see you make a go program that can even beat me, a 10th kyu, not even close to pro level. I dare you to make a go program that can even beat me. Oh, good luck beating even the lowest Dan level.


You would be surprised.

I'd say talk to the guys who coded winboard's chess engine.

The chess engines even proved certain "fairy" pieces are stronger or weaker than they were previously believed to be, etc.

Which is to say, the algorithm was literally better than Grand Master level players at evaluating material value.

The game has absurdly basic rules in a 2-d, turn-based space.

There are guys at Stanford or DARPA would could probably write a generalized mathematical formula to solve all possible versions of this game in one step.

It's actually very similar, to the game "Life" which has been solved years ago...except this is effectively a 2 player variant, instead of a deterministic rule.
antialias_physorg
5 / 5 (4) Apr 17, 2012
It's not like people haven't tried making good Go programs. Go is a lot more popular in the Asian hemisphere than chess is - and if you have followed the e-sports scene at all you will know how fanatical and focused especially Koreans can be when it comes to developing algorithms for beating various games.
Sigh
5 / 5 (3) Apr 17, 2012
Intuitively, a priority on capturing and avoiding capture is the most obvious place to start, since a lost piece is equivalent to a lost turn.

Having read all your comments, I must ask how much go you have played. Capturing stones is not the goal of the game at all. It is possible to win while capturing fewer stones than the opponent, or even without capturing any stones at all. It is also very difficult to develop criteria for evaluating board positions that you can tell to a computer. That's what a 3 dan player told me who has spent years on writing go programmes.

So that I can decide whether I should trust you more, do tell what your rank as a player is, and how much experience you have with writing programmes that play go or other games.
Lurker2358
1 / 5 (3) Apr 17, 2012
Capturing stones is not the goal of the game at all. It is possible to win while capturing fewer stones than the opponent, or even without capturing any stones at all.


If the goal of the game is to control the most area of the board, then capturing piece is almost always beneficial. Particularly since also gain points based on how many stones you captured.

It is also very difficult to develop criteria for evaluating board positions that you can tell to a computer.


Not really.

I've come up with a couple scalable rules already that a comp sci 101 student should be able to code.

That's what a 3 dan player told me who has spent years on writing go programmes.


So what? I can't believe you actually believe a game this pathetically simple is harder to digest than Chess or Starcraft.

I haven't played this game before, but it's easy.

I've already found a way for Black to gain perpetual control of White's turn in as few as 4 moves.
jibbles
5 / 5 (2) Apr 17, 2012
am i the only one really sick and tired of having to wade through lurker's fatuous spewing before being able to read some thoughtful commentary?
Lurker2358
1 / 5 (1) Apr 17, 2012
Anyway, you're quite wrong.

It's pretty damn obvious that unless you're making terrible moves, material, tempo, and position are virtually equivalent to one another in this game.

If a person loses a stone they lost control of at least one grid, and they effectively lost a turn, and of course they lost a potential surround.

Worst case scenario for black:

Place your first stone in the center and then counter-play everything white does for the remainder of the game. Worst thing that can happen is you win by 1 point.
antialias_physorg
5 / 5 (3) Apr 17, 2012
Much simpler games have earned people a PhD (google for Victor Allis who solved connect4 for his. And the dissertation on that is by no means trivial)

I can't believe you actually believe a game this pathetically simple is harder to digest than Chess

Believe it.
http://en.wikiped...hematics

http://en.wikiped...n_number

The estimated number of possible positions for a legal chess game (50 moves rule) is somewhere between 10E46 and 10E47.

The estimated number of possible positions for a go game (with the longest professional games lasting to about 400 moves) is 10E1023

To spell it out: That's 977 ORDERS OF MAGNITUDE greater complexity than chess.
Lurker2358
1 / 5 (1) Apr 17, 2012
Capturing stones is not the goal of the game at all.


Technically, no, but based on the scoring criteria, it sure as hell will help you.

It is possible to win while capturing fewer stones than the opponent,


Only if the opponent has made some very inferior moves. You'd practically need to be playing "give away" in order to lose while making more captures, simply because every piece on or off the board is a point. When you capture a stone not only does that count toward the final score, but it's also a point the opponent lost.

It would take a freakin miracle or a "give-away" to win while down in material...

or even without capturing any stones at all.


That I believe, if it's a very well played game by both players.

But it favors black since he is always either ahead by 1 stone( and therefore 1 space,) or tied, if no captures have been made.
Lurker2358
1 / 5 (1) Apr 17, 2012
Much simpler games have earned people a PhD (google for Victor Allis who solved connect4 for his. And the dissertation on that is by no means trivial)

I can't believe you actually believe a game this pathetically simple is harder to digest than Chess

Believe it.
http://en.wikiped...hematics

The estimated number of possible positions for a legal chess game (50 moves rule) is somewhere between 10E46 and 10E47.

The estimated number of possible positions for a go game (with the longest professional games lasting to about 400 moves) is 10E1023

To spell it out: That's 977 ORDERS OF MAGNITUDE greater complexity than chess.


Yeah well, the Winboard engines in Chess are so good that if you play them against one another, the games cannot be decided in 50 moves or less, and that's even playing with SPEED-Chess rules. Every time I did it the game was called a draw or one lost because they ran out of time somewhere around the 70th or 80th move.
Lurker2358
1 / 5 (1) Apr 17, 2012
The estimated number of possible positions for a go game (with the longest professional games lasting to about 400 moves) is 10E1023


Actually, since Sigh wants to consider winning without capturing material, then the limit of possible games positions is:

The factorial of N squared, where N is the dimension of the board.

However, a real "somewhat skilled" game will have far fewer positions than this, because most of these positions would involve situations where the rules would force a capture.

That is, almost all of the possible positions are the result of what would be extremely unskilled or even random play.

At any rate, the factorial of 19^2 is,

1.4379E768.

And again, most, in fact almost all, of those possible games are the result of what amounts to random placements or just poor skill.

* This does not consider captures clearing the board, giving rise to more potential games, however, at that point one player should have insurmountable advantage.
Lurker2358
1 / 5 (1) Apr 17, 2012
To Sigh:

Show me a case of how you could be down in material by 1 or more stones, but yet have superior position, which you alleged could win the game.

It cannot be the result of a "give-away" or dumbass move by the other player, because that's just comparing a skilled player to an idiot.
antialias_physorg
5 / 5 (2) Apr 17, 2012
It would take a freakin miracle or a "give-away" to win while down in material...

Plenty of examples of sacrifice play in Go which will give you a win. Examlpe:
http://361points....es/19/1/

(Just like in chess. An extreme example would be 'The Immortal game'
http://en.wikiped...tal_Game
where Aderssen sacrificed both rooks, a bishop AND his queen in order to win by checkmate)

Thinking that you can have an 'easy rule' to win (or get a winning strategy) at Go is just fooling yourself. The game is much more complex than you might think. Try it.
SoylentGrin
not rated yet Apr 17, 2012
A captured piece is not the same as a lost turn, Lurker, either in Chess or Go.

The opponent has to "lose" a turn to make the capture. If that opens up a weakness or is in any other way a poor move, the investment of one tempo can return many more.
Sonhouse
5 / 5 (1) Apr 17, 2012
To Sigh:

Show me a case of how you could be down in material by 1 or more stones, but yet have superior position, which you alleged could win the game.

It cannot be the result of a "give-away" or dumbass move by the other player, because that's just comparing a skilled player to an idiot.

You have a pathetically naive view of Go. So show me the money. Write a program that beats even little old me. You think it's so easy, then put your money where your mouth appears to be. Try this exercise: count up the possible separate kinds of surround territories which is the point of the game, capturing usually only makes the difference of ten or twenty points at the end, you get the piece and you get to count the space it left as your own so you get 2 points for a capture. Fine. But count up all the ways a territory can be parsed. I don't have the math for that but you are clearly the most intelligent person on the planet so lets see you do it.
Lurker2358
1 / 5 (1) Apr 17, 2012
A_P:

Ok, wikipedia's rules descripton is insufficient to handle ever detail of this position, although it may not matter ultimately.

Can a player lose a stone on his own turn by making a legal, but stupid move?

i.e. placing a stone inside a ring of the other player's stones, where the rules would seem to auto-capture that stone?

If yes, how do you resolve situations where placing a stone would cause it to be both involved in a capture and itself captured in the same move?

Is there a priority to the player who has the active turn, or not?

That is not explained in the wiki rules description, and is not necessarily covered by the Ko rule either.

When you look at the simplified game example in wikipedia, it appears that white re-moving back to space "A" in the example you linked to should be an illegal move. If that is the case, there is no good reason for black to make his move 6 to space "A" since doing so actually gives up a turn and weakens his position....
Lurker2358
1 / 5 (1) Apr 17, 2012
I see, never-mind.

Priority is always to the active player, so that answers the question. White to "A" would capture 4 stones and black would forfeit at that point.

Black should make the move to "A", but it's kind of a dumb situation that he probably got into because of a mistake earlier.
Lurker2358
1 / 5 (1) Apr 17, 2012
Meh, the example game in Wikipedia isn't even possible as a configuration.

The description claims no captures have been made, but black is ahead by two stones at the end, 22 vs 20, which is not even possible.

So it's actually either an invalid position, or an inaccurate description.

The only way to get to that position is if white sacrificed a stone and gained nothing by doing so, since going first would only explain 1 extra stone for black on the first half of the round...not two...
SoylentGrin
5 / 5 (1) Apr 17, 2012
It's common practice to let the weaker player play black, going first. If this isn't enough to level the playing field, they also get handicap stones. The black stone player can start with as many as 9 extra stones.
Sigh
5 / 5 (1) Apr 18, 2012
I haven't played this game before, but it's easy.

How do you know, without playing? Most of the Go players I know have played chess before, and they switched to Go because it's more difficult and therefore more interesting. If you want to argue that it's only more difficult for humans, and easier than chess for computers, whhere are the good Go programmes?

Worst case scenario for black:

Place your first stone in the center and then counter-play everything white does for the remainder of the game. Worst thing that can happen is you win by 1 point.

That would be called mirror-go. I haven't tried playing that because it would be too boring, but there are moves forcing you to break the symmetry. Even in your scenario, black would lose by 3.5 in your scenario, because moving first is considered worth 4.5 points, which are given to white.
Sigh
5 / 5 (1) Apr 18, 2012
Show me a case of how you could be down in material by 1 or more stones, but yet have superior position, which you alleged could win the game.

Are are you willing to bet money that this can't happen? How much, and at what odds? If I offered to show you a perpetuum mobile, you should be willing to bet most of what you own, at just about any odds. Please quantify how confident you are, provided you are willing to put your money where your mouth is.

I need you to download a Go client that can read files from games, and I need your email address, so I can send you games I watched and saved. I expect I can find some that satisfy your criteria.

It cannot be the result of a "give-away" or dumbass move by the other player, because that's just comparing a skilled player to an idiot.

The games I saved are from Dan level players, so skilled vs idiot doesn't apply. But who judges whether there is a give-away move? You, who never played and has a stake in the answer?
vega12
not rated yet Apr 23, 2012
Dude, Lurker is just trolling you all. If someone obviously doesn't know what they are talking about to this extreme, then just ignore them. Any Go player or computer scientist knows about the extreme challenges building a Go AI poses.
technodiss
not rated yet May 01, 2012
the calculated number of possible go games on a 19x19 board (if i remember correctly) is 1x10^200. i'd put that in long form but there's a character limit. there is no such thing as a 10x10 board and a 9x9 board is babies (no, really. i was 5 when i moved from a 13x13 to a 9 stone handicap on 19x19). while i understand how network theory and statistical modeling apply to the game and vice versa, i don't think that much can be learned in the way of physics.
@lurker, to gain even a moderate understanding of the game, you need to play it for a few decades. even top players admit that they will never fully understand all the nuances, life lessons, and possibilities of the simple grid. one more thing, people have playing go for over 3000 years. don't use Wikipedia as a source of serious information on a subject you obviously don't understand in the first place.
when people talk compressed dimensions ecological stability, i don't quote Wikipedia.
oops, i seem to be ranting, sorry.