Hi Bruno, > With AlphaGo, it is curious that the heuristic half of the system is > also the one that becomes a black box. > > > When you have the time, you might elaborate on this.
AlphaGo combines search trees and neural networks. The old-school approach to solving turn-based games such as checkers, chess, etc is by using the minimax search tree algorithm. The idea of minimax is simple: suppose you start with a give board state and it's your turn. You consider all of your possible moves, then all possible opponent moves from each move and so on, alternating between players. The goals is to maximize your expected outcome on each of your moves, while minimizing your expected outcome for every opponent move (thus the name). Intuitively, it tries to find the strongest possible play assuming the strongest possible opposition. The problem, of course, is combinatorial explosion. A first approach is alpha-beta prunning. When exploring a branch, once it finds that it already knows a play that is guaranteed to be better than the one being explored it stops (prunes) that branch. Then this can be further improved with heuristics. For example, one can have an heuristic function for chess that assigns a utility value to a board configuration, based on the pieces remaining on each side and their positions. By exploring the most promising branches first, more branches can be pruned earlier. Then it can be made even more aggressive by using the heuristic speculatively, cutting branches even if it's not certain (but just likely) that they will be weaker. One strategy for chess is to go as deeps as time allows, and fallback to heuristic pruning once there is no more time. The more powerful the computer and the more clever the implementation the deeper you can go, and this is how Deep Blue eventually defeated a grandmaster (plus a dictionary of openings and endings from human masters playing the game, chess textbooks, etc). AlphaGo replaces the heuristic function with neural networks: the protocol network and the value network. The value network learns to assign a value to board configuration. It also uses a stochastic version of minimax, using a Monte Carlo technique. Instead of following all branches, or following them by some heuristically-determined order, it samples them. The sampling is guided by a probability assigned to each future state. The protocol network learns to assign these probabilities. In the first version of AlphaGo, the protocol network was first trained to replicate the actions of human masters. Then, it was further improved by playing against itself. The first stage is supervised learning, the second is reinforcement learning (more similar dopamine-based learning, if you will). The new version was able to do it purely by reinforcement learning, with no reference to human-generated examples. It became a master by exploring the game from scratch. The neural networks used are convolutional networks, usually applied to image recognition. Instead of taking a large number of inputs (the entire board), they scan it. A smaller square starts on the top-left feeding the input of the network, and then it iteratively roams the board. It's a very clever, hybrid combination of AI techniques, combining the strength of old-fashioned symbolic methods with more recent statistical learning. What I meant is that the search-tree part is purely logic and deterministic, while the neural networks learn to have the right intuition about which board configurations look promising. The search-tree is easy to understand, while the neural network becomes a complex black-box. So the programmers of AlphaGo can inspect its data structures and explain what it hopes to achieve with a given move, but they are not capable of explaining you why the program bet on exploring certain ideas and not others. I find this is akin to the bicameral model of the brain, which I know you like. Here the corpus callosum is simply the piece of code that plugs the output of the neural networks to the Monte Carlo search algo. It seems obvious from the above description that this cannot easily be extrapolated to creating computer programs (or performing self-modification), but it is also clear that this hybrid approach looks promising. I like it very much. There is a big fight in AI between its "tribes" (symbolic, connectionist / statistical, evolutionary). I think that wonderful things will be built by combining all of these ideas, and using their respective strengths where appropriate. Best, Telmo. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
