OK, so let’s talk theory vs practice.
In theory, TD learning approaches asymptotic optimality when used with a full state space. That is, if your RL model has one parameter for each state, then TD will converge those parameters to the game theoretic values. There are some pre-conditions, but this is true with remarkable generality. In particular, there is nothing about stochastic vs deterministic in the theory. So yes, the published experiments for Chess were failures. That is, using a very shallow search and relatively simple evaluation function does not work for chess like it did for Tesauro’s experiments in backgammon. But the conclusion that this is because of stochastic/deterministic is incorrect. Consider Go, for example, where static move generators can play at 1 dan level, and probably quite a bit higher. An inference that is compatible with theory is that to conquer chess you will need a deeper, wider network, or better inputs, or a better search engine. Or all of those. You could imagine measuring the skill of a variety of architectures, and map out the path of steepest ascent. In retrospect, I view Schradolph’s paper as evidence that neural networks have always been surprisingly successful at Go. Like Brugmann’s paper about Monte Carlo, which was underestimated for a long time. Sigh. Best, Brian From: Minjae Kim [mailto:xive...@gmail.com] Sent: Friday, February 24, 2017 11:56 AM To: Brian Sheppard <sheppar...@aol.com>; computer-go@computer-go.org Subject: Re: [Computer-go] dealing with multiple local optima TD-gammon is regarded as a special case from the stochastic characteristics of the backgammon game; it smoothens the search space for the value function and the value function itself to a great degree compared to those 'static' games such as go. Experiments of applying TD learning to chess and go was done after the success of TD-gammon, and the result was not good. I also did a small experiment a while ago applying TD learning to go using a similar network structure to that of TD-gammon. The network gets 'stuck' really fast. You can see similar comments to my experience here (https://chessprogramming.wikispaces.com/Temporal+Difference+Learning). You can make the network more 'actively' trained by doing stochastic move selection rather than simply selecting the move with highest value, but this doesn't work well enough to my experience, where I applied softmax. Schradolph experimented with TD for go in his 1994 paper, where he applied Gibbs sampling for stochastic move selection, although it wasn't a success for building a strong go bot. On Fri, Feb 24, 2017 at 11:03 PM, Brian Sheppard via Computer-go <computer-go@computer-go.org <mailto:computer-go@computer-go.org> > wrote: Neural networks always have a lot of local optima. Simply because they have a high degree of internal symmetry. That is, you can “permute” sets of coefficients and get the same function. Don’t think of starting with expert training as a way to avoid local optima. It is a way to start training with some good examples so that learning can start at a higher level. But then you should continue with self-play. Backgammon was trained to expert level based on self-play games that were initially random. Google “Tesauro backgammon” and you should be able to find a paper. I don’t know NEAT and HyperNEAT; I will look them up. Thank you for the reference. Best, Brian From: Computer-go [mailto:computer-go-boun...@computer-go.org <mailto:computer-go-boun...@computer-go.org> ] On Behalf Of Minjae Kim Sent: Friday, February 24, 2017 3:39 AM To: computer-go@computer-go.org <mailto:computer-go@computer-go.org> Subject: [Computer-go] dealing with multiple local optima I've recently viewed the paper of AlphaGo, which has done gradient-based reinforcement learning to get stronger. The learning was successful enough to beat a human master, but in this case, supervised learning with a large database of master level human games was preceded the reinforcement learning. For a complex enough game as go, one can expect that the search space for the policy function would not be smooth at all. So supposedly supervised learning was necessary to guide the policy function to a good starting point before reinforcement. Without such, applying reinforcement learning directly to a random policy can easily make the policy stuck at a bad local optimum. I could have a miunderstanding at this point; correct me if so, but to continue on: if it is hard to have "the good starting point" such as a trained policy from human expert game records, what is a way to devise one. I've had a look on NEAT and HyperNEAT, which are evolutionary methods. Do these evolutionary algorithms scale well on complex strategic decision processes and not just on simple linear decisions such as food gathering and danger avoidance? In case not, what alternatives are known? Is there any success case of a chess, go, or any kind of complex strategic game playing algorithm, where it gained expert strength without domain knowledge such as expert game examples? _______________________________________________ Computer-go mailing list Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
