3 ms·

You can view there being 5 dimensions/concerns with large scaling factors containing issues needing solving to be generally applicable. 1. How to search 2. How

You can view there being 5 dimensions/concerns with large scaling factors containing issues needing solving to be generally applicable. 1. How to search 2. How to resolve breadth concerns 3. How to resolve depth concerns 4. How to resolve large training requirements 5. How to form and resolve recursive goals With AlphaGo, it looks like they may have solved 3 1. Search. Monte Carlo will likely be used from here on out. Much more efficient than full brute force search (chess style). 2. Breadth - Policy network. Reduced branching factor from 250 to between 5 and 10. 3. Depth - Value network reduced depth from roughly 75 to < 20 Next they're working on applying reinforcement learning to their two NNs. Ie seeing if they can optimize how well they can do and how quickly they can learn. Maybe there are large gains there. If so, the final task would be finding a game or situation that required nesting of sub-goals like everyday life does. They've made some impressive gains. > In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable. I could see Deep Mind applying this to something like catching a ball in the near future. Just to show it's generality. It's not that different of a problem space than learning to play breakout.

mrob 9y ago
Chess AI does not use brute force search. It evaluates board positions with heuristics (eg. pieces captured, blocked pawns, possibility of castling, etc.), and uses the estimated chance of winning to prune the search tree with techniques such as alpha-beta pruning[0]. Both board evaluation and tree pruning are more difficult in Go. In Chess, capturing material is very important, but capturing stones in Go is often useless because the stones are in a bad position ("dead"). You can't decide who's winning just by counting captures. It's very difficult to hand code a board evaluation function, but AlphaGo's neural network solved the problem. However, the neural network alone, with no tree search, was only enough to reach strong amateur level. Unlike Chess, where moves usually have consequences in the near future, a move in Go can be important tens or even hundreds of moves later. Alpha-beta pruning doesn't handle very distant consequences well, but Monte Carlo tree search does much better. Combined with the neural network it was enough to beat humans. [0] https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
- BoiledCabbage 9y ago
  Minmax as used in chess is nothing more than a Depth First Search constrained within the space of moves of agents acting in their own self interest. It searches the maximum number of plies it can (you can think of a ply as a move by a single player in chess[0]) within the time & memory it has allowed. This approach is brute forcing the search space restricted by computational limits. Alpha-Beta is just an optimization to minmax and not a fundamental change in the search approach. Chess and Go are very different games and need to be treated as such. Lots of the recent excitement about Go is due to the innovations in machine learning and specifically deep learning that have been discovered. Particularly their performance on such a complex game - significantly more complex than chess. It was predicted that Go wouldn't be able to match top strength professionals for another 5 to 10 years. AlphaGo Played Lee Sedol last year (considered one of the top players of the past decade) and won.[1] AlphaGo beating this prediction by so much was a large part of the excitement for last year's event. The reason for the excitement was demonstrating that Monte Carlo search, which was originally dismissed as inferior, was a significantly better approach for the game of Go. Monte Carlo is a probabilistic based approach that uses random sampling - this is very different from the DFS approach used in chess.[2] It has proven be to very effective and without another breakthrough will almost certainly be the option used going forward. [0] - https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol [1] - https://en.wikipedia.org/wiki/Ply_(game_theory) https://en.wikipedia.org/wiki/Ply_(game_theory) [2] - https://en.wikipedia.org/wiki/Monte_Carlo_method https://en.wikipedia.org/wiki/Monte_Carlo_method

mrob 9y ago

Chess AI does not use brute force search. It evaluates board positions with heuristics (eg. pieces captured, blocked pawns, possibility of castling, etc.), and uses the estimated chance of winning to prune the search tree with techniques such as alpha-beta pruning[0]. Both board evaluation and tree pruning are more difficult in Go. In Chess, capturing material is very important, but capturing stones in Go is often useless because the stones are in a bad position ("dead"). You can't decide who's winning just by counting captures. It's very difficult to hand code a board evaluation function, but AlphaGo's neural network solved the problem. However, the neural network alone, with no tree search, was only enough to reach strong amateur level. Unlike Chess, where moves usually have consequences in the near future, a move in Go can be important tens or even hundreds of moves later. Alpha-beta pruning doesn't handle very distant consequences well, but Monte Carlo tree search does much better. Combined with the neural network it was enough to beat humans. [0] https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

BoiledCabbage 9y ago
Minmax as used in chess is nothing more than a Depth First Search constrained within the space of moves of agents acting in their own self interest. It searches the maximum number of plies it can (you can think of a ply as a move by a single player in chess[0]) within the time & memory it has allowed. This approach is brute forcing the search space restricted by computational limits. Alpha-Beta is just an optimization to minmax and not a fundamental change in the search approach. Chess and Go are very different games and need to be treated as such. Lots of the recent excitement about Go is due to the innovations in machine learning and specifically deep learning that have been discovered. Particularly their performance on such a complex game - significantly more complex than chess. It was predicted that Go wouldn't be able to match top strength professionals for another 5 to 10 years. AlphaGo Played Lee Sedol last year (considered one of the top players of the past decade) and won.[1] AlphaGo beating this prediction by so much was a large part of the excitement for last year's event. The reason for the excitement was demonstrating that Monte Carlo search, which was originally dismissed as inferior, was a significantly better approach for the game of Go. Monte Carlo is a probabilistic based approach that uses random sampling - this is very different from the DFS approach used in chess.[2] It has proven be to very effective and without another breakthrough will almost certainly be the option used going forward. [0] - https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol [1] - https://en.wikipedia.org/wiki/Ply_(game_theory) https://en.wikipedia.org/wiki/Ply_(game_theory) [2] - https://en.wikipedia.org/wiki/Monte_Carlo_method https://en.wikipedia.org/wiki/Monte_Carlo_method