Stories
Slash Boxes
Comments

SoylentNews is people

posted by LaminatorX on Tuesday December 16 2014, @08:25AM   Printer-friendly
from the considered-joyful dept.

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."

This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2, Informative) by SunTzuWarmaster on Tuesday December 16 2014, @12:56PM

    by SunTzuWarmaster (3971) on Tuesday December 16 2014, @12:56PM (#126475)

    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

    by rts008 (3001) on Tuesday December 16 2014, @02:06PM (#126484)

    ... 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."

    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

    by Covalent (43) on Tuesday December 16 2014, @02:24PM (#126493) Journal

    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

      by Immerman (3985) on Tuesday December 16 2014, @04:09PM (#126530)

      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

        by Anonymous Coward on Tuesday December 16 2014, @06:20PM (#126566)

        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

      by CirclesInSand (2899) on Tuesday December 16 2014, @07:53PM (#126601)

      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

    by pmontra (1175) on Tuesday December 16 2014, @10:09PM (#126640)

    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

    by TheRaven (270) on Wednesday December 17 2014, @09:31AM (#126808) Journal
    Backgammon was another game that was difficult for computers to win. For each move, you have the position of the board (deterministic) and the faces of two dice (known at the start of your turn, non-determinstic when predicting future moves). This gives a large state space to explore. Beyond that, to actually win a sequence of games you need to use the doubling cube effectively (in a game of backgammon, players take it in turns to double the points value of the score for the game, so if you win one and lose the next you can still lose overall if no one doubles in the first game and your opponent doubles once in the second. Best strategy can involve making the opponent believe that they're winning in one game so that they'll double and then you double, then they can win the next two and you still win overall). It took quite a while for a computer to beat a moderately competent human player at backgammon (in spite of it being the oldest recorded board game) and the first program to do so was a neural network.
    --
    sudo mod me up
    • (Score: 2) by cykros on Wednesday December 17 2014, @02:33PM

      by cykros (989) on Wednesday December 17 2014, @02:33PM (#126871)

      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).