Featured Research

from universities, journals, and other organizations

Game of go: A complex network

Date:
April 16, 2012
Source:
CNRS (Délégation Paris Michel-Ange)
Summary:
Could computers ever beat the best 'go' players? Although unthinkable at this stage, this could soon become possible, thanks to theorists. For the first time, scientists have applied network theory to a game of strategy.

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: Image courtesy of CNRS

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 (Université Toulouse III-Paul Sabatier/CNRS) and the Laboratory of Theoretical Physics and Statistical Models (Université Paris-Sud/CNRS), 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 complex networks has attracted increasing interest over the past few years, fuelled in particular by the development of communication and information networks. This new research field is proving very useful for the description of complex systems such as social networks and the Internet. For instance, when network theory 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 goor 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 (Université Toulouse III-Paul Sabatier/CNRS) and Olivier Giraud from the Laboratory of Theoretical Physics and Statistical Models (Université Paris-Sud/CNRS) 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.

* Go is a game of strategy played by two players who take turns to place black and white stones on a board called a goban. The players each try to control a larger portion of the board than their opponent.


Story Source:

The above story is based on materials provided by CNRS (Délégation Paris Michel-Ange). Note: Materials may be edited for content and length.


Journal Reference:

  1. B. Georgeot, O. Giraud. The game of go as a complex network. EPL (Europhysics Letters), 2012; 97 (6): 68002 DOI: 10.1209/0295-5075/97/68002

Cite This Page:

CNRS (Délégation Paris Michel-Ange). "Game of go: A complex network." ScienceDaily. ScienceDaily, 16 April 2012. <www.sciencedaily.com/releases/2012/04/120416100437.htm>.
CNRS (Délégation Paris Michel-Ange). (2012, April 16). Game of go: A complex network. ScienceDaily. Retrieved August 20, 2014 from www.sciencedaily.com/releases/2012/04/120416100437.htm
CNRS (Délégation Paris Michel-Ange). "Game of go: A complex network." ScienceDaily. www.sciencedaily.com/releases/2012/04/120416100437.htm (accessed August 20, 2014).

Share This




More Computers & Math News

Wednesday, August 20, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Ballmer Leaves Microsoft's Board, Has Advice For Nadella

Ballmer Leaves Microsoft's Board, Has Advice For Nadella

Newsy (Aug. 19, 2014) — In a letter to Microsoft CEO Satya Nadella, Ballmer said he's leaving the board of directors and offered tips on how the company can be successful. Video provided by Newsy
Powered by NewsLook.com
What Google Can Gain From Special Accounts For Children

What Google Can Gain From Special Accounts For Children

Newsy (Aug. 19, 2014) — Google will reportedly offer official accounts for children younger than 13 years old. Video provided by Newsy
Powered by NewsLook.com
Breakingviews: Ebola's Economic Impact Could Eclipse SARS

Breakingviews: Ebola's Economic Impact Could Eclipse SARS

Reuters - Business Video Online (Aug. 18, 2014) — The virus ravaging Africa has yet to spread elsewhere. Yet Asia’s SARS crisis in 2003 showed how changes to behaviour can hurt the economy more than the actual disease, says Breakingviews' Una Galani. Video provided by Reuters
Powered by NewsLook.com
Twitter Users Up In Arms After 'Favorites' Show Up In Feeds

Twitter Users Up In Arms After 'Favorites' Show Up In Feeds

Newsy (Aug. 17, 2014) — Twitter is testing a feature on some users that shows favorited tweets from people they follow in their own timeline, the same way a retweet appears. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins