4 ms·

I've always wondered if it's possible to inductively teach a computer to play Go using some form of machine learning by playing tens of thousands of games; perh

by mickeyp 12y ago

I've always wondered if it's possible to inductively teach a computer to play Go using some form of machine learning by playing tens of thousands of games; perhaps games with annotations by humans following a simple format to guide the fledgling AI: "Good move", "Bad move", etc. I used to play Go but stopped a long time ago. It was a game where you had to train your brain to recognise patterns and act on them.

rockdoe 12y ago
It depends on what you consider "teach to play Go". Priming the pattern databases using existing games is a pretty typical strategy.
itry 12y ago
"teach a computer to play Go using some form of machine learning" It would work. Even unsupervised. Let random programs play against each other. Let the losers die and the winners breed offsprings with mutations. If you let that run long enough, i tend to think that the new world champion would arise with certainty. The question is how long "long enough" is. Probably "too long" on current hardware. Would be nice to let this experiment run and draw a graph showing the elo of the best program over time.
- sp332 12y ago
  Random? Like code with random logic statements? Random for-loops, and random data structures initialized with random values, and random exit codes?
  - itry 12y ago
    Yes. See "Genetic Programming" by John R. Koza for empirical research and in depth analysis of this approach.
    - sp332 12y ago
      Yeah, I know what genetic programming is. But your programs don't just have to beat each other, they have to beat expert humans. Since there isn't a way to "crossover" operations from human players to the next generation of programs, crossover is of limited use. That means the only way to progress will be through random mutation, which will take a very long time.
      - ianopolous 12y ago
        I actually tried this for fun during my PhD I made sure the program instruction set was Turing complete and ran it along Koza's lines. As predicted, it took too long. On any reasonable time scale, the best evolved program was to play randomly.
  - deleted 12y ago
    [deleted]
- deleted 12y ago
  [deleted]
- toby 12y ago
  For a game this complex the evolution will be so slow you'll likely never see any progress. My experience with genetic programs is they'll go through hundreds of thousands of generations just to play tic-tac-toe properly.
  - aidenn0 12y ago
    Different parts of the game are amenable to different techniques. I had to do a genetic algorithm for my HS AI class, and I found that checkers opening through middle was quite amenable. Late-middle to end-game of checkers is easy to evaluate positional strength, which allowed a very good fitness function. This meant I was able to create a genetic program to learn to play the first half of the game fairly effectively.
hyperpape 12y ago
Some people have tried: http://senseis.xmp.net/?GeneticProgrammingAndGo http://senseis.xmp.net/?GeneticProgrammingAndGo. See also: http://senseis.xmp.net/?ComputerGoProgramming http://senseis.xmp.net/?ComputerGoProgramming, with relatively bad results.
louisdorard 12y ago
Monte Carlo Tree Search uses Machine Learning indeed! The balance between exploration and exploitation of the game tree is achieved using "bandit" algorithms (a type of Reinforcement Learning algorithm). I recommend reading (Kocsis & Szepesvari, 2006): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102....
- kylebrown 12y ago
  I've been experimenting with exactly this, in an effort to create a trading bot (with an eye on bitcoin/crypto-currencies, in particular). Starting from a lesser-known python library and example that solves the cart-pole task, I managed to apply it to create a pretty neat inventory balancer. Anyone curious about it should email me (email in profile).
- gwern 12y ago
  I think a better overview these days is "A Survey of Monte Carlo Tree Search Methods", Browne et al 2012 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297.3086 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297....

by mickeyp 12y ago

rockdoe 12y ago

It depends on what you consider "teach to play Go". Priming the pattern databases using existing games is a pretty typical strategy.

itry 12y ago

"teach a computer to play Go using some form of machine learning" It would work. Even unsupervised. Let random programs play against each other. Let the losers die and the winners breed offsprings with mutations. If you let that run long enough, i tend to think that the new world champion would arise with certainty. The question is how long "long enough" is. Probably "too long" on current hardware. Would be nice to let this experiment run and draw a graph showing the elo of the best program over time.

sp332 12y ago
Random? Like code with random logic statements? Random for-loops, and random data structures initialized with random values, and random exit codes?
- itry 12y ago
  Yes. See "Genetic Programming" by John R. Koza for empirical research and in depth analysis of this approach.
  - sp332 12y ago
    Yeah, I know what genetic programming is. But your programs don't just have to beat each other, they have to beat expert humans. Since there isn't a way to "crossover" operations from human players to the next generation of programs, crossover is of limited use. That means the only way to progress will be through random mutation, which will take a very long time.
    - ianopolous 12y ago
      I actually tried this for fun during my PhD I made sure the program instruction set was Turing complete and ran it along Koza's lines. As predicted, it took too long. On any reasonable time scale, the best evolved program was to play randomly.
- deleted 12y ago
  [deleted]
deleted 12y ago
[deleted]
toby 12y ago
For a game this complex the evolution will be so slow you'll likely never see any progress. My experience with genetic programs is they'll go through hundreds of thousands of generations just to play tic-tac-toe properly.
- aidenn0 12y ago
  Different parts of the game are amenable to different techniques. I had to do a genetic algorithm for my HS AI class, and I found that checkers opening through middle was quite amenable. Late-middle to end-game of checkers is easy to evaluate positional strength, which allowed a very good fitness function. This meant I was able to create a genetic program to learn to play the first half of the game fairly effectively.

hyperpape 12y ago

Some people have tried: http://senseis.xmp.net/?GeneticProgrammingAndGo http://senseis.xmp.net/?GeneticProgrammingAndGo. See also: http://senseis.xmp.net/?ComputerGoProgramming http://senseis.xmp.net/?ComputerGoProgramming, with relatively bad results.

louisdorard 12y ago

Monte Carlo Tree Search uses Machine Learning indeed! The balance between exploration and exploitation of the game tree is achieved using "bandit" algorithms (a type of Reinforcement Learning algorithm). I recommend reading (Kocsis & Szepesvari, 2006): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102....

kylebrown 12y ago
I've been experimenting with exactly this, in an effort to create a trading bot (with an eye on bitcoin/crypto-currencies, in particular). Starting from a lesser-known python library and example that solves the cart-pole task, I managed to apply it to create a pretty neat inventory balancer. Anyone curious about it should email me (email in profile).
gwern 12y ago
I think a better overview these days is "A Survey of Monte Carlo Tree Search Methods", Browne et al 2012 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297.3086 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297....