GO Ant Go
What can we learn from biological systems to solve the GO maze.
2011-02-07
"Go to the ant, you sluggard! Consider her ways and be wise, which having no captain, overseer
or ruler, provides her supplies in the summer, and gathers her food in the harvest. How long will
you slumber, O sluggard!"
GO (aka Baduk, Weiqi) is a strategic and thinking game being the most ancient board game in the world. Its invention is dated back 2,500-4000 years in China. It has become the national game of Japan, Korea where it is called Baduk and The People's Republic of China.
Over 60 million fans play the game around the world.
Despite its simple rules the game reaches extremely high levels of sophistication. While chess is estimated to have 10 64 possible games, GO has around 10 172 possible game combinations, more than the number of atoms in the universe.
For many years a strong software is pursued. One, that could beat a professional GO player.
A prize of 1.6 million $ was offered and never claimed.
Other complex strategy games have been cracked and strong software exists today for Chess, Shogi, Backgammon etc.
Strong algorithms have been developed for these games, using sophisticated mathematic formulas and statistical tools.
The Shogi association has banned its members from competing against computer software.
There, just as in chess, the computer "machine" beat the Human. However, the computer power, cannot use brute force due the infinite number of possibilities and other techniques could not decipher GO. The models used to solve chess and bridge have been unsuccessful with GO.
Despite the advancement in computer power, calculation ability and speed, GO remains resistant.
Neural networks are applied in solving several games such as backgammon.
Other efforts in trying to solve GO are the Monte Carlo.
We choose a play we want to examine and try to play many random games.
If most of them lead to winning in the majority of games, than it is a good play
It is claimed that the solution to GO playing software may have many applications in other fields of Life Science research and cryptology. Similarly Google, Yahoo and other search engines may benefit from the proposed solution.
Therefore new ways must be explored. The pattern recognition has been incorporated into many such programs together with professional players game databases. The use of artificial intelligence has not been successful either. So this may be good time for some biological wisdom. The path of learning from biological systems should be explored.
We came across an interesting article discussing Argentinian ants, solving optimally the Tower of Hanoi.
The Journal of Experimental Biology (2011) 214, 50-58
Ants have demonstrated an ability to find solutions to complex dynamic problems such as
finding and bringing food to their nest. They do so by collaborating with each other.
Researchers try to decipher this mechanism, hoping it will enable them to improve computer
algorithms.
In the article referenced researchers translated the Towers of Hanoi problem into a physical maze representing ~33k options, and then placed 12 colonies of Argentinian ants in it. The ants were able to find their way to the food within an hour in the shortest way, thus providing a solution to the Towers of Hanoi. When the path was blocked ("someone moved their cheese"), they quickly identified the new source and got there in an optimal short way.
The way in which ants solve dynamic solutions can contribute to optimization algorithms, and from there to optimize human industries.
In the research the ants demonstrated the ability to solve 2 problems:
1. find food (the correct path) in time
2. Find the most efficient (shortest path in a maze).
The ants were able to respond to dynamic changes in the environment.
These abilities were used by the researchers to solve a seemingly unrelated problem.
The ants' behavior can be imitated by a computer algorithm, in order to solve a similar problem. There is a field in artificial intelligence by the name of "Agent Oriented Programming" which does just that – the program is composed of a multitude of agents(in our case – ants), and running it provides us the behavior of an entire colony.
The use of a biological system to solving GO seems fascinating.
The model used "the Towers of Hanoi" appears to be similar to Tsumego (Go riddles) - solving a specific problem.
When adding the dynamic nature of the ant biological systems, it may be extended to the whole game of GO.
We are offering a challenge to bridge the gap between the Towers of Hanoi and solving a Tsumego will be a landmark. The idea is as follows: translate a tsumego into a problem of finding the shortest path in a maze (In computer science it is referred to as a graph), and program an algorithm mimicking the ants behavior to find the solution.
The next phase will be to bridge to a whole game of GO/ Baduk/ Weiqi.
The challenge is to demonstrate good heuristics and how to use mazes / graphs to solve GO.
The heuristic solution may not bring at first the optimal/ ultimate solution but can lead to a concept / rule of thumb that can be further pursued in many GO problems. Such a solution, that will work in most problems will offer a technique that will eliminate the need to evaluate all options.
Extra readings: J. theor. Biol. (1999) 198, 575}592
So, GO do it and earn your PhD's investigating the ants way.
Gambatte ne
Shavit Fragman
Shachar Gluska
Barak Gluska
- Source: http://www.go-mind.com/download/goantgo.pdf
or ruler, provides her supplies in the summer, and gathers her food in the harvest. How long will
you slumber, O sluggard!"
GO (aka Baduk, Weiqi) is a strategic and thinking game being the most ancient board game in the world. Its invention is dated back 2,500-4000 years in China. It has become the national game of Japan, Korea where it is called Baduk and The People's Republic of China.
Over 60 million fans play the game around the world.
Despite its simple rules the game reaches extremely high levels of sophistication. While chess is estimated to have 10 64 possible games, GO has around 10 172 possible game combinations, more than the number of atoms in the universe.
For many years a strong software is pursued. One, that could beat a professional GO player.
A prize of 1.6 million $ was offered and never claimed.
Other complex strategy games have been cracked and strong software exists today for Chess, Shogi, Backgammon etc.
Strong algorithms have been developed for these games, using sophisticated mathematic formulas and statistical tools.
The Shogi association has banned its members from competing against computer software.
There, just as in chess, the computer "machine" beat the Human. However, the computer power, cannot use brute force due the infinite number of possibilities and other techniques could not decipher GO. The models used to solve chess and bridge have been unsuccessful with GO.
Despite the advancement in computer power, calculation ability and speed, GO remains resistant.
Neural networks are applied in solving several games such as backgammon.
Other efforts in trying to solve GO are the Monte Carlo.
We choose a play we want to examine and try to play many random games.
If most of them lead to winning in the majority of games, than it is a good play
It is claimed that the solution to GO playing software may have many applications in other fields of Life Science research and cryptology. Similarly Google, Yahoo and other search engines may benefit from the proposed solution.
Therefore new ways must be explored. The pattern recognition has been incorporated into many such programs together with professional players game databases. The use of artificial intelligence has not been successful either. So this may be good time for some biological wisdom. The path of learning from biological systems should be explored.
We came across an interesting article discussing Argentinian ants, solving optimally the Tower of Hanoi.
The Journal of Experimental Biology (2011) 214, 50-58
Ants have demonstrated an ability to find solutions to complex dynamic problems such as
finding and bringing food to their nest. They do so by collaborating with each other.
Researchers try to decipher this mechanism, hoping it will enable them to improve computer
algorithms.
In the article referenced researchers translated the Towers of Hanoi problem into a physical maze representing ~33k options, and then placed 12 colonies of Argentinian ants in it. The ants were able to find their way to the food within an hour in the shortest way, thus providing a solution to the Towers of Hanoi. When the path was blocked ("someone moved their cheese"), they quickly identified the new source and got there in an optimal short way.
The way in which ants solve dynamic solutions can contribute to optimization algorithms, and from there to optimize human industries.
In the research the ants demonstrated the ability to solve 2 problems:
1. find food (the correct path) in time
2. Find the most efficient (shortest path in a maze).
The ants were able to respond to dynamic changes in the environment.
These abilities were used by the researchers to solve a seemingly unrelated problem.
The ants' behavior can be imitated by a computer algorithm, in order to solve a similar problem. There is a field in artificial intelligence by the name of "Agent Oriented Programming" which does just that – the program is composed of a multitude of agents(in our case – ants), and running it provides us the behavior of an entire colony.
The use of a biological system to solving GO seems fascinating.
The model used "the Towers of Hanoi" appears to be similar to Tsumego (Go riddles) - solving a specific problem.
When adding the dynamic nature of the ant biological systems, it may be extended to the whole game of GO.
We are offering a challenge to bridge the gap between the Towers of Hanoi and solving a Tsumego will be a landmark. The idea is as follows: translate a tsumego into a problem of finding the shortest path in a maze (In computer science it is referred to as a graph), and program an algorithm mimicking the ants behavior to find the solution.
The next phase will be to bridge to a whole game of GO/ Baduk/ Weiqi.
The challenge is to demonstrate good heuristics and how to use mazes / graphs to solve GO.
The heuristic solution may not bring at first the optimal/ ultimate solution but can lead to a concept / rule of thumb that can be further pursued in many GO problems. Such a solution, that will work in most problems will offer a technique that will eliminate the need to evaluate all options.
Extra readings: J. theor. Biol. (1999) 198, 575}592
So, GO do it and earn your PhD's investigating the ants way.
Gambatte ne
Shavit Fragman
Shachar Gluska
Barak Gluska
- Source: http://www.go-mind.com/download/goantgo.pdf
New update