One of the last intellectual bastions of human dominance over computers has been Go. But a new breakthrough at the University of Edinburgh in Scotland using neural networks looks to change this soon.
The way they have approach this is by using a vast database of Go games to train a neural network to find the next move. Clark and Storkey used over 160,000 games between experts to generate a database of 16.5 million positions along with their next move. They used almost 15 million of these position-move pairs to train an eight-layer convolutional neural network to recognize which move these expert players made next. This was a process that took several days.
They then used the rest of the dataset to test the neural network. In other words, they presented the network with a board position from a game and asked it to pick the next move. Clark and Storkey say that the trained network was able to predict the next move up to 44 percent of the time "surpassing previous state of the art on this task by significant margins."
(Score: 2, Informative) by SunTzuWarmaster on Tuesday December 16 2014, @12:56PM
Scalable network learning of Go games from exploitation of the board space:
eplex.cs.ucf.edu/papers/gauci_ppsn10.pdf
(Score: 1) by rts008 on Tuesday December 16 2014, @02:06PM
Also, most likely surpassing 50%(or more) of the USA citizens from my observations.
Disclaimer: I am a US citizen, and have been witnessing 'Stupid People Tricks' for more than five decades.
(Score: 2) by Covalent on Tuesday December 16 2014, @02:24PM
Go is enormously complex, which is why computers have struggled so much with it. All of the other games that computers can beat humans at have almost always been "solved" using "lipstick on a brute force" approach. Chess is played this way by a computer: The computer just plays every possible game (or in faster algorithms, every reasonable game) many moves in advance and selects the move that produces the highest percentage of favorable outcomes.
The problem with Go is that the number of possible moves (and games) is so enormous that no computer can hope to look more than a few moves ahead using this approach. Further, there aren't good algorithms for looking at just the "reasonable" moves.
But this describes many real-world problems that computers need to get a whole lot better at (parking a car in a parking lot comes to mind).
Of course, building an army of terminator robots also falls into this category...
You can't rationally argue somebody out of a position they didn't rationally get into.
(Score: 2) by Immerman on Tuesday December 16 2014, @04:09PM
I would think parking a car would be only marginally more difficult than driving it:
Don't hit anything.
When you find an available place - park there.
It works much more smoothly without the common human near-infinite loop of:
If the available place requires me to walk more than 20 feet, then circle the parking lot again in case a closer spot has opened up.
(Score: 0) by Anonymous Coward on Tuesday December 16 2014, @06:20PM
It works much more smoothly without the common human near-infinite loop of:
If the available place requires me to walk more than 20 feet, then circle the parking lot again in case a closer spot has opened up.
I always stop to pull out my keys by a car closer to the entrance in hope that idiot blocking the aisle waiting for a car to pull out instead of taking the first available space at the end of the row will see me, pull forward and be out of the way when I get to my car and I am ready to leave.
(Score: 1) by CirclesInSand on Tuesday December 16 2014, @07:53PM
In chess, there is no compact way to describe a situation. It comes down to an exponential amount of reading, "if this move then that move...".
In go, on the other hand, situations have exponential optimizations. Two groups are effectively connected, and have more liberties than an opponents group. To describe that situation with a minimax would exponentially blow up the description size. Also, an estimation of which player is ahead on a Go board is hugely difficult. A human can make the estimate with some heuristic visual processing, but not so much on an electronic computer.
Go can't be won with the old minimax + good estimate of board position formula. And any strong player who knows that he is playing a computer knows the situation that software can't handle and will exploit that.
If I was to speculate irresponsibly, I would suggest that first verified software programming and the proof algorithms for that will emerge first, then from that Go playing software will follow. Trying to write Go software before addressing the difficulty of reasoning of propositional concepts will work in the short term, but not the long term.
(Score: 2, Informative) by pmontra on Tuesday December 16 2014, @10:09PM
The most successful approach so far has been the Montecarlo method. The best program plays at about 4-5 dan level, being able to win against old title winner professionals like Ishida and Takemiya https://gogameguru.com/crazy-stone-computer-go-ishida-yoshio-4-stones/ [gogameguru.com] https://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/ [gogameguru.com] (that level was achieved by running it on a small cluster of PCs).
This neural net still loses against a 4 kyu program. 4 kyu to 4 dan is a huge gap for humans to close (I'm 1 kyu, been 1 dan years ago). Maybe it will improve with more training and maybe by combining it with the Montecarlo method. The weakness of the latter seems to be the ability to evaluate correctly large scale fights. Who knows, maybe the neural network is better at that.
(Score: 3, Informative) by TheRaven on Wednesday December 17 2014, @09:31AM
sudo mod me up
(Score: 2) by cykros on Wednesday December 17 2014, @02:33PM
Wish I had some mod points to mod this up informative, as prior to your posting I was under the delusion that Go was the oldest (according to wikipedia, it came nearly 3000 years AFTER backgammon...wish I knew the source of my very wrong info).